多目标规划（1）-第三章多目标规划ppt课件

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

2、人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但消费还得继续进展，这将给人们进一步运用线性规划方法带来困难。为了弥补线性规划问题的局限性，处理有限资源和方案目的之间的矛盾，在线性规划根底上，建立目的规划方法，从而使一些线性规划无法处理的问题得到称心的解答。4-1 多目的规划问题多目的规划问题的提出 在实践问题中，能够会同时思索几个方面都到达最优：产量最高，本钱最低，质量最好，利润最大，环境达标，运输满足等。多目的规划能更好地兼顾统筹处置多种目的的关系，求得更切合实践要求的解。 目的规划可根据实践情况，分主次地、轻重缓急地思索问题。例4-1：一个企业需求同一种原资料

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

4、5小时内；3充分利用工时目的，并依A、B产量的比例确定重要性。例4-3：某电器公司运营的唱机和录音机均有车间A、B流水作业组装。数据见下表。要求按以下目的制定月消费方案：1库存费用不超越4600元；2每月销售唱机不少于80台；3不使A、B车间停工权数由消费费用确定；4A车间加班时间限制在20小时内；5每月销售录音机为100台；6两车间加班时数总和要尽能够小权数由消费费用确定；多目的优先级 先将目的等级化：将目的按重要性的程度不同依次分成一级目的、二级目的.。最次要的目的放在次要的等级中。目的优先级作如下商定：对同一个目的而言，假设有几个决策方案都能使其到达，可以为这些方案就这个目的而言都是最优

5、方案；假设达不到，那么与目的差距越小的越好。目的优先级作如下商定： 不同级别的目的的重要性是不可比的。即较高级别的目的没有到达的损失，任何较低级别的目的上的收获都不可弥补。所以在判别最优方案时，首先从较高级别的目的到达的程度来决策，然后再其次级目的的判别。目的优先级作如下商定：同一级别的目的可以是多个。各自之间的重要程度可用数量权数来描画。因此，同一级别的目的的其中一个的损失，可有其他目的的适当收获来弥补。多目的规划解的概念：假设多目的规划问题的解能使一切的目的都到达，就称该解为多目的规划的最优解；假设解只能满足部分目的，就称该解为多目的规划的次优解；假设找不到满足任何一个目的的解，就称该问题

6、为无解。例4-4：例4-1一个企业需求同一种原资料消费甲乙两种产品，它们的单位产品所需求的原资料的数量及所耗费的加工时间各不一样，从而获得的利润也不一样如下表。那么，该企业应如何安排消费方案，才干使获得的利润到达最大？如何安排消费，使利润到达最大。前面曾经求得最优解=20，20最优值=200百元问题：该厂提出如下目的1利润到达280百元；2钢材不超越100吨，工时不超越120小时；如何安排消费？对例4-1的问题，设超越一吨钢材与超越5个工时的损失一样。现有四个方案进展比较优劣？目的：1利润到达280百元；2钢材不超越100吨，工时不超越120小时；对于1，只需方案4没有完成。排除方案4。对于2

7、，只需方案2到达了，因此方案2是最优。目的：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优于方案4例4-4：继续上例目的：1利润到达280百元；2钢材不超越100吨，工时不超越120小时；对于1，三个方案都没有完成。但方案3离目的最远，方案3最差。方案1与2的差距：工时损失=108-100*5+130-120*1=50方案2与2的差距：工时损失=0*5+160-1

8、20*1=40方案2优于方案1方案2优于方案1优于方案34-2 多目的规划问题的数学模型多目的的处置 为了将不同级别的目的的重要性用数量表示，引进P1，P2，.,用它表示一级目的，二级目的，.，的重要程度，规定P1P2 P3 .。称P1，P2，.,为级别系数。约束方程的处置差别变量：决策变量x超越目的值b的部分记d+决策变量x缺乏目的值b的部分记d-d+ 0, d- 0 且 x- d+ + d-= b多目的的综合假设决策目的中规定 x b, 当 d+ = 0 时目的才算到达。多目的的综合假设决策目的中规定 x b, 当 y+=0 时目的才算到达。假设决策目的中规定 x b, 当 d- = 0

9、时目的才算到达。多目的的综合假设决策目的中规定 x b, 当 y+=0 时目的才算到达。假设决策目的中规定 x b, 当 y-=0 时目的才算到达。假设决策目的中规定 x = b, 当 d+ = d- = 0 时目的才算到达。例4-5例4-4)解：引进级别系数P1：1利润到达280百元；P2：2钢材不超越100吨，工时不超越120小时；权数之比5：1数学模型：目的函数：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

10、,3)例4-6例4-2) 某车间有A、B两条设备一样的消费线，它们消费同一种产品。A消费线每小时可制造2件产品，B消费线每小时可制造1.5件产品。假设每周正常任务时数为45小时，要求制定完成以下目的的消费方案： 1消费量到达210件/周；2 A消费线加班时间限制在15小时内；3充分利用工时目的，并依A、B产量的比例确定重要性。解：设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+=60A消

11、费线加班时间限制在15小时内 X1 + d3- d3+=45 充分利用A的工时目的 X2+ d4- d4+=45 充分利用B的工时目的 X1,X2,di-, di+ 0(i=1,2,3,4)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)例4-7(例4-3)：(1)库存费用不超越4600元；(2)每月销售唱机不少于

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

13、 + 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)目的函数：Min S=P1d1+P2d2-+2 P3d4-+ P3d5- +P4d41+ P5d3-+ P5d3+2P6d4+ P6d5+约束方程： 50X1+30X2+ d1- d1+=4600 X1 + d2- d2+=80 X2 + d3- d3+=100 2X1 + X2+ d4- d4+=180 X1 + 3X2+ d5- d5

14、+=200 d4+ d41- d41+=20 X1,X2,di-, di+ ,d41-,d41+ 0(i=1,2,3,4,5)4-3 多目的规划问题的求解多目的规划问题的图解法例4-8 Min S = d1+ X1+2X2+ d1- d1+ = 10 X1+2X2 6 X1+X2 4 X1,X2,d1-, d1+ 0 x1x204681021342X1+2X2 6x1x204681021342X1+X2 4x1x204681021342x1x204681021342x1x204681021342x1+2x2=105d1+d1-AB(2,2)x1x204681021342x1+2x2=105d1

15、+d1-AB(2,2)当 Min S = d1+ 到达时 d1+ = 0 x1x204681021342x1+2x2=105d1-AB(2,2)当 Min S = d1+ 到达时 d1+ = 0 x1x204681021342x1+2x2+d1- = 10 d1- = 25d1-AB(2,2)当 Min S = d1+ 到达时 d1+ = 0 x1x204681021342x1+2x2+d1- = 10 d1- = 45d1-AB(2,2)有无穷多解：点0，3和点2，2连线上的点都是最优解。(0,3)x1x204681021342x1+2x2+d1- = 10 d1- = 65d1-AB(2,

16、2)有无穷多解：点4，0和点0，2连线上的点都是最优解。(0,3)(4,0)(0,2)x1x204681021342x1+2x2+d1- = 10 d1- = 75d1-AB(2,2)有无穷多解：点1，1和点0，3/2 3，0连线上的点都是最优解。(0,3)(4,0)(1,1)例4-9 Min 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)x1x2020304050101030402050d1-d1+X1+X

17、2=40 x1x2020304050101030402050d1-d1+d2+d2-X1+X2=50 x1x2020304050101030402050d1-d1+d2+d2-d3-X1=30 x1x2020304050101030402050d1-d1+d2+d2-d3-d4-X2=30 x1x2020304050101030402050d1+d2+d2-d3-d4-Min d1- = 0可行域如图x1x2020304050101030402050d1+d2-d3-d4-Min d2+ =0可行域如图x1x2020304050101030402050d1+d2-d4-Min d3- = 0

18、线段AB是可行域ABx1x2020304050101030402050d2-d4-Min d1+ = 0P=(30,10)独一最优解。 d2- =10 d4- = 20P例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)x1x20101520255515201025d1+d1-5X1+10X2=100 x1x20101520255515201025d1+d1-d2+d2-2X1 +X2 =14x1x20101520255515201025d1+d1-d2+d2-d3+d3-X1 =6x1x20101520255515201025d1+d1-d2+d2-d3+d3-d4+d4-X2=10 x1x20101520255515201025d1+d2+d2-d3+d3-d4+d4-Min d1- = 0 x1x20101520255515201025d1+d2-d3+d3-d4+d4-Min d2+ = 0可行域如图x1x20101520255515201025d1+d2-d3+d4+d4-Min d3- =0可行域为空如图x1x201015202