运筹学第8章整数规划

1、第第8章章 整数规划整数规划 （Integer Programming）1整数规划的图解法整数规划的图解法2整数规划的计算机求解整数规划的计算机求解3整数规划的应用整数规划的应用4整数规划的分枝定界法整数规划的分枝定界法& by H. Q. Feng, CUFE2第八章 整数规划q求整数解的线性规划问题，不是用四舍五入法或去尾法对线求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。方法加以解决。q舍入化整求得到解可能是非可行解，或虽是可行解，但不是舍入化整求得到解可能

2、是非可行解，或虽是可行解，但不是最优解最优解q在整数规划中，如果所有的变量都为非负整数，则称为纯整在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；如果有一部分变量为负整数，则称之为混合整数规划问题；如果有一部分变量为负整数，则称之为混合整数规划问题。在整数规划中，如果变量的取值只限于数规划问题。在整数规划中，如果变量的取值只限于0和和1，这样的变量我们称之为这样的变量我们称之为0-1变量。在纯整数规划和混合整数变量。在纯整数规划和混合整数规划问题中，如果所有的变量都为规划问题中，如果所有的变量都为0-1变量，则称之为变量，则称之为0-1规规划。划。& by H. Q.

3、Feng, CUFE31整数规划的图解法例1:某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如下表。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。货物货物每件体积每件体积/（立方（立方英尺）英尺）每件重量每件重量/百千克百千克每件利润每件利润/百元百元甲甲乙乙19527344023托运限制托运限制1365140& by H. Q. Feng, CUFE41整数规划的图解法解：设解：设x1、x2分别为甲、乙两种货物托运的件数，分别为甲、乙两种货物托运的件数，建立模型建立模型目标函数：目标函数：Maxz=2x1+3x2s.t.19

4、5x1+273x213654x1+40 x2140 x14x1，x20的整数。的整数。若去掉变量的整数约束，就是一个线性规划问题。若去掉变量的整数约束，就是一个线性规划问题。& by H. Q. Feng, CUFE5性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。12341232x1+3x2 =14.66x1 x2 2x1+3x2 =142x1+3x2 =61整数规划的图解法得到线性规划的最优解为得到线性规划的最优解为

5、x1=2.44,x2=3.26,目标函目标函数值为数值为14.66。由图表可看出，整数规划的由图表可看出，整数规划的最优解为最优解为x1=4,x2=2,目目标函数值为标函数值为14。& by H. Q. Feng, CUFE6例2： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 - 3x3 2 x1 - 3x2 + 2x3 3 x1,x2,x3 0 的整数例例3 3： Max z = 3x1 + x2 + 3x3 Max z = 3x1 + x2 + 3x3 s.t. s.t. -x1 + 2x2 + x3 4 -x1 + 2x2 +

6、 x3 4 4x2 -3x3 2 4x2 -3x3 2 x1 - 3x2 + 2x3 3 x1 - 3x2 + 2x3 3 x3 1 x3 1 x1,x2,x3 0 x1,x2,x3 0，x1x1，x3 x3 为整为整数，数，x3 x3 为为0-10-1变量变量用管理运筹学软件求解得： x1 = 5 x2 = 2 x3 = 2 Zmax=23用管理运筹学软件求解得： x1 = 4 x2 = 1.25 x3 = 1 z = 16.252整数规划的计算机求解& by H. Q. Feng, CUFE73整数规划的应用一、投资场所的选择（相互排斥的计划，一、投资场所的选择（相互排斥的计划，0

7、-1规划）规划）例例4、京成畜产品公司计划在市区的东、西、南、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有北四区建立销售门市部，拟议中有10个位置个位置Aj(j1，2，3，10)可供选择，考虑到各地区居民的消费可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：水平及居民居住密集度，规定：在东区由在东区由A1，A2，A3三个点至多选择两三个点至多选择两个；个；在西区由在西区由A4，A5两个点中至少选一个；两个点中至少选一个；在南区由在南区由A6，A7两个点中至少选一个；两个点中至少选一个；在北区由在北区由A8，A9，A10三个点中至少选两三个点中至少选两个。个。

8、Aj各点的设备投资及每年可获利润由于地点不各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示同都是不一样的，预测情况见表所示(单位：万元单位：万元)。但投资总额不能超过但投资总额不能超过720万元，问应选择哪几个销售万元，问应选择哪几个销售点，可使年利润为最大点，可使年利润为最大?& by H. Q. Feng, CUFE83整数规划的应用解：设：0-1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。 这样我们可建立如下的数学模型：Max z =36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61

9、x10s.t. 100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 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& by H. Q. Feng, CUFE93整数规划的应用二、固定成本问题二、固定成本问题例例5高压容器公司制造小、中、大三种尺寸的金属容器，所用高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的资源为金属板、劳动

10、力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为为4万元、万元、5万元、万元、6万元，可使用的金属板有万元，可使用的金属板有500吨，劳动力有吨，劳动力有300人人/月，机器有月，机器有100台台/月，此外不管每种容器制造的数量是多少，都要支月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是付一笔固定的费用：小号是l00万元，中号为万元，中号为150万元，大号为万元，大号为200万万元。现在要制定一个生产计划，使获得的利润为最大。元。现在要制定一个生产计划，使获

11、得的利润为最大。& by H. Q. Feng, CUFE103整数规划的应用解：这是一个整数规划的问题。解：这是一个整数规划的问题。设设x1，x2，x3分别为小号容器、中号容器和大号容器的生分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设为了说明固定费用的这种性质，设yi=1(当生产第当生产第i种容器种容器,即即xi0时时)或或0（当不生产第（当不生产第i种容器即种容器即xi=0时）。时）。引入约束引入约束xiMyi，i=1，2，3，M充分大，以保证当充分大

12、，以保证当yi=0时，时，xi=0。这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x35002x1+3x2+4x3300 x1+2x2+3x3100 xiMyi，i=1，2，3，M充分大充分大xj0yj为为0-1变量，变量，i=1,2,3& by H. Q. Feng, CUFE113整数规划的应用三、指派问题（Assignment Problem）有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完

13、成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题。指派问题也是图论中研究重要内容之一，有相应的求解方法，如匈牙利算法。从形式上看，指派问题也可看作运输问题的特例。& by H. Q. Feng, CUFE123整数规划的应用指派问题的数学表的设决策变量为xij，当第i个人承担第j项任务时xij=1,否则，xij=0njnxnixtsxCMaxijniijnjijijninjij,.,2 , 1, i10 x)( ,.,2 , 1j1)( ,.,2 , 1, 1. .;1111，或每项任务只有一人承担，每个人承担一项任务& by

14、H. Q. Feng, CUFE133整数规划的应用例例6 6有四个工人，要分别指派他们完成四项不同的有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。应如何指派工作，才能使总的消耗时间为最少。& by H. Q. Feng, CUFE143整数规划的应用解：引入01变量 xij，并令 xij = 1(当指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时)这可以表示为一个0-1整数规划问题：Min z=15x11+18x12+21x13+24

15、x14+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=

16、 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干) xij 为0-1变量，i,j = 1,2,3,4& by H. Q. Feng, CUFE15指派问题指派问题练习练习1从从5人中选出人中选出4人参加人参加4x100米混合接力赛，每人的百米平均成米混合接力赛，每人的百米平均成绩如下：绩如下：制定参赛方案。& by H. Q. Feng, CUFE16指派问题指派问题练习练习1令令i=1,2,3,4,5分别表示甲、乙，丙，丁，戊队员；分别表示甲、乙，丙，丁，戊队员；j=1,2,3,4分别表示蝶泳等四种泳姿分别表示蝶泳等四种泳姿引入0

17、-1变量xij。若队员i参加泳姿j的比赛，则xij=1,否则为0；Cijxij表示队员i参加j项的成绩，1 , 051414151)( 4 , 3 , 2 , 1j, 1( 5 , 4 , 3 , 2 , 1, 1. .minijiijjijjiijijxxixt sxcf一人参加每项必须有一人且只有每人之多参加一项）甲甲:自由泳；自由泳；乙：蝶泳；乙：蝶泳；丙：仰泳；丙：仰泳；丁：蛙泳；丁：蛙泳；戊落选戊落选成绩成绩4分分13.2秒秒& by H. Q. Feng, CUFE173整数规划的应用四、分布系统设计例7某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩

18、大生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知在 A2 ， A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外， A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。 a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小? b) 如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂? 销地产地B1B2B3产量(千吨)A184330A252310A343420A497530A5104240销量(千吨)302020& by H

19、. Q. Feng, CUFE183整数规划的应用解：（1) 设 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运运输输费费用用固定投资额固定投资额& by H. Q. Feng, CUFE193整数规划的应用s.t. x11+ x12+ x13

20、 30 ( A1 s.t. x11+ x12+ x13 30 ( A1 厂的产量限制厂的产量限制) ) x21+ x22+ x23 10y2 ( A2 x21+ x22+ x23 10y2 ( A2 厂的产量限制厂的产量限制) ) x31+ x32+ x33 20y3 ( A3 x31+ x32+ x33 20y3 ( A3 厂的产量限制厂的产量限制) ) x41+ x42+ x43 30y4 ( A4 x41+ x42+ x43 30y4 ( A4 厂的产量限制厂的产量限制) ) x51+ x52+ x53 40y5 ( A5 x51+ x52+ x53 40y5 ( A5 厂的产量限制厂的

21、产量限制) ) x11+ x21+ x31+ x41 + x51 = 30 ( B1 x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制销地的限制) ) x12+ x22+ x32+ x42 + x52 = 20 ( B2 x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制销地的限制) ) x13+ x23+ x33+ x43 + x53 = 20 ( B3 x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制销地的限制) ) xij 0 xij 0，i = 1,2,3,4,5i = 1,2,3,4,5；

22、j = 1,2,3 j = 1,2,3， yk yk 为为0-0-1 1变量，变量，k =2,3,4,5k =2,3,4,5。& by H. Q. Feng, CUFE203整数规划的应用（2）在上述模型中，增加）在上述模型中，增加y2+y3=1约束，构约束，构成新的规划模型。成新的规划模型。& by H. Q. Feng, CUFE213整数规划的应用五、投资问题例8某公司在今后五年内考虑给以下的项目投资。已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%， 但要求第一年投资最低金额为4万元，第二、三、四年不限； 项目B：第三年初需要投资，到第五年末

23、能回收本利128，但规定最低投资金额为3万元，最高金额为5万元； 项目 C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。 项目 D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。 该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?& by H. Q. Feng, CUFE223整数规划的应用解：解：1) 1) 设设xiAxiA、xiBxiB、xiCxiC、xiD ( i xiD ( i 1 1，2 2，3 3，4 4，5)5)分别表分别表示第示第 i i

24、 年年初给项目年年初给项目A A，B B，C C，D D的投资额；的投资额； 设设yiAyiA， yiB yiB，是，是0101变量，并规定取变量，并规定取 1 1 时分别表示第时分别表示第 i i 年给年给A A、B B投资，否则取投资，否则取 0 0（ i = 1, 2, 3, 4, 5 i = 1, 2, 3, 4, 5）。）。 设设yiC yiC 是非负整数变量，并规定：是非负整数变量，并规定：第第2 2年投资年投资C C项目项目8 8万元时，取值为万元时，取值为4 4；第第2 2年投资年投资C C项目项目6 6万元时，取值万元时，取值3 3；第第2 2年投资年投资C C项目项目4 4

25、万元时，取值万元时，取值2 2；第第2 2年投资年投资C C项目项目2 2万元时，取值万元时，取值1 1；第第2 2年不投资年不投资C C项目时，取值项目时，取值0 0；& by H. Q. Feng, CUFE233整数规划的应用这样我们建立如下的决策变量：这样我们建立如下的决策变量： 第第1 1年年 第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 A x1A x2A x3A x4A A x1A x2A x3A x4A B x3B B x3B C x2C=20000.y2C C x2C=20000.y2C D x1D x2D x3D x4D x5D D x1D x2D

26、 x3D x4D x5D & by H. Q. Feng, CUFE243整数规划的应用2 2）约束条件：）约束条件：第第1 1年：年初有年：年初有100000100000元，元，D D项目在年末可收回投资，故第一年项目在年末可收回投资，故第一年年初应把全部资金投出去，于是年初应把全部资金投出去，于是 x1A+ x1D = 100000 x1A+ x1D = 100000；第第2 2年：年：A A的投资第二年末才可收回，故第二年年初的资金为的投资第二年末才可收回，故第二年年初的资金为1.06x1D1.06x1D，于是，于是x2A+x2C+x2D = 1.06x1Dx2A+x2C+x2D

27、 = 1.06x1D；第第3 3年：年初的资金为年：年初的资金为 1.15x1A+1.06x2D 1.15x1A+1.06x2D，于是，于是 x3A+x3B+x3D = x3A+x3B+x3D = 1.15x1A+ 1.06x2D1.15x1A+ 1.06x2D第第4 4年：年初的资金为年：年初的资金为 1.15x2A+1.06x3D 1.15x2A+1.06x3D，于是，于是 x4A + x4D = x4A + x4D = 1.15x2A+ 1.06x3D1.15x2A+ 1.06x3D& by H. Q. Feng, CUFE253整数规划的应用第第5 5年：年初的资金为年：年初的

28、资金为 1.15x3A+1.06x4D 1.15x3A+1.06x4D，于是，于是 x5D = 1.15x3A+ 1.06x4D x5D = 1.15x3A+ 1.06x4D。 关于项目关于项目A A的投资额规定的投资额规定: : x1A 40000y1A x1A 40000y1A ，x1A 200000y1A x1A 200000y1A ，200000200000是足够大的数；保证当是足够大的数；保证当 y1A=0 y1A=0时，时，x1A=0 x1A=0 ；当；当y1A= y1A= 1 1时，时，x1A40000 x1A40000 。 关于项目关于项目B B的投资额规定的投资额规定: :

29、x3B30000y3B x3B30000y3B ，x3B 50000y3B x3B 50000y3B ； 保证当保证当y3B=0y3B=0时，时，x3B=0 x3B=0；当；当y3B=1y3B=1时，时，50000 x3B30000 50000 x3B30000 。 关于项目关于项目C C的投资额规定的投资额规定: x2C=20000y2C: x2C=20000y2C，y2C=0y2C=0，1 1，2 2，3 3，4 4。& by H. Q. Feng, CUFE263整数规划的应用3）目标函数及模型： Max z = 1.15x4A+ 1.40 x2C+ 1.28x3B + 1.06

30、x5D 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） &a

31、mp; by H. Q. Feng, CUFE27练习练习2（指派问题、运输问题的变形）（指派问题、运输问题的变形）q消防指挥中心同时接到三处火警报告，根据当前警情判断，消防指挥中心同时接到三处火警报告，根据当前警情判断，需要分别调需要分别调2辆、辆、2辆和辆和3辆消防车前往处警。辆消防车前往处警。q指挥中心现有指挥中心现有7辆消防车，分属于三个消防站（各消防站的辆消防车，分属于三个消防站（各消防站的车辆分别为车辆分别为3,2,2辆）。从消防站到火警点的时间为（分钟）：辆）。从消防站到火警点的时间为（分钟）：q 火灾造成的损失依赖于消防车大到的时间。设火灾造成的损失依赖于消防车大到的时间。设t

32、ij表示第表示第j辆消防车到辆消防车到达火警点达火警点i的时间。三处的损失分别为：的时间。三处的损失分别为：q 6t11+4t12;7t21+3t22和和9t31+8t32+5t33q 指挥中心如何调度？指挥中心如何调度？& by H. Q. Feng, CUFE284整数规划的分枝定界法 对于整数规划，若可行域有界，首先想到的是穷对于整数规划，若可行域有界，首先想到的是穷举法：枚举所有可行的整数组合。举法：枚举所有可行的整数组合。 对于类似有对于类似有“n“n项任务由项任务由n n个人去完成的个人去完成的”指派问指派问题，指派方案有题，指派方案有n!n!。 当当n=10n=10，指派

33、方案超过，指派方案超过300300万个。万个。 n=20, n=20, 组合方案数达组合方案数达2X10182X1018枚举法不可行！分枝定界法是求解整数规划的一种常用的有效分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。商用软件就是基于分枝定界法而编制成的。& by H. Q. Feng, CUFE294整数规划的分枝定界法 分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数

34、条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。 下面以例9予以说明。& by H. Q. Feng, CUFE304整数规划的分枝定界法例例9用分枝定界法求解整数规划用分枝定界法求解整数规划Max2x1+3x2s.t.195x1+273x213654x1+40 x2140 x14x1,x20且且x1,x2为整数为整数解解:(一一)先求出以下线性规划的解：先求出以下线性规划的解：Max2x1+3x2s.t.195x1+273x213654x1+4

35、0 x2140 x14x1,x20得得z1=14.66,x1=2.44,x2=3.26(二二)确定整数规划的最优目标函数值确定整数规划的最优目标函数值z*初始上界初始上界和下界和下界z。分析后，知道分析后，知道=14.66，由观察法得下界，由观察法得下界z=13（当（当x1=2,x2=3时）。时）。zz& by H. Q. Feng, CUFE314整数规划的分枝定界法( (三三) )将一个线性规划问题分为两枝，并求解。将一个线性规划问题分为两枝，并求解。 可由可由x12x12或或x13x13中取值。将线性规划中取值。将线性规划1 1分解为两分解为两支，如下：支，如下：线性规划线性规划

36、2 2： Max 2x1+3x2 Max 2x1+3x2 s.t. 195x1+273x21365 s.t. 195x1+273x21365 4x1+ 40 x2140 4x1+ 40 x2140 x1 4 x1 4 x1 2 x1 2 x1,x2 0 x1,x2 0解得解得 z2=13.90,x1=2,x2=3.30z2=13.90,x1=2,x2=3.30线性规划线性规划3 3： Max 2x1+3x2 Max 2x1+3x2 s.t. 195x1+273x21365 s.t. 195x1+273x21365 4x1+ 40 x2140 4x1+ 40 x2140 x1 4 x1 4 x1

37、 3 x1 3 x1,x2 0 x1,x2 0 解得解得z3=14.58,x1=3,x2=2.86z3=14.58,x1=3,x2=2.86& by H. Q. Feng, CUFE32( (四四) )修改整数规划的最优目标函数的上下界。修改整数规划的最优目标函数的上下界。 经分析，将上界经分析，将上界 =14.66 =14.66修改为修改为 =14.58 =14.58，z=13z=13。( (五五) )在线性规划在线性规划2 2和线性规划和线性规划3 3中选择一个上界最大的线性规划，即线性规中选择一个上界最大的线性规划，即线性规划划3 3，进行分枝。，进行分枝。 线性规划线性规划3

38、3分解为线性规划分解为线性规划4 4和线性规划和线性规划5 5，如下：，如下：4整数规划的分枝定界法zz线性规划线性规划4 4： Max 2x1+3x2 Max 2x1+3x2 s.t. 195x1+273x21365 s.t. 195x1+273x21365 4x1+ 40 x2140 4x1+ 40 x2140 x1 4 x1 4 x1 3 x1 3 x2 2 x2 2 x1,x2 0 x1,x2 0 解得解得x1=4,x2=2,z4=14x1=4,x2=2,z4=14线性规划线性规划5 5： Max 2x1+3x2 Max 2x1+3x2 s.t. 195x1+273x21365 s.t

39、. 195x1+273x21365 4x1+ 40 x2140 4x1+ 40 x2140 x1 x1 3 3 x2 3 x2 3 x1,x2 0 x1,x2 0 无可行解无可行解& by H. Q. Feng, CUFE334整数规划的分枝定界法( (六六) )进一步修改整数规划最优目标函数值进一步修改整数规划最优目标函数值z z* *的上下界。的上下界。 从线性规划从线性规划2 2，4 4，5 5中修改上下界。分析后，可得中修改上下界。分析后，可得 =14 =14， z=14z=14。都取线性规划。都取线性规划2 2，4 4，5 5中的整数可行解的目标函数值的最大中的整数可行解的目标函数值的最大值。值。性质性质2 2： 当整数规划的最优目标函数值当整数规划的最优目标函数值z z* *的上界的上界 等于其下界等于其下界z z时，该整时，该整数规划的最优解已经被求出。这个整数的最优解即为其目标函数数规划的最优解已经被求出。这个整数的最优解即为其目标函数值取此下界的对应线性规划的整数可行解。值取此下界的对应线性规划的整数可行解。zz& by H. Q. Feng, CUFE344整数规划的分枝定界法用图用图8-28-2表示例表示例9 9的求解过程与求解结果的求解过程与求解结果z线性规划线