第八章整数规划.ppt

《第八章整数规划.ppt》由会员分享，可在线阅读，更多相关《第八章整数规划.ppt（131页珍藏版）》请在三一办公上搜索。

1、第八章 整数规划,Integer Programming,第八章 整数规划,在前面讨论的线性规划问题中，最优解可能是整数，也可能不是整数，但对于某些实际问题，要求答案必须是整数。如，所求的解是安排上班的人数，按某个方案裁剪钢材的根数，生产机器的台数等。,第八章 整数规划,8.1 整数规划模型,8.1 整数规划模型,整数规划模型的一般形式,Max（或Min）Z=cjxjs.t.aijxj(或=,)bi i=1,2,m xj 0 j=1,2,n x1,x2,xn 中部分或全部取整数,8.1 整数规划模型,在线性规划模型中,如果所有的决策变量都要求为非负整数，则这样的线性规划问题称之为纯整数规划问题

2、。如果只有一部分决策变量要求为非负整数，则这样的线性规划问题称之为混合整数规划问题。如果决策变量的取值只限于 0 和 1，则这样的整数线性规划问题称之为 01型整数规划问题。,8.1 整数规划模型,例：一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为25公斤。,8.1 整数规划模型,解：令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i:Max Z=20 x1+15x2+18x3+14x4+8x5+4x6+10 x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x

3、7 25 xi=1 或 xi=0 i=1,2,.7,8.1 整数规划模型,背包问题(Knapsack Problem)一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,有限制:最多只能装b公斤的物品而每件物品只能整个携带每件物品规定了一个“价值”以表示其有用的程度如果共有n件物品,第 j 件物品aj公斤,其价值为cj.问题变成:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大?,8.1 整数规划模型,背包问题(Knapsack Problem),解：令xj=1表示携带物品j,xj=0表示不携带物品j，Max Z=cjxj s.t.ajxj b xj=0 或 1

4、,8.1 整数规划模型,解：令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i:Max Z=20 x1+15x2+18x3+14x4+8x5+4x6+10 x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x7 25 xi=1 或 xi=0 i=1,2,.7,8.1 整数规划模型,当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。例如，背包问题充其量有 2n种方式,8.1 整数规划模型,解：令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i:Max Z=20 x1+15x2+18x3+

5、14x4+8x5+4x6+10 x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x7 25 xi=1 或 xi=0 i=1,2,.7,8.1 整数规划模型,当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。实际上这种方法是不可行。设想计算机每秒能比较1000000个方式，那么要比较完20!（大于2*1018）种方式，大约需要800年。那么要比较完比较完260种方式，大约需要360世纪,8.1 整数规划模型,当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方

6、案。先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解。,8.1 整数规划模型,例.某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运所受限制如下表所示，甲种货物至多托运 4 件，问两种货物各托运多少件，可使获得利润最大。,解：设 x1、x2 分别为甲、乙两种货物托运的件数，显然 x1、x2 应该是非负整数，该问题的数学模型如下所示：max z=2x1+3x2 s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，x2 0 x1，x2 为整数。,解：设 x1、x2 分别为甲、乙两种货物托运的件数，显然 x1、x

7、2 应该是非负整数，该问题的数学模型如下所示：max z=2x1+3x2 s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，x2 0 x1，x2 为整数。如果将上述整数线性规划中的最后一个约束：x1、x2 为整数去掉，它就是一个线性规划的问题。用图解法来解这个整数规划，以及与它相应的线性规划问题，并把它们的最优解加以比较。,max z=2x1+3x2 s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，x2 0,max z=2x1+3x2 s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，

8、x2 0,1,2,3,4,1,2,3,x2,x1,平移目标函数的等值线，得线性规划的最优解为 x12.44，x23.26，目标函数的最优值为14.66。,2x1+3x214.66,max z=2x1+3x2 s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，x2 0 x1，x2 为整数,2x1+3x214,同样把目标函数的等值线尽量向右上方移以便取得最大值，同时又必须过整数规划的可行点，可得整数规划的最优解 x14，x22，这时其最优目标函数值为14。,8.1 整数规划模型,当我们对相应的线性规划的最优解进行四舍五入或去尾法时，得 x12，x23，这时目标函

9、数值为 13，并不是此整数规划的最优解。当我们对相应的线性规划的最优解进行进一法时，取 x13，x23；x12，x2 4；x13，x24 都不是此整数规划的可行解。,线性规划的最优解 x12.44，x23.26，最优值为 14.66整数规划的最优解 x14，x22，最优值为 14,8.1 整数规划模型,当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解。这个整数规划的最优解并不可以将它对应的线性规划的不为整数的最优解进行四舍五入法或去尾法或进一法而得到的。,8

10、.1 整数规划模型,当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案。先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解。结论：求解整数规划问题必须要有自己的解法。,8.1 整数规划模型,任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值，小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值，大于或等于相应的线性规划的最小目标函数值。,max z=2x1+3x2 s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1

11、，x2 0 x1，x2 为整数,2x1+3x214.66,2x1+3x214,A,B,第八章 整数规划,8.1 整数规划模型 8.2 整数规划的应用,8.2 整数规划的应用,一、投资场所的选择,例 京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有 10 个位置 Aj(j 1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区从 A1，A2，A3 三个点中至多选择两个；在西区从 A4，A5 两个点中至少选一个；在南区从 A6，A7 两个点中至少选一个；在北区从 A8，A9，A10 三个点中至少选两个。Aj 各点的设备投资及每年可获利润由于地点不同

12、都是不一样的。但投资总额不能超过 720 万元，问应选择哪几个销售点，可使年利润为最大?,8.2 整数规划的应用,AT&T公司（美国电信电报公司）,公司商业用户服务的电话销售中心的优化选址,用户规划及特征竞争对手地理位置成本的核算交通状况 经营场地面积,例 京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有 10 个位置 Aj(j 1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区从 A1，A2，A3 三个点中至多选择两个；在西区从 A4，A5 两个点中至少选一个；在南区从 A6，A7 两个点中至少选一个；在北区从 A8，A9，A10 三个点

13、中至少选两个。Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的。但投资总额不能超过 720 万元，问应选择哪几个销售点，可使年利润为最大?,解：设：01 变量 xi=1，当 Ai 点被选用时；xi=0，当 Ai 点没被选用时。,max z=36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10s.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 2x4+x5 1 x6+x7 1 x8+x9+x10 2xj 0，且 xj

14、 为 01 变量，j=1，2，10。,用“管理运筹学软件包”中的 01 整数规划程序求解得：max z=245；x1=x2=x5=x6=x9=x10=1，其余为 0。,8.2 整数规划的应用,一、投资场所的选择二、固定成本问题,例 高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4 万元、5 万元、6 万元，可使用的金属板有 500 吨，劳动力有 300 人月，机器有 100 台月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是 l00 万元，中号为

15、 150 万元，大号为 200 万元。现在要制定一个生产计划，使获得的利润为最大。,固定成本问题,“不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是 l00 万元，中号为 150 万元，大号为 200 万元。”,解：这是一个整数规划问题。设 x1，x2，x3 分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，即 yi=1，当生产第 i 种容器，即 xi 0 时；yi=0，当不生产第 i 种容器，即 xi=0 时。,可建立如下的数学模型：max z=4x1+5x2+6x3-100y1-150y2-200y3 s.t.2x1+4x2+8x3 5

16、00 2x1+3x2+4x3 300 x1+2x2+3x3 100 xi M yi，i=1，2，3，xj 0，且为整数，yj 为 01 变量，j=1，2，3。M 充分大，以保证当 yi=0 时，xi=0。,8.2 整数规划的应用,一、投资场所的选择二、固定成本问题三、指派问题,例.有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。,指派问题,解：引入 01 变量 xij，并令 xij=1，当指派第 i 人去完成第 j 项工作时；xij=0，当不指派第 i 人去完成第 j 项工作时。这样该问题即被表示成一个 01 整数

17、规划问题：min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+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工作只能一人干

18、)x14+x24+x34+x44=1(D工作只能一人干)xij 为 01 变量，i，j=1，2，3，4。求解得:min z=70；x21=1，x12=1，x33=1，x44=1。,例.有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。,指派问题,8.2 整数规划的应用,一、投资场所的选择二、固定成本问题三、指派问题四、分布系统设计,例某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2，A3，A4，A5 地中再选择几个地方建厂。已知在 A2，A3，A4，A5 地建厂的固定成本分别

19、为 175 千元、300 千元、375 千元、500 千元，另外，A1 产量及 A2，A3，A4，A5 建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。a)问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?b)如果由于政策要求必须在 A2，A3 地建一个厂，应在哪几个地方建厂?,解：a)设 xij 为从 Ai 运往 Bj 的运输量(单位千箱)，yk=1，当 Ak 被选中时；yk=0，当 Ak 没被选中时，k=2，3，4，5。这样我们的问题可以被表示成一个(混合)整数规划问题:,min z=175y2+300y3+375y4+50

20、0y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10 x51+4x52+2x53 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+x5

21、3=20(B3 销地的限制)xij 0，且为整数，i=1，2，3，4，5；j=1，2，3，yk 为 01 变量，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 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

22、(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 为 01 变量，k=2，3，4，5。,分布系统设计,Reynolds金属制品公司 200多个工厂、仓库和供应商的货物装载调度系统的自动化,01 整数规划,Delta航空公司 超过2500个国内航线的飞机类型配置 以达到利润最大化,8.2 整数规划的应用,一、投资场所的选择二、固定成本问题三、指派问题四、分布系统设计五

23、、投资问题-P183 案例9,案例9：华南公司投资方案,设 Xij 为第 i 年在第 j 方案上的投资额，例如X21表示在第二年投资在项目A1上的金额Yij=1，当第 i 年给第 j 项目投资时，Yij=0，当第 i 年不给第 j 项目投资时。因此第一年投资在项目A1上的金额X11可表示为:X11220Y11,A1：建立彩色印刷厂，第一、二年年初分别投入220万元和220万元，第二年年底可获利60万元，第三年起每年获利130万元,X11-220Y11=0（A1 第一年初投入220万元）X21-220Y21=0（A1 第二年初投入220万元）Y11-Y21=0（A1 第一、二年都要投入）,A2：

24、投资离子镀膜基地，第一年投资70万元，第二年起每年可获利50万元,X11-220Y11=0（A1 第一年初投入220万元）X21-220Y21=0（A1 第二年初投入220万元）Y11-Y21=0（A1 第一、二年都要投入）X12-70Y12=0（A2 第一年初投入70万元）,A3：投资参股F企业，第二年投入180万元设备，第三年起每年可获利50万元,X11-220Y11=0（A1 第一年初投入220万元）X21-220Y21=0（A1 第二年初投入220万元）Y11-Y21=0（A1 第一、二年都要投入）X12-70Y12=0（A2 第一年初投入70万元）X23-180Y23=0（A3 第二

25、年初投入180万元）,A4：投资D企业，每年年底可获投资额的25利润，但是第一年最高投资额为 80 万元，以后每年递增不超过 15 万元。,X11-220Y11=0（A1 第一年初投入220万元）X21-220Y21=0（A1 第二年初投入220万元）Y11-Y21=0（A1 第一、二年都要投入）X12-70Y12=0（A2 第一年初投入70万元）X23-180Y23=0（A3 第二年初投入180万元）X1480（A4 第一年最高为 80 万元）X24-X1415（A4每年递增不超过 15 万元）X34-X2415（A4每年递增不超过 15 万元）X44-X3415（A4每年递增不超过 15

26、万元）X54-X4415（A4每年递增不超过 15 万元）,A5：建立细骨粉生产线，第三年投入320，第四年起每年可获利90万元。,X11-220Y11=0 X21-220Y21=0Y11-Y21=0X12-70Y12=0X23-180Y23=0X1480X24-X1415X34-X2415X44-X3415X54-X4415,X35-320Y35=0(A5 第一年初投入220万元),A6：投资所属中北机电设备公司，年底回收本利120。但每年投资额不低于60万元。,X11-220Y11=0 X21-220Y21=0Y11-Y21=0X12-70Y12=0X23-180Y23=0X1480X24

27、-X1415X34-X2415X44-X3415X54-X4415,X35-320Y35=0(A5 第一年初投入220万元)X1660（A6 每年投资不低于60万元）X2660（A6 每年投资不低于60万元）X3660（A6 每年投资不低于60万元）X4660（A6 每年投资不低于60万元）X5660（A6 每年投资不低于60万元）,A7：投资所属澳得技术公司，年底回收本利115。,X11-220Y11=0 X21-220Y21=0Y11-Y21=0X12-70Y12=0X23-180Y23=0X1480X24-X1415X34-X2415X44-X3415X54-X4415,X35-320Y

28、35=0(A5 第一年初投入220万元)X1660（A6 每年投资不低于60万元）X2660（A6 每年投资不低于60万元）X3660（A6 每年投资不低于60万元）X4660（A6 每年投资不低于60万元）X5660（A6 每年投资不低于60万元）,一、项目资金约束,X11-220Y11=0 X21-220Y21=0Y11-Y21=0X12-70Y12=0X23-180Y23=0X1480X24-X1415X34-X2415X44-X3415X54-X4415,X35-320Y35=0X1660X2660X3660X4660X5660,一、项目资金约束,二、年度资金约束,投资总额为800万元

29、，其中第一年350万，第二年300万，第三年150万,第一年：X11+X12+X14+X16+X17=350第二年：X21+X23+X24+X26+X27=0.25X14+1.2X16+1.15X17+300第三年:X34+X35+X36+X37=60Y11+18Y12+0.25X24+1.2X26+1.15X27+150第四年:X44+X46+X47=130Y11+18 Y12+50Y23+0.25X34+1.2X36+1.15X37第五年:X54+X56+X57=130Y11+18Y12+50Y23+0.25X44+90Y35+1.2X46+1.15X47,一、项目资金约束,二、年度资金约

30、束,三、目标函数,A1：建立彩色印刷厂，第一、二年年初分别投入220万元和220万元，第二年年底可获利60万元，第三年起每年获利130万元;A2：投资离子镀膜基地，第一年投资70万元，第二年起每年可获利18万元;A3：投资参股F企业，第二年投入180万元设备，第三年起每年可获利50万元A4：投资D企业，每年年底可获投资额的25利润，但是第一年最高投资额为 80 万元，以后每年递增不超过 15 万元。A5：建立细骨粉生产线，第三年投入320，第四年起每年可获利90万元。A6：投资所属中北机电设备公司，年底回收本利120。但每年投资额不低于60万元。A7：投资所属澳得技术公司，年底回收本利115。

31、,MAX 130Y11+18Y12+50Y23+0.25X54+90Y35+1.2X56+1.15X57,案例9：华南公司投资方案,解：设 Xij 为第 i 年在第 j 方案上的投资额，Yij=1，当第 i 年给第 j 项目投资时，Yij=0，当第 i 年不给第 j 项目投资时。MAX 130Y11+18Y12+50Y23+0.25X54+90Y35+1.2X56+1.15X57,X11-220Y11=0 X21-220Y21=0Y11-Y21=0X12-70Y12=0X23-180Y23=0,X1480X24-X1415X34-X2415X44-X3415X54-X4415,X35-320Y

32、35=0X1660X2660X3660X4660X5660,X11+X12+X14+X16+X17=350X21+X23+X24+X26+X27=0.25X14+1.2X16+1.15X17+300X34+X35+X36+X37=60Y11+18Y12+0.25X24+1.2X26+1.15X27+150X44+X46+X47=130Y11+18Y12+50Y23+0.25X34+1.2X36+1.15X37X54+X56+X57=130Y11+18Y12+50Y23+0.25X44+90Y35+1.2X46+1.15X47,Xi,j0,i=1,2,3,4,5,j=1,2,3,4,5,6,7Y

33、11,Y12,Y23,Y35 为0-1 变量,约束条件:,第八章 整数规划,8.1 整数规划模型 8.2 整数规划的应用8.3 整数规划的分枝定界法,8.3 整数规划的分枝定界法,分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。,8.3 整数规划的分枝定界法,混合整数规划问题一般存在穷多个可行解；纯整数规划问题，随着问题规模得扩大，其可行解得数目也急剧增加。因此通过枚举全部可行解，并从中筛选出最优解的算法无实际应用价值。分枝定界法是一种隐枚举法或部分枚举法，是枚举法基础上的改进。,

34、8.3 整数规划的分枝定界法,原问题的松驰问题：任何整数规划，凡放弃某些约束条件（如整数要求）后，所得到的问题都称为松驰问题。,解：设 x1、x2 分别为甲、乙两种货物托运的件数，显然 x1、x2 应该是非负整数，该问题的数学模型如下所示：max z=2x1+3x2 s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，x2 0 x1，x2 为整数。,整数规划问题,解：设 x1、x2 分别为甲、乙两种货物托运的件数，显然 x1、x2 应该是非负整数，该问题的数学模型如下所示：max z=2x1+3x2 s.t.195x1+273x2 1365 4x1+40 x2

35、 140 x1 4 x1，x2 0 x1，x2 为整数。,原问题,松驰问题,解：设 x1、x2 分别为甲、乙两种货物托运的件数，显然 x1、x2 应该是非负整数，该问题的数学模型如下所示：max z=2x1+3x2 s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，x2 0 x1，x2 为整数。,原问题,松驰问题,8.3 整数规划的分枝定界法,原问题的松驰问题：任何整数规划，凡放弃某些约束条件（如整数要求）后，所得到的问题都称为松驰问题。,8.3 整数规划的分枝定界法,分枝定界法：求整数规划相应的线性规划问题。如果其最优解不符合整数条件，则求出整数规划最优解

36、的上下界增加约束条件的将相应的线性规划问题的可行域分成子区域(称为分枝)，再求解这些子区域上的线性规划问题，不断缩小整数规划最优解上下界的距离，最后求得整数规划的最优解分枝定界法的关键是分枝和定界,分枝：若整数规划的松弛问题的最优解不符合整数要求。假设xi=bi不符合整数要求，bi 是不超过bi最大整数构造两个附加约束：xi bi 和 xi bi+1,分别将其并入上述松弛问题中，从而形成两个分枝。加入这两个约束，可得到两个子问题，即两个后续问题。,例：用分枝定界法求解下面整数规划 max z=2x1+3x2 s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，

37、x2 0 x1，x2 为整数。,例：用分枝定界法求解下面整数规划 max z=2x1+3x2 s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，x2 0,解：先求出相应的线性规划问题(LP1)，即松弛问题的解。求得这个线性规划的最优解为 x12.44，x23.26，目标函数的最优值为 14.66。显然，这个解不是原整数规划的可行解。,分枝：若整数规划的松弛问题的最优解不符合整数要求。假设xi=bi不符合整数要求，bi 是不超过bi最大整数构造两个附加约束：xi bi 和 xi bi+1,分别将其并入上述松弛问题中，从而形成两个分枝。加入这两个约束，可得到两个

38、子问题，即两个后续问题。,将一个线性规划问题分为两枝，并求解。在线性规划(LP1)的最优解的两个非整数变量x12.44，x23.26 中，挑选一个最远离整数的那个变量 x12.44 进行分枝，即增加约束条件 x12 和 x13，并将线性规划(LP1)分为两个线性规划-(LP2)和(LP3)：,(LP2)：max z=2x1+3x2s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1 2 x1，x2 0。,(LP3)：max z=2x1+3x2s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1 3 x1，x2 0。,(LP1)：m

39、ax z=2x1+3x2s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，x2 0。,1,2,3,4,1,2,3,x2,x1,(LP2)的可行域,(LP3)的可行域,x1 2,x1 3,分枝：若整数规划的松弛问题的最优解不符合整数要求。假设xi=bi不符合整数要求，bi 是不超过bi最大整数构造两个附加约束：xr bi 和 xr bi+1,分别将其并入上述松弛问题中，从而形成两个分枝。加入这两个约束，可得到两个子问题，即两个后续问题。显然这两个子问题的域中包含原整数规划问题的所有可行解。而在原松弛问题可行域中，满足bi xi bi+1的一部分区域在以后的求解

40、过程中被遗弃了，然而它不包含整数规划的任何可行解,1,2,3,4,1,2,3,x2,x1,(LP2)的可行域,(LP3)的可行域,被遗弃的区域,x1 2,x1 3,分枝：若整数规划的松弛问题的最优解不符合整数要求。假设xi=bi不符合整数要求，bi 是不超过bi最大整数构造两个附加约束：xr bi 和 xr bi+1,分别将其并入上述松弛问题中，从而形成两个分枝。加入这两个约束，可得到两个子问题，即两个后续问题。显然这两个子问题的域中包含原整数规划问题的所有可行解。而在原松弛问题可行域中，满足bi xi bi+1的一部分区域在以后的求解过程中被遗弃了，然而它不包含整数规划的任何可行解 根据需要

41、，各后续问题问题可以类似地产生自己的分支，直到获得整数规划的最优解,1,2,3,4,1,2,3,x2,x1,(LP2)的可行域,(LP3)的可行域,被遗弃的区域,x1 2,x1 3,xi b,xi b+1,b xi b+1,1,2,3,4,1,2,3,x2,x1,(LP4)的可行域,(LP3)的可行域,被遗弃的区域,(LP5)的可行域,1,2,3,4,1,2,3,x2,x1,(LP1)的可行域,1,2,3,4,1,2,3,x2,x1,(LP4)的可行域,(LP3)的可行域,被遗弃的区域,(LP5)的可行域,分枝：若整数规划的松弛问题的最优解不符合整数要求。假设xi=bi不符合整数要求，bi 是

42、不超过bi最大整数构造两个附加约束：xr bi 和 xr bi+1,分别将其并入上述松弛问题中，从而形成两个分枝。加入这两个约束，可得到两个子问题，即两个后续问题。显然这两个子问题的域中包含原整数规划问题的所有可行解。而在原松弛问题可行域中，满足bi xi bi+1的一部分区域在以后的求解过程中被遗弃了，然而它不包含整数规划的任何可行解 根据需要，各后续问题问题可以类似地产生自己的分支，直到获得整数规划的最优解,定界：在分枝过程中，若某个后续问题恰好获得整数规划问题的一个可行解。那么，它的目标函数值就是一个“界限”，可以作为衡量处理其他分支的一个依据。整数规划问题的可行解集是它的松弛问题可行解

43、集的一个子集，前者最优解的目标函数不会优于后者最优解的目标函数值。对于那些相应松弛问题最优解的目标函数比上述“界限”值差的后继问题，就可以剔除不再考虑了。,例：用分枝定界法求解下面整数规划 max z=2x1+3x2 s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，x2 0,解：1.先求出相应的线性规划问题(LP1)，即松弛问题的解。求得这个线性规划的最优解为 x12.44，x23.26，目标函数的最优值为 14.66。显然，这个解不是原整数规划的可行解。,2.确定整数规划的最优目标函数值z*的初始上界 和下界。因(LP1)目标函数的最优值为 14.66，

44、故可取,定界：在分枝过程中，若某个后续问题恰好获得整数规划问题的一个可行解。那么，它的目标函数值就是一个“界限”，可以作为衡量处理其他分支的一个依据。整数规划问题的可行解集是它的松弛问题可行解集的一个子集，前者最优解的目标函数不会优于后者最优解的目标函数值。对于那些相应松弛问题最优解的目标函数比上述“界限”值差的后继问题，就可以剔除不再考虑了。,2.确定整数规划的最优目标函数值z*的初始上界 和下界。因(LP1)目标函数的最优值为 14.66，故可取 又用观察法可知，x12，x23 是原整数规划的可行解，其对应的目标函数值为 z=2x1+3x213，故可取=13。因为，所以需要进行分枝。,3.

45、将一个线性规划问题分为两枝，并求解。在线性规划(LP1)的最优解的两个非整数变量x12.44，x23.26 中，挑选一个最远离整数的那个变量 x12.44 进行分枝，即增加约束条件 x12 和 x13，并将线性规划(LP1)分为两个线性规划-(LP2)和(LP3)：,(LP2)：max z=2x1+3x2s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1 2 x1，x2 0。,(LP3)：max z=2x1+3x2s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1 3 x1，x2 0。,(LP1)：max z=2x1+3x2s

46、.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，x2 0。,(LP2)：max z=2x1+3x2s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1 2 x1，x2 0。求得这个线性规划的最优解为 x12，x23.3，目标函数的最优值为 13.9。,(LP3)：max z=2x1+3x2s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1 3 x1，x2 0。求得这个线性规划的最优解为 x13，x22.86，目标函数的最优值为 14.58。,4.修改整数规划的最优目标函数值 z*的上、下界。因

47、为(LP2)(x1 2)目标函数的最优值为 13.9，(LP2)对应的整数规划的最优目标函数值不会超过13.9；(LP3)(x13)目标函数的最优值为 14.58，(LP3)对应的整数规划的最优目标函数值不会超过 14.58。综上所述，不论 x1(4)取任何整数值，原整数规划的最优目标函数值不会超过 14.58，于是整数规划的最优目标函数值 z*的上界可修改为,又用观察法可知，在(LP2)(x12)中 x12，x23 是该整数规划的一个可行解，其对应的目标函数值为 z=2x1+3x213；在(LP3)(x13)中 x13，x22 是该整数规划的一个可行解，其对应的目标函数值为 z=2x1+3x

48、212。综上所述，不论 x1(4)取任何整数值，原整数规划的最优目标函数值不会小于 13，于是整数规划的最优目标函数值 z*的下界可(修改)为:,注意：在分枝定界求解过程中，为了求出最优整数解，我们要不断地缩小其最优目标函数值上界与下界的距离，故通过分枝要使得其上界越来越小，而其下界越来越大。由前可知，通过对上、下界的修改，上下界的距离有所缩小，但因为，所以还要继续进行分枝。,(LP1)z1=14.66x1=2.44x2=3.26,(LP2)z2=13.90 x1=2x2=3.30,(LP3)z3=14.58x1=3x2=2.86,x12,x13,5.重复(3.)，将一个线性规划问题分为两枝，

49、并求解。在(LP2)与(LP3)中选择目标函数的最优值大的那个线性规划进行分枝，即对(LP3)进行分枝。因为(LP3)的最优解为 x13，x22.86，挑选一个最远离整数的那个变量 x22.86，进行分枝，即增加约束条件 x22 和 x23，将线性规划(LP3)分为两个线性规划(LP4)和(LP5)：,(LP2)：max z=2x1+3x2s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1 2 x1，x2 0。,(LP3)：max z=2x1+3x2s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1 3 x1，x2 0。,(L

50、P1)：max z=2x1+3x2s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，x2 0。,(LP2)：max z=2x1+3x2s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1 2 x1，x2 0。,(LP3)：max z=2x1+3x2s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1 3 x1，x2 0。,(LP1)：max z=2x1+3x2s.t.195x1+273x2 1365 4x1+40 x2 140 x1 4 x1，x2 0。,(LP2)：max z=2x1+3x2s