多目标规划优秀课件.ppt

《多目标规划优秀课件.ppt》由会员分享，可在线阅读，更多相关《多目标规划优秀课件.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、多目标规划第1页，本讲稿共83页1、线性规划的不足1、线性规划只研究在满足一定条件下，单、线性规划只研究在满足一定条件下，单一目标函数取得最优解。一目标函数取得最优解。但是在企业管理中，经常遇到多目标决策但是在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度（即优用率等。这些指标之间的重要程度（即优先顺序）也不相同，有些目标之间往往相先顺序）也不相同，有些目标之间往往相互发生矛盾。互发生矛盾。第2页，本讲稿共83页1、线性规划的不足2、线性

2、规划致力于解决某个目标函数的最、线性规划致力于解决某个目标函数的最优解。优解。3、线性规划把各个约束条件的重要性都不、线性规划把各个约束条件的重要性都不分主次地等同看待，不符合实际情况。分主次地等同看待，不符合实际情况。第3页，本讲稿共83页1、线性规划的不足4、求解线性规划问题，首先要求约束条件、求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解。出现了矛盾，就得不到问题的可行解。但是在生产实际中即使出现了这样的情但是在生产实际中即使

3、出现了这样的情况，生产还得继续进行。这就给人们进一况，生产还得继续进行。这就给人们进一步应用线性规划方法带来困难。使线性规步应用线性规划方法带来困难。使线性规划的应用受到限制。划的应用受到限制。第4页，本讲稿共83页2、目标规划的作用、目标规划的作用 在实际生产管理问题中，可能会同时考虑几个方面都在实际生产管理问题中，可能会同时考虑几个方面都在实际生产管理问题中，可能会同时考虑几个方面都在实际生产管理问题中，可能会同时考虑几个方面都要求达到最优，如：产量最高，成本最低，质量最好，要求达到最优，如：产量最高，成本最低，质量最好，要求达到最优，如：产量最高，成本最低，质量最好，要求达到最优，如：产

4、量最高，成本最低，质量最好，利润最大，环境达标，运输满足等。同时考虑多个决利润最大，环境达标，运输满足等。同时考虑多个决利润最大，环境达标，运输满足等。同时考虑多个决利润最大，环境达标，运输满足等。同时考虑多个决策目标时，称为多目标规划问题。策目标时，称为多目标规划问题。策目标时，称为多目标规划问题。策目标时，称为多目标规划问题。1 1、为了弥补线性规划问题的局限性，解决有限资源和计、为了弥补线性规划问题的局限性，解决有限资源和计、为了弥补线性规划问题的局限性，解决有限资源和计、为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，应用建立目标划指标之间的矛盾，在线

5、性规划基础上，应用建立目标划指标之间的矛盾，在线性规划基础上，应用建立目标划指标之间的矛盾，在线性规划基础上，应用建立目标规划方法，从而使一些线性规划无法解决的问题得到满规划方法，从而使一些线性规划无法解决的问题得到满规划方法，从而使一些线性规划无法解决的问题得到满规划方法，从而使一些线性规划无法解决的问题得到满意的解答。意的解答。意的解答。意的解答。第5页，本讲稿共83页2、目标规划的作用2、目标规划能更好地兼顾统筹处理多种目、目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。标的关系，求得更切合实际要求的解。3、目标规划可根据实际情况，分主次地、目标规划可根据实际情况，分

6、主次地、轻重缓急地考虑问题。轻重缓急地考虑问题。第6页，本讲稿共83页3、多目标规划问题的提出、多目标规划问题的提出 例例1：一个企业需要同一种原材料生产甲乙一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使么，该企业应如何安排生产计划，才能使获得的利润达到最大？获得的利润达到最大？第7页，本讲稿共83页解：设生产甲产品X1件，乙产品X2件，则应用线性规划，建立模

7、型如下：MAX Z=6X1+4X2 2X1+3X2100 4X1+2X2120 X1、X2 0第8页，本讲稿共83页初始单纯形表初始单纯形表C6400CBXBX1X2X3X4b0X32310100500X4420112030 6 40 0 0第9页，本讲稿共83页C6400CBXBX1X2X3X4b0X3021-1/2406X111/201/430010-3/2C6400CBXBX1X2X3X4b4X2011/2-1/4206X110-1/43/82000-1/2-5/4第10页，本讲稿共83页最终单纯形表为：最终单纯形表为：C6400CBXBX1X2X3X4b4X2011/2-1/4206X

8、110-1/43/82000-1/2-5/4原问题最优解为：原问题最优解为：原问题最优解为：原问题最优解为：X1X1=20=20，X2=20X2=20最优值最优值最优值最优值 Z=200Z=200（百元）（百元）（百元）（百元）对偶问题最优解为：Y1=1/2，Y2=5/4最优值最优值最优值最优值 Z=200Z=200（百元）（百元）（百元）（百元）第11页，本讲稿共83页问题提出问题提出该厂提出如下目标该厂提出如下目标（1）利润达到）利润达到280百元；百元；（2）钢材不超过）钢材不超过100吨，工时不超过吨，工时不超过120小时；小时；如何安排生产？如何安排生产？第12页，本讲稿共83页例例

9、2某车间有某车间有A、B两条设备相同的生产线，它两条设备相同的生产线，它们生产同一种产品。们生产同一种产品。A生产线每小时可制造生产线每小时可制造2件产品，件产品，B生产线每小时可制造生产线每小时可制造1.5件产品。件产品。如果每周正常工作时数为如果每周正常工作时数为45小时，要求制小时，要求制定完成下列目标的生产计划：定完成下列目标的生产计划：（1）生产量达到）生产量达到210件件/周；周；（2）A生产线加班时间限制在生产线加班时间限制在15小时内；小时内；（3）充分利用工时指标，并依）充分利用工时指标，并依A、B产量产量 的比例确定重要性。的比例确定重要性。第13页，本讲稿共83页例例3

10、某电器公司经营的唱机和录音机均有车间某电器公司经营的唱机和录音机均有车间某电器公司经营的唱机和录音机均有车间某电器公司经营的唱机和录音机均有车间A A、B B流水作业组装。数据见下表。流水作业组装。数据见下表。流水作业组装。数据见下表。流水作业组装。数据见下表。第14页，本讲稿共83页 公司计划要求按以下目标制订月生产计划：公司计划要求按以下目标制订月生产计划：（1 1）库存费用不超过）库存费用不超过46004600元；元；（2 2）每月销售唱机不少于）每月销售唱机不少于8080台；台；（3 3）不使）不使A A、B B车间停工（权数由生产费用确定）；车间停工（权数由生产费用确定）；（4 4）

11、A A车间加班时间限制在车间加班时间限制在2020小时内；小时内；（5 5）每月销售录音机为）每月销售录音机为100100台；台；（6 6）两车间加班时数总和要尽可能小（权数由生产）两车间加班时数总和要尽可能小（权数由生产 费用确定）；费用确定）；第15页，本讲稿共83页4、多目标规划优先级的概念、多目标规划优先级的概念1、目标等级化：将目标按重要性的程度不同、目标等级化：将目标按重要性的程度不同依次分成一级目标、二级目标依次分成一级目标、二级目标.。最次要。最次要的目标放在次要的等级中。的目标放在次要的等级中。2、对同一个目标而言，若有几个决策方案都、对同一个目标而言，若有几个决策方案都能使

12、其达到，可认为这些方案就这个目标能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标而言都是最优方案；若达不到，则与目标差距越小的越好。差距越小的越好。第16页，本讲稿共83页4、多目标规划优先级的概念、多目标规划优先级的概念3 3、不同级别的目标的重要性是不可比的。即较高级、不同级别的目标的重要性是不可比的。即较高级、不同级别的目标的重要性是不可比的。即较高级、不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别的目标上别的目标没有达到的损失，任何较低级别的目标上别的目标没有达到的损失，任何较低级别的目标上别的目标没有达到的损失，任何较低级别的目

13、标上的收获都不可弥补。的收获都不可弥补。的收获都不可弥补。的收获都不可弥补。4 4、在判断最优方案时，首先从较高级别的目标达到的、在判断最优方案时，首先从较高级别的目标达到的、在判断最优方案时，首先从较高级别的目标达到的、在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。程度来决策，然后再其次级目标的判断。程度来决策，然后再其次级目标的判断。程度来决策，然后再其次级目标的判断。5 5、同一级别的目标可以是多个。各自之间的重要程度可、同一级别的目标可以是多个。各自之间的重要程度可、同一级别的目标可以是多个。各自之间的重要程度可、同一级别的目标可以是多个。各自之间的重

14、要程度可用数量（权数）来描述。因此，同一级别的目标的其中用数量（权数）来描述。因此，同一级别的目标的其中用数量（权数）来描述。因此，同一级别的目标的其中用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，可用其余目标的适当收获来弥补。一个的损失，可用其余目标的适当收获来弥补。一个的损失，可用其余目标的适当收获来弥补。一个的损失，可用其余目标的适当收获来弥补。第17页，本讲稿共83页5、多目标规划解的概念、多目标规划解的概念1、若多目标规划问题的解能使所有的目标都、若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解；达到，就称该解为多目标规划的最优解；2、若解只能满足

15、部分目标，就称该解为多目、若解只能满足部分目标，就称该解为多目标规划的次优解；标规划的次优解；3、若找不到满足任何一个目标的解，就称该、若找不到满足任何一个目标的解，就称该问题为无解。问题为无解。第18页，本讲稿共83页5、多目标规划解的概念举例、多目标规划解的概念举例 一个企业需要同一种原材料生产甲乙两种一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得该企

16、业应如何安排生产计划，才能使获得的利润达到最大？的利润达到最大？第19页，本讲稿共83页解：设生产甲产品X1件，乙产品X2件，则应用线性规划，建立模型如下：MAX Z=6X1+4X2 2X1+3X2100 4X1+2X2 0用单纯形法求得最优解用单纯形法求得最优解用单纯形法求得最优解用单纯形法求得最优解=（2020，2020）；最优值）；最优值）；最优值）；最优值=200=200（百元）（百元）（百元）（百元）第20页，本讲稿共83页问题提出问题提出 该厂提出如下目标该厂提出如下目标该厂提出如下目标该厂提出如下目标（1 1）利润达到）利润达到）利润达到）利润达到280280百元；百元；百元；百

17、元；（2 2）钢材不超过）钢材不超过）钢材不超过）钢材不超过100100吨，工时不超过吨，工时不超过吨，工时不超过吨，工时不超过120120小时；小时；小时；小时；如何安排生产？如何安排生产？如何安排生产？如何安排生产？（注：超过一吨钢材与超过（注：超过一吨钢材与超过（注：超过一吨钢材与超过（注：超过一吨钢材与超过5 5个工时的损失相同）个工时的损失相同）个工时的损失相同）个工时的损失相同）第21页，本讲稿共83页解：为达到第一目标，现可以提出解：为达到第一目标，现可以提出解：为达到第一目标，现可以提出解：为达到第一目标，现可以提出4 4 4 4个方案如下：个方案如下：个方案如下：个方案如下：

18、方案号甲产品产量乙产品产量钢材（吨）工时（时）利润（百元)损失量150010020030080207021014028057034441001842806444539918628266第22页，本讲稿共83页通过对上述四个方案比较进行求解：通过对上述四个方案比较进行求解：通过对上述四个方案比较进行求解：通过对上述四个方案比较进行求解：目标：（目标：（目标：（目标：（1 1 1 1）利润达到）利润达到）利润达到）利润达到280280280280百元；百元；百元；百元；（2 2 2 2）钢材不超过）钢材不超过）钢材不超过）钢材不超过100100100100吨，工时不超过吨，工时不超过吨，工时不超过

19、吨，工时不超过120120120120小时；小时；小时；小时；讨论：上述方案都达到了目标（讨论：上述方案都达到了目标（讨论：上述方案都达到了目标（讨论：上述方案都达到了目标（1 1 1 1），），），），但是没有达到目标（但是没有达到目标（但是没有达到目标（但是没有达到目标（2 2）方案方案方案方案1 1与目标（与目标（与目标（与目标（2 2）的差距：）的差距：）的差距：）的差距：工时损失工时损失工时损失工时损失=（100-100100-100）*5+5+（200-120200-120）*1=801=80方案方案方案方案2 2与目标（与目标（与目标（与目标（2 2）的差距：）的差距：）的差距：

20、）的差距：工时损失工时损失工时损失工时损失=（210-100210-100）*5+5+（140-120140-120）*1=5701=570方案方案方案方案3 3与目标（与目标（与目标（与目标（2 2）的差距：）的差距：）的差距：）的差距：工时损失工时损失工时损失工时损失=（100-100100-100）*5+5+（184-120184-120）*1=641=64方案方案方案方案4 4与目标（与目标（与目标（与目标（2 2）的差距：）的差距：）的差距：）的差距：工时损失工时损失工时损失工时损失=（0 0）*5+5+（186-120186-120）*1=661=66方案排序：方案方案排序：方案方

21、案排序：方案方案排序：方案2 2 方案方案方案方案1 1 方案方案方案方案3 3 方案方案方案方案4 4第23页，本讲稿共83页6、多目标规划数学模型建立、多目标规划数学模型建立1、多目标的处理、多目标的处理 为了将不同级别目标的重要性用数量表为了将不同级别目标的重要性用数量表示，引进示，引进P1，P2，.,用它表示一级目标，用它表示一级目标，二级目标，二级目标，.，的重要程度。，的重要程度。规定规定P1 P2 P3 .。称称P1，P2，.,为级别系数。为级别系数。第24页，本讲稿共83页6、多目标规划数学模型建立、多目标规划数学模型建立2、约束方程的处理、约束方程的处理 引入差异变量引入差异

22、变量d+、d-并规定如下：并规定如下：（1）决策变量）决策变量x超过目标值超过目标值b的部分记的部分记d+（2）决策变量）决策变量x不足目标值不足目标值b的部分记的部分记d-（3）d+0,d-0 且且 x-d+d-=b第25页，本讲稿共83页6、多目标规划数学模型建立、多目标规划数学模型建立3 3、多目标的综合、多目标的综合、多目标的综合、多目标的综合（1 1）若决策目标中规定）若决策目标中规定）若决策目标中规定）若决策目标中规定 x x b,b,当当当当 d d+=0 =0 时目标才时目标才时目标才时目标才算达到。算达到。算达到。算达到。（2 2）若决策目标中规定）若决策目标中规定）若决策目

23、标中规定）若决策目标中规定 x x b,b,当当当当 d d-=0 =0 时目标才算时目标才算时目标才算时目标才算达到。达到。达到。达到。（3 3）若决策目标中规定）若决策目标中规定）若决策目标中规定）若决策目标中规定 x=b,x=b,当当当当 d d+=d=d-=0 =0 时目时目时目时目标才算达到。标才算达到。标才算达到。标才算达到。第26页，本讲稿共83页示例示例 一个企业需要同一种原材料生产甲乙一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同不相

24、同，从而获得的利润也不相同（如下表）。那么，该企业应如何安（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到排生产计划，才能使获得的利润达到最大？最大？第27页，本讲稿共83页解：设生产甲产品X1件，乙产品X2件，则应用线性规划，建立模型如下：MAX Z=6X1+4X2 2X1+3X2100 4X1+2X2 0用单纯形法求得最优解用单纯形法求得最优解用单纯形法求得最优解用单纯形法求得最优解=（2020，2020）；最优值）；最优值）；最优值）；最优值=200=200（百元）（百元）（百元）（百元）第28页，本讲稿共83页问题提出问题提出该厂提出如下目标该厂提出如下目标（1）利润达

25、到）利润达到280百元；百元；（2）钢材不超过）钢材不超过100吨，工时不超过吨，工时不超过120小时；小时；如何安排生产？如何安排生产？第29页，本讲稿共83页解：引进级别系数解：引进级别系数P1P1：（：（1 1 1 1）利润达到）利润达到280280百元；百元；P2P2：（：（2 2）钢材不超过）钢材不超过100100吨，工时不超过吨，工时不超过120120 小时；（权数之比小时；（权数之比小时；（权数之比小时；（权数之比5 5：1 1）第30页，本讲稿共83页建立多目标规划数学模型：建立多目标规划数学模型：目标函数：目标函数：Min S=PMin S=P1 1d d1 1-+P+P2

26、2(5d(5d2 2+d+d3 3+)约束方程：约束方程：6X6X1 1+4X+4X2 2+d+d1 1-d-d1 1+=280=280 2X 2X1 1+3X+3X2 2+d+d2 2-d-d2 2+=100=100 4X 4X1 1+2X+2X2 2+d+d3 3-d-d3 3+=120=120 X X1 1,X,X2 2,d,di i-,d,di i+0(i=1,2,3)0(i=1,2,3)第31页，本讲稿共83页练习1 某车间有某车间有A、B两条设备相同的生产线，它两条设备相同的生产线，它们生产同一种产品。们生产同一种产品。A生产线每小时可制造生产线每小时可制造2件产品，件产品，B生产

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

28、数：Min S=PMin S=P1 1d d1 1-+P+P2 2d d2 2+4+4 P P3 3d d3 3-+3 P+3 P3 3d d4 4-约束方程：约束方程：2X2X1 1+1.5X+1.5X2 2+d+d1 1-d-d1 1+=210=210 （生产量达到（生产量达到210210件件/周）周）X X1 1 +d+d2 2-d-d2 2+=60=60 （A A生产线加班时间限制在生产线加班时间限制在1515小时内）小时内）X1 +d3X1 +d3-d3-d3+=45=45 （充分利用（充分利用A A的工时指标）的工时指标）X2+d4X2+d4-d4-d4+=45=45 （充分利用（

29、充分利用B B的工时指标）的工时指标）X1,X2,di-,di+X1,X2,di-,di+0(i=1,2,3,4)0(i=1,2,3,4)第33页，本讲稿共83页练习练习2 某电器公司经营的唱机和录音机均有车间某电器公司经营的唱机和录音机均有车间某电器公司经营的唱机和录音机均有车间某电器公司经营的唱机和录音机均有车间A A、B B流水作业组装。数据见下表。流水作业组装。数据见下表。流水作业组装。数据见下表。流水作业组装。数据见下表。第34页，本讲稿共83页 公司计划要求按以下目标制订月生产计划：公司计划要求按以下目标制订月生产计划：（1 1）库存费用不超过）库存费用不超过46004600元；元

30、；（2 2）每月销售唱机不少于）每月销售唱机不少于8080台；台；（3 3）不使）不使A A、B B车间停工（权数由生产费用确定）；车间停工（权数由生产费用确定）；（4 4）A A车间加班时间限制在车间加班时间限制在2020小时内；小时内；（5 5）每月销售录音机为）每月销售录音机为100100台；台；（6 6）两车间加班时数总和要尽可能小（权数由生产）两车间加班时数总和要尽可能小（权数由生产 费用确定）；费用确定）；第35页，本讲稿共83页解：设每月生产唱机解：设每月生产唱机解：设每月生产唱机解：设每月生产唱机X X1 1，、录音机、录音机、录音机、录音机X X2 2台。且台。且台。且台。且

31、A A、B B的生产费用之比的生产费用之比的生产费用之比的生产费用之比为为为为 100100：50=250=2：1 1目标函数：目标函数：目标函数：目标函数：Min S=P1d1Min S=P1d1Min S=P1d1Min S=P1d1+P2d2+P2d2+P2d2+P2d2-+2P3d4+2P3d4+2P3d4+2P3d4-+P3d5+P3d5+P3d5+P3d5-+P4d41+P4d41+P4d41+P4d41+P5d3 P5d3 P5d3 P5d3-+P5d3+P5d3+P5d3+P5d3+2P6d4+2P6d4+2P6d4+2P6d4+P6d5+P6d5+P6d5+P6d5+约束方程

32、：约束方程：约束方程：约束方程：50X1+30X2+d150X1+30X2+d150X1+30X2+d150X1+30X2+d1-d1-d1-d1-d1+=4600=4600=4600=4600 （库存费用不超过（库存费用不超过（库存费用不超过（库存费用不超过4600460046004600元）元）元）元）X1 +d2X1 +d2X1 +d2X1 +d2-d2-d2-d2-d2+=80=80=80=80 （每月销售唱机不少于（每月销售唱机不少于（每月销售唱机不少于（每月销售唱机不少于80808080台）台）台）台）X2+d3X2+d3X2+d3X2+d3-d3-d3-d3-d3+=100=10

33、0=100=100 （每月销售录音机为（每月销售录音机为（每月销售录音机为（每月销售录音机为100100100100台）台）台）台）2X1+X2+d42X1+X2+d42X1+X2+d42X1+X2+d4-d4-d4-d4-d4+=180=180=180=180 （不使（不使（不使（不使A A A A车间停工）车间停工）车间停工）车间停工）X1+3X2+d5X1+3X2+d5X1+3X2+d5X1+3X2+d5-d5-d5-d5-d5+=200=200=200=200 （不使（不使（不使（不使B B B B车间停工）车间停工）车间停工）车间停工）d4d4d4d4+d41+d41+d41+d41

34、-d41-d41-d41-d41+=20=20=20=20 （A A A A车间加班时间限制在车间加班时间限制在车间加班时间限制在车间加班时间限制在20202020小时内）小时内）小时内）小时内）X1,X2,dX1,X2,dX1,X2,dX1,X2,di i i i-,d,d,d,di i i i+,d41,d41,d41,d41-,d41,d41,d41,d41+0(i=1,2,3,4,5)0(i=1,2,3,4,5)0(i=1,2,3,4,5)0(i=1,2,3,4,5)第36页，本讲稿共83页目标函数：目标函数：目标函数：目标函数：Min S=PMin S=P1 1d d1 1 1 1+

35、P+P2 2d d2 2-+2+2+2+2 P P3 3 3 3d d4 4-+P+P3 3d d5 5 5 5-+P +P4 4d d4141+P+P+P+P5 5d d3 3-+P+P5 5d d3 3 3 3+2P+2P+2P+2P6 6d d4 4+P+P+P+P6 6d d5 5+约束方程：约束方程：50X50X1 1+30X+30X+30X+30X2 2+d+d1 1-d-d1 1+=4600=4600 X X X X1 1 +d+d2 2-d-d-d-d2 2+=80=80 X X2 2+d+d3 3 3 3-d-d3 3+=100=100 2X 2X1 1 1 1+X+X2 2

36、 2 2+d+d4 4 4 4-d-d4 4+=180=180 X X1 1+3X+3X2 2 2 2+d+d5 5-d-d5 5+=200=200 d d4 4+d+d4141-d-d4141+=20=20 X X1 1,X,X2 2,d,d,d,di i i i-,d,di i+,d,d4141-,d,d4141+0(i=1,2,3,4,5)0(i=1,2,3,4,5)第37页，本讲稿共83页7、多目标规划问题的求解、多目标规划问题的求解图解法图解法例例1:一个企业需要同一种原材料生产甲乙一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材两种产品，它们的单位产品所需要的原

37、材料的数量及所耗费的加工时间各不相同，料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使么，该企业应如何安排生产计划，才能使获得的利润达到最大？获得的利润达到最大？第38页，本讲稿共83页解：设生产甲产品X1件，乙产品X2件，则应用线性规划，建立模型如下：MAX Z=6X1+4X2 2X1+3X2100 4X1+2X2 0用单纯形法求得最优解用单纯形法求得最优解用单纯形法求得最优解用单纯形法求得最优解=（2020，2020）；最优值）；最优值）；最优值）；最优值=200=200（百元）（百元）（百元）

38、（百元）第39页，本讲稿共83页问题提出问题提出该厂提出如下目标该厂提出如下目标（1）利润达到）利润达到280百元；百元；（2）钢材不超过）钢材不超过100吨，工时不超过吨，工时不超过120小时；小时；如何安排生产？如何安排生产？第40页，本讲稿共83页解：引进级别系数解：引进级别系数P1P1：（：（1 1）利润达到）利润达到280280百元；百元；P2P2P2P2：（：（2 2 2 2）钢材不超过）钢材不超过）钢材不超过）钢材不超过100100吨，工时不超过吨，工时不超过120120 小时；（权数之比小时；（权数之比5 5：1 1）第41页，本讲稿共83页建立多目标规划数学模型：建立多目标规

39、划数学模型：目标函数：目标函数：Min S=PMin S=P1 1d d1 1-+P+P2 2(5d(5d2 2+d+d3 3+)约束方程：约束方程：6X6X1 1+4X+4X2 2+d+d1 1-d-d1 1+=280=280 2X 2X1 1+3X+3X2 2+d+d2 2-d-d2 2+=100=100 4X 4X1 1+2X+2X2 2+d+d3 3-d-d3 3+=120=120 X X1 1,X,X2 2,d,di i-,d,di i+0(i=1,2,3)0(i=1,2,3)第42页，本讲稿共83页1020304050605040302010706X1+4X26X1+4X2 280

40、280 2X1+3X22X1+3X2 1001004X1+2X24X1+2X2 120120第43页，本讲稿共83页讨论：讨论：讨论：讨论：对于目标对于目标对于目标对于目标P1P1与目标与目标与目标与目标P2P2中第一个子目标很容易达到。但目标中第一个子目标很容易达到。但目标中第一个子目标很容易达到。但目标中第一个子目标很容易达到。但目标P2P2的两个指标不能同时满足，否则无解。的两个指标不能同时满足，否则无解。的两个指标不能同时满足，否则无解。的两个指标不能同时满足，否则无解。讨论如下：讨论如下：讨论如下：讨论如下：（1 1）Min dMin d3 3-=0=0；原问题无解。；原问题无解。；

41、原问题无解。；原问题无解。（2 2）Min dMin d3 3-0 0；(44,4)(44,4)是原问题的次优解。但需要增加工是原问题的次优解。但需要增加工是原问题的次优解。但需要增加工是原问题的次优解。但需要增加工时量。时量。时量。时量。计算需要增加的工时量的数量：计算需要增加的工时量的数量：计算需要增加的工时量的数量：计算需要增加的工时量的数量：由由由由 6X6X1 1+4X+4X2 2=280=280和和和和 2X2X1 1+3X+3X2 2=100=100解得交点为（解得交点为（解得交点为（解得交点为（44,4)44,4)；则把；则把；则把；则把方程方程方程方程4x4x1 1+2x+2

42、x2 2=120=120平移到点（平移到点（平移到点（平移到点（4444，4 4）后得到：）后得到：）后得到：）后得到：4x4x1 1+2x+2x2 2=4=4*44+2*4=*44+2*4=184184因此增加工时量为因此增加工时量为因此增加工时量为因此增加工时量为184-120=64184-120=64个工时。个工时。个工时。个工时。第44页，本讲稿共83页例例2 Min S=d1+X1+2X2+d1-d1+=10 X1+2X2 6 X1+X2 4 X1,X2,d1-,d1+0第45页，本讲稿共83页x1x204681021342X X1 1+2X+2X2 2 6 6第46页，本讲稿共83

43、页x1x204681021342X X1 1+X+X2 2 4 4第47页，本讲稿共83页x1x204681021342第48页，本讲稿共83页x1x204681021342第49页，本讲稿共83页x1x204681021342x x1 1+2x+2x2 2=10=105d1 1+d1 1-AB(2,2)第50页，本讲稿共83页x1x204681021342x x1 1+2x+2x2 2=10=105d1 1+d1 1-AB(2,2)当当 Min S=d1+达到时达到时 d1+=0第51页，本讲稿共83页x1x204681021342x x1 1+2x+2x2 2=10=105d1 1-AB(

44、2,2)当当 Min S=d1+达到时达到时 d1+=0第52页，本讲稿共83页x1x204681021342x x1 1+2x+2x2 2+d+d1 1-=10 d=10 d1 1-=2=25d1 1-AB(2,2)当当当当 Min S=d Min S=d1+达到时达到时 d1+=0第53页，本讲稿共83页x1x204681021342x x1 1+2x+2x2 2+d+d1 1-=10 d=10 d1 1-=4=45d1 1-AB(2,2)有无穷多解：点（有无穷多解：点（有无穷多解：点（有无穷多解：点（0 0，3 3）和）和）和）和点（点（点（点（2 2，2 2）连线上的点都是）连线上的点

45、都是）连线上的点都是）连线上的点都是最优解。最优解。最优解。最优解。(0,3)第54页，本讲稿共83页x1x204681021342x x1 1+2x+2x2 2+d+d1 1-=10 d=10 d1 1-=6=65d1 1-AB(2,2)有无穷多解：点（有无穷多解：点（有无穷多解：点（有无穷多解：点（4 4，0 0）和）和）和）和点（点（点（点（0 0，2 2）连线上的点都是）连线上的点都是）连线上的点都是）连线上的点都是最优解。最优解。最优解。最优解。(0,3)(4,0)(0,2)第55页，本讲稿共83页x1x204681021342x x1 1+2x+2x2 2+d+d1 1-=10 d

46、=10 d1 1-=7=75d1 1-AB(2,2)有无穷多解：点（有无穷多解：点（1，1）和点（和点（0，3/2）（3，0）连线上的点都是最优解。连线上的点都是最优解。(0,3)(4,0)(1,1)第56页，本讲稿共83页例例3 3 Min S=P Min S=P Min S=P Min S=P1 1d d d d1 1-+P+P+P+P2 2d d2 2+5+5 P P3 3 3 3d d d d3 3 3 3-+P+P3 3d d d d1 1+X X1 1 1 1+X+X2 2+d+d1 1-d-d-d-d1 1+=40=40 X X1 1+X+X2 2+d+d+d+d2 2-d-d2

47、 2+=50=50 X X1 1 +d+d3 3-=30=30=30=30 X X2 2+d+d+d+d4 4-=30=30 X X1 1,X,X2 2,d,dI I-,d,dI I+0(I=1,2,3,4)0(I=1,2,3,4)0(I=1,2,3,4)0(I=1,2,3,4)第57页，本讲稿共83页x1x2020304050101030402050d1 1-d1 1+X X1 1+X+X2 2=40=40第58页，本讲稿共83页x1x2020304050101030402050d1 1-d1 1+d2 2+d2 2-X X1 1+X+X2 2=50=50第59页，本讲稿共83页x1x202

48、0304050101030402050d1 1-d1 1+d2 2+d2 2-d3 3-X X1 1=30=30第60页，本讲稿共83页x1x2020304050101030402050d1 1-d1 1+d2 2+d2 2-d3 3-d4 4-X X2 2=30=30第61页，本讲稿共83页x1x2020304050101030402050d1 1+d2 2+d2 2-d3 3-d4 4-Min d1-=0可行域如图可行域如图可行域如图可行域如图第62页，本讲稿共83页x1x2020304050101030402050d1 1+d2 2-d3 3-d4 4-Min d2+=0=0可行域如图可

49、行域如图第63页，本讲稿共83页x1x2020304050101030402050d1 1+d2 2-d4 4-Min dMin d3 3-=0=0 线段线段AB是可行域是可行域AB第64页，本讲稿共83页x1x2020304050101030402050d2 2-d4 4-Min d1 1+=0P=(30,10)P=(30,10)唯一唯一最优解。最优解。d d2 2-=10=10 d d4 4-=20=20P第65页，本讲稿共83页例例4 Min S=PMin S=P1 1d1 1-+P2d2+P P3d d3-+P3d4 4-5X 5X1 1+10X2+d+d1-d1 1+=100 2X1

50、+X+X2+d2-d2+=14 X1 +d+d3-d-d3+=6 X2+d4 4-d4+=10 X1 1,X,X2,di-,di i+0(i=1,2,3,4)第66页，本讲稿共83页x1x20101520255515201025d1 1+d1 1-5X5X1 1+10X+10X2 2=100=100第67页，本讲稿共83页x1x20101520255515201025d1 1+d1 1-d2 2+d2 2-2X2X1 1+X+X2 2=14=14第68页，本讲稿共83页x1x20101520255515201025d1 1+d1 1-d2 2+d2 2-d3 3+d3 3-X X1 1 =6=