高等教育运筹学课程--多目标规划.ppt

多目标规划（1）,概述与图解法,1、线性规划的不足,1、线性规划只研究在满足一定条件下，单一目标函数取得最优解。 但是在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度（即优先顺序）也不相同，有些目标之间往往相互发生矛盾。,1、线性规划的不足,2、线性规划致力于解决某个目标函数的最优解。 3、线性规划把各个约束条件的重要性都不分主次地等同看待，不符合实际情况。,1、线性规划的不足,4、求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解。 但是在生产实际中即使出现了这样的情况，生产还得继续进行。这就给人们进一步应用线性规划方法带来困难。使线性规划的应用受到限制。,2、目标规划的作用,在实际生产管理问题中，可能会同时考虑几个方面都要求达到最优，如：产量最高，成本最低，质量最好，利润最大，环境达标，运输满足等。同时考虑多个决策目标时，称为多目标规划问题。 1、为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，应用建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。,2、目标规划的作用,2、目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。 3、目标规划可根据实际情况，分主次地、轻重缓急地考虑问题。,3、多目标规划问题的提出,例1：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？,解：设生产甲产品X1件，乙产品X2件，则应用线性规划，建立模型如下： MAX Z=6X1+4X2 2X1+3X2100 4X1+2X2120 X1、X2 0,初始单纯形表,最终单纯形表为：,原问题最优解为： X1 =20，X2=20 最优值 Z=200（百元） 对偶问题最优解为：Y1=1/2，Y2=5/4 最优值 Z=200（百元）,问题提出,该厂提出如下目标 （1）利润达到280百元； （2）钢材不超过100吨，工时不超过120小时； 如何安排生产？,例2,某车间有A、B两条设备相同的生产线，它们生产同一种产品。A生产线每小时可制造2件产品，B生产线每小时可制造1.5件产品。如果每周正常工作时数为45小时，要求制定完成下列目标的生产计划： （1）生产量达到210件/周； （2） A生产线加班时间限制在15小时内； （3）充分利用工时指标，并依A、B产量 的比例确定重要性。,例3,某电器公司经营的唱机和录音机均有车间A、B流水作业组装。数据见下表。,公司计划要求按以下目标制订月生产计划： （1）库存费用不超过4600元； （2）每月销售唱机不少于80台； （3）不使A、B车间停工（权数由生产费用确定）； （4）A车间加班时间限制在20小时内； （5）每月销售录音机为100台； （6）两车间加班时数总和要尽可能小（权数由生产 费用确定）；,4、多目标规划优先级的概念,1、目标等级化：将目标按重要性的程度不同依次分成一级目标、二级目标。最次要的目标放在次要的等级中。 2、对同一个目标而言，若有几个决策方案都能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标差距越小的越好。,4、多目标规划优先级的概念,3、不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别的目标上的收获都不可弥补。 4、在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。 5、同一级别的目标可以是多个。各自之间的重要程度可用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，可用其余目标的适当收获来弥补。,5、多目标规划解的概念,1、若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解； 2、若解只能满足部分目标，就称该解为多目标规划的次优解； 3、若找不到满足任何一个目标的解，就称该问题为无解。,5、多目标规划解的概念举例,一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？,解：设生产甲产品X1件，乙产品X2件，则应用线性规划，建立模型如下： MAX Z=6X1+4X2 2X1+3X2 0 用单纯形法求得最优解=（20，20）；最优值=200（百元）,问题提出,该厂提出如下目标 （1）利润达到280百元； （2）钢材不超过100吨，工时不超过120小时； 如何安排生产？ （注：超过一吨钢材与超过5个工时的损失相同）,解：为达到第一目标，现可以提出4个方案如下：,通过对上述四个方案比较进行求解： 目标：（1）利润达到280百元； （2）钢材不超过100吨，工时不超过120小时； 讨论：上述方案都达到了目标（1），但是没有达到目标（2） 方案1与目标（2）的差距： 工时损失=（100-100）*5+（200-120）*1=80 方案2与目标（2）的差距： 工时损失=（210-100）*5+（140-120）*1=570 方案3与目标（2）的差距： 工时损失=（100-100）*5+（184-120）*1=64 方案4与目标（2）的差距： 工时损失=（0）*5+（186-120）*1=66 方案排序：方案2 方案1 方案3 方案4,6、多目标规划数学模型建立,1、多目标的处理 为了将不同级别目标的重要性用数量表示，引进P1，P2，.,用它表示一级目标，二级目标，.，的重要程度。 规定P1P2 P3 .。 称P1，P2，.,为级别系数。,6、多目标规划数学模型建立,2、约束方程的处理 引入差异变量d+ 、d- 并规定如下： （1）决策变量x超过目标值b的部分记d+ （2）决策变量x不足目标值b的部分记d- （3）d+ 0, d- 0 且 x- d+ + d- = b,6、多目标规划数学模型建立,3、多目标的综合 （1）若决策目标中规定 x b, 当 d+ = 0 时目标才算达到。 （2）若决策目标中规定 x b, 当 d- = 0 时目标才算达到。 （3）若决策目标中规定 x = b, 当 d+ = d- = 0 时目标才算达到。,示例,一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？,解：设生产甲产品X1件，乙产品X2件，则应用线性规划，建立模型如下： MAX Z=6X1+4X2 2X1+3X2 0 用单纯形法求得最优解=（20，20）；最优值=200（百元）,问题提出,该厂提出如下目标 （1）利润达到280百元； （2）钢材不超过100吨，工时不超过120小时； 如何安排生产？,解：引进级别系数 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,3),练习1,某车间有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+=60 （A生产线加班时间限制在15小时内） X1 + d3- d3+=45 （充分利用A的工时指标） X2+ d4- d4+=45 （充分利用B的工时指标） X1,X2,di-, di+ 0(i=1,2,3,4),练习2,某电器公司经营的唱机和录音机均有车间A、B流水作业组装。数据见下表。,公司计划要求按以下目标制订月生产计划： （1）库存费用不超过4600元； （2）每月销售唱机不少于80台； （3）不使A、B车间停工（权数由生产费用确定）； （4）A车间加班时间限制在20小时内； （5）每月销售录音机为100台； （6）两车间加班时数总和要尽可能小（权数由生产 费用确定）；,解：设每月生产唱机X1， 、录音机X2台。且A、B的生产费用之比为 100：50=2：1 目标函数：Min S=P1d1+P2d2-+2P3d4-+ P3d5-+P4d41+ P5d3-+ P5d3+2P6d4+ P6d5+ 约束方程： 50X1+30X2+ d1- d1+=4600 （库存费用不超过4600元） X1 + d2- d2+=80 （每月销售唱机不少于80台） 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),目标函数：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+=200 d4+ d41- d41+=20 X1,X2,di-, di+ ,d41-,d41+ 0(i=1,2,3,4,5),7、多目标规划问题的求解图解法,例1: 一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？,解：设生产甲产品X1件，乙产品X2件，则应用线性规划，建立模型如下： MAX Z=6X1+4X2 2X1+3X2 0 用单纯形法求得最优解=（20，20）；最优值=200（百元）,问题提出,该厂提出如下目标 （1）利润达到280百元； （2）钢材不超过100吨，工时不超过120小时； 如何安排生产？,解：引进级别系数 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,3),10,20,30,40,50,60,50,40,30,20,10,70,6X1+4X2280,2X1+3X2100,4X1+2X2120,讨论： 对于目标P1与目标P2中第一个子目标很容易达到。但目标P2的两个指标不能同时满足，否则无解。 讨论如下： （1）Min d3- =0；原问题无解。 （2）Min d3- 0 ； (44,4)是原问题的次优解。但需要增加工时量。 计算需要增加的工时量的数量： 由 6X1+4X2=280和 2X1+3X2=100解得交点为（44,4)；则把方程4x1+2x2=120平移到点（44，4）后得到：4x1+2x2=4*44+2*4=184 因此增加工时量为184-120=64个工时。,例2 Min S = d1+ X1+2X2+ d1- d1+ = 10 X1+2X2 6 X1+X2 4 X1,X2,d1-, d1+ 0,x1,x2,0,4,6,8,10,2,1,3,4,2,X1+2X2 6,x1,x2,0,4,6,8,10,2,1,3,4,2,X1+X2 4,x1,x2,0,4,6,8,10,2,1,3,4,2,x1,x2,0,4,6,8,10,2,1,3,4,2,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2=10,5,d1+,d1-,A,B,(2,2),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,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,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,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),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),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),例3 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),x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,X1+X2=40,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,d2+,d2-,X1+X2=50,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,d2+,d2-,d3-,X1=30,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,d2+,d2-,d3-,d4-,X2=30,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1+,d2+,d2-,d3-,d4-,Min d1- = 0 可行域如图,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1+,d2-,d3-,d4-,Min d2+ =0 可行域如图,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1+,d2-,d4-,Min d3- = 0 线段AB是可行域,A,B,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d2-,d4-,Min d1+ = 0 P=(30,10)唯一最优解。 d2- =10 d4- = 20,P,例4 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),x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,5X1+10X2=100,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,d2+,d2-,2X1 +X2 =14,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,d2+,d2-,d3+,d3-,X1 =6,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,X2=10,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2+,d2-,d3+,d3-,d4+,d4-,Min d1- = 0,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2-,d3+,d3-,d4+,d4-,Min d2+ = 0 可行域如图,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2-,d3+,d4+,d4-,Min d3- =0 可行域