第8章整数规划ppt课件.ppt

《第8章整数规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《第8章整数规划ppt课件.ppt（25页珍藏版）》请在三一文库上搜索。

1、第八章 整数规划,1 整数规划的图解法 2 整数规划的计算机求解 3 整数规划的应用 4 整数规划的分枝定界法,1,第八章 整数规划,求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。 在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；如果有一部分变量为负整数，则称之为混合整数规划问题。在整数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量。在纯整数规划和混合整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划。,2,1 整数规划的图解法,例1. 某公司拟用集装箱托运甲、乙两种货物，

2、这两种货物每件的体积、 重量、可获利润以及托运所受限制如表所示。 甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。 解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型 目标函数： Max z = 2x1 +3 x2 约束条件： s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 4 x1，x2 0 ,为整数。 如果去掉最后一个约束，就是一个线性规划问题。利用图解法，,3,1 整数规划的图解法,得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。 由图表可看出，整数规划的最优解为x1=4, x2=2,目

3、标函数值为14。 性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目 标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目 标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相 应的线性规划的最小目标函数值。,4,1 整数规划的图解法,x1,0,例2： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x1,x2,x3 0 x1,x3为整数,例3： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3

4、x2 + 2x3 3 x3 1 x1,x2,x3 0 x1为整数,x3为0-1变量,5,用管理运筹学软件求解得： x1 = 5 x2 = 2 x3 = 2,用管理运筹学软件求解得： x1 = 4 x2 = 1.25 x3 = 1 z = 16.25,2 整数规划的计算机求解,3 整数规划的应用,一、投资场所的选择 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由

5、A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?,6,3 整数规划的应用,解：设：0-1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。 这样我们可建立如下的数学模型： Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x

6、7+140x8+160x9+180x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xi 0,且xi 为0-1变量,i = 1,2,3,10 把上述模型输入管理运筹学软件,即得到此问题的最优解如下: 最优目标函数值为245. 最优解为: x1=1,x2=1,x3=0,x4=0,x5=1,x6=1,x7=0,x8=0,x9=1,x10=1,7,3 整数规划的应用,二、固定成本问题 例5高压容器公司制造小、中、大三种尺寸的金属容器， 所用资源为金属板、劳动力和机器设备，制造一个容器所需 的各种资源的数量如表所示。不考虑固定费用，每

7、种容器 售出一只所得的利润分别为 4万元、5万元、6万元，可使用的 金属板有500吨，劳动力有300人/月，机器有100台/月，此外 不管每种容器制造的数量是多少，都要支付一笔固定的费用： 小号是l00万元，中号为 150 万元，大号为200万元。现在要制 定一个生产计划，使获得的利润为最大。,8,3 整数规划的应用,解：这是一个整数规划的问题。 设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。各 种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这 种性质，设 yi = 1(当生产第 i种容器, 即 xi 0 时) 或0（当不生产第 i种容 器即 xi = 0

8、 时）。 引入约束 xi M yi ，i =1，2，3，M充分大，以保证当 yi = 0 时，xi = 0 。 这样我们可建立如下的数学模型： Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大 xi 0 yi 为0-1变量，i = 1,2,3,9,3 整数规划的应用,三、指派问题 有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情

9、况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题。 例6有四个工人，要分别指派他们完成四项不同的工作，每 人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能总的消耗时间为最少。,10,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

10、 +19x34+19x41 +21x42+23x43+17x44 s.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工作只

11、能一人干) xij 为0-1变量，i,j = 1,2,3,4 * * * 求解可用管理运筹学软件中整数规划方法。,11,3 整数规划的应用,四、分布系统设计 例7某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知在A2 ， A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外， A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销 量以及产地到销地的单位运价(每千箱运费)如下表所示。 a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用

12、之和最小? b) 如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?,12,3 整数规划的应用,解： a) 设 xij为从Ai 运往Bj 的运输量(单位：千箱)，yk = 1(当Ai 被选中时)或0（当Ai 没被选中时),k =2,3,4,5这可以表示为一个整数规划问题： Min z = 175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+ 3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53 其中前4项为固定投资额，后面的项为运输费用。 s.t. x11+ x12+ x13 30

13、( 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,

14、3， yk 为0-1变量，k =2,3,4,5。 * * * 求解可用管理运筹学软件中整数规划方法。,13,3 整数规划的应用,五、投资问题 例8某公司在今后五年内考虑给以下的项目投资。已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利 115%， 但要求第一年投资最低金额为4万元，第二、三、四年不限； 项目B：第三年初需要投资，到第五年末能回收本利1投资金额为3万元，最高金额为5万元； 项目 C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元，或为6万元或为8万元。 项目 D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金

15、额不限。 该部门现有资金10万元，问它应如何确定给这些项目的每年投资额， 使到第五年末拥有的资金本利总额为最大?,14,3 整数规划的应用,解：1) 设xiA、xiB、xiC、xiD ( i 1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额； 设yiA， yiB，是01变量，并规定取 1 时分别表示第 i 年给A、B投资， 否则取 0（ i = 1, 2, 3, 4, 5）。 设y2C 是非负整数变量，并规定：第2年投资C项目8万元时，取值为4； 第 2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2； 第2年投资C项目2万元时，取值1；第2年不投资C项目时

16、，取值0； 这样我们建立如下的决策变量： 第1年 第2年 第3年 第4年 第5年 A x1A x2A x3A x4A B x3B C x2C=20000y2C D x1D x2D x3D x4D x5D,15,3 整数规划的应用,2）约束条件： 第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是 x1A+ x1D = 100000； 第二年：A的投资第二年末才可收回，故第二年年初的资金为1.06x1D，于是x2A+x2C+x2D = 1.06x1D； 第三年：年初的资金为 1.15x1A+1.06x2D，于是 x3A+x3B+x3D = 1.15x1A+

17、 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时，

18、50000 x3B 30000 。 关于项目C的投资额规定: x2C = 20000y2C ，y2C = 0，1，2，3，4。,16,3 整数规划的应用,3）目标函数及模型： Max z = 1.15x4A+ 1.40x2C+ 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 30

19、000y3B ， 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）,17,4 整数规划的分枝定界法,18,分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。 分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子

20、区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。 下面以例9予以说明。,4 整数规划的分枝定界法,例9 用分枝定界法求解整数规划 Max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40x2140 x1 4 x1,x2 0且x1,x2为整数 解: (一)先求出以下线性规划的解： Max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40x2140 x1 4 x1,x2 0 得z1=14.66,x1=2.44,x2=3.26 (二)确定整数规划的最优目标函数值z*初始上界 和下界z。 分析后

21、，知道 =14.66，由观察法得下界z=13（当x1=2,x2=3时）。,19,4 整数规划的分枝定界法,(三)将一个线性规划问题分为两枝，并求解。 可由x12或x13中取值。将线性规划1分解为两支，如下： 线性规划2：Max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40x2140 x1 4 x1 2 x1,x2 0 解得z2=13.90,x1=2,x2=3.30 线性规划3：Max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40x2140 x1 4 x1 3 x1,x2 0 解得z3=14.58,x1=3,x2=2.86,20,4 整数规

22、划的分枝定界法,(四)修改整数规划的最优目标函数的上下界。 经分析，将上界 =14.66修改为 =14.58，z=13。 (五)在线性规划2和线性规划3中选择一个上界最大的线性规划，即线性规 划3，进行分枝。 线性规划3分解为线性规划4和线性规划5，如下： 线性规划4： Max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40x2140 x1 4 x1 3 x2 2 x1,x2 0 解得z4=14,x1=4,x2=2 线性规划5： Max 2x1+3x2 s.t. 195x1+273x21365 4x1+ 40x2140 x1 4 x1 3 x2 3 x1,x2 0 无

23、可行解,21,4 整数规划的分枝定界法,(六)进一步修改整数规划最优目标函数值z*的上下界。 从线性规划2，4，5中修改z*的上下界。分析后，可得=14， z=14。都 取线性规划2，4，5中的整数可行解的目标函数值的最大值。 性质2： 当整数规划的最优目标函数值z*的上界 等于其下界z 时，该整数规划的最优解已经被求出。这个整数规划的最优解 即为其目标函数值取此下界的对应线性规划的整数可行解。,22,4 整数规划的分枝定界法,用图8-2表示例9的求解过程与求解结果,23,线性规划1 Z1=14.66 X1=2.44 X2=3.26,z=13, =14.66,线性规划2 Z2=13.90 X1

24、=2 X2=3.30,线性规划3 Z3=14.58 X1=3 X2=2.86,线性规划4 Z4=14.00 X1=4 X2=2,线性规划5 无可行解,X12,X13,X22,X23,z=13, =14.58,z=14, =14,图8-2,4 整数规划的分枝定界法,24,从以上解题过程可得用分枝定界法求解目标函数值最大的整数规划的步骤，我们将求解的整数规划问题称为A，将与其相对应的线性规划问题称为B： 第一步：求解问题B，可得以下情况之一： 1.B没有可行解，则A也没有可行解，求解过程停止。 2.B有最优解，且符合问题A的整数条件，则B的最优解即为A的最优解，求解过程停止。 3.B有最优解，但不

25、符合A的整数条件，记其目标函数值为z1。 第二步：确定A的最优目标函数值z*的上下界，其上界即为z1, =z1,再用观察法找到A的一个整数可行解，求其目标函数值作为z*的下界，记为z 。 第三步：判断 是否等于z 。若相等，则整数规划最优解即为其目标函数值等于z的A的那个整数可行解；否则进行第四步。,4 整数规划的分枝定界法,25,第四步：在B的最优解中选一个最远离整数要求的变量，不妨设此变量为xj =bj ，以bj表示小于bj的最大整数，构造以下两个约束条件，并加入问题B，得到B的两个分枝B1和B2。 xj bj和xj bj+1 第五步：求解B1和B2 。修改A问题的最优目标函数值z*的上下界， 和z 。 第六步：比较和剪枝。各分枝的最优目标函数值中若有小于z者，则剪掉这枝（用打表示），即以后不再考虑了。若大于 ，则不符合整数条件，则重复第三步至第六步，直至 =z，求出最优解为止。 对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。,