运筹学第六章目标规划.ppt

《运筹学第六章目标规划.ppt》由会员分享，可在线阅读，更多相关《运筹学第六章目标规划.ppt（94页珍藏版）》请在三一办公上搜索。

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

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

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

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

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

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

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

8、（110-100）*5+（130-120）*1=60,25,方案1与（2）的差距：60方案3与（2）的差距：工时损失=0*5+（190-120）*1=70方案1优于方案3。方案2 优于方案1 优于方案3 优于方案4,钢材不超过100吨，工时不超过120小时；超过一吨钢材与超过5个工时的损失相同,26,继续上例,27,目标：（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；对于（1），三个方案都没有完成。但方案3离目标最远，方案3最差。方案1与（2）的差距：工时损失=,超过一吨钢材与超过5个工时的损失相同,（108-100）*5+（130-120）*1=50,28,方案1

9、与（2）的差距：50方案2与（2）的差距：工时损失=0*5+（160-120）*1=40方案2优于方案1方案2 优于方案1 优于方案3,钢材不超过100吨，工时不超过120小时；超过一吨钢材与超过5个工时的损失相同,29,目标规划的数学模型一、基本概念1、多目标的处理：优先因子和权系数 优先因子Pk：为了将不同级别的目标的重要性用数量表示，引进P1，P2，,用它表示一级目标，二级目标，的重要程度。规定Pk Pk+1：表示Pk比Pk+1 有绝对的优先权。即：首先保证P1级目标实现，不考虑其他级,P2级目标是在保证P1级目标值不变前提下考虑的。权系数wj:具有相同优先因子的多个目标用wj来区别（越

10、重要，w值越大）。,30,2、约束方程的处理：偏差变量决策变量：x1，x2，x3偏差变量：正偏差量：实际决策值超过目标值bi的部分记di+负偏差量：实际决策值不足目标值bi的部分记di-di+0,di-0 且 fi(x)-di+di-=bi恒有：di+.di-0（不可能既超过目标值又低于目标值）,31,目标约束：由决策变量x，正、负偏差变量和要追求的目标值组成的软约束，具有一定的弹性。（目标约束不会不满足，但可能偏差过大）fi(x)-di+di-=bi：目标约束的一般形式 若附加上约束：di-0 若附加上约束：di+0 若附加上约束：di+di-0,fi(x)bi,fi(x)bi,fi(x)b

11、i,32,3、目标函数,1）不含决策变量：由各目标约束的偏差变量及相应的优先因子和权系数构成。2）总是极小化（总是希望尽可能缩小偏差）3）应用时，有三种基本表达式：,（1）要求恰好达到目标值。这时决策值超过或不足目标值都是不希望的，故有（2）要求不超过目标值。这时不希望决策值超过目标值，允许不足目标值。故有（3）要求不低于目标值。这时不希望决策值低于目标值，允许超过目标值。故有,33,例：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？,34,问题

12、：该厂提出如下目标（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；如何安排生产？（设超过1吨钢材与超过5个工时的损失相同),35,解：引进优先因子P1：（1）利润达到280百元；P2：（2）钢材不超过100吨，工时不超过120小时；（权数之比5：1）,数学模型：目标函数：Min a=P1d1-,约束方程：G1:6X1+4X2+d1-d1+=280G2:2X1+3X2+d2-d2+=100G3:4X1+2X2+d3-d3+=120 X1,X2,di-,di+0(i=1,2,3),P2(5d2+d3+),36,例:某车间有A、B两条设备相同的生产线，它们生产同一种产品。A

13、生产线每小时可制造2件产品，B生产线每小时可制造1.5件产品。如果每周正常工作时数为45小时，要求制定完成下列目标的生产计划：,（1）生产量达到210件/周；（2）A生产线加班时间限制在15小时内；（3）充分利用工时指标，并依A、B产量的比例确定重要性。,37,解：设A，B生产线每周工作时间为X1，X2。A，B的产量比例为 2:1.5=4:3约束方程：G1:2X1+1.5X2+d1-d1+=210（生产量达到210件/周）G2:X1+d2-d2+=60（A生产线加班时间限制在15小时内）,（1）生产量达到210件/周；（2）A生产线加班时间限制在15小时内；（3）充分利用工时指标，并依A、B产

14、量的比例确定重要性。,38,G3:X1+d3-d3+=45（充分利用A的工时指标）G4:X2+d4-d4+=45（充分利用B的工时指标）X1,X2,di-,di+0(i=1,2,3,4)目标函数：Min a=P1d1-,（1）生产量达到210件/周；（2）A生产线加班时间限制在15小时内；（3）充分利用工时指标，并依A、B产量的比例确定重要性。约束方程：G1:2X1+1.5X2+d1-d1+=210（生产量达到210件/周）G2:X1+d2-d2+=60（A生产线加班时间限制在15小时内）,P2d2+,P3(4 d3-+3 d4-),2:1.5=4:3,39,A，B的产量比例2：1.5=4:3

15、目标函数：Min a=P1d1-,P2d2+,P3(4 d3-+3 d4-)约束方程：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),（1）生产量达到210件/周；（2）A生产线加班时间限制在15小时内；（3）充分利用工时指标，并依A、B产量的比例确定重要性。,40,例：某电器公司经营的唱机和录音机均有车间A、B流水作业组装。要求按以下目标制订月生产计划：(1)库存费用不超过4600元；(2)每月销售唱机不少于80台；(3)不使A、B车间停工（权数由生产费用确定）；(4)

16、A车间加班时间限制在20小时内；(5)每月销售录音机为100台；(6)两车间加班时数总和要尽可能小（权数由生产费用确定）；,41,约束方程：50X1+30X2+d1-d1+=4600（库存费用不超过4600元）X1+d2-d2+=80（每月销售唱机不少于80台）2X1+X2+d3-d3+=180（不使A车间停工）X1+3X2+d4-d4+=200（不使B车间停工）,解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1,42,d3+d31-d31+=20（A车间加班时间限制 在20小时内）X2+d5-d5+=100（每月销售录音机为100台）X1,X2,di-,d

17、i+,d31-,d31+0(i=1,2,3,4,5)目标函数：Min a=P1d1+,50X1+30X2+d1-d1+=4600X1+d2-d2+=80 2X1+X2+d3-d3+=180 X1+3X2+d4-d4+=200,生产费用之比为100：50=2：1,P2d2-,P3(2d3-+d4-),P4d31+,P5(d5-+d5+),P6(2d3+d4+),43,目标函数：Min a=P1d1+,P2d2-,P3(2d3-+d4-),P4d31+,P5(d5-+d5+),P6(2d3+d4+)约束方程：50X1+30X2+d1-d1+=4600 X1+d2-d2+=80 2X1+X2+d3-

18、d3+=180 X1+3X2+d4-d4+=200 d3+d31-d31+=20 X2+d5-d5+=100 X1,X2,di-,di+,d31-,d31+0(i=1,2,3,4,5),44,作业：P124 3.8,45,6.2 线性目标规划的图解法目标规划问题的图解法:求一个区域，提供了相互矛盾的目标集的折衷方案。例 Min S=d1+X1+2X2+d1-d1+=10 X1+2X2 6 X1+X2 4 X1,X2,d1-,d1+0,46,x1,x2,0,4,6,8,10,2,1,3,4,2,X1+2X2 6,Min S=d1+X1+2X2+d1-d1+=10 X1+2X2 6 X1+X2 4

19、 X1,X2,d1-,d1+0,5,47,x1,x2,0,4,6,8,10,2,1,3,4,2,X1+X2 4,Min S=d1+X1+2X2+d1-d1+=10 X1+2X2 6 X1+X2 4 X1,X2,d1-,d1+0,5,48,x1,x2,0,4,6,8,10,2,1,3,4,2,Min S=d1+X1+2X2+d1-d1+=10 X1+2X2 6 X1+X2 4 X1,X2,d1-,d1+0,5,49,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+X1+2X2+d1-d1+=10 X1+2X2 6

20、 X1+X2 4 X1,X2,d1-,d1+0,50,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,51,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,52,x1,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,53,x1,x2,0,4,6,8,10,2,1,3,4,2,x

21、1+2x2+d1-=10 d1-=4,5,d1-,A,B,(2,2),有无穷多解：点（0，3）和点（2，2）连线上的点都是最优解。,(0,3),Min S=d1+X1+2X2+d1-d1+=10 X1+2X2 6 X1+X2 4 X1,X2,d1-,d1+0,54,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,3),(4,0),(0,2),55,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2+d1-=10 d1-=7,5,d1-

22、,A,B,(2,2),有无穷多解：点（1，1）和点（0，3/2）（3，0）连线上的点都是最优解。,(0,3),(4,0),(1,1),56,步骤：1、作所有约束直线2、加注偏差变量3、确定第一优先级目标集的最优解空间4、求k+1级最优解空间5、令k=k+1，反复执行4，直至求解完毕。,57,例 Min S=P1d1-，P2d2+，P3（5 d3-+d1+）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),58,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1

23、-,d1+,X1+X2=40,Min S=P1d1-，P2d2+，P3（5 d3-+d1+）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),59,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,d2+,d2-,X1+X2=50,Min S=P1d1-，P2d2+，P3（5 d3-+d1+）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),6

24、0,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,d2+,d2-,d3-,X1=30,Min S=P1d1-，P2d2+，P3（5 d3-+d1+）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),61,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,d2+,d2-,d3-,d4-,X2=30,Min S=P1d1-，P2d2+，P3（5 d3-+d1+）X1+X2+d1-d1+=40 X1+X2+d

25、2-d2+=50 X1+d3-=30 X2+d4-=30 X1,X2,dI-,dI+0(I=1,2,3,4),62,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1+,d2-,d3-,d4-,Min d1-=0可行域如图,d1-,Min S=P1d1-，P2d2+，P3（5 d3-+d1+）,63,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1+,d2-,d4-,Min d2+=0可行域如图,Min S=P1d1-，P2d2+，P3（5 d3-+d1+）,64,x1,x2,0,20,30,40,50,10,10,30,40,20

26、,50,d2-,d4-,Min d3-=0 线段AB是可行域,A,B,Min S=P1d1-，P2d2+，P3（5 d3-+d1+）,65,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d2-,d4-,Min d1+=0P=(30,10)唯一最优解。d2-=10 d4-=20,P,Min S=P1d1-，P2d2+，P3（5 d3-+d1+）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),66,例 Min S=P1d1-,P2d2+,P3(d3-+d4-)5

27、X1+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),67,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,5X1+10X2=100,Min S=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),68,x1,x2,0,10,15,20,25,5,5,15,20,10,

28、25,d1+,d1-,d2+,d2-,2X1+X2=14,Min S=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),69,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,d2+,d2-,d3+,d3-,X1=6,Min S=P1d1-,P2d2+,P3(d3-+d4-)5X1+10X2+d1-d1+=100 2X1+X2+d2-d2+=14 X1+d3-d3+=6 X2+d4-d4

29、+=10 X1,X2,di-,di+0(i=1,2,3,4),70,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,X2=10,Min S=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),71,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2+,d2-,d3+,d3-,d4+,d4-,Min d1-=

30、0,d1-,Min S=P1d1-,P2d2+,P3(d3-+d4-),72,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2-,d3+,d3-,d4+,d4-,Min d2+=0可行域如图,d2+,Min S=P1d1-,P2d2+,P3(d3-+d4-),73,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2-,d3+,d4+,d4-,d3-,Min d3-=0Min d4-0可行域为空如图,Min S=P1d1-,P2d2+,P3(d3-+d4-),74,x1,x2,0,10,15,20,25,5,5,15,20,1

31、0,25,d1+,d2-,d3+,d4+,Min d3-0Min d4-=0可行域如图,d3-,(2,10),d4-,Min S=P1d1-,P2d2+,P3(d3-+d4-),75,对于目标P1与目标P2很容易达到。目标P3的两个指标不能同时满足，否则无解。又因为P3中的两个目标同样重要，要讨论（1）Min d3-=0 Min d4-0 原问题无解。（2）Min d3-0=4 Min d4-=0原问题(2,10)是次优解。,Min S=P1d1-,P2d2+,P3(d3-+d4-)5X1+10X2+d1-d1+=100 2X1+X2+d2-d2+=14 X1+d3-d3+=6 X2+d4-d

32、4+=10 X1,X2,di-,di+0(i=1,2,3,4),76,作业：P123 3.2（图解法）,77,6.3 序贯式算法,序贯式算法：根据优先级别，把线性目标规划分解为多个单目标线性规划，依次求解。方法特点：简单，计算量大，一般用计算机求解。,78,步骤：1、求解对应第一优先级的单目标线性规划模型2、设已求得k级单目标线性规划问题，得到最优值ak*3、令k=k+1,建立对应新的优先级k的单目标线性规划模型,返回步骤2求解，直至k大于总的优先级别数。,79,例：,一级单目标：,单纯形法求得：,80,二级单目标：,为避免劣化一级已达到的目标值,单纯形法求得：,81,三级单目标：,单纯形法求

33、得：,82,四级单目标：,单纯形法求得：,83,6.4 线性目标规划的单纯形法,目标规划的数学模型实际上是最小化形式的线性规划问题，可以用单纯形法求解。在用单纯形法解目标规划时，检验数是各优先因子的线性组合。因此，在判别各检验数的正负及大小时，必须注意。当所有检验数都已满足最优性条件 时，从最终单纯形表上就可以得到目标规划的解。,84,例 用单纯形法解：,解：引入松驰变量，将目标规划模型化为线性规划标准形式：,85,用单纯形法解上面的标准形式，解题过程的单纯形表见下表。,86,在单纯形表中，非基变量 和 的检验数皆负，但的检验数更小些，故确定 为换入变量。按最小比值规则，为换出变量。经迭代变量

34、得单纯形表。,87,在单纯形表中，由于非基变量 和 的检验数都是零，故知例题有多重最优解（满意解）。如以 为换入变量继续进行迭代，可得单纯形表；,88,89,如以 为换入变量继续进行迭代，可单纯形表,从单纯形表和中，分别可得到例题的另两个满意解，即 和。,90,与单目标方法不同处：1、检验数：按k级优先因子分解为k项，写成k行；2、最优性检验：首先判别Pk行检验数是否已达最 优。若是；再考虑Pk+1级，且同时保证Pk级最优值不被劣化。例,91,*,-8,-1,-12,-1.5,1,1,1,1,1,1.5,-1000,-52.5,92,-8,-1,1,1,1,-12,1,1,12,1.5,-820,-30,*,93,1,1,1,4,2,1,-8,1,-1,-4,8,1,*,-0.5,-740,-20,94,1,-8,1,1,-12,2,1,8,-1,1,-2,1.5,12,1,-580,-20,最优解：,x1=30,x2=15,d1+=d2+=d3+=d1-=d2-=d4-=0,d3-=580,d4+=20,a*=(0,580,20,0),