运筹学多目标规划(1)

1、例4-1：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？用单纯形法求得最优解=（20，20）最优值=200（百元）1问题：该厂提出如下目标（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；如何安排生产？2例4-2：某车间有A、B两条设备相同的生产线，它们生产同一种产品。A生产线每小时可制造2件产品，B生产线每小时可制造1.5件产品。如果每周正常工作时数为45小时，要求制定完成下列目标的生产计划： （1）生产量达到210件/

2、周；（2） A生产线加班时间限制在15小时内；（3）充分利用工时指标，并依A、B产量的比例确定重要性。3例4-3：某电器公司经营的唱机和录音机均有车间A、B流水作业组装。数据见下表。要求按以下目标制订月生产计划：（1）库存费用不超过4600元；（2）每月销售唱机不少于80台；（3）不使A、B车间停工（权数由生产费用确定）；（4）A车间加班时间限制在20小时内；（5）每月销售录音机为100台；（6）两车间加班时数总和要尽可能小（权数由生产费用确定）；4多目标优先级 先将目标等级化：将目标按重要性的程度不同依次分成一级目标、二级目标.。最次要的目标放在次要的等级中。目标优先级作如下约定：对同一个目

3、标而言，若有几个决策方案都能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标差距越小的越好。不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别的目标上的收获都不可弥补。所以在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。同一级别的目标可以是多个。各自之间的重要程度可用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，可有其余目标的适当收获来弥补。5多目标规划解的概念：若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解；若解只能满足部分目标，就称该解为多目标规划的次优解；若找不到满足任何

4、一个目标的解，就称该问题为无解。6例4-1：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？用单纯形法求得最优解=（20，20）最优值=200（百元）7问题：该厂提出如下目标（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；如何安排生产？8对例4-1的问题，设超过一吨钢材与超过5个工时的损失相同。现有四个方案进行比较优劣？9目标：（1）利润达到280百元； （2）钢材不超过100吨，工时不超过120小时；对于（1），只有方案

5、4没有完成。排除方案4。对于（2），只有方案2达到了，因此方案2是最优。10目标：（1）利润达到280百元； （2）钢材不超过100吨，工时不超过120小时；方案1与方案3都达到了（1），又没达到（2）方案1与（2）的差距：工时损失=（110-100）*5+（130-120）*1=60方案3与（2）的差距：工时损失=0*5+（190-120）*1=70方案1优于方案3。方案2优于方案1、优于方案3、优于方案411例4-4：继续上例12目标：（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；对于（1），三个方案都没有完成。但方案3离目标最远，方案3最差。方案5与（2）的差

6、距：工时损失=（108-100）*5+（130-120）*1=50方案6与（2）的差距：工时损失=0*5+（160-120）*1=40方案6优于方案5方案6优于方案5、优于方案7134-2 多目标规划问题的数学模型多目标的处理 为了将不同级别的目标的重要性用数量表示，引进P1，P2，.,用它表示一级目标，二级目标，.，的重要程度，规定P1P2 P3 .。称P1，P2，.,为级别系数。约束方程的处理决策变量x超过目标值b的部分记d+ ；决策变量x不足目标值b的部分记d- 。 d+ 、 d-称为差异变量。d+ 0, d- 0 。且 x- d+ + d-= b14多目标的综合若决策目标中规定为 时,

7、 应使 minZ=f( d+ ) 。若决策目标中规定为 时,应使 minZ=f( d- ) 。若决策目标中规定为 =时,应使 minZ=f(d+ + d- )。15例4-5（例4-4)解：引进级别系数P1：（1）利润达到280百元；P2：（2）钢材不超过100吨，工时不超过120小时；（权数之比5：1）16数学模型：目标函数：Min Z=P1d1-+P2(5d2+d3+)约束方程： 6X1+4X2+ d1- d1+=280 2X1+3X2+ d2- d2+=100 4X1+2X2+ d3- d3+=120 X1,X2,di-, di+ 0(i=1,2,3)17例4-6（例4-2) 某车间有A、

8、B两条设备相同的生产线，它们生产同一种产品。A生产线每小时可制造2件产品，B生产线每小时可制造1.5件产品。如果每周正常工作时数为45小时，要求制定完成下列目标的生产计划： （1）生产量达到210件/周；（2） A生产线加班时间限制在15小时内；（3）充分利用工时指标，并依A、B产量的比例确定重要性。18解：设A，B生产线每周工作时间为X1，X2。A，B的产量比例2：1.5 = 4:3目标函数：Min Z=P1d1-+P2d2+ P3（ 4 d3-+3 d4- ）约束方程： 2X1+1.5X2+ d1- d1+=210 （生产量达到210件/周） X1 + d2- d2+=60（A生产线加班时

9、间限制在15小时内） X1 + d3- d3+=45 （充分利用A的工时指标） X2 + d4- d4+=45 （充分利用B的工时指标） X1,X2,di-, di+ 0(i=1,2,3,4) 19例4-3：某电器公司经营的唱机和录音机均有车间A、B流水作业组装。数据见下表。要求按以下目标制订月生产计划：（1）库存费用不超过4600元；（2）每月销售唱机不少于80台；（3）不使A、B车间停工（权数由生产费用确定）；（4）A车间加班时间限制在20小时内；（5）每月销售录音机为100台；（6）两车间加班时数总和要尽可能小（权数由生产费用确定）；20解：设每月生产唱机、录音机X1，X2台。且A、B的

10、生产费用之比为100：50=2：1目标函数：Min S=P1d1+P2d2-+P3（ 2 d4-+ d5- ） +P4d41+ P5 （ d3+ + d3- ） +P6 （ 2d4+ d5+ ）约束方程： 50X1+30X2+ d1- - d1+=4600 （库存费用不超过4600元）X1 + d2- -d2+ =80 （每月销售唱机不少于80台）21 2X1 + X2+ d4- - d4+=180 （不使A车间停工） X1 + 3X2+ d5- - d5+=200 （不使B车间停工） d4+ d41- - d41+=20 （A车间加班时间限制在20小时内） X2 + d3- - d3+=10

11、0 （每月销售录音机为100台） X1,X2,di-, di+ ,d41-,d41+ 0(i=1,2,3,4,5)22目标函数：Min S=P1d1+P2d2-+P3（ 2 d4-+ d5- ） +P4d41+ P5 （ d3+ + d3- ） +P6 （ 2d4+ d5+ ）约束方程： 50X1+30X2+ d1- d1+=4600 X1 + d2- d2+=80 X2 + d3- d3+=100 2X1 + X2+ d4- d4+=180 X1 + 3X2+ d5- d5+=200 d4+ d41- d41+=20 X1,X2,di-, di+ ,d41-,d41+ 0(i=1,2,3,4

12、,5)234-3 多目标规划问题的图解法例4-8 Min Z = d1+ X1+2X2+ d1- d1+ = 10 X1+2X2 6 X1+X2 4 X1,X2,d1-, d1+ 0法24x1x204681021342X1+2X2 625x1x204681021342X1+X2 426x1x20468102134227x1x20468102134228x1x204681021342x1+2x2=105d1+d1-AB(2,2)29x1x204681021342x1+2x2=105d1+d1-AB(2,2)当 Min Z = d1+ 达到时 d1+ = 030 x1x204681021342x1

13、+2x2+d1- = 10 d1- = 25d1-AB(2,2)当 Min Z = d1+ 达到时 d1+ = 031x1x204681021342x1+2x2+d1- = 10 d1- = 45d1-AB(2,2)有无穷多解：点（0，3）和点（2，2）连线上的点都是最优解。(0,3)32x1x204681021342x1+2x2+d1- = 10 d1- = 65d1-AB(2,2)有无穷多解：点（4，0）和点（0，2）连线上的点都是最优解。(0,3)(4,0)(0,2)33x1x204681021342x1+2x2+d1- = 10 d1- = 75d1-AB(2,2)有无穷多解：点（0，

14、3/2） （3，0）连线上的点都是最优解。(0,3)(4,0)(1,1)34例4-9 Min Z=P1d1-+P2d2+ P3（ 5 d3-+ d1+ ） X1+X2+ d1- d1+=40 X1+X2 + d2- d2+=50 X1 + d3- =30 X2 + d4- =30X1,X2,dI-, dI+ 0(I=1,2,3,4)35x1x2020304050101030402050d1-d1+X1+X2=4036x1x2020304050101030402050d1-d1+d2+d2-X1+X2=5037x1x2020304050101030402050d1-d1+d2+d2-d3-X1=

15、3038x1x2020304050101030402050d1-d1+d2+d2-d3-d4-X2=3039x1x2020304050101030402050d1+d2+d2-d3-d4-Min d1- = 0可行域如图40 x1x2020304050101030402050d1+d2-d3-d4-Min d2+ =0可行域如图41x1x2020304050101030402050d1+d2-d4-Min d3- = 0 线段AB是可行域AB42x1x2020304050101030402050d2-d4-Min d1+ = 0P=(30,10)唯一最优解。 d2- =10 d4- = 20P

16、43例4-10 Min Z=P1d1-+P2d2+ P3（d3-+ d4- ） 5X1+10X2+ d1- d1+=100 2X1 + X2 + d2- d2+=14 X1 + d3- d3+=6 X2+ d4- d4+=10 X1,X2,di-, di+ 0(i=1,2,3,4)44x1x20101520255515201025d1+d1-5X1+10X2=10045x1x20101520255515201025d1+d1-d2+d2-2X1 +X2 =1446x1x20101520255515201025d1+d1-d2+d2-d3+d3-X1 =647x1x201015202555152

17、01025d1+d1-d2+d2-d3+d3-d4+d4-X2=1048x1x20101520255515201025d1+d2+d2-d3+d3-d4+d4-Min d1- = 049x1x20101520255515201025d1+d2-d3+d3-d4+d4-Min d2+ = 0可行域如图50 x1x20101520255515201025d1+d2-d3+d4+d4-Min d3- =0可行域为空如图51x1x20101520255515201025d1+d2-d3+d4+Min d3- 0Min d4- = 0可行域如图d3-(2,10)52x1x20101520255515201025d1+d2-d3+d4+Min d3- = 0Min d4- 0可行域为空如图d4-53对于目标P1与目标P2很容易达到。目标P3的两个指标不能同时满足，否则无解。又因为P3中的两个目标同样重要，要讨论 （1）Min d3-=0 Min d4- 0 原问题无解。（2） Min d3- 0 Min d4-=0原问题(2,10)是次优解。54例4-11 Min Z=P1 （ d1-+d2- ） X1 +d1- d1+=15 4X1 + 5X2 + d2- d2+=200 3X1 +4X2 120 X1 -2X2 15 X1,X2,di-, di+ 0(i=1,2)55x1x2020