多目标规划(1)

多目标规划（1）概述与图解法1、线性规划的不足•1、线性规划只研究在满足一定条件下，单一目标函数取得最优解。•但是在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度（即优先顺序）也不相同，有些目标之间往往相互发生矛盾。1、线性规划的不足•2、线性规划致力于解决某个目标函数的最优解。•若是这个最优解超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。•3、线性规划把各个约束条件的重要性都不分主次地等同看待，不符合实际情况。1、线性规划的不足•4、求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解。•但是在生产实际中即使出现了这样的情况，生产还得继续进行。这就给人们进一步应用线性规划方法带来困难。使线性规划的应用受到限制。2、目标规划的作用•在实际生产管理问题中，可能会同时考虑几个方面都要求达到最优，如：产量最高，成本最低，质量最好，利润最大，环境达标，运输满足等。同时考虑多个决策目标时，称为多目标规划问题。•1、为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，应用建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。2、目标规划的作用•2、目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。••3、目标规划可根据实际情况，分主次地、轻重缓急地考虑问题。3、多目标规划问题的提出例1：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？产品/资源甲乙可利用的资源总量原材料钢（吨）23100加工时间（小时）42120单位利润（百元）64解：设生产甲产品X1件，乙产品X2件，则应用线性规划，建立模型如下：MAXZ=6X1+4X22X1+3X21002X1+2X2120X1、X20用单纯形法求得最优解=（20，20）；最优值=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流水作业组装。数据见下表。工时消耗（时/台）项目品种AB库存费用（元/台月）利润（元/台）唱机2150250录音机1330150总工时/月180200生产费用/时10050公司计划要求按以下目标制订月生产计划：（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、多目标规划解的概念举例一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？产品/资源甲乙可利用的资源总量原材料钢（吨）23100加工时间（小时）42120单位利润（百元）64解：设生产甲产品X1件，乙产品X2件，则应用线性规划，建立模型如下：MAXZ=6X1+4X22X1+3X21002X1+2X2120X1、X20用单纯形法求得最优解=（20，20）；最优值=200（百元）问题提出•该厂提出如下目标（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；如何安排生产？（注：超过一吨钢材与超过5个工时的损失相同）解：为达到第一目标，现可以提出4个方案如下：方案号甲产品产量乙产品产量钢材（吨）工时（时）利润（百元)损失量150010020030080207021014028057034441001842806444539918628266通过对上述四个方案比较进行求解：目标：（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方案46、多目标规划数学模型建立•1、多目标的处理•为了将不同级别目标的重要性用数量表示，引进P1，P2，….,用它表示一级目标，二级目标，….，的重要程度。•规定P1P2P3….。•称P1，P2，….,为级别系数。6、多目标规划数学模型建立2、约束方程的处理•引入差异变量d+、d-并规定如下：（1）决策变量x超过目标值b的部分记d+（2）决策变量x不足目标值b的部分记d-（3）d+0,d-0且x-d++d-=b6、多目标规划数学模型建立3、多目标的综合•（1）若决策目标中规定xb,当d+=0时目标才算达到。•（2）若决策目标中规定xb,当d-=0时目标才算达到。•（3）若决策目标中规定x=b,当d+=d-=0时目标才算达到。示例一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？产品/资源甲乙可利用的资源总量原材料钢（吨）23100加工时间（小时）42120单位利润（百元）64解：设生产甲产品X1件，乙产品X2件，则应用线性规划，建立模型如下：MAXZ=6X1+4X22X1+3X21002X1+2X2120X1、X20用单纯形法求得最优解=（20，20）；最优值=200（百元）问题提出•该厂提出如下目标（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；如何安排生产？解：引进级别系数P1：（1）利润达到280百元；P2：（2）钢材不超过100吨，工时不超过120小时；（权数之比5：1）建立多目标规划数学模型：目标函数：MinS=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)练习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目标函数：MinS=P1d1-+P2d2++4P3d3-+3P3d4-约束方程：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流水作业组装。数据见下表。工时消耗（时/台）项目品种AB库存费用（元/台月）利润（元/台）唱机2150250录音机1330150总工时/月180200生产费用/时10050公司计划要求按以下目标制订月生产计划：（1）库存费用不超过4600元；（2）每月销售唱机不少于80台；（3）不使A、B车间停工（权数由生产费用确定）；（4）A车间加班时间限制在20小时内；（5）每月销售录音机为100台；（6）两车间加班时数总和要尽可能小（权数由生产费用确定）；解：设每月生产唱机X1，、录音机X2台。且A、B的生产费用之比为100：50=2：1目标函数：MinS=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)目标函数：MinS=P1d1++P2d2-+2P3d4-+P3d5-+P4d41++P5d3-+P5d3++2P6d4++P6d5+约束方程：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)7、多目标规划问题的求解—图解法•例1:一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？产品/资源甲乙可利用的资源总量原材料钢（吨）23100加工时间（小时）42120单位利润（百元）64解：设生产甲产品X1件，乙产品X2件，则应用线性规划，建立模型如下：MAXZ=6X1+4X22X1+3X21002X1+2X2120X1、X20用单纯形法求得最优解=（20，20）；最优值=200（百元）问题提出•该厂提出如下目标（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；如何安排生产？解：引进级别系数P1：（1）利润达到280百元；P2：（2）钢材不超过100吨，工时不超过120小时；（权数之比5：1）建立多目标规划数学模型：目标函数：MinS=P1d1-+P2(5d2++d3+)约束方程：6X1+4X2+d1--d1+=2802X1+3X2+d2--d2+=1004X1