运筹学资料3多目标规划1

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,目 标 规 划,(Goal programming),目标规划的数学模型,目标规划的图解法,目标规划的单纯形法,目标规划概述,同时考虑多个决策目标时，称为多目标规划问题。,4-0 引言,从线性规划问题可看出：,线性规划只研究在满足一定条件下，单一目标函数取得最优解，而在企业管理中，经常遇到多目标决策问题，如拟订生产方案时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度即优先顺序也不相同，有些目标之间往往相互发生矛盾。,线性规划致力于某个目标函数的最优解，这个最优解假设是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。,线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。,求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。,为了弥补线性规划问题的局限性，解决有限资源和方案指标之间的矛盾，在线性规划根底上，建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。,4-1 多目标规划问题,多目标规划问题的提出,在实际问题中，可能会同时考虑几个方面都到达最优：产量最高，本钱最低，质量最好，利润最大，环境达标，运输满足等。多目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。,目标规划可根据实际情况，分主次地、轻重缓急地考虑问题。,例4-1：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所消耗的加工时间各不相同，从而获得的利润也不相同如下表。那么，该企业应如何安排生产方案，才能使获得的利润到达最大？,如何安排生产，使利润到达最大。,用单纯形法求得最优解=20，20,最优值=200百元,问题：该厂提出如下目标,1利润到达280百元；,2钢材不超过100吨，工时不超过120小时；,如何安排生产？,例4-2：某车间有A、B两条设备相同的生产线，它们生产同一种产品。A生产线每小时可制造2件产品，B生产线每小时可制造1.5件产品。如果每周正常工作时数为45小时，要求制定完成以下目标的生产方案：,1生产量到达210件/周；,2 A生产线加班时间限制在15小时内；,3充分利用工时指标，并依A、B产量的比例确定重要性。,例4-3：某电器公司经营的唱机和录音机均有车间A、B流水作业组装。数据见下表。,要求按以下目标制订月生产方案：,1库存费用不超过4600元；,2每月销售唱机不少于80台；,3不使A、B车间停工权数由生产费用确定；,4A车间加班时间限制在20小时内；,5每月销售录音机为100台；,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，只有方案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-120*1=40,方案2优于方案1,方案2优于方案1优于方案3,4-2 多目标规划问题的数学模型,多目标的处理,为了将不同级别的目标的重要性用数量表示，引进P1，P2，.,用它表示一级目标，二级目标，.，的重要程度，规定P1?P2 ? 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 时目标才算到达。,多目标的综合,假设决策目标中规定 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=P,1,d,1,-,+P,2,(5d,2,+,+d,3,+,),约束方程：,6X,1,+4X,2,+ d,1,-,- d,1,+,=280,2X,1,+3X,2,+ d,2,-,- d,2,+,=100,4X,1,+2X,2,+ d,3,-,- d,3,+,=120,X,1,X,2,d,i,-, d,i,+,0(i=1,2,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+=60,A生产线加班时间限制在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=P,1,d,1,-,+P,2,d,2,+,+4,P,3,d,3,-,+3 P,3,d,4,-,约束方程： 2X,1,+1.5X,2,+ d,1,-,- d,1,+,= 210,X,1,+ d,2,-,- d,2,+,= 60,X,1,+ d,3,-,- d,3,+,= 45,X,2,+ d,4,-,- d,4,+,= 45,X,1,X,2,d,i,-, d,i,+,0 (i=1,2,3,4),例4-7(例4-3)：,(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-+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 + 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=P,1,d,1,+,+P,2,d,2,-,+2,P,3,d,4,-,+ P,3,d,5,-,+P,4,d,41,+,+ P,5,d,3,-,+ P,5,d,3,+,+2P,6,d,4,+,+ P,6,d,5,+,约束方程： 50X,1,+30X,2,+ d,1,-,- d,1,+,=4600,X,1,+ d,2,-,- d,2,+,=80,X,2,+ d,3,-,- d,3,+,=100,2X,1,+ X,2,+ d,4,-,- d,4,+,=180,X,1,+ 3X,2,+ d,5,-,- d,5,+,=200,d,4,+,+ d,41,-,- d,41,+,=20,X,1,X,2,d,i,-, d,i,+,d,41,-,d,41,+,0(i=1,2,3,4,5),4-3 多目标规划问题的求解,多目标规划问题的图解法,例4-8,Min S = d,1,+,X,1,+2X,2,+ d,1,-,- d,1,+,= 10,X,1,+2X,2,6,X,1,+X,2,4,X,1,X,2,d,1,-, d,1,+,0,x1,x2,0,4,6,8,10,2,1,3,4,2,X,1,+2X,2,6,x1,x2,0,4,6,8,10,2,1,3,4,2,X,1,+X,2,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,x,1,+2x,2,=10,5,d,1,+,d,1,-,A,B,(2,2),x1,x2,0,4,6,8,10,2,1,3,4,2,x,1,+2x,2,=10,5,d,1,+,d,1,-,A,B,(2,2),当 Min S = d1+ 到达时 d1+ = 0,x1,x2,0,4,6,8,10,2,1,3,4,2,x,1,+2x,2,=10,5,d,1,-,A,B,(2,2),当 Min S = d1+ 到达时 d1+ = 0,x1,x2,0,4,6,8,10,2,1,3,4,2,x,1,+2x,2,+d,1,-,= 10 d,1,-,= 2,5,d,1,-,A,B,(2,2),当 Min S = d1+ 到达时 d1+ = 0,x1,x2,0,4,6,8,10,2,1,3,4,2,x,1,+2x,2,+d,1,-,= 10 d,1,-,= 4,5,d,1,-,A,B,(2,2),有无穷多解：点0，3和点2，2连线上的点都是最优解。,(0,3),x1,x2,0,4,6,8,10,2,1,3,4,2,x,1,+2x,2,+d,1,-,= 10 d,1,-,= 6,5,d,1,-,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,x,1,+2x,2,+d,1,-,= 10 d,1,-,= 7,5,d,1,-,A,B,(2,2),有无穷多解：点1，1和点0，3/2 3，0连线上的点都是最优解。,(0,3),(4,0),(1,1),例4-9,Min S=P,1,d,1,-,+P,2,d,2,+,+5,P,3,d,3,-,+ P,3,d,1,+,X,1,+X,2,+ d,1,-,- d,1,+,=40,X,1,+X,2,+ d,2,-,- d,2,+,=50,X,1,+ d,3,-,=30,X,2,+ d,4,-,=30,X,1,X,2,d,I,-, d,I,+,0(I=1,2,3,4),x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,1,-,d,1,+,X,1,+X,2,=40,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,1,-,d,1,+,d,2,+,d,2,-,X,1,+X,2,=50,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,1,-,d,1,+,d,2,+,d,2,-,d,3,-,X,1,=30,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,1,-,d,1,+,d,2,+,d,2,-,d,3,-,d,4,-,X,2,=30,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,1,+,d,2,+,d,2,-,d,3,-,d,4,-,Min d,1,-,= 0,可行域如图,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,1,+,d,2,-,d,3,-,d,4,-,Min d,2,+,=0,可行域如图,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,1,+,d,2,-,d,4,-,Min d,3,-,= 0,线段AB是可行域,A,B,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,2,-,d,4,-,Min d,1,+,= 0,P=(30,10)唯一最优解。,d,2,-,=10,d,4,-,= 20,P,例4-10,Min S=P,1,d,1,-,+P,2,d,2,+,+,P,3,d,3,-,+ P,3,d,4,-,5X,1,+10X,2,+ d,1,-,- d,1,+,=100,2X,1,+ X,2,+ d,2,-,- d,2,+,=14,X,1,+ d,3,-,- d,3,+,=6,X,2,+ d,4,-,- d,4,+,=10,X,1,X,2,d,i,-, d,i,+,0(i=1,2,3,4),x1,x2,0,10,15,20,25,5,5,15,20,10,25,d,1,+,d,1,-,5X,1,+10X,2,=100,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d,1,+,d,1,-,d,2,+,d,2,-,2X,1,+X,2,=14,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d,1,+,d,1,-,d,2,+,d,2,-,d,3,+,d,3,-,X,1,=6,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d,1,+,d,1,-,d,2,+,d,2,-,d,3,+,d,3,-,d,4,+,d,4,-,X,2,=10,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d,1,+,d,2,+,d,2,-,d,3,+,d,3,-,d,4,+,d,4,-,Min d,1,-,= 0,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d,1,+,d,2,-,d,3,+,d,3,-,d,4,+,d,4,-,Min d,2,+,= 0,可行域如图,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d,1,+,d,2,-,d,3,+,d,4,+,d,4,-,Min d,3,-,=0,可行域为空如图,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d,1,+,d,2,-,d,3,+,d,4,+,Min d,3,-,0,Min d,4,-,= 0,可行域如图,d,3,-,(2,10),x1,x2,0,10,15,20,25,5,5,15,20,10,25,d,1,+,d,2,-,d,3,+,d,4,+,Min d,3,-,= 0,Min d,4,-,0,可行域为空如图,d,4,-,对于目标P1与目标P2很容易到达。目标P3的两个指标不能同时满足，否那么无解。又因为P3中的两个目标同样重要，要讨论,1Min d3-=0 Min d4- 0,原问题无解。,2 Min d3- 0 Min d4-=0,原问题(2,10)是次优解。,例4-11,Min S=P,1,d,1,-,+P,1,d,2,-,X,1,+d,1,-,- d,1,+,=15,4X,1,+ 5X,2,+ d,2,-,- d,2,+,=200,3X,1,+4X,2,120,X,1,-2X,2,15,X,1,X,2,d,i,-, d,i,+,0(i=1,2),x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,1,+,d,1,-,X,1,=15,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,1,+,d,1,-,d,2,+,d,2,-,4X,1,+ 5X,2,=200,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,1,+,d,1,-,d,2,+,d,2,-,3X,1,+4X,2,120,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,1,+,d,1,-,d,2,+,d,2,-,X,1,-2X,2,15,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,1,+,d,1,-,d,2,+,d,2,-,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d,1,+,d,2,+,同时考虑 d,1,-,=0,d,2,-,=0,原问题无解。,谢谢大家！,