第四章多目标规划(运筹学-上海电力学院,施泉生.ppt

《第四章多目标规划(运筹学-上海电力学院,施泉生.ppt》由会员分享，可在线阅读，更多相关《第四章多目标规划(运筹学-上海电力学院,施泉生.ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 多目标规划多目标规划 同时考虑多个决策目标同时考虑多个决策目标时，称为多目标规划问题。时，称为多目标规划问题。2021/9/2114-0 4-0 引言引言从线性规划问题可看出：从线性规划问题可看出：线性规划只研究在满足一定条件下，单线性规划只研究在满足一定条件下，单一目标函数取得最优解，而在企业管理一目标函数取得最优解，而在企业管理中，经常遇到多目标决策问题，如拟订中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。考虑利润，产品质量和设备利用率等。这些指标之间的重要程度（即优先顺序）这些指标之间

2、的重要程度（即优先顺序）也不相同，有些目标之间往往相互发生也不相同，有些目标之间往往相互发生矛盾。矛盾。2021/9/212线性规划致力于某个目标函数的线性规划致力于某个目标函数的最优解，这个最优解若是超过了实最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。了约束条件中的某些资源作为代价。线性规划把各个约束条件的重要线性规划把各个约束条件的重要性都不分主次地等同看待，这也不性都不分主次地等同看待，这也不符合实际情况。符合实际情况。2021/9/213求解线性规划问题，首先要求求解线性规划问题，首先要求约束条件必须相容，如

3、果约束约束条件必须相容，如果约束条件中，由于人力，设备等资条件中，由于人力，设备等资源条件的限制，使约束条件之源条件的限制，使约束条件之间出现了矛盾，就得不到问题间出现了矛盾，就得不到问题的可行解，但生产还得继续进的可行解，但生产还得继续进行，这将给人们进一步应用线行，这将给人们进一步应用线性规划方法带来困难。性规划方法带来困难。2021/9/214为了弥补线性规划问题的局限为了弥补线性规划问题的局限性，解决有限资源和计划指标性，解决有限资源和计划指标之间的矛盾，在线性规划基础之间的矛盾，在线性规划基础上，建立目标规划方法，从而上，建立目标规划方法，从而使一些线性规划无法解决的问使一些线性规划

4、无法解决的问题得到满意的解答。题得到满意的解答。2021/9/2154-1 4-1 多目标规划问题多目标规划问题多目标规划问题的提出多目标规划问题的提出 在实际问题中，可能会同时考虑几个方在实际问题中，可能会同时考虑几个方面都达到最优：产量最高，成本最低，质面都达到最优：产量最高，成本最低，质量最好，利润最大，环境达标，运输满足量最好，利润最大，环境达标，运输满足等。多目标规划能更好地兼顾统筹处理多等。多目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。种目标的关系，求得更切合实际要求的解。目标规划可根据实际情况，分主次地、目标规划可根据实际情况，分主次地、轻重缓急地考虑问题

5、。轻重缓急地考虑问题。2021/9/216例例4-1：一个企业需要同一种原一个企业需要同一种原材料生产甲乙两种产品，它们材料生产甲乙两种产品，它们的单位产品所需要的原材料的的单位产品所需要的原材料的数量及所耗费的加工时间各不数量及所耗费的加工时间各不相同，从而获得的利润也不相相同，从而获得的利润也不相同（如下表）。那么，该企业同（如下表）。那么，该企业应如何安排生产计划，才能使应如何安排生产计划，才能使获得的利润达到最大？获得的利润达到最大？2021/9/217如何安排生产，使利润达到最大。如何安排生产，使利润达到最大。用单纯形法求得最优解用单纯形法求得最优解=（20，20）最优值最优值=20

6、0（百元）（百元）2021/9/218问题：问题：该厂提出如下目标该厂提出如下目标（1）利润达到）利润达到280百元；百元；（2）钢材不超过）钢材不超过100吨，工时不吨，工时不超过超过120小时；小时；如何安排生产？如何安排生产？2021/9/219例例4-2：某车间有某车间有A、B两条设备两条设备相同的生产线，它们生产同一种相同的生产线，它们生产同一种产品。产品。A生产线每小时可制造生产线每小时可制造2件产品，件产品，B生产线每小时可制造生产线每小时可制造1.5件产品。如果每周正常工作件产品。如果每周正常工作时数为时数为45小时，要求制定完成下小时，要求制定完成下列目标的生产计划：列目标的

7、生产计划：2021/9/2110（1）生产量达到）生产量达到210件件/周；周；（2）A生产线加班时间限制在生产线加班时间限制在15小时内；小时内；（3）充分利用工时指标，并依）充分利用工时指标，并依A、B产量的比例确定重要性。产量的比例确定重要性。2021/9/2111例例4-3：某电器公司经营的唱机和某电器公司经营的唱机和录音机均有车间录音机均有车间A、B流水作业组流水作业组装。数据见下表。装。数据见下表。要求按以下目标制订月生产计划：要求按以下目标制订月生产计划：（1）库存费用不超过）库存费用不超过4600元；元；（2）每月销售唱机不少于）每月销售唱机不少于80台；台；2021/9/21

8、12（3）不使）不使A、B车间停工（权数由车间停工（权数由生产费用确定）；生产费用确定）；（4）A车间加班时间限制在车间加班时间限制在20小时小时内；内；（5）每月销售录音机为）每月销售录音机为100台；台；（6）两车间加班时数总和要尽可能）两车间加班时数总和要尽可能小（权数由生产费用确定）；小（权数由生产费用确定）；2021/9/21132021/9/2114多目标优先级多目标优先级 先将目标等级化：将目先将目标等级化：将目标按重要性的程度不同依次标按重要性的程度不同依次分成一级目标、二级目标分成一级目标、二级目标.。最次要的目标放在次。最次要的目标放在次要的等级中要的等级中。2021/9/

9、2115目标优先级作如下约定：目标优先级作如下约定：对同一个目标而言，若有几个决对同一个目标而言，若有几个决策方案都能使其达到，可认为这策方案都能使其达到，可认为这些方案就这个目标而言都是最优些方案就这个目标而言都是最优方案；若达不到，则与目标差距方案；若达不到，则与目标差距越小的越好。越小的越好。2021/9/2116目标优先级作如下约定目标优先级作如下约定：不同级别的目标的重要性是不可不同级别的目标的重要性是不可比的。即较高级别的目标没有达到比的。即较高级别的目标没有达到的损失，任何较低级别的目标上的的损失，任何较低级别的目标上的收获都不可弥补。所以在判断最优收获都不可弥补。所以在判断最优

10、方案时，首先从较高级别的目标达方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目到的程度来决策，然后再其次级目标的判断。标的判断。2021/9/2117目标优先级作如下约定：目标优先级作如下约定：同一级别的目标可以是多个。同一级别的目标可以是多个。各自之间的重要程度可用数量各自之间的重要程度可用数量（权数）来描述。因此，同一（权数）来描述。因此，同一级别的目标的其中一个的损失，级别的目标的其中一个的损失，可有其余目标的适当收获来弥可有其余目标的适当收获来弥补。补。2021/9/2118多目标规划解的概念：多目标规划解的概念：若多目标规划问题的解能使所若多目标规划问题的解能使所有的目标

11、都达到，就称该解为有的目标都达到，就称该解为多目标规划的最优解多目标规划的最优解；2021/9/2119多目标规划解的概念：多目标规划解的概念：若多目标规划问题的解能使所若多目标规划问题的解能使所有的目标都达到，就称该解为有的目标都达到，就称该解为多目标规划的最优解；多目标规划的最优解；若解只能满足部分目标，就称若解只能满足部分目标，就称该解为多目标规划的次优解；该解为多目标规划的次优解；2021/9/2120多目标规划解的概念：多目标规划解的概念：若多目标规划问题的解能使所若多目标规划问题的解能使所有的目标都达到，就称该解为有的目标都达到，就称该解为多目标规划的最优解；多目标规划的最优解；若

12、解只能满足部分目标，就称若解只能满足部分目标，就称该解为多目标规划的次优解；该解为多目标规划的次优解；若找不到满足任何一个目标的若找不到满足任何一个目标的解，就称该问题为无解。解，就称该问题为无解。2021/9/2121例例4-4：（例：（例4-1）一个企业需要一个企业需要同一种原材料生产甲乙两种产品，同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料它们的单位产品所需要的原材料的数量及所耗费的加工时间各不的数量及所耗费的加工时间各不相同，从而获得的利润也不相同相同，从而获得的利润也不相同（如下表）。那么，该企业应如（如下表）。那么，该企业应如何安排生产计划，才能使获得的何安排生产计划

13、，才能使获得的利润达到最大？利润达到最大？2021/9/2122如何安排生产，使利润达到最大。如何安排生产，使利润达到最大。前面已经求得最优解前面已经求得最优解=（20，20）最优值最优值=200（百元）（百元）2021/9/2123问题：问题：该厂提出如下目标该厂提出如下目标（1）利润达到）利润达到280百元；百元；（2）钢材不超过）钢材不超过100吨，工时不吨，工时不超过超过120小时；小时；如何安排生产？如何安排生产？2021/9/2124对例对例4-1的问题，设超过一吨钢材与超过的问题，设超过一吨钢材与超过5个工时的损失相同。现有四个方案进行比个工时的损失相同。现有四个方案进行比较优劣

14、？较优劣？2021/9/2125目标：（目标：（1）利润达到）利润达到280百元；百元；（2）钢材不超过）钢材不超过100吨，工时不超吨，工时不超过过120小时；小时；对于（对于（1），只有方案），只有方案4没有完成。没有完成。排除方案排除方案4。对于（对于（2），只有方案），只有方案2达到了，因达到了，因此方案此方案2是最优。是最优。2021/9/2126目标：（目标：（1）利润达到）利润达到280百元；百元；（2）钢材不超过）钢材不超过100吨，工时不超过吨，工时不超过120小时；小时；方案方案1与方案与方案3都达到了（都达到了（1），又没），又没达到（达到（2）方案方案1与（与（2）的差

15、距：）的差距：工时损失工时损失=（110-100）*5+（130-120）*1=602021/9/2127方案方案3与（与（2）的差距：）的差距：工时损失工时损失=0*5+（190-120）*1=70方案方案1优于方案优于方案3。方案方案2优于方案优于方案1优于方案优于方案3优于方优于方案案42021/9/2128例例4-4：继续上例：继续上例2021/9/2129目标：（目标：（1）利润达到）利润达到280百元；百元；（2）钢材不超过）钢材不超过100吨，工时不超吨，工时不超过过120小时；小时；对于（对于（1），三个方案都没有完成。），三个方案都没有完成。但方案但方案3离目标最远，方案离目

16、标最远，方案3最差。最差。方案方案1与（与（2）的差距：）的差距：工时损失工时损失=（108-100）*5+（130-120）*1=502021/9/2130方案方案2与（与（2）的差距：）的差距：工时损失工时损失=0*5+（160-120）*1=40方案方案2优于方案优于方案1方案方案2优于方案优于方案1优于方案优于方案32021/9/21314-2 4-2 多目标规划问题的数学模型多目标规划问题的数学模型多目标的处理多目标的处理 为了将不同级别的目标的重要为了将不同级别的目标的重要性用数量表示，引进性用数量表示，引进P P1 1，P P2 2，.,.,用用它表示一级目标，二级目标，它表示一

17、级目标，二级目标，.，的重要程度，规定的重要程度，规定P P1 1P P2 2 P P3 3.。称。称P P1 1，P P2 2，.,.,为级别系数。为级别系数。2021/9/2132约束方程的处理约束方程的处理差异变量：差异变量：决策变量决策变量x超过目标值超过目标值b的部分记的部分记d+决策变量决策变量x不足目标值不足目标值b的部分记的部分记d-d+0,d-0 且且 x-d+d-=b2021/9/2133多目标的综合多目标的综合若决策目标中规定若决策目标中规定 x b,当当 d+=0 时目标才算达到。时目标才算达到。2021/9/2134多目标的综合多目标的综合若决策目标中规定若决策目标中

18、规定 x b,当当 y+=0 时目标才算达到。时目标才算达到。若决策目标中规定若决策目标中规定 x b,当当 d-=0 时目标才算达到。时目标才算达到。2021/9/2135多目标的综合多目标的综合若决策目标中规定若决策目标中规定 x b,当当 y+=0 时目标才算达到。时目标才算达到。若决策目标中规定若决策目标中规定 x b,当当 y-=0 时目标才算达到。时目标才算达到。若决策目标中规定若决策目标中规定 x=b,当当 d+=d-=0 时目标才算达到。时目标才算达到。2021/9/2136例例4-5（例（例4-4)解：引进级别系数解：引进级别系数P1：（：（1）利润达到）利润达到280百元；

19、百元；P2：（：（2）钢材不超过）钢材不超过100吨，吨，工时不超过工时不超过120小时；（权数之小时；（权数之比比5：1）2021/9/2137数学模型：数学模型：目标函数：目标函数：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)2021/9/2138例例4-6（例（例4-2)某车间有某车间有A、B两条两条设备相同的生产线，它们生产同一设备相同的生产线，它们生产同一种产品。种产品。A生产线每小时可制造生产线每小时可

20、制造2件件产品，产品，B生产线每小时可制造生产线每小时可制造1.5件件产品。如果每周正常工作时数为产品。如果每周正常工作时数为45小时，要求制定完成下列目标的生小时，要求制定完成下列目标的生产计划：产计划：2021/9/2139（1）生产量达到）生产量达到210件件/周；周；（2）A生产线加班时间限制在生产线加班时间限制在15小时内；小时内；（3）充分利用工时指标，并依）充分利用工时指标，并依A、B产量的比例确定重要性。产量的比例确定重要性。2021/9/2140解：解：设设A，B生产线每周工作时间为生产线每周工作时间为X1，X2。A，B的产量比例的产量比例2：1.5=4:3目标函数：目标函数

21、：Min S=P1d1-+P2d2+4 P3d3-+3 P3d4-约束方程：约束方程：2X1+1.5X2+d1-d1+=210 （生产量达到（生产量达到210件件/周）周）X1 +d2-d2+=60（A生产线加班时间限制在生产线加班时间限制在15小时内）小时内）2021/9/2141 X1 +d3-d3+=45 （充分利用（充分利用A的工时指标）的工时指标）X2+d4-d4+=45 （充分利用（充分利用B的工时指标）的工时指标）X1,X2,di-,di+0(i=1,2,3,4)2021/9/2142A，B的产量比例的产量比例2：1.5=4:3目标函数：目标函数：Min S=P1d1-+P2d2

22、+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)2021/9/2143例例4-7(例例4-3)：(1)库存费用不超过库存费用不超过4600元；元；(2)每月销售唱机不少于每月销售唱机不少于80台；台；(3)不使不使A、B车间停工（权数由生车间停工（权数由生产费用确定）；产费用确定）；(4)A车间加班时间限制在车间加班时间限制在20小时内；小时内；2021/9/2144（5）每月销售录音机为）每月销售录音机为100台；台

23、；（6）两车间加班时数总和要尽可能）两车间加班时数总和要尽可能小（权数由生产费用确定）；小（权数由生产费用确定）；解：解：设每月生产唱机、录音机设每月生产唱机、录音机X1，X2台。且台。且A、B的生产费用之比为的生产费用之比为100：50=2：12021/9/2145目标函数：目标函数：Min S=P1d1+P2d2-+2 P3d4-+P3d5-+P4d41+P5d3-+P5d3+2P6d4+P6d5+约束方程：约束方程：50X1+30X2+d1-d1+=4600 （库存费用不超过（库存费用不超过4600元）元）X1 +d2-d2+=80 （每月销售唱机不少于（每月销售唱机不少于80台）台）2

24、021/9/2146 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)2021/9/2147目标函数：目标函数：Min S=P1d1+P2d2-+2 P3d4-+P3d5-+P4d41+P5d3-+P5d3+2P6d4+P6d5+约束方程：约束方程：50X1+30X

25、2+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,5)2021/9/21484-3 4-3 多目标规划问题的求解多目标规划问题的求解多目标规划问题的图解法多目标规划问题的图解法例例4-8 Min S=d1+X1+2X2+d1-d1+=10 X1+2X2 6 X1+X2 4 X1,X2,d1-,d1+02021/9/2149x1x204681021342X X1 1+2X+2X2 2 6 62

26、021/9/2150 x1x204681021342X X1 1+X+X2 2 4 42021/9/2151x1x2046810213422021/9/2152x1x2046810213422021/9/2153x1x204681021342x x1 1+2x+2x2 2=10=105d1 1+d1 1-AB(2,2)2021/9/2154x1x204681021342x x1 1+2x+2x2 2=10=105d1 1+d1 1-AB(2,2)当当 Min S=d1+达到时达到时 d1+=02021/9/2155x1x204681021342x x1 1+2x+2x2 2=10=105d1

27、1-AB(2,2)当当 Min S=d1+达到时达到时 d1+=02021/9/2156x1x204681021342x x1 1+2x+2x2 2+d+d1 1-=10 d=10 d1 1-=2=25d1 1-AB(2,2)当当 Min S=d1+达到时达到时 d1+=02021/9/2157x1x204681021342x x1 1+2x+2x2 2+d+d1 1-=10 d=10 d1 1-=4=45d1 1-AB(2,2)有无穷多解：点（有无穷多解：点（0，3）和点（）和点（2，2）连线上）连线上的点都是最优解。的点都是最优解。(0,3)2021/9/2158x1x2046810213

28、42x x1 1+2x+2x2 2+d+d1 1-=10 d=10 d1 1-=6=65d1 1-AB(2,2)有无穷多解：点（有无穷多解：点（4，0）和点（）和点（0，2）连线上）连线上的点都是最优解。的点都是最优解。(0,3)(4,0)(0,2)2021/9/2159x1x204681021342x x1 1+2x+2x2 2+d+d1 1-=10 d=10 d1 1-=7=75d1 1-AB(2,2)有无穷多解：点（有无穷多解：点（1，1）和点（）和点（0，3/2）（3，0）连线上的点都是最）连线上的点都是最优解。优解。(0,3)(4,0)(1,1)2021/9/2160例例4-9 Mi

29、n S=P1d1-+P2d2+5 P3d3-+P3d1+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)2021/9/2161x1x2020304050101030402050d1 1-d1 1+X X1 1+X+X2 2=40=402021/9/2162x1x2020304050101030402050d1 1-d1 1+d2 2+d2 2-X X1 1+X+X2 2=50=502021/9/2163x1x2020304050101030402050d1 1-d1 1+d2 2+d2

30、2-d3 3-X X1 1=30=302021/9/2164x1x2020304050101030402050d1 1-d1 1+d2 2+d2 2-d3 3-d4 4-X X2 2=30=302021/9/2165x1x2020304050101030402050d1 1+d2 2+d2 2-d3 3-d4 4-Min d1-=0可行域如图可行域如图2021/9/2166x1x2020304050101030402050d1 1+d2 2-d3 3-d4 4-Min d2+=0可行域如图可行域如图2021/9/2167x1x2020304050101030402050d1 1+d2 2-d4

31、 4-Min d3-=0 线段线段AB是可行域是可行域AB2021/9/2168x1x2020304050101030402050d2 2-d4 4-Min d1+=0P=(30,10)唯一唯一最优解。最优解。d d2 2-=10=10 d d4 4-=2020P2021/9/2169例例4-10 Min S=P1d1-+P2d2+P3d3-+P3d4-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)2021/9/2170 x1x2010152025551520102

32、5d1 1+d1 1-5X5X1 1+10X+10X2 2=100=1002021/9/2171x1x20101520255515201025d1 1+d1 1-d2 2+d2 2-2X2X1 1+X+X2 2=14=142021/9/2172x1x20101520255515201025d1 1+d1 1-d2 2+d2 2-d3 3+d3 3-X X1 1 =6=62021/9/2173x1x20101520255515201025d1 1+d1 1-d2 2+d2 2-d3 3+d3 3-d4 4+d4 4-X X2 2=10=102021/9/2174x1x20101520255515

33、201025d1 1+d2 2+d2 2-d3 3+d3 3-d4 4+d4 4-Min d1-=02021/9/2175x1x20101520255515201025d1 1+d2 2-d3 3+d3 3-d4 4+d4 4-Min d2+=0可行域如图可行域如图2021/9/2176x1x20101520255515201025d1 1+d2 2-d3 3+d4 4+d4 4-Min d3-=0可行域为空如图可行域为空如图2021/9/2177x1x20101520255515201025d1 1+d2 2-d3 3+d4 4+Min d3-0Min d4-=0可行域如图可行域如图d3 3

34、-(2,10)2021/9/2178x1x20101520255515201025d1 1+d2 2-d3 3+d4 4+Min d3-=0Min d4-0可行域为空如图可行域为空如图d4 4-2021/9/2179对于目标对于目标P1与目标与目标P2很容易达到。目很容易达到。目标标P3的两个指标不能同时满足，否则的两个指标不能同时满足，否则无解。又因为无解。又因为P3中的两个目标同样重中的两个目标同样重要，要讨论要，要讨论 （1）Min d3-=0 Min d4-0 原问题无解。原问题无解。（2）Min d3-0 Min d4-=0原问题原问题(2,10)是次优解。是次优解。2021/9/2

35、180例例4-11 Min S=P1d1-+P1d2-X1 +d1-d1+=15 4X1+5X2+d2-d2+=200 3X1+4X2 120 X1-2X2 15 X1,X2,di-,di+0(i=1,2)2021/9/2181x1x2020304050101030402050d1 1+d1 1-X X1 1=15=152021/9/2182x1x2020304050101030402050d1 1+d1 1-d2 2+d2 2-4X4X1 1+5X+5X2 2=200=2002021/9/2183x1x2020304050101030402050d1 1+d1 1-d2 2+d2 2-3X3X1 1+4X+4X2 2 120 1202021/9/2184x1x2020304050101030402050d1 1+d1 1-d2 2+d2 2-X X1 1-2X-2X2 2 15152021/9/2185x1x2020304050101030402050d1 1+d1 1-d2 2+d2 2-2021/9/2186x1x2020304050101030402050d1 1+d2 2+同时考虑同时考虑 d1-=0,d2-=0 原问题无解。原问题无解。2021/9/2187习题四习题四P1124.14.2(1)(2)2021/9/2188