目标规划与整数规划

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

2、际情况。第3页，共188页，2022年，5月20日，1点6分，星期六求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。第4页，共188页，2022年，5月20日，1点6分，星期六为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。第5页，共188页，2022年，5月20日，1点6分，星期六多目标优先级 先将目标等级化：将目标按重要性的程度不同依次分成

3、一级目标、二级目标.。最次要的目标放在次要的等级中。第6页，共188页，2022年，5月20日，1点6分，星期六目标优先级作如下约定：对同一个目标而言，若有几个决策方案都能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标差距越小的越好。第7页，共188页，2022年，5月20日，1点6分，星期六目标优先级作如下约定： 不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别的目标上的收获都不可弥补。所以在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。第8页，共188页，2022年，5月20日，1点6分，星期六目标优先级

4、作如下约定：同一级别的目标可以是多个。各自之间的重要程度可用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，可有其余目标的适当收获来弥补。第9页，共188页，2022年，5月20日，1点6分，星期六1 多目标规划问题的数学模型多目标的处理 为了将不同级别的目标的重要性用数量表示，引进P1，P2，.,用它表示一级目标，二级目标，.，的重要程度，规定P1P2 P3 .。称P1，P2，.,为级别系数。同一级Pi中，系数大的优先考虑。第10页，共188页，2022年，5月20日，1点6分，星期六约束方程的处理差异变量：决策变量x超过目标值b的部分记d+为正偏差；决策变量x不足目标值b的部分记

5、d-为负偏差d+ 0, d- 0 且 x + d - - d+ = b同一个目标约束中d - d+=0。第11页，共188页，2022年，5月20日，1点6分，星期六多目标的综合 x + d - - d+ = b若决策目标中规定 x b, 故 d+取最小。 若决策目标中规定 x b, d-取最小若决策目标中规定 x = b, 故 d-+d+取最小。绝对约束（硬约束）：必须严格满足的等式约束和不等式 约束。目标约束（软约束）：含正负偏差的约束。bd+ d- 第12页，共188页，2022年，5月20日，1点6分，星期六 目标规划问题的求解(1)目标规划问题的图解法(2)用单纯形法求目标函数的最优

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

7、定）；第16页，共188页，2022年，5月20日，1点6分，星期六解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1P1:库存费用不超过4600元, 50X1+30X2+ d1- d1+=4600第17页，共188页，2022年，5月20日，1点6分，星期六解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1P1:库存费用不超过4600元, P1d1+ 50X1+30X2+ d1- d1+=4600第18页，共188页，2022年，5月20日，1点6分，星期六解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为10

8、0：50=2：1P1:库存费用不超过4600元, P1d1+ 50X1+30X2+ d1- d1+=4600P2 :每月销售唱机不少于80台, X1 + d2- d2+=80第19页，共188页，2022年，5月20日，1点6分，星期六解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1P1:库存费用不超过4600元, P1d1+ 50X1+30X2+ d1- d1+=4600P2 :每月销售唱机不少于80台, P2d2- X1 + d2- d2+=80第20页，共188页，2022年，5月20日，1点6分，星期六解：设每月生产唱机、录音机X1，X2台。且A、B

9、的生产费用之比为100：50=2：1P1:库存费用不超过4600元, P1d1+ 50X1+30X2+ d1- d1+=4600P2 :每月销售唱机不少于80台, P2d2- X1 + d2- d2+=80P3 :不使A车间停工,不使B车间停工, A车间:2X1 + X2+ d3- d3+=180 B车间:X1 + 3X2+ d4- d4+=200 第21页，共188页，2022年，5月20日，1点6分，星期六解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1P1:库存费用不超过4600元, P1d1+ 50X1+30X2+ d1- d1+=4600P2 :每

10、月销售唱机不少于80台, P2d2- X1 + d2- d2+=80P3 :不使A车间停工,不使B车间停工, 2 P3d3-+ P3d4- 2X1 + X2+ d3- d3+=180 X1 + 3X2+ d4- d4+=200 第22页，共188页，2022年，5月20日，1点6分，星期六 P4 : A车间加班时间限制在20小时内； 2X1 + X2+ d5- d5+=200第23页，共188页，2022年，5月20日，1点6分，星期六 P4 : A车间加班时间限制在20小时内； P4d5+ 2X1 + X2+ d5- d5+=200第24页，共188页，2022年，5月20日，1点6分，星期

11、六 P4 : A车间加班时间限制在20小时内； P4d5+ 2X1 + X2+ d5- d5+=200P5 : 每月销售录音机至少为100台； X2 + d6- d6+=100第25页，共188页，2022年，5月20日，1点6分，星期六 P4 : A车间加班时间限制在20小时内； P4d5+ 2X1 + X2+ d5- d5+=200P5 : 每月销售录音机至少为100台； P5d6- X2 + d6- d6+=100第26页，共188页，2022年，5月20日，1点6分，星期六 P4 : A车间加班时间限制在20小时内； P4d5+ 2X1 + X2+ d5- d5+=200P5 : 每月

12、销售录音机至少为100台； P5d6- X2 + d6- d6+=100P6 :两车间加班时数总和要尽可能小（权数由生产费用确定）, 2P6d5+ P6d4+ X1,X2,di-, di+ , 0(i=1,2,3,4,5,6)第27页，共188页，2022年，5月20日，1点6分，星期六Min 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

13、 + X2+ d5- d5+=200 X2 + d6- d6+=100 X1,X2,di-, di+ , 0(i=1,2,3,4,5,6) 第28页，共188页，2022年，5月20日，1点6分，星期六2 目标规划的图解法 拥有量原材料（kg）2 111设备1 210利润（元/件）8 10例：某工厂生产、两种产品，数据如下 决策者在原材料供应严格受限制的情况考虑：首先产品 的产量不低于产品的产量；其次充分利用设备有效台时，不加班；再次利润不低于56元。列出模型，并求解。第29页，共188页，2022年，5月20日，1点6分，星期六Min Z=P1d1+P2 (d2-+d2+)+ P3d3-约束

14、方程： 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,) 第30页，共188页，2022年，5月20日，1点6分，星期六1086422x1+x2 11BAOABOMin 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,) 2468

15、 10第31页，共188页，2022年，5月20日，1点6分，星期六1086422x1+x2 50Min 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-BDAOAB ODBO第32页，共188页，2022年，5月20日，1点6分，星期六1086422x1+x2 50Min Z=P1d1+P2 (d2-+d2+)+ P3d3-约束方程： 2X1+X211 X1 -

16、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+BEDAOAB ODB DE Od2-2468 10第33页，共188页，2022年，5月20日，1点6分，星期六1086422x1+x2 50Min 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

17、,2,3,) 2468x1 10d1+d1-d2+d2-d3+d3-BFEGDJAOAB OCB DE DGO第34页，共188页，2022年，5月20日，1点6分，星期六彩电 黑白拥有量装配线（小时）1 140销量24 30利润（元/件）80 40例2：某工厂生产彩电、黑白两种电视机，数据如下第35页，共188页，2022年，5月20日，1点6分，星期六解：P1:充分利用装配线每周计划开动40小时；X1 +X2 +d1- - d1+ =40P2 :允许装配线加班；但加班时间每周尽量不 超过10小时；X1 +X2 +d2- - d2+ =50P3 :电视机的数量尽量满足市场要求，权系数为利润比

18、。X1 +d3- - d3+ =24 ； X2 +d4- - d4+ =30目标函数： Min S=P1d1-+P2d2+ P3(2d3-+ d4-)第36页，共188页，2022年，5月20日，1点6分，星期六Min 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小时；第三：电视机要满足市场要求

19、，彩电权系数取2。第37页，共188页，2022年，5月20日，1点6分，星期六108642OMin 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,) A2468BCDHGEF d1-d1+d2-d2+d3-d3+d4+d4-第38页，共188页，2022年，5月20日，1点6分，星期六例 Min S = d1- X1+2X2+ d1- d1+ = 10 X1+2X2 6

20、X1+X2 4 X1,X2,d1-, d1+ 0第39页，共188页，2022年，5月20日，1点6分，星期六x1x204681021342X1+2X2 6第40页，共188页，2022年，5月20日，1点6分，星期六x1x204681021342X1+X2 4第41页，共188页，2022年，5月20日，1点6分，星期六x1x204681021342第42页，共188页，2022年，5月20日，1点6分，星期六x1x204681021342第43页，共188页，2022年，5月20日，1点6分，星期六x1x204681021342x1+2x2=105d1+d1-AB(2,2)X1+2X2 6

21、第44页，共188页，2022年，5月20日，1点6分，星期六x1x204681021342x1+2x2=105d1+d1-AB(2,2)当 Min S = d1- 达到时 d1- = 0X1+2X2 6第45页，共188页，2022年，5月20日，1点6分，星期六x1x204681021342x1+2x2=105d1-AB(2,2)X1+2X2 6当 Min S = d1- 达到时 d1- = 0第46页，共188页，2022年，5月20日，1点6分，星期六x1x204681021342x1+2x2+d1- = 10 d1- = 45d1-AB(2,2)有无穷多解：点（0，3）和点（2，2）

22、连线上的点都是最优解。(0,3)第47页，共188页，2022年，5月20日，1点6分，星期六（1）目标函数求最小化，检验数大于等于0为最优准则；（2）非基变量的检验数中含有不同等级的优先因子，即 cj - zj =akj Pk, j=1,2, ,n; k= 1,2, ,K因P1 P2 Pk, 从整体来看：检验数的正负首先取决于Pi的系数aij 的正负。若a1j =0，这时检验数的正负取决于P2的系数a2j 的正负，下面依次类推。目标规划的单纯形法第48页，共188页，2022年，5月20日，1点6分，星期六目标规划的单纯形法例：用单纯形法求解目标规划问题第49页，共188页，2022年，5月

23、20日，1点6分，星期六X2换入， d2- 换出表1 CjP1P2P2P3CB XB bX1 X2XSd1-d1+d2-d2+d3-d3+ Xs 11 d1- 0P2 d2- 10P3 d3- 56 2 1 1 8 1 -1 2 10 1 1 -11-11-110/2 P1Cj zj P2 P3-1-8-2-10121第50页，共188页，2022年，5月20日，1点6分，星期六 CjP1P2P2P3CB XB bX1 X2XSd1-d1+d2-d2+d3-d3+ Xs 6 d1- 5 X2 5P3 d3- 6 3/23/2 1/2 3 1 1 1 -1-1/21/21/2- 51/2-1/2

24、-1/2 5 1-16/3 P1Cj zj P2 P3-31 1 51-5 1X1换入， d3- 换出表2第51页，共188页，2022年，5月20日，1点6分，星期六 CjP1P2P2P3CB XB bX1 X2XSd1-d1+d2-d2+d3-d3+ Xs 3 d1- 2 X2 4P3 X1 2 32 4 2 1 1 1 1234/3-5/3-2-3-4/35/3-1/2-1/2-1/61/31/21/21/6-1/3 P1Cj zj P2 P31 1 11 非基变量 d3+检验数为0，有无穷多最优解表3第52页，共188页，2022年，5月20日，1点6分，星期六 CjP1P2P2P3C

25、B XB bX1 X2XSd1-d1+d2-d2+d3-d3+ Xs 1 d3+ 4 X2 10/3 X1 10/3 1 1 1 -1 2-1/32/31-2 1/3-2/3-161/31/31-6-1/3-1/3-11 P1Cj zj P2 P31 1 11 d3+换入， d1-换出第53页，共188页，2022年，5月20日，1点6分，星期六4目标规划的灵敏度分析例：已知目标规划问题用单纯形法得到的最终标为表4 - 5第54页，共188页，2022年，5月20日，1点6分，星期六表4 - 5目标函数的优先等级变化为：原问题的目标函数第55页，共188页，2022年，5月20日，1点6分，星

26、期六目标函数的优先等级变化为：分析原最优解有什么变化。解：分析（1）相当于检验数中第二行与第三行互换。检验数仍为非负，最优解不变。 分析（2）相当于检验数中第一行与第二行互换。有检验数为负，最优解变化了。原问题的目标函数第56页，共188页，2022年，5月20日，1点6分，星期六第57页，共188页，2022年，5月20日，1点6分，星期六第58页，共188页，2022年，5月20日，1点6分，星期六例:某单位领导在考虑本单位职工的升级调资方案时,依次遵守以下规定:(1)不超过月工资总额60000元;(2)每级人数不超过定编规定的人数;(3)、级的升级面尽可能达到现有人数的20%；(4)级不

27、足的人数可录用新职工,又级的职工中有10%要退休.相关资料如下表:第59页，共188页，2022年，5月20日，1点6分，星期六等级工资额(元/月)现有人数编制人数 2000150010001012151215153742第60页，共188页，2022年，5月20日，1点6分，星期六解:设x1,x2,x3分别表示提升到、级和录用新职工的人数.P1:不超过月工资总额60000元;P2:每级人数不超过定编规定的人数;P3:、级的升级面尽可能达到现有人数的20%调整以后各级的人数为:级:10-1010%+ x1级:12- x1+x2级:15- x2+x3第61页，共188页，2022年，5月20日，

28、1点6分，星期六分析:P1:不超过月工资总额60000元, P1d1+2000(10-1010%+ x1 )+1500(12- x1+x2)+1000(15- x2+x3)+ d1- d1+ =60000P2:每级人数不超过定编规定的人数, P2(d2+ +d3+ +d4+)级:10-1010%+ x1+d2- d2+ =12级:12- x1+x2 +d3- d3+ =15级:15- x2+x3 +d4- d4+ =15第62页，共188页，2022年，5月20日，1点6分，星期六P3:、级的升级面尽可能达到现有人数的20%,P3(d5- +d6-)级:x1+d5 d5+ =1220%级:x2

29、 +d6 d6+ =1520%第63页，共188页，2022年，5月20日，1点6分，星期六数学模型为:Minz= P1d1+ P2(d2+ +d3+ +d4+)+P3(d5- +d6-)2000(10-1010%+ x1 )+1500(12- x1+x2)+1000(15- x2+x3)+ d1- d1+ =6000010-1010%+ x1+d2- d2+ =1212- x1+x2 +d3- d3+ =1515- x2+x3 +d4- d4+ =15x1+d5 d5+ =1220%x2 +d6 d6+ =1520%X1,x2 , x3 0, di- di+ 0,i=1,2,3,4,5,6第

30、64页，共188页，2022年，5月20日，1点6分，星期六例3:已知三个产地给四个销地供应某种产品,供需量与单位运价表如下表: 销地产地B1B2B3B4产量A15 2 6 7 300A23 5 4 6 200A3452 3 400销量 200100450 250 9001000第65页，共188页，2022年，5月20日，1点6分，星期六考虑调运方案时,依次考虑以下七项指标:P1: B4是重点保护单位必须全部满足其要求;P2:A3向B1提供的产量不少于100;P3:每个销地的供应量不小于需要量的80%;P4: 所订调运方案的总费用不超过最小调运方案的10%;P5:因路段的问题,尽量避免安排A

31、2运往B4;P6:给B1和B3的供应率要相同;P7:力求总运费最省;试求满意的调运方案第66页，共188页，2022年，5月20日，1点6分，星期六解:由于产量小于销量,假想一个产地A4,其产量为100.用表上作业法求得最优表如下,最小运费为2950元. 销地产地B1B2B3B4产量A1200 100 300A20 200 200A3A4250 150 100400100销量 200100450 250 第67页，共188页，2022年，5月20日，1点6分，星期六分析: 供应约束: x11+x12 + x13+x14300 x21+x22 + x23+x24200 x31+x32 + x33

32、+x34400 需求约束 : x11+x21 + x31+ d1- d1+ =200 x12+x22 + x32+ d2- d2+ =100 x13+x23 + x33+ d3- d3+ =450 x14+x24 + x34+ d4- d4+ =250P1: B4是重点保护单位必须全部满足其要求,P1 d4-P2:A3向B1提供的产量不少于100, P2 d5- x31+ d5- d5+ =100第68页，共188页，2022年，5月20日，1点6分，星期六分析: P3:每个销地的供应量不小于需要量的80%, P3(d6- +d7-+d8-+ d9- ) x11+x21 + x31+ d6-

33、d6+ =2000.8 x12+x22 + x32+ d7- d7+ =1000.8 x13+x23 + x33+ d8- d8+ =4500.8 x14+x24 + x34+ d9- d9+ =2500.8P4: 所订调运方案的总费用不超过最小调运方案的 10%, P4 d10+第69页，共188页，2022年，5月20日，1点6分，星期六分析: P5:因路段的问题,尽量避免安排A2运往B4, P5 d11+ x24+ d11- d11+ =0P6:给B1和B3的供应率要相同, P6 (d12-+d11+) 供应率=实际供应量/销量,即: (x11+x21 + x31) /200=(x13+

34、x23 + x33 )/450,目标约束为: (x11+x21 + x31)-(200/450) (x13+x23 + x33 ) +d12- d12+ =0P7:力求总运费最省, P7 d13+第70页，共188页，2022年，5月20日，1点6分，星期六 供应约束: 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+ =450P1 x14+x24

35、+ x34+ d4- d4+ =250P2 x31+ d5- d5+ =100 第71页，共188页，2022年，5月20日，1点6分，星期六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.8P5 x24+ d11- d11+ =0P6 (x11+x21 + x31)-(200/450) (x13+x23 + x33 ) +d12- d12+ =0P7Minz=P1 d4- +P2 d5-+P3

36、(d6- +d7+-+d8-+ d9- )+ P4 d10+P5 d11+P6 (d12-+d11+)+ P7 d13+第72页，共188页，2022年，5月20日，1点6分，星期六例：友谊农场有3万亩农田欲种植玉米、大豆和小麦三种农作物，各种作物每亩需施化肥分别为0.12吨、0.20吨、0.15吨。预计秋后玉米每亩可收获500千克，售价为0.24元/千克,大豆每亩可收获200千克,售价为1.20元/千克,小麦每亩可收获300千克,售价为0.70元/千克.农场年初规划时考虑如下几个方面: :年终收益不低于350万元; :总产量不低于1.25万吨; :小麦产量以0.5万吨为宜; :大豆产量不少于

37、0.2万吨; :玉米产量不超过0.6万吨; :农场现能提供5000吨化肥;若不够,可在市场高价购买,但希望高价采购愈少愈好.试就该农场生产计划建立数学模型(不用求解). 第73页，共188页，2022年，5月20日，1点6分，星期六玉米大豆小麦化肥吨/亩0.120.200.15收获千克/亩500200300售价元/千克0.241.200.70第74页，共188页，2022年，5月20日，1点6分，星期六解:设种植玉米、大豆和小麦三种农作物各为亩,该问题的数学模型为:第75页，共188页，2022年，5月20日，1点6分，星期六第五章 整数规划本章要求理解整数规划的含义掌握分枝定界法的思想和方法

38、掌握0-1变量的含义和用法掌握指派问题的算法第76页，共188页，2022年，5月20日，1点6分，星期六5.1 整数规划问题的提出决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数如何解决？四舍五入不行，枚举法太慢问题分类：纯整数规划、混合整数规划、0-1整数规划专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法第77页，共188页，2022年，5月20日，1点6分，星期六 整数规划是数学规划一个较弱的分支，目前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的办法。问题举例第78页，共188页，2022年，5月20日，1点6分，星期六例1:某集装箱运输公司，箱型标准

39、体积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显然不是可行解第79页，共188页，2022年，5月20日，1点6分，星期六第80页，共188页，2022年，5月20日，1点6分，星期六整数规划图解法x1 1 2 3 4 5 6 7 BAx2maxZ=2000 x1+1000 x2 5x1+4x224 2 x1+5x2

40、13 x1,x2 0且为整数 x1=4.8， x2 =0,z=96第81页，共188页，2022年，5月20日，1点6分，星期六先放弃变量的整数性要求，解一个线性规划问题，最优解为x1=4.8， x2 =0。然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。x1=5， x2 =0不是可行解,因为不满足5x1+4x224x1=4， x2 =0,z=80 x1=4， x2 =1是可行解,z=90maxZ=2000 x1+1000 x2 5x1+4x224 2 x1+5x2 13 x1,x2 0且为整数第82页，

41、共188页，2022年，5月20日，1点6分，星期六图解法的启示A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解纯整数规划的可行解就是可行域中的整数点非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化IP问题的最优解不优于LP问题的最优解第83页，共188页，2022年，5月20日，1点6分，星期六例2：一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为31公斤。序号1234567物品食品氧气冰镐绳索帐篷相机设备重量

42、55261224重要系数201518141048第84页，共188页，2022年，5月20日，1点6分，星期六解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划: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第85页，共188页，2022年，5月20日，1点6分，星期六数学模型整数规划(IP)的一般数学模型:Max (min) Z = cjxjs.t. aijxj bi(i=1,

43、2,m) xj 0 且部分或全部是整数第86页，共188页，2022年，5月20日，1点6分，星期六解法概述当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n种方式；指派问题充其量有n!种方式；实际上这种方法是不可行。第87页，共188页，2022年，5月20日，1点6分，星期六 设想计算机每秒能比较1000000个方式，那么要比较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。第88页，共188页，2022年，5月20日，1点6分，星期六例 求下列问题：Ma

44、x Z=3x1+13x21+9x2 40 11x1-8x2 82x1,x2 0,且取整数值第89页，共188页，2022年，5月20日，1点6分，星期六O 1 2 3 4 5 6 7 8 9 10 x1x2I(2,4)B(9.2,2.4)AD可行域OABD内整数点，放弃整数要求后，最优解B(9.2,2.4) Z0=58.8，而原整数规划最优解I(2,4) Z0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。第90页，共188页，2022年，5月20日，1点6分，星期六x2I(2,4)B(9.2,2.4)假如能求出可行域的“整点凸包”（包含所有整点的最

45、小多边形(OEFGHIJ），则可在此凸包上求线性规划的解，即为原问题的解。但求“整点凸包”十分困难。FGHIJ第91页，共188页，2022年，5月20日，1点6分，星期六x2I(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) P1P2P3第92页，共188页，2022年，5月20日，1点6分，星期六2 分枝定界解法（Branch and Bound Method)原问题的松驰问题：任何整数规划（IP），凡放弃某些

46、约束条件（如整数要求）后，所得到的问题（P） 都称为（IP）的松驰问题。第93页，共188页，2022年，5月20日，1点6分，星期六 最通常的松驰问题是放弃变量的整数性要求后，（IP）为线性规划问题。*整数规划的解集是其对应的线性规划解集的子集。 *整数规划求最大化时，线性规划的最优解是其解的上界。*整数规划求最小化时，线性规划的最优解是其解的下界。第94页，共188页，2022年，5月20日，1点6分，星期六 分枝定界法步骤一般求解对应的松驰问题，可能会出现下面几种情况：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。若松驰问题无可行解，则原整数规划问题也无可行

47、解，计算结束。第95页，共188页，2022年，5月20日，1点6分，星期六若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。从不满足整数条件的基变量中任选 一个xl进行分枝，它必须满足xl xl 或xl xl +1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。第96页，共188页，2022年，5月20日，1点6分，星期六定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。第97页，共188页，2022年

48、，5月20日，1点6分，星期六例5-6 用分枝定界法求解：Max Z=4x1+3x2s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 整数用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。第98页，共188页，2022年，5月20日，1点6分，星期六0 1 2 3 44 3 2 1x1x2分枝：X1 1,x1 2P1P2Max Z=4x1+3x2s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 整数最优解（6/5，21/10）3x1+4x2 12 4x1+2x2 9 第99页，共188页，2022年，5月20日，1点

49、6分，星期六两个子问题：（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)第100页，共188页，2022年，5月20日，1点6分，星期六（P2）Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ， x1 2 ，整数用单纯形法可解得相应的（P2）的最优解（2，1/2） Z=9(1/2)第101页，共188页，2022年，5月20日，1点6分，星期六0 1 2 3 44 3 2 1x1x2再对（P1）分枝：

50、X1 1（P3） x2 2 （P4） x2 3P1P2P3P4第102页，共188页，2022年，5月20日，1点6分，星期六（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第103页，共188页，2022年，5月20日，1点6分，星期六X1 2X2 2X1 1X2 3P1:(1,9/4)Z=10(3/4)P4: (0,3) Z=9P2:(2,1/2) Z=9(1/2)P3: (1,2) Z=10P:(6/5,21/10) Z=111/

51、10原问题的最优解（1，2） Z=10第104页，共188页，2022年，5月20日，1点6分，星期六例5-7 用分枝定界法求解：Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 整数用单纯形法可解得相应的松驰问题的最优解（10/3，4/3）Z=26/3为各分枝的下界。第105页，共188页，2022年，5月20日，1点6分，星期六 0 1 2 3 4 5 6 8 7 6 5 4 3 2 1x1x2pMin Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 整数最优解（10/3，4/3）Z=26/32x1+ x2 8 x1

52、+2x2 6 第106页，共188页，2022年，5月20日，1点6分，星期六 0 1 2 3 4 5 6 8 7 6 5 4 3 2 1x1x2p选 x1进行分枝： (P1) x1 3(P2) x1 4 为空集P1（P1）Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 3 整数用单纯形法可解得（P1）的最优解（3，3/2）Z=9第107页，共188页，2022年，5月20日，1点6分，星期六（P1）Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 3 整数用单纯形法可解得（P1）的最优解（3，3/2

53、）Z=9第108页，共188页，2022年，5月20日，1点6分，星期六（P2）Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 4 整数无可行解。第109页，共188页，2022年，5月20日，1点6分，星期六 0 1 2 3 4 5 6 8 7 6 5 4 3 2 1x1x2pP4（P3）Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0， x1 3 ，x2 1整数无可行解。（P4）Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0， x1 3 ，x2 2整数用单纯形法

54、可解得（P4）的最优解（2，2）Z=10第110页，共188页，2022年，5月20日，1点6分，星期六（P3）Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0， x1 3 ，x2 1整数无可行解。第111页，共188页，2022年，5月20日，1点6分，星期六（P4）Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0， x1 3 ，x2 2整数用单纯形法可解得（P4）的最优解（2，2）Z=10第112页，共188页，2022年，5月20日，1点6分，星期六X1 4X2 1X1 3X2 2P1:(3,3/2)Z=9P

55、4:(2,2) Z=10P2:无可行解P3:无可行解P:(10/3,4/3) Z=26/3原问题的最优解（2，2） Z=10第113页，共188页，2022年，5月20日，1点6分，星期六例：求解Max Z=40 x1+90 x2s.t. 9x1+ 7x2 56 7 x1+20 x2 56 x1,x2 0 且为整数第114页，共188页，2022年，5月20日，1点6分，星期六Max Z=40 x1+90 x2s.t. 9x1+ 7x2 56 7 x1+20 x2 70 (B) x1,x2 0 且为整数最优解x1,=4.81,x2 =1.82 z=3568 7 6 5 4 3 2 1x1x2

56、0 1 2 3 4 5 6 7 8 9 109x1+ 7x2 567 x1+20 x2 70第115页，共188页，2022年，5月20日，1点6分，星期六8 7 6 5 4 3 2 1x1x2 0 1 2 3 4 5 6 7 8 9 109x1+ 7x2 56问题（B）x1,=4.81,x2 =1.82 z=356P1P2问题（B1）x1,=4,x2 =2.1 z=349问题（B2）x1,=5,x2 =1.57z=341x14x2 5第116页，共188页，2022年，5月20日，1点6分，星期六8 7 6 5 4 3 2 1x1x2 0 1 2 3 4 5 6 7 8 9 109x1+ 7

57、x2 56问题（B）x1,=4.81,x2 =1.82 z=356P3P2P4问题（B1）x1,=4,x2 =2.1 P1z=349问题（B2）x1,=5,x2 =1.57 P2z=341x14x1 5x22x2 3第117页，共188页，2022年，5月20日，1点6分，星期六8 7 6 5 4 3 2 1x1x2 0 1 2 3 4 5 6 7 8 9 109x1+ 7x2 56问题（B）x1,=4.81,x2 =1.82 z=356P3P2P4问题（B1）x1,=4,x2 =2.1 P1z=349问题（B2）x1,=5,x2 =1.57 P2z=341问题（B3）x1,=4,x2 =2

58、P3z=340问题（B4）x1,=1.42,x2 =3 P4z=327x14x1 5x22x2 3第118页，共188页，2022年，5月20日，1点6分，星期六8 7 6 5 4 3 2 1x1x2 0 1 2 3 4 5 6 7 8 9 109x1+ 7x2 56问题（B）x1,=4.81,x2 =1.82 z=356P3P2P4问题（B1）x1,=4,x2 =2.1 P1z=349问题（B2）x1,=5,x2 =1.57 P2z=341问题（B3）x1,=4,x2 =2 P3z=340问题（B4）x1,=1.42,x2 =3 P4z=327x14x1 5x21x2 3x22x2 2x1x

59、2 0 1 2 3 4 5 6 7 8 9 109x1+ 7x2 56问题（B）x1,=4.81,x2 =1.82 z=356P3P2P4问题（B1）x1,=4,x2 =2.1 P1z=349问题（B2）x1,=5,x2 =1.57 P2z=341问题（B3）x1,=4,x2 =2 P3z=340问题（B4）x1,=1.42,x2 =3 P4z=327x14x1 5x2 3第119页，共188页，2022年，5月20日，1点6分，星期六8 7 6 5 4 3 2 1x1x2 0 1 2 3 4 5 6 7 8 9 109x1+ 7x2 56问题（B）x1,=4.81,x2 =1.82 z=35

60、6P3P2P4问题（B1）x1,=4,x2 =2.1 P1z=349问题（B2）x1,=5,x2 =1.57 P2z=341问题（B3）x1,=4,x2 =2 P3z=340问题（B4）x1,=1.42,x2 =3 P4z=327x14x1 5x21x2 3问题（B4）x1=5.44,x2 =1 P5z=308问题（B4）无可行解x22x2 2x1x2 0 1 2 3 4 5 6 7 8 9 109x1+ 7x2 56问题（B）x1,=4.81,x2 =1.82 z=356P3P2P4问题（B1）x1,=4,x2 =2.1 P1z=349问题（B2）x1,=5,x2 =1.57 P2z=341