《第4章 多目标规划.ppt》由会员分享，可在线阅读，更多相关《第4章 多目标规划.ppt（116页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 多目标规划多目标规划 同时考虑多个决策目标同时考虑多个决策目标时，称为多目标规划问题。时，称为多目标规划问题。4-0 4-0 引言引言从线性规划问题可看出：从线性规划问题可看出：线性规划只研究在满足一定条件下，单线性规划只研究在满足一定条件下，单一目标函数取得最优解，而在企业管理一目标函数取得最优解，而在企业管理中，经常遇到多目标决策问题，如拟订中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。考虑利润，产品质量和设备利用率等。这些指标之间的重要程度（即优先顺序）这些指标之间的重要程度（即优先顺
2、序）也不相同，有些目标之间往往相互发生也不相同，有些目标之间往往相互发生矛盾。矛盾。线性规划致力于某个目标函数的线性规划致力于某个目标函数的最优解，这个最优解若是超过了实最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。了约束条件中的某些资源作为代价。线性规划把各个约束条件的重要线性规划把各个约束条件的重要性都不分主次地等同看待，这也不性都不分主次地等同看待，这也不符合实际情况。符合实际情况。求解线性规划问题，首先要求求解线性规划问题，首先要求约束条件必须相容，如果约束约束条件必须相容，如果约束条件中，由于人力，设备等资条
3、件中，由于人力，设备等资源条件的限制，使约束条件之源条件的限制，使约束条件之间出现了矛盾，就得不到问题间出现了矛盾，就得不到问题的可行解，但生产还得继续进的可行解，但生产还得继续进行，这将给人们进一步应用线行，这将给人们进一步应用线性规划方法带来困难。性规划方法带来困难。为了弥补线性规划问题的局限为了弥补线性规划问题的局限性，解决有限资源和计划指标性，解决有限资源和计划指标之间的矛盾，在线性规划基础之间的矛盾，在线性规划基础上，建立目标规划方法，从而上，建立目标规划方法，从而使一些线性规划无法解决的问使一些线性规划无法解决的问题得到满意的解答。题得到满意的解答。4-1 4-1 多目标规划问题多
4、目标规划问题多目标规划问题的提出多目标规划问题的提出 在实际问题中，可能会同时考虑几个方面在实际问题中，可能会同时考虑几个方面都达到最优：产量最高，成本最低，质量最都达到最优：产量最高，成本最低，质量最好，利润最大，环境达标，运输满足等。多好，利润最大，环境达标，运输满足等。多目标规划能更好地兼顾统筹处理多种目标的目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。关系，求得更切合实际要求的解。目标规划可根据实际情况，分主次地、目标规划可根据实际情况，分主次地、轻重缓急地考虑问题。轻重缓急地考虑问题。例例4-14-1：一个企业需要同一种原一个企业需要同一种原材料生产甲乙两种产品
5、，它们材料生产甲乙两种产品，它们的单位产品所需要的原材料的的单位产品所需要的原材料的数量及所耗费的加工时间各不数量及所耗费的加工时间各不相同，从而获得的利润也不相相同，从而获得的利润也不相同（如下表）。那么，该企业同（如下表）。那么，该企业应如何安排生产计划，才能使应如何安排生产计划，才能使获得的利润达到最大？获得的利润达到最大？如何安排生产，使利润达到最大。如何安排生产，使利润达到最大。用单纯形法求得最优解用单纯形法求得最优解=（2020，2020）最优值最优值=200=200（百元）（百元）问题：问题：该厂提出如下目标该厂提出如下目标（1 1）利润达到）利润达到280280百元；百元；（2
6、 2）钢材不超过）钢材不超过100100吨，工时不吨，工时不超过超过120120小时；小时；如何安排生产？如何安排生产？例例4-24-2：某车间有某车间有A A、B B两条设备两条设备相同的生产线，它们生产同一种相同的生产线，它们生产同一种产品。产品。A A生产线每小时可制造生产线每小时可制造2 2件件产品，产品，B B生产线每小时可制造生产线每小时可制造1.51.5件产品。如果每周正常工作时数件产品。如果每周正常工作时数为为4545小时，要求制定完成下列目小时，要求制定完成下列目标的生产计划：标的生产计划：（1 1）生产量达到）生产量达到210210件件/周；周；（2 2）A A生产线加班时
7、间限制在生产线加班时间限制在1515小时内；小时内；（3 3）充分利用工时指标，并依）充分利用工时指标，并依A A、B B产量的比例确定重要性。产量的比例确定重要性。例例4-34-3：某电器公司经营的唱机和某电器公司经营的唱机和录音机均有车间录音机均有车间A A、B B流水作业组流水作业组装。数据见下表。装。数据见下表。要求按以下目标制订月生产计划：要求按以下目标制订月生产计划：（1 1）库存费用不超过）库存费用不超过46004600元；元；（2 2）每月销售唱机不少于）每月销售唱机不少于8080台；台；（3 3）不使）不使A A、B B车间停工（权数由生车间停工（权数由生产费用确定）；产费用
8、确定）；（4 4）A A车间加班时间限制在车间加班时间限制在2020小时小时内；内；（5 5）每月销售录音机为）每月销售录音机为100100台；台；（6 6）两车间加班时数总和要尽可能）两车间加班时数总和要尽可能小（权数由生产费用确定）；小（权数由生产费用确定）；多目标优先级多目标优先级 先将目标等级化：将目先将目标等级化：将目标按重要性的程度不同依次标按重要性的程度不同依次分成一级目标、二级目标分成一级目标、二级目标.。最次要的目标放在次。最次要的目标放在次要的等级中要的等级中。目标优先级作如下约定：目标优先级作如下约定：对同一个目标而言，若有几个决对同一个目标而言，若有几个决策方案都能使其
9、达到，可认为这策方案都能使其达到，可认为这些方案就这个目标而言都是最优些方案就这个目标而言都是最优方案；若达不到，则与目标差距方案；若达不到，则与目标差距越小的越好。越小的越好。目标优先级作如下约定目标优先级作如下约定：不同级别的目标的重要性是不可不同级别的目标的重要性是不可比的。即较高级别的目标没有达到比的。即较高级别的目标没有达到的损失，任何较低级别的目标上的的损失，任何较低级别的目标上的收获都不可弥补。所以在判断最优收获都不可弥补。所以在判断最优方案时，首先从较高级别的目标达方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目到的程度来决策，然后再其次级目标的判断。标的判断。目标
10、优先级作如下约定：目标优先级作如下约定：同一级别的目标可以是多个。同一级别的目标可以是多个。各自之间的重要程度可用数量各自之间的重要程度可用数量（权数）来描述。因此，同一（权数）来描述。因此，同一级别的目标的其中一个的损失，级别的目标的其中一个的损失，可有其余目标的适当收获来弥可有其余目标的适当收获来弥补。补。多目标规划解的概念：多目标规划解的概念：若多目标规划问题的解能使所若多目标规划问题的解能使所有的目标都达到，就称该解为有的目标都达到，就称该解为多目标规划的最优解；多目标规划的最优解；若解只能满足部分目标，就称若解只能满足部分目标，就称该解为多目标规划的次优解；该解为多目标规划的次优解；
11、若找不到满足任何一个目标的若找不到满足任何一个目标的解，就称该问题为无解。解，就称该问题为无解。例例4-44-4：（例：（例4-14-1）一个企业需要一个企业需要同一种原材料生产甲乙两种产品，同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料它们的单位产品所需要的原材料的数量及所耗费的加工时间各不的数量及所耗费的加工时间各不相同，从而获得的利润也不相同相同，从而获得的利润也不相同（如下表）。那么，该企业应如（如下表）。那么，该企业应如何安排生产计划，才能使获得的何安排生产计划，才能使获得的利润达到最大？利润达到最大？如何安排生产，使利润达到最大。如何安排生产，使利润达到最大。前面已经求
12、得最优解前面已经求得最优解=（2020，2020）最优值最优值=200=200（百元）（百元）问题：问题：该厂提出如下目标该厂提出如下目标（1 1）利润达到）利润达到280280百元；百元；（2 2）钢材不超过）钢材不超过100100吨，工时不吨，工时不超过超过120120小时；小时；如何安排生产？如何安排生产？对例对例4-14-1的问题，设超过一吨钢材与超过的问题，设超过一吨钢材与超过5 5个工时的损失相同。现有四个方案进行比个工时的损失相同。现有四个方案进行比较优劣？较优劣？目标：（目标：（1 1）利润达到）利润达到280280百元；百元；（2 2）钢材不超过）钢材不超过100100吨，工
13、时不超吨，工时不超过过120120小时；小时；对于（对于（1 1），只有方案），只有方案4 4没有完成。没有完成。排除方案排除方案4 4。对于（对于（2 2），只有方案），只有方案2 2达到了，因达到了，因此方案此方案2 2是最优。是最优。目标：（目标：（1 1）利润达到）利润达到280280百元；百元；（2 2）钢材不超过）钢材不超过100100吨，工时不超过吨，工时不超过120120小时；小时；方案方案1 1与方案与方案3 3都达到了（都达到了（1 1），又没），又没达到（达到（2 2）方案方案1 1与（与（2 2）的差距：）的差距：工时损失工时损失=（110-100110-100）*5+
14、5+（130-120130-120）*1=601=60方案方案3 3与（与（2 2）的差距：）的差距：工时损失工时损失=0*5+=0*5+（190-120190-120）*1=701=70方案方案1 1优于方案优于方案3 3。方案方案2 2优于方案优于方案1 1优于方案优于方案3 3优于方优于方案案4 4例例4-44-4：继续上例：继续上例目标：（目标：（1 1）利润达到）利润达到280280百元；百元；（2 2）钢材不超过）钢材不超过100100吨，工时不超吨，工时不超过过120120小时；小时；对于（对于（1 1），三个方案都没有完成。），三个方案都没有完成。但方案但方案3 3离目标最远，
15、方案离目标最远，方案3 3最差。最差。方案方案1 1与（与（2 2）的差距：）的差距：工时损失工时损失=（108-100108-100）*5+5+（130-120130-120）*1=501=50方案方案2 2与（与（2 2）的差距：）的差距：工时损失工时损失=0*5+=0*5+（160-120160-120）*1=401=40方案方案2 2优于方案优于方案1 1方案方案2 2优于方案优于方案1 1优于方案优于方案3 34-2 4-2 多目标规划问题的数学模型多目标规划问题的数学模型多目标的处理多目标的处理 为了将不同级别的目标的重要为了将不同级别的目标的重要性用数量表示，引进性用数量表示，引
16、进P P1 1，P P2 2，.,.,用用它表示一级目标，二级目标，它表示一级目标，二级目标，.，的重要程度，规定的重要程度，规定P P1 1P P2 2 P P3 3.。称。称P P1 1，P P2 2，.,.,为级别系数。为级别系数。约束方程的处理约束方程的处理差异变量：差异变量：决策变量决策变量x x超过目标值超过目标值b b的部分记的部分记d d+决策变量决策变量x x不足目标值不足目标值b b的部分记的部分记d d-d d+0,d0,d-0 0 且且 x-dx-d+d d-=b=b多目标的综合多目标的综合若决策目标中规定若决策目标中规定 x b,当当 d+=0 时目标才算达到。时目标
17、才算达到。多目标的综合多目标的综合若决策目标中规定若决策目标中规定 x b,当当 d+=0 时目标才算达到。时目标才算达到。若决策目标中规定若决策目标中规定 x b,当当 d-=0 时目标才算达到。时目标才算达到。多目标的综合多目标的综合若决策目标中规定若决策目标中规定 x b,当当 d+=0 时目标才算达到。时目标才算达到。若决策目标中规定若决策目标中规定 x b,当当 d-=0 时目标才算达到。时目标才算达到。若决策目标中规定若决策目标中规定 x=b,当当 d+=d-=0 时目标才算达到。时目标才算达到。例例4-54-5（例（例4-4)4-4)解：引进级别系数解：引进级别系数P1P1：（：
18、（1 1）利润达到利润达到280280百元；百元；P2P2：（：（2 2）钢材不超过钢材不超过100100吨，吨，工时不超过工时不超过120120小时；（权数之小时；（权数之比比5 5：1 1）数学模型：数学模型：目标函数：目标函数：Min S=PMin S=P1 1d d1 1-+P+P2 2(5d(5d2 2+d+d3 3+)约束方程：约束方程：6X6X1 1+4X+4X2 2+d+d1 1-d-d1 1+=280=280 2X 2X1 1+3X+3X2 2+d+d2 2-d-d2 2+=100=100 4X 4X1 1+2X+2X2 2+d+d3 3-d-d3 3+=120=120 X
19、X1 1,X,X2 2,d,di i-,d di i+0(i=1,2,3)0(i=1,2,3)例例4-64-6（例（例4-2)4-2)某车间有某车间有A A、B B两条两条设备相同的生产线，它们生产同一设备相同的生产线，它们生产同一种产品。种产品。A A生产线每小时可制造生产线每小时可制造2 2件件产品，产品，B B生产线每小时可制造生产线每小时可制造1.51.5件件产品。如果每周正常工作时数为产品。如果每周正常工作时数为4545小时，要求制定完成下列目标的生小时，要求制定完成下列目标的生产计划：产计划：（1 1）生产量达到）生产量达到210210件件/周；周；（2 2）A A生产线加班时间限
20、制在生产线加班时间限制在1515小时内；小时内；（3 3）充分利用工时指标，并依）充分利用工时指标，并依A A、B B产量的比例确定重要性。产量的比例确定重要性。解：解：设设A A，B B生产线每周工作时间为生产线每周工作时间为X X1 1，X X2 2。A A，B B的产量比例的产量比例2 2：1.5=4:31.5=4:3目标函数：目标函数：Min S=PMin S=P1 1d d1 1-+P+P2 2d d2 2+4+4 P P3 3d d3 3-+3 P+3 P3 3d d4 4-约束方程：约束方程：2X2X1 1+1.5X+1.5X2 2+d+d1 1-d-d1 1+=210=210
21、（生产量达到生产量达到210210件件/周）周）X X1 1 +d+d2 2-d-d2 2+=60=60（A A生产线加班时间限制在生产线加班时间限制在1515小时内）小时内）X X1 1 +d+d3 3-d-d3 3+=45=45 （充分利用充分利用A A的工时指标）的工时指标）X X2 2+d+d4 4-d-d4 4+=45=45 （充分利用充分利用B B的工时指标）的工时指标）X X1 1,X,X2 2,d,di i-,d di i+0(i=1,2,3,4)0(i=1,2,3,4)A A，B B的产量比例的产量比例2 2：1.5=4:31.5=4:3目标函数：目标函数：Min S=PMi
22、n S=P1 1d d1 1-+P+P2 2d d2 2+4+4 P P3 3d d3 3-+3 P+3 P3 3d d4 4-约束方程：约束方程：2X2X1 1+1.5X+1.5X2 2+d+d1 1-d-d1 1+=210=210 X X1 1 +d+d2 2-d-d2 2+=60=60 X X1 1 +d+d3 3-d-d3 3+=45=45 X2 +d+d4 4-d-d4 4+=45=45 X X1 1,X,X2 2,d,di i-,d di i+0(i=1,2,3,4)0(i=1,2,3,4)例例4-7(4-7(例例4-3)4-3)：(1)(1)库存费用不超过库存费用不超过46004
23、600元；元；(2)(2)每月销售唱机不少于每月销售唱机不少于8080台；台；(3)(3)不使不使A A、B B车间停工（权数由生产车间停工（权数由生产费用确定）；费用确定）；(4)A(4)A车间加班时间限制在车间加班时间限制在2020小时内；小时内；（5）每月销售录音机为）每月销售录音机为100台；台；（6）两车间加班时数总和要尽可能）两车间加班时数总和要尽可能小（权数由生产费用确定）；小（权数由生产费用确定）；解：解：设每月生产唱机、录音机设每月生产唱机、录音机X1，X2台。且台。且A、B的生产费用之比为的生产费用之比为100：50=2：1目标函数：目标函数：Min S=PMin S=P1
24、 1d d1 1+P+P2 2d d2 2-+2+2 P P3 3d d4 4-+P+P3 3d d5 5-+P +P4 4d d4141+P+P5 5d d3 3-+P+P5 5d d3 3+2P+2P6 6d d4 4+P+P6 6d d5 5+约束方程：约束方程：50X50X1 1+30X+30X2 2+d+d1 1-d-d1 1+=4600=4600 （库存费用不超过库存费用不超过46004600元）元）X X1 1 +d+d2 2-d-d2 2+=80=80 （每月销售唱机不少于每月销售唱机不少于8080台）台）X X2 2+d+d3 3-d-d3 3+=100=100 （每月销售录
25、音机为每月销售录音机为100100台）台）2X2X1 1+X+X2 2+d+d4 4-d-d4 4+=180=180 （不使不使A A车间停工）车间停工）X X1 1+3X+3X2 2+d+d5 5-d-d5 5+=200=200 （不使不使B B车间停工）车间停工）d d4 4+d+d4141-d-d4141+=20=20 （A A车间加班时间限制在车间加班时间限制在2020小时内）小时内）X X1 1,X,X2 2,d,di i-,d di i+,d,d4141-,d,d4141+0(i=1,2,3,4,5)0(i=1,2,3,4,5)目标函数：目标函数：Min S=PMin S=P1 1
26、d d1 1+P+P2 2d d2 2-+2+2 P P3 3d d4 4-+P+P3 3d d5 5-+P +P4 4d d4141+P+P5 5d d3 3-+P+P5 5d d3 3+2P+2P6 6d d4 4+P+P6 6d d5 5+约束方程：约束方程：50X50X1 1+30X+30X2 2+d+d1 1-d-d1 1+=4600=4600 X X1 1 +d+d2 2-d-d2 2+=80=80 X X2 2+d+d3 3-d-d3 3+=100=100 2X 2X1 1+X+X2 2+d+d4 4-d-d4 4+=180=180 X X1 1+3X+3X2 2+d+d5 5-
27、d-d5 5+=200=200 d d4 4+d+d4141-d-d4141+=20=20 X X1 1,X,X2 2,d,di i-,d di i+,d,d4141-,d,d4141+0(i=1,2,3,4,5)0(i=1,2,3,4,5)4-3 4-3 多目标规划问题的求解多目标规划问题的求解多目标规划问题的图解法多目标规划问题的图解法例例4-84-8 Min S=dMin S=d1 1+X X1 1+2X+2X2 2+d+d1 1-d-d1 1+=10=10 X X1 1+2X+2X2 2 6 6 X X1 1+X+X2 2 4 4 X X1 1,X,X2 2,d,d1 1-,d,d1
28、1+0 0 x1x204681021342X X1 1+2X+2X2 2 6 6x1x204681021342X X1 1+X+X2 2 4 4x1x204681021342x1x204681021342x1x204681021342x x1 1+2x+2x2 2=10=105d1 1+d1 1-AB(2,2)x1x204681021342x x1 1+2x+2x2 2=10=105d1 1+d1 1-AB(2,2)当当 Min S=d1+达到时达到时 d1+=0 x1x204681021342x x1 1+2x+2x2 2=10=105d1 1-AB(2,2)当当 Min S=d1+达到时达
29、到时 d1+=0 x1x204681021342x x1 1+2x+2x2 2+d+d1 1-=10 d=10 d1 1-=2=25d1 1-AB(2,2)当当 Min S=d1+达到时达到时 d1+=0 x1x204681021342x x1 1+2x+2x2 2+d+d1 1-=10 d=10 d1 1-=4=45d1 1-AB(2,2)有无穷多解：点（有无穷多解：点（0，3）和点（）和点（2，2）连线上）连线上的点都是最优解。的点都是最优解。(0,3)x1x204681021342x x1 1+2x+2x2 2+d+d1 1-=10 d=10 d1 1-=6=65d1 1-AB(2,2)
30、有无穷多解：点（有无穷多解：点（4，0）和点（）和点（0，2）连线上）连线上的点都是最优解。的点都是最优解。(0,3)(4,0)(0,2)x1x204681021342x x1 1+2x+2x2 2+d+d1 1-=10 d=10 d1 1-=7=75d1 1-AB(2,2)有无穷多解：点（有无穷多解：点（1，1）和点（）和点（0，3/2）（3，0）连线上的点都是最）连线上的点都是最优解。优解。(0,3)(4,0)(1,1)例例4-9 4-9 Min S=P Min S=P1 1d d1 1-+P+P2 2d d2 2+P+P3 3d d3 3-+P+P4 4d d4 4-X X1 1+X+X
31、2 2+d+d1 1-d-d1 1+=40=40 X X1 1+X+X2 2+d+d2 2-d-d2 2+=50=50 X X1 1 +d+d3 3-=30=30 X X2 2+d+d4 4-=30=30 X X1 1,X,X2 2,d,dI I-,d dI I+0(I=1,2,3,4)0(I=1,2,3,4)x1x2020304050101030402050d1 1-d1 1+X X1 1+X+X2 2=40=40 x1x2020304050101030402050d1 1-d1 1+d2 2+d2 2-X X1 1+X+X2 2=50=50 x1x202030405010103040205
32、0d2 2-d1 1+x1x2020304050101030402050d2 2-X X1 1=30=30d1 1+d3 3-x1x2020304050101030402050d1 1+d2 2-d3 3-X X1 1=30=30 x1x2020304050101030402050d1 1+d2 2-d3 3-X X1 1=30=30d4 4-x1x2020304050101030402050d1 1+d2 2-d3 3-d4 4-Min d2+=0可行可行域如图域如图x1x2020304050101030402050d1 1+d2 2-d4 4-Min d3-=0 线段线段AB是可行域是可行
33、域ABx1x2020304050101030402050d2 2-d4 4-Min d4-P=(30,20)唯一唯一最优解。最优解。d d2 2-=10=10 d d4 4-=1010P例例4-10 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)x1x20101520255515201025d1 1+d1 1-5X5X1 1+10X+10X2 2=100=100 x1x20101520255515201025d
34、1 1+d1 1-d2 2+d2 2-2X2X1 1+X+X2 2=14=14x1x20101520255515201025d1 1+d1 1-d2 2+d2 2-d3 3+d3 3-X X1 1 =6=6x1x20101520255515201025d1 1+d1 1-d2 2+d2 2-d3 3+d3 3-d4 4+d4 4-X X2 2=10=10 x1x20101520255515201025d1 1+d2 2+d2 2-d3 3+d3 3-d4 4+d4 4-Min d1-=0 x1x20101520255515201025d1 1+d2 2-d3 3+d3 3-d4 4+d4 4-
35、Min d2+=0可行域如图可行域如图x1x20101520255515201025d1 1+d2 2-d3 3+d4 4+d4 4-Min d3-=0可行域为空如图可行域为空如图d3 3-x1x20101520255515201025d1 1+d2 2-d3 3+d4 4+d4 4-Min d3-0,如何如何使使P3（d3-+d4-）最小呢？最小呢？Qd3 3-QEd3 3-Ex1x20101520255515201025d1 1+d2 2-d3 3+d4 4+d4 4-x1x20101520255515201025d1 1+d2 2-d3 3+d4 4+d4 4-x1x2010152025
36、5515201025d1 1+d2 2-d3 3+d4 4+d4 4-P1(2,10)P2(26/3,8/3)2X2X1 1+X+X2 2=14=14d d3 3-+d+d4 4-=16-(X16-(X1 1+X+X2 2)=16-(2X =16-(2X1 1+X+X2 2)+X1 =2+X1于是于是于是于是P1P1为最优点。为最优点。为最优点。为最优点。多目标规划的单纯形算法多目标规划的单纯形算法 多目标规划问题与线性规划多目标规划问题与线性规划问题相似，可用单纯形算法求解。问题相似，可用单纯形算法求解。注意：在比较检验数大小时，要注意：在比较检验数大小时，要先比较较高级别的系数，再比较先比
37、较较高级别的系数，再比较较低级别的系数。较低级别的系数。例例4-114-11（例（例4-64-6）目标函数：目标函数：Min S=PMin S=P1 1d d1 1-+P+P2 2(5d(5d2 2+d+d3 3+)约束方程：约束方程：6X6X1 1+4X+4X2 2+d+d1 1-d-d1 1+=280=280 2X 2X1 1+3X+3X2 2+d+d2 2-d-d2 2+=100=100 4X 4X1 1+2X+2X2 2+d+d3 3-d-d3 3+=120=120 X X1 1,X,X2 2,d,di i-,d di i+0(i=1,2,3)0(i=1,2,3)标准型标准型目标函数：
38、目标函数：Max S=-PMax S=-P1 1d d1 1-P P2 2(5d(5d2 2+d+d3 3+)约束方程：约束方程：6X6X1 1+4X+4X2 2+d+d1 1-d-d1 1+=280=280 2X 2X1 1+3X+3X2 2+d+d2 2-d-d2 2+=100=100 4X 4X1 1+2X+2X2 2+d+d3 3-d-d3 3+=120=120 X X1 1,X,X2 2,d,di i-,d di i+0(i=1,2,3)0(i=1,2,3)初始单纯形表初始单纯形表首先满足第一目标首先满足第一目标P P1 1进基变量进基变量X X1 1，出基变量出基变量y y3 3-
39、主元（主元（4 4）主元运算：第三行除以主元运算：第三行除以4 4主元运算：第一行加上第三行（主元运算：第一行加上第三行（-6-6）倍）倍主元运算：第二行加上第三行（主元运算：第二行加上第三行（-2-2）倍）倍重新计算检验数重新计算检验数第二行除以第二行除以2 2第一行加上第二行（第一行加上第二行（-1-1）第三行加上第二行（第三行加上第二行（-1/2-1/2）计算检验数计算检验数计算检验数计算检验数第一行乘上第一行乘上4/54/5第三行加上第一行（第三行加上第一行（3/83/8）计算检验数计算检验数最后变量最后变量 y y1 1-的检验数为的检验数为-P-P1 1+(4/5)P+(4/5)P
40、2 2由由于假定于假定P P1 1P P2 2，所以此检验数也小于零。所以此检验数也小于零。该问题的最优方案为生产该问题的最优方案为生产A A产品产品4444个单位，个单位，B B产品产品4 4个单位，个单位，利润为利润为280280百元。此时，原料百元。此时，原料正好用了正好用了100100吨，工时比原计吨，工时比原计划超了划超了6464小时。小时。例例4-114-11 设某工厂生产两种产品，都要经设某工厂生产两种产品，都要经过两道工序，有关资料如下表。假如工过两道工序，有关资料如下表。假如工序序1 1，2 2都允许加班，使得利润不少于都允许加班，使得利润不少于10001000元作为目标。又
41、以：第元作为目标。又以：第1 1，2 2工序的工序的加班工时之和尽可能在加班工时之和尽可能在160160之内为第一目之内为第一目标；产品乙必须严格控制在标；产品乙必须严格控制在7070公斤之内公斤之内为第二目标；该厂的利润越高越好为第为第二目标；该厂的利润越高越好为第三目标；尽量减少工序三目标；尽量减少工序1 1，2 2加班工时为加班工时为第四目标第四目标.试问：在上述条件下，该厂应试问：在上述条件下，该厂应如何生产？如何生产？小时小时/公斤公斤甲甲乙乙能能提供提供的工时的工时工序工序1 12 21 1100100工序工序2 21 11 18080产量上界产量上界(kg)(kg)不限不限707
42、0利润（元利润（元/kg)/kg)6 64 4解：设解：设X X1 1，X X2 2为甲，乙两种产品的生产公斤数，为甲，乙两种产品的生产公斤数，d d1 1-，d d1 1+分别为低于或超过利润分别为低于或超过利润10001000元的偏差元的偏差d d2 2-，d d2 2+分别为第分别为第1 1道工序剩余和加班的工时数道工序剩余和加班的工时数d d3 3-，d d3 3+分别为第分别为第2 2道工序剩余和加班的工时数道工序剩余和加班的工时数d d4 4-，d d4 4+为加班工时之和低于或超过为加班工时之和低于或超过160160工时数工时数由于产品由于产品X2X2必须严格控制在必须严格控制在
43、7070公斤之内为第一目公斤之内为第一目标，则可取标，则可取d d5 5-为实际公斤数不到为实际公斤数不到7070的偏差，且的偏差，且 d d5 5+=0=0。目标函数：目标函数：Min Z=PMin Z=P1 1d d4 4+P+P2 2d d5 5-+P+P3 3d d1 1-+P+P4 4(d(d2 2+d+d3 3+)约束方程：约束方程：6X6X1 1+4X+4X2 2+d+d1 1-d-d1 1+=1000=1000 2X 2X1 1+X+X2 2+d+d2 2-d-d2 2+=100=100 X X1 1+X+X2 2+d+d3 3-d-d3 3+=80=80 d d2 2+d+d
44、3 3+d d4 4-d-d4 4+=160=160 X X2 2 +d d5 5=70=70 X X1 1,X,X2 2,d,di i-,d di i+,d d5 5 0(i=1,2,3,4)0(i=1,2,3,4)目标函数：目标函数：Max s=-PMax s=-P1 1d d4 4+-P-P2 2d d5 5-P-P3 3d d1 1-P-P4 4(d(d2 2+d+d3 3+)约束方程：约束方程：6X6X1 1+4X+4X2 2+d+d1 1-d-d1 1+=1000=1000 2X 2X1 1+X+X2 2+d+d2 2-d-d2 2+=100=100 X X1 1+X+X2 2+d
45、+d3 3-d-d3 3+=80=80 d d2 2+d+d3 3+d d4 4 d d4 4+=160=160 X X2 2 +d d5 5=70=70 X X1 1,X,X2 2,d,di i-,d di i+,d d5 5 0(i=1,2,3,4)0(i=1,2,3,4)表表1 1C C0 00 0-p-p3 30 00 0-p-p4 40 0-p-p4 40 0-p-p1 1-p-p2 2C CB BX XB BX X1 1X X2 2d d1 1-d d1 1+d d2 2-d d2 2+d d3 3-d d3 3+d d4 4-d d4 4+d d5 5-b b-p-p3 3d d
46、1 1-6 64 41 1-1-10 00 00 00 00 00 00 0100010000 0d d2 2-2 21 10 00 01 1-1-10 00 00 00 00 01001000 0d d3 3-1 11 10 00 00 00 01 1-1-10 00 00 080800 0d d4 4-0 00 00 00 00 01 10 01 11 1-1-10 0160160-p-p2 2d d5 5-0 01 10 00 00 00 00 00 00 00 01 17070 p p4 40 00 00 00 00 0-1-10 0-1-10 00 00 00 0p p3 36 64
47、 40 0-1-10 00 00 00 00 00 00 010001000p p2 20 01 10 00 00 00 00 00 00 00 00 07070p p1 10 00 00 00 00 00 00 00 00 0-1-10 00 0表表1 1C C0 00 0-p-p3 30 00 0-p-p4 40 0-p-p4 40 0-p-p1 1-p-p2 2C CB BX XB BX X1 1X X2 2d d1 1-d d1 1+d d2 2-d d2 2+d d3 3-d d3 3+d d4 4-d d4 4+d d5 5-b b-p-p3 3d d1 1-6 60 01 1-1
48、-10 00 00 00 00 00 0-4-47207200 0d d2 2-2 20 00 00 01 1-1-10 00 00 00 0-1-130300 0d d3 3-1 10 00 00 00 00 01 1-1-10 00 0-1-110100 0d d4 4-0 00 00 00 00 01 10 01 11 1-1-10 01601600 0X X2 20 01 10 00 00 00 00 00 00 00 01 17070 p p4 40 00 00 00 00 0-1-10 0-1-10 00 00 00 0p p3 36 60 00 0-1-10 00 00 00 0
49、0 00 0-4-4720720p p2 20 00 00 00 00 00 00 00 00 00 0-1-10 0p p1 10 00 00 00 00 00 00 00 00 0-1-10 00 0表表1 1C C0 00 0-p-p3 30 00 0-p-p4 40 0-p-p4 40 0-p-p1 1-p-p2 2C CB BX XB BX X1 1X X2 2d d1 1-d d1 1+d d2 2-d d2 2+d d3 3-d d3 3+d d4 4-d d4 4+d d5 5-b b-p-p3 3d d1 1-0 00 01 1-1-10 00 0-6-66 60 00 02
50、 26606600 0d d2 2-0 00 00 00 01 1-1-1-2-22 20 00 01 110100 0X X1 11 10 00 00 00 00 01 1-1-10 00 0-1-110100 0d d4 4-0 00 00 00 00 01 10 01 11 1-1-10 01601600 0X X2 20 01 10 00 00 00 00 00 00 00 01 17070 p p4 40 00 00 00 00 0-1-10 0-1-10 00 00 00 0p p3 30 00 00 0-1-10 00 0-6-66 60 00 02 2660660p p2 20