运筹学多目标规划(1)

例4-1：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？用单纯形法求得最优解=（20，20）最优值=200（百元）产品/资源甲乙可利用的资源总量原材料钢（吨）23100加工时间（小时）42120单位利润（百元）64问题：该厂提出如下目标（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车间停工（权数由生产费用确定）；（4）A车间加班时间限制在20小时内；（5）每月销售录音机为100台；（6）两车间加班时数总和要尽可能小（权数由生产费用确定）；工时消耗（时/台）项目品种AB库存费用（元/台月）利润（元/台）唱机2150250录音机1330150总工时/月180200生产费用/时10050多目标优先级先将目标等级化：将目标按重要性的程度不同依次分成一级目标、二级目标…..。最次要的目标放在次要的等级中。目标优先级作如下约定：•对同一个目标而言，若有几个决策方案都能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标差距越小的越好。•不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别的目标上的收获都不可弥补。所以在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。•同一级别的目标可以是多个。各自之间的重要程度可用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，可有其余目标的适当收获来弥补。多目标规划解的概念：•若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解；•若解只能满足部分目标，就称该解为多目标规划的次优解；•若找不到满足任何一个目标的解，就称该问题为无解。例4-1：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？用单纯形法求得最优解=（20，20）最优值=200（百元）产品/资源甲乙可利用的资源总量原材料钢（吨）23100加工时间（小时）42120单位利润（百元）64问题：该厂提出如下目标（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；如何安排生产？对例4-1的问题，设超过一吨钢材与超过5个工时的损失相同。现有四个方案进行比较优劣？方案编号利润(百元)钢(吨)工时(时)12901101302280100115328595190427090120目标：（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：继续上例方案编号利润(百元)钢(吨)工时(时)5270108130627080160726080120目标：（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；对于（1），三个方案都没有完成。但方案3离目标最远，方案3最差。方案5与（2）的差距：工时损失=（108-100）*5+（130-120）*1=50方案6与（2）的差距：工时损失=0*5+（160-120）*1=40方案6优于方案5方案6优于方案5、优于方案74-2多目标规划问题的数学模型多目标的处理为了将不同级别的目标的重要性用数量表示，引进P1，P2，….,用它表示一级目标，二级目标，….，的重要程度，规定P1》P2》P3》….。称P1，P2，….,为级别系数。约束方程的处理决策变量x超过目标值b的部分记d+；决策变量x不足目标值b的部分记d-。d+、d-称为差异变量。d+0,d-0。且x-d++d-=b多目标的综合•若决策目标中规定为时,应使minZ=f(d+)。•若决策目标中规定为时,应使minZ=f(d-)。•若决策目标中规定为=时,应使minZ=f(d++d-)。例4-5（例4-4)解：引进级别系数P1：（1）利润达到280百元；P2：（2）钢材不超过100吨，工时不超过120小时；（权数之比5：1）数学模型：目标函数：MinZ=P1d1-+P2(5d2++d3+)约束方程：6X1+4X2+d1--d1+=2802X1+3X2+d2--d2+=1004X1+2X2+d3--d3+=120X1,X2,di-,di+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目标函数：MinZ=P1d1-+P2d2++P3（4d3-+3d4-）约束方程：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)例4-3：某电器公司经营的唱机和录音机均有车间A、B流水作业组装。数据见下表。要求按以下目标制订月生产计划：（1）库存费用不超过4600元；（2）每月销售唱机不少于80台；（3）不使A、B车间停工（权数由生产费用确定）；（4）A车间加班时间限制在20小时内；（5）每月销售录音机为100台；（6）两车间加班时数总和要尽可能小（权数由生产费用确定）；工时消耗（时/台）项目品种AB库存费用（元/台月）利润（元/台）唱机2150250录音机1330150总工时/月180200生产费用/时10050解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1目标函数：MinS=P1d1++P2d2-+P3（2d4-+d5-）+P4d41++P5（d3++d3-）+P6（2d4++d5+）约束方程：50X1+30X2+d1--d1+=4600（库存费用不超过4600元）X1+d2--d2+=80（每月销售唱机不少于80台）2X1+X2+d4--d4+=180（不使A车间停工）X1+3X2+d5--d5+=200（不使B车间停工）d4++d41--d41+=20（A车间加班时间限制在20小时内）X2+d3--d3+=100（每月销售录音机为100台）X1,X2,di-,di+,d41-,d41+0(i=1,2,3,4,5)目标函数：MinS=P1d1++P2d2-+P3（2d4-+d5-）+P4d41++P5（d3++d3-）+P6（2d4++d5+）约束方程：50X1+30X2+d1--d1+=4600X1+d2--d2+=80X2+d3--d3+=1002X1+X2+d4--d4+=180X1+3X2+d5--d5+=200d4++d41--d41+=20X1,X2,di-,di+,d41-,d41+0(i=1,2,3,4,5)4-3多目标规划问题的图解法例4-8MinZ=d1+X1+2X2+d1--d1+=10X1+2X26X1+X24X1,X2,d1-,d1+0法x1x204681021342X1+2X26x1x204681021342X1+X24x1x204681021342x1x204681021342x1x204681021342x1+2x2=105d1+d1-AB(2,2)x1x204681021342x1+2x2=105d1+d1-AB(2,2)当MinZ=d1+达到时d1+=0x1x204681021342x1+2x2+d1-=10d1-=25d1-AB(2,2)当MinZ=d1+达到时d1+=0x1x204681021342x1+2x2+d1-=10d1-=45d1-AB(2,2)有无穷多解：点（0，3）和点（2，2）连线上的点都是最优解。(0,3)x1x204681021342x1+2x2+d1-=10d1-=65d1-AB(2,2)有无穷多解：点（4，0）和点（0，2）连线上的点都是最优解。(0,3)(4,0)(0,2)x1x204681021342x1+2x2+d1-=10d1-=75d1-AB(2,2)有无穷多解：点（0，3/2）（3，0）连线上的点都是最优解。(0,3)(4,0)(1,1)例4-9MinZ=P1d1-+P2d2++P3（5d3-+d1+）X1+X2+d1--d1+=40X1+X2+d2--d2+=50X1+d3-=30X2+d4-=30X1,X2,dI-,dI+0(I=1,2,3,4)x1x2020304050101030402050d1-d1+X1+X2=40x1x2020304050101030402050d1-d1+d2+d2-X1+X2=50x1x2020304050101030402050d1-d1+d2+d2-d3-X1=30x1x2020304050101030402050d1-d1+d2+d2-d3-d4-X2=30x1x2020304050101030402050d1+d2+d2-d3-d4-Mind1-=0可行域如图x1x2020304050101030402050d1+d2-d3-d4-Mind2+=0可行域如图x1x2020304050101030402050d1+d2-d4-Mind3-=0线段AB是可行域ABx1x2020304050101030402050d2-d4-Mind1+=0P=(30,10)唯一最优解。d2-=10d4-=20P例4-10MinZ=P1d1-+P2d2++P3（d3-+d4-）5X1+10X2+d1--d1+=1002X1+X2+d2--d2+=14X1+d3--d3+=6X2+d4--d4+=10X1,X2,di-,di+0(i=1,2,3,4)x1x20101520255515201025d1+d1-5X1+10X2=100x1x20101520255515201025d1+d1-d2+d2-2X1+X2=14x1x20101520255515201025d1+d1-d2+d2-d3+d3-X1=6x1x20101520255515201025d1+d1-d2+d2-d3+d3-d4+d4-X2=10x1x20101520255515201025d1+d2+d2-d3+d3-d4+d4-Mind1-=0x1x20101520255515201025d1+d2-d3+d3-d4+d4-Mind2+=0可行域如图x1x20101520255515201025d1+d2-d3+d4+d4-Mind