第4章-多目标规划PPT课件.ppt

《第4章-多目标规划PPT课件.ppt》由会员分享，可在线阅读，更多相关《第4章-多目标规划PPT课件.ppt（112页珍藏版）》请在三一文库上搜索。

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

2、须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。,5,为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。,6,4-1 多目标规划问题 多目标规划问题的提出 在实际问题中，可能会同时考虑几个方面都达到最优：产量最高，成本最低，质量最好，利润最大，环境达标，运输满足等。多目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。 目标规划可根据实际情况，分主次地、轻重缓急地考

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

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

5、：将目标按重要性的程度不同依次分成一级目标、二级目标.。最次要的目标放在次要的等级中。,16,目标优先级作如下约定： 对同一个目标而言，若有几个决策方案都能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标差距越小的越好。,17,目标优先级作如下约定： 不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别的目标上的收获都不可弥补。所以在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。,18,目标优先级作如下约定： 同一级别的目标可以是多个。各自之间的重要程度可用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，

6、可有其余目标的适当收获来弥补。,19,多目标规划解的概念： 若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解； 若解只能满足部分目标，就称该解为多目标规划的次优解； 若找不到满足任何一个目标的解，就称该问题为无解。,20,例4-4：（例4-1）一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？,21,如何安排生产，使利润达到最大。 前面已经求得最优解=（20，20） 最优值=200（百元）,22,问题：该厂提出如下目标 （1）利

7、润达到280百元； （2）钢材不超过100吨，工时不超过120小时； 如何安排生产？,23,对例4-1的问题，设超过一吨钢材与超过5个工时的损失相同。现有四个方案进行比较优劣？,24,目标：（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时； 对于（1），只有方案4没有完成。排除方案4。 对于（2），只有方案2达到了，因此方案2是最优。,25,目标：（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时； 方案1与方案3都达到了（1），又没达到（2） 方案1与（2）的差距： 工时损失 =（110-100）*5+（130-120）*1=60,26,方案3与

8、（2）的差距： 工时损失=0*5+（190-120）*1=70 方案1优于方案3。 方案2优于方案1优于方案3优于方案4,27,例4-4：继续上例,28,目标：（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时； 对于（1），三个方案都没有完成。但方案3离目标最远，方案3最差。 方案1与（2）的差距： 工时损失= （108-100）*5+（130-120）*1=50,29,方案2与（2）的差距： 工时损失 =0*5+（160-120）*1=40 方案2优于方案1 方案2优于方案1优于方案3,30,4-2 多目标规划问题的数学模型 多目标的处理 为了将不同级别的目标的重要性

9、用数量表示，引进P1，P2，.,用它表示一级目标，二级目标，.，的重要程度，规定P1P2 P3 .。称P1，P2，.,为级别系数。,31,约束方程的处理 差异变量： 决策变量x超过目标值b的部分记d+ 决策变量x不足目标值b的部分记d- d+ 0, d- 0 且 x- d+ + d-= b,32,多目标的综合 若决策目标中规定 x b, 当 d+ = 0 时目标才算达到。,33,多目标的综合 若决策目标中规定 x b, 当 y+=0 时目标才算达到。 若决策目标中规定 x b, 当 d- = 0 时目标才算达到。,34,多目标的综合 若决策目标中规定 x b, 当 y+=0 时目标才算达到。

10、若决策目标中规定 x b, 当 y-=0 时目标才算达到。 若决策目标中规定 x = b, 当 d+ = d- = 0 时目标才算达到。,35,例4-5（例4-4) 解：引进级别系数 P1：（1）利润达到280百元； P2：（2）钢材不超过100吨，工时不超过120小时；（权数之比5：1）,36,数学模型： 目标函数：Min S=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),37,例4-6（例4-2) 某车间有A、B

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

12、生产线加班时间限制在15小时内）,40,X1 + d3- d3+=45 （充分利用A的工时指标） X2+ d4- d4+=45 （充分利用B的工时指标） X1,X2,di-, di+ 0(i=1,2,3,4),41,A，B的产量比例2：1.5 = 4:3 目标函数： Min S=P1d1-+P2d2+4 P3d3-+3 P3d4- 约束方程： 2X1+1.5X2+ d1- d1+= 210 X1 + d2- d2+= 60 X1 + d3- d3+= 45 X2 + d4- d4+= 45 X1,X2,di-, di+ 0 (i=1,2,3,4),42,例4-7(例4-3)： (1)库存费用不

13、超过4600元； (2)每月销售唱机不少于80台； (3)不使A、B车间停工（权数由生产费用确定）； (4)A车间加班时间限制在20小时内；,43,（5）每月销售录音机为100台； （6）两车间加班时数总和要尽可能小（权数由生产费用确定）； 解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1,44,目标函数： Min S=P1d1+P2d2-+2 P3d4-+ P3d5- +P4d41+ P5d3-+ P5d3+2P6d4+ P6d5+ 约束方程： 50X1+30X2+ d1- d1+=4600 （库存费用不超过4600元） X1 + d2- d2+=80 （

14、每月销售唱机不少于80台）,45,X2 + d3- d3+=100 （每月销售录音机为100台） 2X1 + X2+ d4- d4+=180 （不使A车间停工） X1 + 3X2+ d5- d5+=200 （不使B车间停工） d4+ d41- d41+=20 （A车间加班时间限制在20小时内） X1,X2,di-, di+ ,d41-,d41+ 0(i=1,2,3,4,5),46,目标函数：Min S=P1d1+P2d2-+2 P3d4-+ P3d5- +P4d41+ P5d3-+ P5d3+2P6d4+ P6d5+ 约束方程： 50X1+30X2+ d1- d1+=4600 X1 + d2-

15、 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,5),47,4-3 多目标规划问题的求解 多目标规划问题的图解法 例4-8 Min S = d1+ X1+2X2+ d1- d1+ = 10 X1+2X2 6 X1+X2 4 X1,X2,d1-, d1+ 0,48,x1,x2,0,4,6,8,10,2,1,3,4,2,X1+2X2 6,49,x1,x2,0,4,6,8,10,2,1,3,4,2,X1

16、+X2 4,50,x1,x2,0,4,6,8,10,2,1,3,4,2,51,x1,x2,0,4,6,8,10,2,1,3,4,2,52,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2=10,5,d1+,d1-,A,B,(2,2),53,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,54,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2=10,5,d1-,A,B,(2,2),当 Min S = d1+ 达到时 d1+ = 0,55,x1,

17、x2,0,4,6,8,10,2,1,3,4,2,x1+2x2+d1- = 10 d1- = 2,5,d1-,A,B,(2,2),当 Min S = d1+ 达到时 d1+ = 0,56,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2+d1- = 10 d1- = 4,5,d1-,A,B,(2,2),有无穷多解：点（0，3）和点（2，2）连线上的点都是最优解。,(0,3),57,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2+d1- = 10 d1- = 6,5,d1-,A,B,(2,2),有无穷多解：点（4，0）和点（0，2）连线上的点都是最优解。,(0

18、,3),(4,0),(0,2),58,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2+d1- = 10 d1- = 7,5,d1-,A,B,(2,2),有无穷多解：点（1，1）和点（0，3/2） （3，0）连线上的点都是最优解。,(0,3),(4,0),(1,1),59,例4-9 Min S=P1d1-+P2d2+5 P3d3-+ P3d4- X1+X2+ d1- d1+=40 X1+X2 + d2- d2+=50 X1 + d3- =30 X2+ d4- =30 X1,X2,dI-, dI+ 0(I=1,2,3,4),60,x1,x2,0,20,30,40,50,10,1

19、0,30,40,20,50,d1-,d1+,X1+X2=40,61,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,d2+,d2-,X1+X2=50,62,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,d2+,d2-,d3-,X1=30,63,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,d2+,d2-,d3-,d4-,X2=30,64,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1+,d2+,d2-,d3-,d4-,Min

20、d1- = 0 可行域如图,65,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1+,d2-,d3-,d4-,Min d2+ =0 可行域如图,66,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1+,d2-,d4-,Min d3- = 0 线段AB是可行域,A,B,67,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d2-,d4-,Min d4- P=(30,20)唯一最优解。 d2- =10 d4- = 10,P,68,例4-10 Min S=P1d1-+P2d2+ P3d3-+ P3d4- 5X

21、1+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),69,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,5X1+10X2=100,70,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,d2+,d2-,2X1 +X2 =14,71,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,d2+,d2-,d3+,d3-,X1 =6,72,x

22、1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,X2=10,73,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2+,d2-,d3+,d3-,d4+,d4-,Min d1- = 0,74,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2-,d3+,d3-,d4+,d4-,Min d2+ = 0 可行域如图,75,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2-,d3+,d4+,d4-,Min d3-

23、=0 可行域为空如图,76,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2-,d3+,d4+,d4-,Min d3- 0,如何使P3 （d3-+ d4-）最小呢？ 对于2X1 + X2 =14来说，x1减少1个单位，x2却增加2个单位，于是P1为最优点。,P1(2,10),P2(26/3,8/3),77,多目标规划的单纯形算法 多目标规划问题与线性规划问题相似，可用单纯形算法求解。 注意：在比较检验数大小时，要先比较较高级别的系数，再比较较低级别的系数。,78,例4-11（例4-6） 目标函数：Min S=P1d1-+P2(5d2+d3+) 约束方程： 6

24、X1+4X2+ d1- d1+=280 2X1+3X2+ d2- d2+=100 4X1+2X2+ d3- d3+=120 X1,X2,di-, di+ 0(i=1,2,3),79,标准型 目标函数：Max S=-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),80,初始单纯形表,81,首先满足第一目标P1进基变量X1，出基变量y3- 主元（4）,82,主元运算：第三行除以4,83,主元运算：第一行加上第三行（-6）倍,

25、84,主元运算：第二行加上第三行（-2）倍,85,重新计算检验数,86,87,第二行除以2,88,第一行加上第二行（-1）,89,第三行加上第二行（-1/2）,90,计算检验数,91,计算检验数,92,第一行乘上4/5,93,第三行加上第一行（3/8）,94,计算检验数,95,最后变量 y1-的检验数为-P1+(4/5)P2由于假定P1P2，所以此检验数也小于零。,96,该问题的最优方案为生产A产品44个单位，B产品4个单位，利润为280百元。此时，原料正好用了100吨，工时比原计划超了64小时。,97,例4-11 设某工厂生产两种产品，都要经过两道工序，有关资料如下表。假如工序1，2都允许加

26、班，使得利润不少于1000元作为目标。又以：第1，2工序的加班工时之和尽可能在160之内为第一目标；产品乙必须严格控制在70公斤之内为第二目标；该厂的利润越高越好为第三目标；尽量减少工序1，2加班工时为第四目标.试问：在上述条件下，该厂应如何生产？,98,99,解：设X1，X2为甲，乙两种产品的生产公斤数， d1-， d1+分别为低于或超过利润1000元的偏差 d2-， d2+分别为第1道工序剩余和加班的工时数 d3-， d3+分别为第2道工序剩余和加班的工时数 d4-， d4+为加班工时之和低于或超过160工时数 由于产品X2必须严格控制在70公斤之内为第一目标，则可取d5-为实际公斤数不到

27、70的偏差，且 d5+=0。,100,目标函数： Min Z=P1d4+ P2d5- + P3d1-+ P4( d2+d3+) 约束方程： 6X1+4X2+ d1- d1+=1000 2X1+ X2+ d2- d2+=100 X1+X2+ d3- d3+=80 d2+ + d3+ + d4 -d4+=160 X2 + d5 =70 X1,X2,di-, di+ , d5 0(i=1,2,3,4),101,目标函数： Max s= -P1d4+-P2d5- - P3d1- P4( d2+d3+) 约束方程： 6X1+4X2+ d1- d1+=1000 2X1+ X2+ d2- d2+=100 X

28、1+X2+ d3- d3+=80 d2+ + d3+ + d4 d4+=160 X2 + d5 =70 X1,X2,di-, di+ , d5 0(i=1,2,3,4),102,103,104,105,106,107,到目前为止，已经不能再进行下去，（2）（1）否则会破坏已经满足的条件。 该题的解答：X1=200/3 ，X2=70， d1- =320， d2+=310/3， d3+=170/3 d4+= d4- = d5- =0 即该厂生产方案：生产产品甲200/3公斤，产品乙70公斤，第1道工序加班310/3工时，第2道工序加班170/3工时，才能获利 1000- d1- =1000-320

29、=680元。,108,投资规划实例 某经济区准备筹集资金，在下个计划期内投资建设新项目，有轻工业、重工业和新技术产业三种项目，这些项目能否如期建成有一定风险。在建成投产后，其收入与投资额有关，经过分析研究，各项目的建设方案不能如期投入的风险因子及投产后可以增加的经济收入的资金收益率百分数如下,109,110,根据该地区情况，决策部门提出如下要求：用于轻工业的投资额不超过总资金的35%；用于新技术产业的投资额至少占总资金的15%；用于重工业的投资额不超过总资金的50%；并且首先有考虑总风险因子不超过0.2;其次考虑总收益率至少要达到22%；然后再考虑各项投资的总和不能超过总资金额。现在要确定对不

30、同行业的各投资方案所占的比例。,111,解：设xi为第I方案投资占总资金的比例，若总资金数为100% 则轻工业的投资额不超过总资金的35%，可表示为： x1 +x2 +x3 + x4 0.35 用于新技术产业的投资额至少占总资金的15% ，可表示为： x5 +x6 + x7 0.15 用于重工业的投资额不超过总资金的50% x8 +x9 +x10 + x11 0. 5,112,第一项：优先因子为P1约束条件： ri xi + d1- - d1+ = 0.2 第二项：优先因子为P2约束条件： gi xi + d2- - d2+ = 0.22 第三项：优先因子为P3约束条件： xi + d3- - d3+ = 1 目标函数：min Z= P1 d1+ + P2 d2- + P3 d3+,