运筹学-08-整数规划.ppt
管管 理理 运运 筹筹 学学1第八章第八章 整数规划整数规划1整数规划的图解法2整数规划的计算机求解3整数规划的应用4整数规划的分枝定界法管管 理理 运运 筹筹 学学2第八章第八章 整数规划整数规划求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；如果有一部分变量为负整数，则称之为混合整数规划问题。在整数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量。在纯整数规划和混合整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划。管管 理理 运运 筹筹 学学31 1整数规划的图解法整数规划的图解法例例1.某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。解：解：设x1、x2分别为甲、乙两种货物托运的件数，建立模型目标函数：Maxz=2x1+3x2约束条件：s.t.195x1+273x213654x1+40 x2140 x14x1，x20为整数。如果去掉最后一个约束，就是一个线性规划问题。利用图解法，货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制1365140管管 理理 运运 筹筹 学学4得到线性规划的最优解为x1=2.44,x2=3.26,目标函数值为14.66。由图表可看出，整数规划的最优解为x1=4,x2=2,目标函数值为14。性质性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=61 1 整数规划的图解法整数规划的图解法1 1整数规划的图解法整数规划的图解法管管 理理 运运 筹筹 学学5例例2 2：Max z=3x1+x2+3x3 s.t.-x1+2x2+x3 4 4x2-3x3 2 x1-3x2+2x3 3 x1,x2,x3 0 为整数例3：Max z=3x1+x2+3x3 s.t.-x1+2x2+x3 4 4x2-3x3 2 x1-3x2+2x3 3 x3 1 x1,x2,x3 0 x1，x3 为整数 x3 为0-1变量用管理运筹学软件求解得：x1=5 x2=2 x3=2 用管理运筹学软件求解得：x1=4 x2=1.25 x3=1 z=16.252 2整数规划的计算机求解整数规划的计算机求解管管 理理 运运 筹筹 学学63 3整数规划的应用整数规划的应用一、投资场所的选择一、投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Aj(j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由A1，A2，A3三个点至多选择两个；在西区由A4，A5两个点中至少选一个；在南区由A6，A7两个点中至少选一个；在北区由A8，A9，A10三个点中至少选两个。Aj各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?管管 理理 运运 筹筹 学学73 3整数规划的应用整数规划的应用解：解：设：0-1变量xi=1(Ai点被选用）或0(Ai点没被选用）。这样我们可建立如下的数学模型：Max z=36Max z=36x x1 1+40+40 x x2 2+50+50 x x3 3+22+22x x4 4+20+20 x x5 5+30+30 x x6 6+25+25x x7 7+48+48x x8 8+58+58x x9 9+61+61x x1010s.t.100s.t.100 x x1 1+120+120 x x2 2+150+150 x x3 3+80+80 x x4 4+70+70 x x5 5+90+90 x x6 6+80+80 x x7 7+140+140 x x8 8+160+160 x x9 9+180+180 x x1010 720 720 x1+x2+x3 2 x4+x5 1 x6+x7 1 x8+x9+x10 2 xj 0 且xj 为0-1变量，i=1,2,3,10管管 理理 运运 筹筹 学学83 3整数规划的应用整数规划的应用二、固定成本问题 例例5高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。管管 理理 运运 筹筹 学学93 3整数规划的应用整数规划的应用解：这是一个整数规划的问题。设x1，x2，x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设yi=1(当生产第i种容器,即xi0时)或0（当不生产第i种容器即xi=0时）。引入约束xiMyi，i=1，2，3，M充分大，以保证当yi=0时，xi=0。这样我们可建立如下的数学模型：Max z=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3 500 2x1+3x2+4x3 300 x1+2x2+3x3 100 xiMyi，i=1，2，3，M充分大 xj 0 yj 为0-1变量，i=1,2,3管管 理理 运运 筹筹 学学103 3整数规划的应用整数规划的应用三、指派问题三、指派问题 有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题。例6有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。管管 理理 运运 筹筹 学学113 3整数规划的应用整数规划的应用解解：引入01变量 xij，并令 xij=1(当指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时)这可以表示为一个0-1整数规划问题：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1 (甲只能干一项工作)x21+x22+x23+x24=1 (乙只能干一项工作)x31+x32+x33+x34=1 (丙只能干一项工作)x41+x42+x43+x44=1 (丁只能干一项工作)x11+x21+x31+x41=1 (A工作只能一人干)x12+x22+x32+x42=1 (B工作只能一人干)x13+x23+x33+x43=1 (C工作只能一人干)x14+x24+x34+x44=1 (D工作只能一人干)xij 为0-1变量，i,j=1,2,3,4 *求解可用管理运筹学软件中整数规划方法。管管 理理 运运 筹筹 学学123 3整数规划的应用整数规划的应用四、分布系统设计四、分布系统设计例例7某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂。已知在A2，A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。a)问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?b)如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?管管 理理 运运 筹筹 学学133 3整数规划的应用整数规划的应用解：解：a)设xij为从Ai运往Bj的运输量(单位千箱)，yk=1(当Ak 被选中时)或0（当Ak 没被选中时),k=2,3,4,5这可以表示为一个整数规划问题：Min z=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10 x51+4x52+2x53其中前4项为固定投资额，后面的项为运输费用。s.t.x11+x12+x13 30 (A1 厂的产量限制)x21+x22+x23 10y2 (A2 厂的产量限制)x31+x32+x33 20y3 (A3 厂的产量限制)x41+x42+x43 30y4 (A4 厂的产量限制)x51+x52+x53 40y5 (A5 厂的产量限制)x11+x21+x31+x41+x51=30 (B1 销地的限制)x12+x22+x32+x42+x52=20 (B2 销地的限制)x13+x23+x33+x43+x53=20 (B3 销地的限制)xij 0，i=1,2,3,4,5；j=1,2,3，yk 为0-1变量，k=2,3,4,5。*求解可用管理运筹学软件中整数规划方法。管管 理理 运运 筹筹 学学143 3整数规划的应用整数规划的应用五、投资问题五、投资问题 例例8 8某公司在今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限；项目B：第三年初需要投资，到第五年末能回收本利128，但规定最低投资金额为3万元，最高金额为5万元；项目C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。项目D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?管管 理理 运运 筹筹 学学153 3整数规划的应用整数规划的应用解：解：1)设xiA、xiB、xiC、xiD(i1，2，3，4，5)分别表示第i年年初给项目A，B，C，D的投资额；设yiA，yiB，是01变量，并规定取1时分别表示第i年给A、B投资，否则取0（i=1,2,3,4,5）。设yiC 是非负整数变量，并规定：第2年投资C项目8万元时，取值为4；第2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2；第2年投资C项目2万元时，取值1；第2年不投资C项目时，取值0；这样我们建立如下的决策变量：第1年 第2年 第3年 第4年 第5年 A x1A x2A x3A x4A B x3B C x2C=20000y2C D x1D x2D x3D x4D x5D 管管 理理 运运 筹筹 学学163 3整数规划的应用整数规划的应用2 2）约束条件：）约束条件：第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是 x1A+x1D=100000；第二年：A的投资第二年末才可收回，故第二年年初的资金为1.06x1D，于是x2A+x2C+x2D=1.06x1D；第三年：年初的资金为 1.15x1A+1.06x2D，于是 x3A+x3B+x3D=1.15x1A+1.06x2D；第四年：年初的资金为 1.15x2A+1.06x3D，于是 x4A+x4D=1.15x2A+1.06x3D；第五年：年初的资金为 1.15x3A+1.06x4D，于是 x5D=1.15x3A+1.06x4D。关于项目A的投资额规定:x1A 40000y1A，x1A 200000y1A，200000是足够大的数；保证当 y1A=0时，x1A=0；当y1A=1时，x1A 40000。关于项目B的投资额规定:x3B 30000y3B，x3B 50000y3B；保证当 y3B=0时，x3B=0；当y3B=1时，50000 x3B 30000。关于项目C的投资额规定:x2C=20000y2C，y2C=0，1，2，3，4。管管 理理 运运 筹筹 学学173 3整数规划的应用整数规划的应用3 3）目标函数及模型：）目标函数及模型：Max z=1.15x4A+1.40 x2C+1.28x3B+1.06x5D s.t.x1A+x1D=100000；x2A+x2C+x2D=1.06x1D；x3A+x3B+x3D=1.15x1A+1.06x2D；x4A+x4D=1.15x2A+1.06x3D；x5D=1.15x3A+1.06x4D；x1A 40000y1A，x1A 200000y1A，x3B 30000y3B，x3B 50000y3B；x2C=20000y2C，yiA，yiB=0 或 1，i=1,2,3,4,5 y2C=0，1，2，3，4 xiA，xiB，xiC，xiD 0 (i=1、2、3、4、5）管管 理理 运运 筹筹 学学184 4整数规划的分枝定界法整数规划的分枝定界法 分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。下面以例9予以说明。管管 理理 运运 筹筹 学学194 4整数规划的分枝定界法整数规划的分枝定界法例9用分枝定界法求解整数规划Max 2x1+3x2s.t.195x1+273x21365 4x1+40 x2140 x1 4 x1,x2 0且x1,x2为整数解:(一)先求出以下线性规划的解：Max 2x1+3x2 s.t.195x1+273x21365 4x1+40 x2140 x1 4 x1,x2 0 得z1=14.66,x1=2.44,x2=3.26 (二)确定整数规划的最优目标函数值z*初始上界 和下界z。分析后，知道 =14.66，由观察法得下界z=13（当x1=2,x2=3时）。管管 理理 运运 筹筹 学学204 4整数规划的分枝定界法整数规划的分枝定界法(三)将一个线性规划问题分为两枝，并求解。可由x12或x13中取值。将线性规划1分解为两支，如下：线性规划2：Max 2x1+3x2 s.t.195x1+273x21365 4x1+40 x2140 x1 4 x2 2 x1,x2 0 解得z2=13.90,x1=2,x2=3.30 线性规划3：Max 2x1+3x2 s.t.195x1+273x21365 4x1+40 x2140 x1 4 x1 3 x1,x2 0 解得z3=14.58,x1=3,x2=2.86管管 理理 运运 筹筹 学学214 4整数规划的分枝定界法整数规划的分枝定界法(四)修改整数规划的最优目标函数的上下界。经分析，将上界 =14.66修改为 =14.58，z=13。(五)在线性规划2和线性规划3中选择一个上界最大的线性规划，即线性规划3，进行分枝。线性规划3分解为线性规划4和线性规划5，如下：线性规划4：Max 2x1+3x2 s.t.195x1+273x21365 4x1+40 x2140 x1 4 x1 3 x2 2 x1,x2 0 解得z4=14,x1=4,x2=2 线性规划5：Max 2x1+3x2 s.t.195x1+273x21365 4x1+40 x2140 x1 3 x2 3 x1,x2 0 无可行解管管 理理 运运 筹筹 学学224 4整数规划的分枝定界法整数规划的分枝定界法(六)进一步修改整数规划最优目标函数值z*的上下界。从线性规划2，4，5中修改上下界。分析后，可得 =14，z=14。都取线性规划2，4，5中的整数可行解的目标函数值的最大值。性质2：当整数规划的最优目标函数值z*的上界 等于其下界z时，该整数规划的最优解已经被求出。这个整数的最优解即为其目标函数值取此下界的对应线性规划的整数可行解。管管 理理 运运 筹筹 学学234 4整数规划的分枝定界法整数规划的分枝定界法用图8-2表示例9的求解过程与求解结果线性规划线性规划1Z1=14.66X1=2.44X2=3.26z z=13,=13,=14.66 线性规划线性规划2Z2=13.90X1=2X2=3.30线性规划线性规划3Z3=14.58X1=3X2=2.86线性规划线性规划4Z4=14.00X1=4X2=2线性规划线性规划5无可行解无可行解X12X13X22X23z z=13,=13,=14.58 z z=14,=14,=14图图8-28-2管管 理理 运运 筹筹 学学244 4整数规划的分枝定界法整数规划的分枝定界法 从以上解题过程可得用分枝定界法求解目标函数值最大的整数规划的步骤，我们将求解的整数规划问题称为A，将与其相对应的线性规划问题称为B：第一步：求解问题B，可得以下情况之一：1.B没有可行解，则A也没有可行解，求解过程停止。2.B有最优解，且符合问题A的整数条件，则B的最优解即为A的最优解，求解过程停止。3.B有最优解，但不符合A的整数条件，记其目标函数值为z1。第二步：确定A的最优目标函数值z*的上下界，其上界即为z1,=z1,再用观察法找到A的一个整数可行解，求其目标函数值作为z*的下界，记为z。第三步：判断 是否等于z。若相等，则整数规划最优解即为其目标函数值等于z的A的那个整数可行解；否则进行第四步。管管 理理 运运 筹筹 学学254 4整数规划的分枝定界法整数规划的分枝定界法 第四步：在B的最优解中选一个最远离整数要求的变量，不妨设此变量为xj，以bj表示小于bj的最大整数，构造以下两个约束条件，并加入问题B，得到B的两个分枝B1和B2。xjbj和xjbj+1第五步：求解B1和B2。修改A问题的最优目标函数值z*的上下界，和z。第六步：比较和剪枝。各分枝的最优目标函数值中若有小于z者，则剪掉这枝（用打表示），即以后不再考虑了。若大于 ，则不符合整数条件，则重复第三步至第六步，直至 =z，求出最优解为止。对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。
