运筹学 --目标规划与整数规划1.ppt

1、第四章 目标规划,同时考虑多个决策目标时，称为目标规划问题。,0 引言 从线性规划问题可看出： 线性规划只研究在满足一定条件下，单一目标函数取得最优解，而在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度（即优先顺序）也不相同，有些目标之间往往相互发生矛盾。,线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。 线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。,求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，

2、由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。,为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。,多目标优先级 先将目标等级化：将目标按重要性的程度不同依次分成一级目标、二级目标.。最次要的目标放在次要的等级中。,目标优先级作如下约定： 对同一个目标而言，若有几个决策方案都能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标差距越小的越好。,目标优先级作如下约定： 不同级别的目标的

3、重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别的目标上的收获都不可弥补。所以在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。,目标优先级作如下约定： 同一级别的目标可以是多个。各自之间的重要程度可用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，可有其余目标的适当收获来弥补。,1 多目标规划问题的数学模型 多目标的处理 为了将不同级别的目标的重要性用数量表示，引进P1，P2，.,用它表示一级目标，二级目标，.，的重要程度，规定P1P2 P3 .。称P1，P2，.,为级别系数。同一级Pi中，系数大的优先考虑。,约束方程的处理 差异变量：

4、决策变量x超过目标值b的部分记d+ 为正偏差；决策变量x不足目标值b的 部分记d-为负偏差d+ 0, d- 0 且 x + d - - d+ = b 同一个目标约束中d - d+=0。,多目标的综合 x + d - - d+ = b 若决策目标中规定 x b, 故 d+取最小。 若决策目标中规定 x b, d-取最小 若决策目标中规定 x = b, 故 d-+d+取最小。 绝对约束（硬约束）：必须严格满足的等式 约束和不等式 约束。 目标约束（软约束）：含正负偏差的约束。,b,d+,d-,目标规划问题的求解 (1)目标规划问题的图解法 (2)用单纯形法求目标函数的最优解 (3)灵敏度分析: 目

5、标规划的灵敏度分析与线性规划类似，对优先因子的变化问题进行举例说明。,例1：某电器公司经营的唱机和录音机均有车间A、B流水作业组装。数据见下表。,目标级为： (1)库存费用不超过4600元； (2)每月销售唱机不少于80台； (3)不使A、B车间停工（权数由生产费用确定）； (4)A车间加班时间限制在20小时内； （5）每月销售录音机至少为100台； （6）两车间加班时数总和要尽可能小（权数由生产费用确定）；,解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1 P1:库存费用不超过4600元, 50X1+30X2+ d1- d1+=4600,解：设每月生产唱机

6、、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1 P1:库存费用不超过4600元, P1d1+ 50X1+30X2+ d1- d1+=4600,解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1 P1:库存费用不超过4600元, P1d1+ 50X1+30X2+ d1- d1+=4600 P2 :每月销售唱机不少于80台, X1 + d2- d2+=80,解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1 P1:库存费用不超过4600元, P1d1+ 50X1+30X2+ d1- d1+=4600 P2 :每

7、月销售唱机不少于80台, P2d2- X1 + d2- d2+=80,解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1 P1:库存费用不超过4600元, P1d1+ 50X1+30X2+ d1- d1+=4600 P2 :每月销售唱机不少于80台, P2d2- X1 + d2- d2+=80 P3 :不使A车间停工,不使B车间停工, A车间:2X1 + X2+ d3- d3+=180 B车间:X1 + 3X2+ d4- d4+=200,解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1 P1:库存费用不超过4600元, P1

8、d1+ 50X1+30X2+ d1- d1+=4600 P2 :每月销售唱机不少于80台, P2d2- X1 + d2- d2+=80 P3 :不使A车间停工,不使B车间停工, 2 P3d3-+ P3d4- 2X1 + X2+ d3- d3+=180 X1 + 3X2+ d4- d4+=200,P4 : A车间加班时间限制在20小时内； 2X1 + X2+ d5- d5+=200,P4 : A车间加班时间限制在20小时内； P4d5+ 2X1 + X2+ d5- d5+=200,P4 : A车间加班时间限制在20小时内； P4d5+ 2X1 + X2+ d5- d5+=200 P5 : 每月销

9、售录音机至少为100台； X2 + d6- d6+=100,P4 : A车间加班时间限制在20小时内； P4d5+ 2X1 + X2+ d5- d5+=200 P5 : 每月销售录音机至少为100台； P5d6- X2 + d6- d6+=100,P4 : A车间加班时间限制在20小时内； P4d5+ 2X1 + X2+ d5- d5+=200 P5 : 每月销售录音机至少为100台； P5d6- X2 + d6- d6+=100 P6 :两车间加班时数总和要尽可能小（权数由生产费用确定）, 2P6d5+ P6d4+ X1,X2,di-, di+ , 0(i=1,2,3,4,5,6),Min

10、S=P1d1+P2d2-+2 P3d3-+ P3d4- +P4d5+ P5d6-+ P5d3+2P6d5+ P6d4+ 约束方程： 50X1+30X2+ d1- d1+=4600 X1 + d2- d2+=80 2X1 + X2+ d3- d3+=180 X1 + 3X2+ d4- d4+=200 2X1 + X2+ d5- d5+=200 X2 + d6- d6+=100 X1,X2,di-, di+ , 0(i=1,2,3,4,5,6),2 目标规划的图解法,例：某工厂生产、两种产品，数据如下,决策者在原材料供应严格受限制的情况考虑：首先产品 的产量不低于产品的产量；其次充分利用设备有效台

11、时，不 加班；再次利润不低于56元。列出模型，并求解。,Min Z=P1d1+P2 (d2-+d2+)+ P3d3- 约束方程： 2X1+X211 X1 - X2 +d1- d1+=0 X1 + 2X2+ d2- d2+=10 8X1 + 10X2+ d3- d3+ =56 X1,X2,di-, di+ , 0(i=1,2,3,),10,8,6,4,2,2x1+x2 11,B,A,OAB,O,Min Z=P1d1+P2 (d2-+d2+)+ P3d3- 约束方程： 2X1+X211 X1 - X2 +d1- d1+=0 X1 + 2X2+ d2- d2+=10 8X1 + 10X2+ d3-

12、d3+ =56 X1,X2,di-, di+ , 0(i=1,2,3,),2,4,6,8,10,10,8,6,4,2,2x1+x2 50,Min Z=P1d1+P2 (d2-+d2+)+ P3d3- 约束方程： 2X1+X211 X1 - X2 +d1- d1+=0 X1 + 2X2+ d2- d2+=10 8X1 + 10X2+ d3- d3+ =56 X1,X2,di-, di+ , 0(i=1,2,3,),d1+,d1-,B,D,A,OAB ODB,O,10,8,6,4,2,2x1+x2 50,Min Z=P1d1+P2 (d2-+d2+)+ P3d3- 约束方程： 2X1+X211 X

13、1 - X2 +d1- d1+=0 X1 + 2X2+ d2- d2+=10 8X1 + 10X2+ d3- d3+ =56 X1,X2,di-, di+ , 0(i=1,2,3,),d1+,d1-,d2+,B,E,D,A,OAB ODB DE,O,d2-,2,4,6,8,10,10,8,6,4,2,2x1+x2 50,Min Z=P1d1+P2 (d2-+d2+)+ P3d3- 约束方程： 2X1+X211 X1 - X2 +d1- d1+=0 X1 + 2X2+ d2- d2+=10 8X1 + 10X2+ d3- d3+ =56 X1,X2,di-, di+ , 0(i=1,2,3,),

14、2,4,6,8,x1,10,d1+,d1-,d2+,d2-,d3+,d3-,B,F,E,G,D,J,A,OAB OCB DE DG,O,例2：某工厂生产彩电、黑白两种电视机，数据如下,解： P1:充分利用装配线每周计划开动40小时； X1 +X2 +d1- - d1+ =40 P2 :允许装配线加班；但加班时间每周尽量不 超过10小时； X1 +X2 +d2- - d2+ =50 P3 :电视机的数量尽量满足市场要求，权系数为利润比。 X1 +d3- - d3+ =24 ； X2 +d4- - d4+ =30 目标函数： Min S=P1d1-+P2d2+ P3(2d3-+ d4-),Min

15、Z=P1d1-+P2 d2+ P3（2 d3-+ d4- ） 约束方程： X1 +X2 +d1- d1+=40 X1 +X2 +d1- d1+=50 X1 + d3- d3+ =24 X2 + d4- d4+ =30 X1,X2,di-, di+ , 0(i=1,2,3,),第一：充分利用装配线每周计划开动40小时； 第二：允许加班，但尽量不超过10小时； 第三：电视机要满足市场要求，彩电权系数取2。,10,8,6,4,2,O,Min Z=P1d1-+P2 d2+ P3（2 d3-+ d4- ） 约束方程： X1 +X2 +d1- d1+=40 X1 +X2 +d1- d1+=50 X1 +

16、d3- d3+ =24 X2 + d4- d4+ =30 X1,X2,di-, di+ , 0(i=1,2,3,),A,2,4,6,8,B,C,D,H,G,E,F,d1-,d1+,d2-,d2+,d3-,d3+,d4+,d4-,例 Min S = d1- X1+2X2+ d1- d1+ = 10 X1+2X2 6 X1+X2 4 X1,X2,d1-, d1+ 0,x1,x2,0,4,6,8,10,2,1,3,4,2,X1+2X2 6,x1,x2,0,4,6,8,10,2,1,3,4,2,X1+X2 4,x1,x2,0,4,6,8,10,2,1,3,4,2,x1,x2,0,4,6,8,10,2,

17、1,3,4,2,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2=10,5,d1+,d1-,A,B,(2,2),X1+2X2 6,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2=10,5,d1+,d1-,A,B,(2,2),当 Min S = d1- 达到时 d1- = 0,X1+2X2 6,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2=10,5,d1-,A,B,(2,2),X1+2X2 6,当 Min S = d1- 达到时 d1- = 0,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2+d1- = 10 d1-

18、 = 4,5,d1-,A,B,(2,2),有无穷多解：点（0，3）和点（2，2）连线上的点都是最优解。,(0,3),（1）目标函数求最小化，检验数大于等于0为最优准则； （2）非基变量的检验数中含有不同等级的优先因子，即 cj - zj =akj Pk, j=1,2, ,n; k= 1,2, ,K 因P1 P2 Pk, 从整体来看：检验数的正负首先取决于Pi的系数aij 的正负。若a1j =0，这时检验数的正负取决于P2的系数a2j 的正负，下面依次类推。,目标规划的单纯形法,目标规划的单纯形法 例：用单纯形法求解目标规划问题,X2换入， d2- 换出,表1,X1换入， d3- 换出,表2,非

19、基变量 d3+检验数为0，有无穷多最优解,表3,d3+换入， d1-换出,4目标规划的灵敏度分析 例：已知目标规划问题,用单纯形法得到的最终标为表4 - 5,表4 - 5,目标函数的优先等级变化为：,原问题的目标函数,目标函数的优先等级变化为：,分析原最优解有什么变化。 解：分析（1）相当于检验数中第二行与第三行互换。 检验数仍为非负，最优解不变。 分析（2）相当于检验数中第一行与第二行互换。 有检验数为负，最优解变化了。,原问题的目标函数,例:某单位领导在考虑本单位职工的升级调资方案时,依次遵守以下规定: (1)不超过月工资总额60000元; (2)每级人数不超过定编规定的人数; (3)、级

20、的升级面尽可能达到现有人数的20%； (4)级不足的人数可录用新职工,又级的职工中有10%要退休. 相关资料如下表:,解:设x1,x2,x3分别表示提升到、级和录用新职工的人数. P1:不超过月工资总额60000元; P2:每级人数不超过定编规定的人数; P3:、级的升级面尽可能达到现有人数的20% 调整以后各级的人数为: 级:10-1010%+ x1 级:12- x1+x2 级:15- x2+x3,分析: P1:不超过月工资总额60000元, P1d1+ 2000(10-1010%+ x1 )+1500(12- x1+x2)+1000(15- x2+x3)+ d1- d1+ =60000 P

21、2:每级人数不超过定编规定的人数, P2(d2+ +d3+ +d4+) 级:10-1010%+ x1+d2- d2+ =12 级:12- x1+x2 +d3- d3+ =15 级:15- x2+x3 +d4- d4+ =15,P3:、级的升级面尽可能达到现有人数的20%, P3(d5- +d6-) 级:x1+d5 d5+ =1220% 级:x2 +d6 d6+ =1520%,数学模型为: Minz= P1d1+ P2(d2+ +d3+ +d4+)+P3(d5- +d6-) 2000(10-1010%+ x1 )+1500(12- x1+x2)+1000(15- x2+x3)+ d1- d1+

22、=60000 10-1010%+ x1+d2- d2+ =12 12- x1+x2 +d3- d3+ =15 15- x2+x3 +d4- d4+ =15 x1+d5 d5+ =1220% x2 +d6 d6+ =1520% X1,x2 , x3 0, di- di+ 0,i=1,2,3,4,5,6,例3:已知三个产地给四个销地供应某种产品,供需量与单位运价表如下表:,考虑调运方案时,依次考虑以下七项指标: P1: B4是重点保护单位必须全部满足其要求; P2:A3向B1提供的产量不少于100; P3:每个销地的供应量不小于需要量的80%; P4: 所订调运方案的总费用不超过最小调运方案的10

23、%; P5:因路段的问题,尽量避免安排A2运往B4; P6:给B1和B3的供应率要相同; P7:力求总运费最省; 试求满意的调运方案,解:由于产量小于销量,假想一个产地A4,其产量为100. 用表上作业法求得最优表如下,最小运费为2950元.,分析: 供应约束: x11+x12 + x13+x14300 x21+x22 + x23+x24200 x31+x32 + x33+x34400 需求约束 : x11+x21 + x31+ d1- d1+ =200 x12+x22 + x32+ d2- d2+ =100 x13+x23 + x33+ d3- d3+ =450 x14+x24 + x34+

24、 d4- d4+ =250 P1: B4是重点保护单位必须全部满足其要求,P1 d4- P2:A3向B1提供的产量不少于100, P2 d5- x31+ d5- d5+ =100,分析: P3:每个销地的供应量不小于需要量的80%, P3(d6- +d7-+d8-+ d9- ) x11+x21 + x31+ d6- d6+ =2000.8 x12+x22 + x32+ d7- d7+ =1000.8 x13+x23 + x33+ d8- d8+ =4500.8 x14+x24 + x34+ d9- d9+ =2500.8 P4: 所订调运方案的总费用不超过最小调运方案的 10%, P4 d10

25、+,分析: P5:因路段的问题,尽量避免安排A2运往B4, P5 d11+ x24+ d11- d11+ =0 P6:给B1和B3的供应率要相同, P6 (d12-+d11+) 供应率=实际供应量/销量,即: (x11+x21 + x31) /200=(x13+x23 + x33 )/450,目标约束为: (x11+x21 + x31)-(200/450) (x13+x23 + x33 ) +d12- d12+ =0 P7:力求总运费最省, P7 d13+,供应约束: x11+x12 + x13+x14300 x21+x22 + x23+x24200 x31+x32 + x33+x34400

26、需求约束 : x11+x21 + x31+ d1- d1+ =200 x12+x22 + x32+ d2- d2+ =100 x13+x23 + x33+ d3- d3+ =450 P1 x14+x24 + x34+ d4- d4+ =250 P2 x31+ d5- d5+ =100,P4 x11+x21 + x31+ d6- d6+ =2000.8 x12+x22 + x32+ d7- d7+ =1000.8 x13+x23 + x33+ d8- d8+ =4500.8 x14+x24 + x34+ d9- d9+ =2500.8 P5 x24+ d11- d11+ =0 P6 (x11+x

27、21 + x31)-(200/450) (x13+x23 + x33 ) +d12- d12+ =0 P7 Minz=P1 d4- +P2 d5-+P3(d6- +d7+-+d8-+ d9- )+ P4 d10+P5 d11+P6 (d12-+d11+)+ P7 d13+,例：友谊农场有3万亩农田欲种植玉米、大豆和小麦三种农作物，各种作物每亩需施化肥分别为0.12吨、0.20吨、0.15吨。预计秋后玉米每亩可收获500千克，售价为0.24元/千克,大豆每亩可收获200千克,售价为1.20元/千克,小麦每亩可收获300千克,售价为0.70元/千克.农场年初规划时考虑如下几个方面: :年终收益不低

28、于350万元; :总产量不低于1.25万吨; :小麦产量以0.5万吨为宜; :大豆产量不少于0.2万吨; :玉米产量不超过0.6万吨; :农场现能提供5000吨化肥;若不够,可在市场高价购买,但希望高价采购愈少愈好. 试就该农场生产计划建立数学模型(不用求解).,解:设种植玉米、大豆和小麦三种农作物各为亩,该问题的数学模型为:,第五章 整数规划本章要求理解整数规划的含义掌握分枝定界法的思想和方法掌握0-1变量的含义和用法掌握指派问题的算法,5.1 整数规划问题的提出,决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数如何解决？四舍五入不行，枚举法太慢 问题分类：纯整数规划、混合整数规划

29、、0-1整数规划 专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法,整数规划是数学规划一个较弱的分支， 目前只能解中等规模的线性整数规划问题， 而非线性整数规划问题，还没有好的办法。,问题举例,例1:某集装箱运输公司，箱型标准体积24m3，重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2000元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？ maxZ=2000 x1+1000 x2 5x1+4x224 2 x1+5x2 13 x1,x2 0且为整数 解此LP问题，得： x1=4.8， x2 =0,z=96 显然不是可行解,整数规划图解法,x1,1

30、 2 3 4 5 6 7,B,A,x2,maxZ=2000 x1+1000 x2 5x1+4x224 2 x1+5x2 13 x1,x2 0且为整数 x1=4.8， x2 =0,z=96,先放弃变量的整数性要求，解一个线性规划问题，最优解为x1=4.8， x2 =0。然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。 x1=5， x2 =0不是可行解,因为不满足5x1+4x224 x1=4， x2 =0,z=80 x1=4， x2 =1是可行解,z=90,maxZ=2000 x1+1000 x2 5x1+4

31、x224 2 x1+5x2 13 x1,x2 0且为整数,图解法的启示,A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解 纯整数规划的可行解就是可行域中的整数点 非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化 IP问题的最优解不优于LP问题的最优解,例2：一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为31公斤。,解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划

32、: Max Z= 20 x1+15x2 +18x3 +14x4 +8x5 +4x6 +10 x7 s.t. 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6 +4x7 25 xi=1或xi=0 i=1,2,.7,数学模型 整数规划(IP)的一般数学模型: Max (min) Z = cjxj s.t. aijxj bi(i=1,2,m) xj 0 且部分或全部是整数,解法概述 当人们开始接触整数规划问题时，常会有如下两种初始想法： 因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n种方式；指派问题充其量有n!种方式；实际上这种方法是不可行。,设想

33、计算机每秒能比较1000000个方式，那么要比较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。,例 求下列问题： Max Z=3x1+13x2 s.t.2x1+9x2 40 11x1-8x2 82 x1,x2 0,且取整数值,O 1 2 3 4 5 6 7 8 9 10,x1,x2,I(2,4),B(9.2,2.4),A,D,可行域OABD内整数点，放弃整数要求后，最优解B(9.2,2.4) Z0=58.8，而原整数规划最优解I(2,4) Z0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。,x2,I(

34、2,4),B(9.2,2.4),假如能求出可行域的“整点凸包”（包含所有整点的最小多边形(OEFGHIJ），则可在此凸包上求线性规划的解，即为原问题的解。但求“整点凸包”十分困难。,F,G,H,I,J,x2,I(2,4),B(9.2,2.4),假如把可行域分解成五个互不相交的子问题P1 P2 P3 之和,而放弃整数要求后P1最优解I(2,4),Z1=58 P2最优解(6,3),Z2=57 P3最优解(98/11,2),Z4=52(8/11),P1,P2,P3,2 分枝定界解法 （Branch and Bound Method) 原问题的松驰问题：任何整数规划（IP），凡放弃某些约束条件（如整数

35、要求）后，所得到的问题（P） 都称为（IP）的松驰问题。,最通常的松驰问题是放弃变量的整数性要求后，（IP）为线性规划问题。 *整数规划的解集是其对应的线性规划解集的子集。 *整数规划求最大化时，线性规划的最优解是其解的上界。 *整数规划求最小化时，线性规划的最优解是其解的下界。,分枝定界法步骤 一般求解对应的松驰问题，可能会出现下面几种情况： 若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。 若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。,若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。 从不满足整数条件的基变量中任

36、选 一个xl进行分枝，它必须满足xl xl 或xl xl +1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。,定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。 剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。,例5-6 用分枝定界法求解： Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 整数 用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。,0 1 2 3 4,4 3 2 1,x1,x2,分

37、枝：X1 1,x1 2,P1,P2,Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 整数 最优解（6/5，21/10）,3x1+4x2 12,4x1+2x2 9,两个子问题： （P1）Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ， x1 1 ，整数 用单纯形法可解得相应的（P1）的最优解（1，9/4） Z=10(3/4),（P2）Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ， x1 2 ，整数 用单纯形法可解得相应的（P2）的最优解（2，1/2

38、） Z=9(1/2),0 1 2 3 4,4 3 2 1,x1,x2,再对（P1）分枝：X1 1 （P3） x2 2 （P4） x2 3,P1,P2,P3,P4,（P1）两个子问题： （P3）Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ,x1 1, x2 2整数 用单纯形法可解得相应的（P3）的最优解（1，2） Z=10,X1 2,X2 2,X1 1,X2 3,P1:(1,9/4) Z=10(3/4),P4: (0,3) Z=9,P2:(2,1/2) Z=9(1/2),P3: (1,2) Z=10,P:(6/5,21/10) Z=111/10

39、,原问题的最优解（1，2） Z=10,例5-7 用分枝定界法求解： Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 整数 用单纯形法可解得相应的松驰问题的最优解（10/3，4/3）Z=26/3为各分枝的下界。,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 整数 最优解（10/3，4/3）Z=26/3,2x1+ x2 8,x1+2x2 6,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,选 x1进行分枝：

40、 (P1) x1 3(P2) x1 4 为空集,P1,（P1） Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 3 整数 用单纯形法可解得（P1）的最优解（3，3/2）Z=9,（P1） Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 3 整数 用单纯形法可解得（P1）的最优解（3，3/2）Z=9,（P2） Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 4 整数 无可行解。,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,

41、p,P4,（P3） Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0， x1 3 ，x2 1整数 无可行解。,（P4） Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0， x1 3 ，x2 2整数 用单纯形法可解得（P4）的最优解（2，2）Z=10,（P3） Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0， x1 3 ，x2 1整数 无可行解。,（P4） Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0， x1 3 ，x2 2

42、整数 用单纯形法可解得（P4）的最优解（2，2）Z=10,X1 4,X2 1,X1 3,X2 2,P1:(3,3/2) Z=9,P4:(2,2) Z=10,P2:无可行解,P3:无可行解,P:(10/3,4/3) Z=26/3,原问题的最优解（2，2） Z=10,例：求解 Max Z=40 x1+90 x2 s.t. 9x1+ 7x2 56 7 x1+20 x2 56 x1,x2 0 且为整数,Max Z=40 x1+90 x2 s.t. 9x1+ 7x2 56 7 x1+20 x2 70 (B) x1,x2 0 且为整数 最优解x1,=4.81,x2 =1.82 z=356,8 7 6 5

43、4 3 2 1,x1,x2,0 1 2 3 4 5 6 7 8 9 10,9x1+ 7x2 56,7 x1+20 x2 70,8 7 6 5 4 3 2 1,x1,x2,0 1 2 3 4 5 6 7 8 9 10,9x1+ 7x2 56,问题（B） x1,=4.81,x2 =1.82 z=356,P1,P2,问题（B1） x1,=4,x2 =2.1 z=349,问题（B2） x1,=5,x2 =1.57 z=341,x14,x2 5,8 7 6 5 4 3 2 1,x1,x2,0 1 2 3 4 5 6 7 8 9 10,9x1+ 7x2 56,问题（B） x1,=4.81,x2 =1.82

44、 z=356,P3,P2,P4,问题（B1） x1,=4,x2 =2.1 P1 z=349,问题（B2） x1,=5,x2 =1.57 P2 z=341,x14,x1 5,x22,x2 3,8 7 6 5 4 3 2 1,x1,x2,0 1 2 3 4 5 6 7 8 9 10,9x1+ 7x2 56,问题（B） x1,=4.81,x2 =1.82 z=356,P3,P2,P4,问题（B1） x1,=4,x2 =2.1 P1 z=349,问题（B2） x1,=5,x2 =1.57 P2 z=341,问题（B3） x1,=4,x2 =2 P3 z=340,问题（B4） x1,=1.42,x2 =

45、3 P4 z=327,x14,x1 5,x22,x2 3,8 7 6 5 4 3 2 1,x1,x2,0 1 2 3 4 5 6 7 8 9 10,9x1+ 7x2 56,问题（B） x1,=4.81,x2 =1.82 z=356,P3,P2,P4,问题（B1） x1,=4,x2 =2.1 P1 z=349,问题（B2） x1,=5,x2 =1.57 P2 z=341,问题（B3） x1,=4,x2 =2 P3 z=340,问题（B4） x1,=1.42,x2 =3 P4 z=327,x14,x1 5,x21,x2 3,x22,x2 2,x1,x2,0 1 2 3 4 5 6 7 8 9 10

46、,9x1+ 7x2 56,问题（B） x1,=4.81,x2 =1.82 z=356,P3,P2,P4,问题（B1） x1,=4,x2 =2.1 P1 z=349,问题（B2） x1,=5,x2 =1.57 P2 z=341,问题（B3） x1,=4,x2 =2 P3 z=340,问题（B4） x1,=1.42,x2 =3 P4 z=327,x14,x1 5,x2 3,8 7 6 5 4 3 2 1,x1,x2,0 1 2 3 4 5 6 7 8 9 10,9x1+ 7x2 56,问题（B） x1,=4.81,x2 =1.82 z=356,P3,P2,P4,问题（B1） x1,=4,x2 =2

47、.1 P1 z=349,问题（B2） x1,=5,x2 =1.57 P2 z=341,问题（B3） x1,=4,x2 =2 P3 z=340,问题（B4） x1,=1.42,x2 =3 P4 z=327,x14,x1 5,x21,x2 3,问题（B4） x1=5.44,x2 =1 P5 z=308,问题（B4） 无可行解,x22,x2 2,x1,x2,0 1 2 3 4 5 6 7 8 9 10,9x1+ 7x2 56,问题（B） x1,=4.81,x2 =1.82 z=356,P3,P2,P4,问题（B1） x1,=4,x2 =2.1 P1 z=349,问题（B2） x1,=5,x2 =1.

48、57 P2 z=341,问题（B3） x1,=4,x2 =2 P3 z=340,问题（B4） x1,=1.42,x2 =3 P4 z=327,x14,x1 5,x2 3,3 割平面解法 （Gomory的割平面法）,例：求解 Max Z= x1+x2 s.t. -x1+ x2 1 3x1+x2 4 x1,x2 0， x1 ，x2 为整数 对应的LP的可行域如下图,0 1 2,2 1,A,x1,3x1+x2 4,-x1+x2 1,C,x2,D,LP的标准型为： Max Z= x1+x2 s.t. -x1+ x2 + x3 = 1 3x1+x2 + x4= 4 x1,x2 ,x3 ,x4 0 最终计

49、算表中得到非整数的最优解表5-2,3 0-1型整数规划,等价于,取整数,一 引例,例：某公司拟在东、西、南三区建立门市部，有7个位置Ai (i=1,2,7)可供选择。 在东区，由A1 、 A2 、 A3 三个点中至多选两个； 在西区由A4 、 A5 两个点中至少选一个； 在南区由A6 、 A 7两个点中至少选一个。 如选用点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？,解：引入0-1变量,当Ai点被采用,当Ai点没被采用,东区，由A1 、 A2 、 A3 三个点中至多选两个；,东区，由A1 、 A2 、 A3 三个点中至多选两个；

50、,东区，由A1 、 A2 、 A3 三个点中至多选两个； 在西区由A4 、 A5 两个点中至少选一个；,东区，由A1 、 A2 、 A3 三个点中至多选两个； 在西区由A4 、 A5 两个点中至少选一个；,东区，由A1 、 A2 、 A3 三个点中至多选两个； 在西区由A4 、 A5 两个点中至少选两个； 在南区由A6 、 A 7两个点中至少选一个。,东区，由A1 、 A2 、 A3 三个点中至多选两个； 在西区由A4 、 A5 两个点中至少选两个； 在南区由A6 、 A 7两个点中至少选一个。,东区，由A1 、 A2 、 A3 三个点中至多选两个； 在西区由A4 、 A5 两个点中至少选两个

51、； 在南区由A6 、 A 7两个点中至少选一个。 如选用点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。,东区，由A1 、 A2 、 A3 三个点中至多选两个； 在西区由A4 、 A5 两个点中至少选两个； 在南区由A6 、 A 7两个点中至少选一个。 如选用点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。,解：引入0-1变量,当Ai点被采用,当Ai点没被采用,数学模型为：,例：,体积限制为： 5x1+4x224 设其为车运时的体积限制 7x1+3x245 设其为船运时的体积限制,用船运,用车运,5x1+4x224+yM 7x1+3x24

52、5+(1-yM),若有m个互相排斥的约束：,为保证m个约束条件只有一个起作用，引入m个0-1变量 ，和充分大的数M。作如下约束即可。,约束条件只有一个起作用,二 0-1规划的解法,例：,是可行解。,故：,是过滤条件,Z值,5,3,8,变量,按照目标函数的系数递增的顺序排列：,也按下列顺序取值（0，0，0），,（0，0，1）， （0，1，1），这样最优解易较 早得到，同时，结合过滤条件的改进，使计算简化。 上例写为：,过滤条件改进为：,过滤条件改进为：,5 指派问题,指派问题：有n项工作，恰好有n个人去承担，每个人的专长不同，做每项工作的效率不同，应派哪个人去完成哪项工作，使总效率最高。,例：有

53、一份中文说明书，需译成英、日、德、俄四种文字。表格如下：,丁,人员,甲,乙,丙,任务,E,G,J,R,2 10 9 7,15 4 14 8,13 14 16 11,4 15 13 9,人,工作,1 2 n,1 2 n, ,应派哪个人去完成哪项工作，使总效率最高。,当指派第 个人完成第 项任务,当不指派第 个人完成第 项任务,数学模型： 设 是第 个人完成第 项任务的效率， ， =1，2， ，n.引入变量 ，其取值为1或0。,当指派第 个人完成第 项任务,当不指派第 个人完成第 项任务,数学模型： 设 是第 个人完成第 项任务的效率， ， =1，2， ，n.引入变量 ，其取值为1或0。,当指派第 个人完成第 项任务,当不指派第 个人完成第 项任务,第 项任务只能有一个人来完成,数学模型： 设 是第 个人完成第 项任务的效率， ， =1，2， ，n.引入变量 ，其取值为1或0。,当指派第 个人完成第 项任务,当不指派第 个人完成第 项任务,第 项任务只能有一个人来完成,第 个人只能完成一项任务,满足约束条件的可行解 写成矩阵形式，称为解矩阵。如：,解矩阵中的1一定在不同的行和不同的列。,指派问题的一些结果： (1)指派问题是0-1规划的特例也是