《第四章目标规划优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第四章目标规划优秀PPT.ppt（76页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章目标规划第一页，本课件共有76页第二页，本课件共有76页第三页，本课件共有76页第四页，本课件共有76页第五页，本课件共有76页 线性规划把各个约束条件的重要性都不分线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。主次地等同看待，这也不符合实际情况。求解线性规划问题，首先要求约束条件必求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，就得不到问题的可行解，但生产还得继续进行，
2、这将给人们进一步应用线性规划方法带来困难。这将给人们进一步应用线性规划方法带来困难。为了弥补线性规划问题的局限性，解决有限资为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，源和计划指标之间的矛盾，在线性规划基础上，建立目标规划方法，从而使一些线性规划无法建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。解决的问题得到满意的解答。第六页，本课件共有76页第一节第一节 目标规划问题目标规划问题一、一、目标规划问题的提出目标规划问题的提出 在实际问题中，可能会同时考虑几个方在实际问题中，可能会同时考虑几个方面都达到最优：产量最高，成本最低，质量面都达
3、到最优：产量最高，成本最低，质量最好，利润最大，环境达标，运输满足等。最好，利润最大，环境达标，运输满足等。多目标规划能更好地兼顾统筹处理多种目标多目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。的关系，求得更切合实际要求的解。目标规划可根据实际情况，分主次地、目标规划可根据实际情况，分主次地、轻重缓急地考虑问题。轻重缓急地考虑问题。第七页，本课件共有76页例例1 某公司分厂用一条生产线生产两种产品某公司分厂用一条生产线生产两种产品A和和B，每周生产线运行时间为每周生产线运行时间为60小时，生产一台小时，生产一台A产品需要产品需要4小小时，生产一台时，生产一台B产品需要产品
4、需要6小时根据市场预测，小时根据市场预测，A、B产产品平均销售量分别为每周品平均销售量分别为每周9、8台，它们销售利润分别为台，它们销售利润分别为12、18万元。在制定生产计划时，经理考虑下述万元。在制定生产计划时，经理考虑下述4项目项目标：标：(1)产量不能超过市场预测的销售量；产量不能超过市场预测的销售量；(2)工人加班时间最少；工人加班时间最少；(3)希望总利润最大；希望总利润最大；(4)要尽可能满足市场需求要尽可能满足市场需求,当不能满足时当不能满足时,市场市场认为认为B产品的重要性是产品的重要性是A产品的产品的2倍。倍。试建立这个问题的数学模型试建立这个问题的数学模型第八页，本课件共
5、有76页 若把总利润最大看作目标，而把产量不能超若把总利润最大看作目标，而把产量不能超过市场预测的销售量、工人加班时间最少和要尽过市场预测的销售量、工人加班时间最少和要尽可能满足市场需求的目标看作约束，则可建立一可能满足市场需求的目标看作约束，则可建立一个单目标线性规划模型：个单目标线性规划模型：设决策变量设决策变量 x1，x2 分别为产品分别为产品A,B的产量，的产量，Max Z=12x1+18x2 第九页，本课件共有76页 容易求得上述线性规划的最优解为容易求得上述线性规划的最优解为(9,4)T 到到(3,8)T 所在线段上的点，最优目所在线段上的点，最优目标值为标值为Z*=180，即可选
6、方案有多种。即可选方案有多种。在实际上，这个结果并非完全符合决策在实际上，这个结果并非完全符合决策者的要求，它只实现了经理的第一、二、者的要求，它只实现了经理的第一、二、三条目标，而没有达到最后的一个目标。三条目标，而没有达到最后的一个目标。进一步分析可知，要实现全体目标是不进一步分析可知，要实现全体目标是不可能的。可能的。第十页，本课件共有76页 例例2 一家具制造企业，主要生产桌子、椅子两一家具制造企业，主要生产桌子、椅子两种家具，其经营环境主要受到两种资源种家具，其经营环境主要受到两种资源木工木工和油漆工每天的有效工作时间的限制。企业过和油漆工每天的有效工作时间的限制。企业过去的经营环境
7、条件如下：去的经营环境条件如下：(1)每天木工和油漆工的总有效工作时间分别为每天木工和油漆工的总有效工作时间分别为 11小时和小时和10小时。小时。(2)每生产一把椅子需要每生产一把椅子需要2小时的木工、小时的木工、1小时小时的油漆工。的油漆工。(3)每生产一张桌子需要每生产一张桌子需要1小时的木工、小时的木工、2小时小时的油漆工。的油漆工。第十一页，本课件共有76页(4)每生产一把椅子和一张桌子分别可获利润每生产一把椅子和一张桌子分别可获利润 8元、元、10元。元。求解此线性规划问题可以得到最优方案：求解此线性规划问题可以得到最优方案：每天生产椅子每天生产椅子 4 把，桌子把，桌子 3 张，
8、获最大利润张，获最大利润 62 元。元。企业过去一直以如何计划两种家具的生企业过去一直以如何计划两种家具的生产量才能获得最大总利润为其生产、经营的产量才能获得最大总利润为其生产、经营的唯一目标。然而，市场经济环境下新的问题唯一目标。然而，市场经济环境下新的问题出现了，它迫使企业不得不考虑出现了，它迫使企业不得不考虑.第十二页，本课件共有76页（1）首先，根据市场信息，椅子的销售量已有下）首先，根据市场信息，椅子的销售量已有下降的趋势，故应果断决策减少椅子的产量，其产量降的趋势，故应果断决策减少椅子的产量，其产量最好不大于桌子的产量。最好不大于桌子的产量。（2）其次，市场上找不到符合生产质量要求
9、的木）其次，市场上找不到符合生产质量要求的木工了，因此决不可能考虑增加木工这种资源来增加工了，因此决不可能考虑增加木工这种资源来增加产量，并且由于某种原因木工决不可能加班。产量，并且由于某种原因木工决不可能加班。（3）再其次，应尽可能充分利用油漆工的有效）再其次，应尽可能充分利用油漆工的有效工作时间，但油漆工希望最好不加班。工作时间，但油漆工希望最好不加班。（4）最后，企业考虑最好达到并超过预计利润指）最后，企业考虑最好达到并超过预计利润指标标 56元。元。第十三页，本课件共有76页 二、目标规划模型的基本概念二、目标规划模型的基本概念 把例把例1的的4个目标表示为不等式，仍设决个目标表示为不
10、等式，仍设决策变量策变量 x1，x2 分别为产品分别为产品A，B的产量。那么，的产量。那么，第一个目标为第一个目标为:x1 9，x2 8；第二个目标为第二个目标为:4x1+6x2 60；第三个目标为第三个目标为:希望总利润最大，要表示希望总利润最大，要表示成不等式需要找到一个目标上界，这里可成不等式需要找到一个目标上界，这里可以估计为以估计为252（=12 9+18 8），于是有），于是有 12x1+18x2 252；第四个目标为第四个目标为:x19，x28；第十四页，本课件共有76页下面引入与建立目标规划数学模型有关的概念下面引入与建立目标规划数学模型有关的概念1正、负偏差变量正、负偏差变量
11、d+，d-我们用正偏差变量我们用正偏差变量d+表示决策值超过目标值的表示决策值超过目标值的部分；负偏差变量部分；负偏差变量d-表示决策值不足目标值的部分。表示决策值不足目标值的部分。因决策值不可能既超过目标值同时又末达到目标值，故因决策值不可能既超过目标值同时又末达到目标值，故恒有恒有 d+d-0。2绝对约束和目标约束绝对约束和目标约束 我们把所有等式、不等式约束分为两部分：绝对我们把所有等式、不等式约束分为两部分：绝对约束和目标约束。绝对约束是指必须严格满足的等式约束和目标约束。绝对约束是指必须严格满足的等式约束和不等式约束；如在线性规划问题中考虑的约束约束和不等式约束；如在线性规划问题中考
12、虑的约束条件，不能满足这些约束条件的解称为非可行解，所条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。如例以它们是硬约束。如例1 中生产中生产A，B产品所需原材料产品所需原材料数量有限制，并且无法从其它渠道予以补充，则构成数量有限制，并且无法从其它渠道予以补充，则构成绝对约束。绝对约束。第十五页，本课件共有76页 目标约束是目标规划特有的，目标约束目标约束是目标规划特有的，目标约束具有更大的弹性，我们可以把约束右端项看具有更大的弹性，我们可以把约束右端项看作要努力追求的目标值，但允许结果与所制作要努力追求的目标值，但允许结果与所制定的目标值存在正或负的偏差，用在约束中定的目标值存
13、在正或负的偏差，用在约束中加入正、负偏差变量来表示，于是称它们是加入正、负偏差变量来表示，于是称它们是软约束。软约束。对于例对于例1，我们有如下目标约束，我们有如下目标约束 x1 +d1-d1+=9 (4.1)x2+d2-d2+=8 (4.2)4x1+6x2+d3-d3+=60 (4.3)12x1+18x2+d4-d4+=252 (4.4)第十六页，本课件共有76页3优先因子与权系数优先因子与权系数 对于多目标问题，决策者在要求达到这些目标对于多目标问题，决策者在要求达到这些目标是，是有主次或轻重缓急的不同。多个目标之间有相是，是有主次或轻重缓急的不同。多个目标之间有相互冲突时，决策者首先必须
14、对目标排序。设置各目标互冲突时，决策者首先必须对目标排序。设置各目标的优先因子，依据优先因子的大小确定目标顺序。的优先因子，依据优先因子的大小确定目标顺序。要求第一位达到的目标赋予优先因子要求第一位达到的目标赋予优先因子P1，次位，次位的目标赋予优先因子的目标赋予优先因子P2，并规定，并规定PkPk+1，k=1,2,，K。表示。表示Pk比比Pk+1有更大的优先权。即首有更大的优先权。即首先保证先保证P1级目标的实现，这时可不考虑次级目标；级目标的实现，这时可不考虑次级目标；而而P2级目标是在实现级目标是在实现P1级目标的基础上考虑的；依级目标的基础上考虑的；依此类推。若要区别具有相同优先因子的
15、两个目标的此类推。若要区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数差别，这时可分别赋予它们不同的权系数j，这些都，这些都由决策者按具体情况而定。由决策者按具体情况而定。第十七页，本课件共有76页4目标规划的目标函数目标规划的目标函数 目标规划的目标函数是通过各目标约束的正、负目标规划的目标函数是通过各目标约束的正、负偏差变量和赋于相应的优先等级来构造的。当每一目偏差变量和赋于相应的优先等级来构造的。当每一目标值确定后，决策者的要求是尽可能从某个方向缩小标值确定后，决策者的要求是尽可能从某个方向缩小偏离目标的数值。于是，目标规划的目标函数应该是偏离目标的数值。于是，目标规
16、划的目标函数应该是求极小：求极小：min f f（d+，d-)。其基本形式有三种：。其基本形式有三种：（1）要求恰好达到目标值，即使相应目标约束的）要求恰好达到目标值，即使相应目标约束的正、负偏差变量都要尽可能地小。这时取正、负偏差变量都要尽可能地小。这时取 min（d+d-)；（2）要求不超过目标值，即使相应目标约束的）要求不超过目标值，即使相应目标约束的正偏差变量要尽可能地小。这时取正偏差变量要尽可能地小。这时取 min（d+)；（3）要求不低于目标值，即使相应目标约束的负偏）要求不低于目标值，即使相应目标约束的负偏差变量要尽可能地小。这时取差变量要尽可能地小。这时取 min（d-)；第十
17、八页，本课件共有76页 目标规划的目标函数中包含了多个目标，目标规划的目标函数中包含了多个目标，决策者对于具有相同重要性的目标可以合并为一决策者对于具有相同重要性的目标可以合并为一个目标，如果同一目标中还想分出先后次序，可个目标，如果同一目标中还想分出先后次序，可以赋予不同的权系数，按系数大小再排序。以赋予不同的权系数，按系数大小再排序。对于例对于例1,我们根据决策者的考虑知我们根据决策者的考虑知 第一优先级要求第一优先级要求 min（d1+d2+)；第二优先级要求第二优先级要求 min（d3+)；第三优先级要求第三优先级要求 min（d4-）；）；第四优先级要求第四优先级要求 min（d1-
18、+2d2-），这里，当），这里，当不能满足市场需求时，市场认为不能满足市场需求时，市场认为B产品的重要性是产品的重要性是A产产品的品的2倍即减少倍即减少B产品的影响是产品的影响是A产品的产品的2倍，因此倍，因此我们引入了我们引入了2:1的权系数。的权系数。第十九页，本课件共有76页 综合上述分析，我们可得到下列目标规综合上述分析，我们可得到下列目标规划模型划模型:Min f=P1（d1+d2+)+P2 d3+P3 d4-+P4（d1-+2d2-)(4.5)第二十页，本课件共有76页三、目标规划模型的一般形式三、目标规划模型的一般形式 根据上面讨论根据上面讨论,我们可以得到目标规划的一我们可以得
19、到目标规划的一般形式如下般形式如下第二十一页，本课件共有76页例例例例3：某车间有：某车间有：某车间有：某车间有A、B两条设备相同的生产线，它两条设备相同的生产线，它两条设备相同的生产线，它两条设备相同的生产线，它们生产同一种产品。们生产同一种产品。们生产同一种产品。们生产同一种产品。A A生产线每小时可制造生产线每小时可制造生产线每小时可制造生产线每小时可制造2件产品，件产品，件产品，件产品，B B生产线每小时可制造生产线每小时可制造生产线每小时可制造生产线每小时可制造1.5件产品。如果每周正常件产品。如果每周正常工作时数为工作时数为45小时，要求制定完成下列目标的生小时，要求制定完成下列目
20、标的生小时，要求制定完成下列目标的生小时，要求制定完成下列目标的生产计划：产计划：产计划：产计划：（1）生产量达到）生产量达到210件件/周；周；周；周；（2）A A生产线加班时间限制在生产线加班时间限制在1515小时内；小时内；（3）充分利用工时指标，并依）充分利用工时指标，并依A、B产量的比例产量的比例确定重要性。确定重要性。建立目标规划的数学模型时，需要确定目标值、建立目标规划的数学模型时，需要确定目标值、优先等级、权系数等，它都具有一定的主观性和优先等级、权系数等，它都具有一定的主观性和模糊性，可以用专家评定法给以量化。模糊性，可以用专家评定法给以量化。第二十二页，本课件共有76页解：
21、解：设设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小时内）小时内）第二十三页，本课件共有76页 X1 +d3-d3+=45 （充分利用（充分利用A的工时指标）的工时指标）X2+d4-d4+=45 （充分利用（充分利用B的工时指标）的工时指标）X1,X2,di-,di+0(i=
22、1,2,3,4)第二十四页，本课件共有76页A，B的产量比例的产量比例2：1.5=4:3目标函数：目标函数：Min S=P1d1-+P2d2+4 P3d3-+3 P3d4-约束方程：约束方程：2X1+1.5X2+d1-d1+=210 X1 +d2-d2+=60 X1 +d3-d3+=45 X2+d4-d4+=45 X1,X2,di-,di+0(i=1,2,3,4)第二十五页，本课件共有76页例例4：某电器公司经营的唱机和录音机均有车间：某电器公司经营的唱机和录音机均有车间A、B流水作业组装。数据见下表。流水作业组装。数据见下表。要求按以下目标制订月生产计划：要求按以下目标制订月生产计划：（1）
23、库存费用不超过）库存费用不超过4600元；元；（2）每月销售唱机不少于）每月销售唱机不少于80台；台；（3）不使）不使A、B车间停工车间停工(权数由生产费用确定权数由生产费用确定)；（4）A车间加班时间限制在车间加班时间限制在20小时内；小时内；（5）每月销售录音机为）每月销售录音机为100台；台；（6）两车间加班时数总和要尽可能小（权数由）两车间加班时数总和要尽可能小（权数由生产费用确定）；生产费用确定）；第二十六页，本课件共有76页第二十七页，本课件共有76页解：设每月生产唱机、录音机解：设每月生产唱机、录音机X1，X2台。且台。且A、B的生产费用之比为的生产费用之比为100：50=2：1
24、目标函数：目标函数：Min S=P1d1+P2d2-+2 P3d4-+P3d5-+P4d41+P5d3-+P5d3+2P6d4+P6d5+约束方程：约束方程：50X1+30X2+d1-d1+=4600 （库存费用不超过（库存费用不超过4600元）元）X1 +d2-d2+=80 （每月销售唱机不少于（每月销售唱机不少于80台）台）第二十八页，本课件共有76页 X2+d3-d3+=100 （每月销售录音机为（每月销售录音机为100台）台）2X1+X2+d4-d4+=180 （不使（不使A车间停工）车间停工）X1+3X2+d5-d5+=200 （不使（不使B车间停工）车间停工）d4+d41-d41+
25、=20 （A车间加班时间限制在车间加班时间限制在20小时内）小时内）X1,X2,di-,di+,d41-,d41+0(i=1,2,3,4,5)第二十九页，本课件共有76页目标函数：目标函数：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,
26、5)第三十页，本课件共有76页例例5 某单位领导在考虑本单位职工的升某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：级调资方案时，依次遵守以下规定：(1)不超过年工资总额不超过年工资总额60000元；元；(2)每级的人数不超过定编规定的人数；每级的人数不超过定编规定的人数；(3)，级的升级面尽可能达到现有人级的升级面尽可能达到现有人数的数的20%，且无越级提升；，且无越级提升；(4)级不足编制的人数可录用新职工，又级不足编制的人数可录用新职工，又级的职工中有级的职工中有10%要退休。要退休。有关资料汇总于表有关资料汇总于表4.1中，问该领导应如何中，问该领导应如何拟订一个满意的方
27、案。拟订一个满意的方案。第三十一页，本课件共有76页 表表4.1等等级级工工资额资额(元元/年年)现现有人数有人数编编制人数制人数200020001500150010001000101012121515121215151515合合计计37374242解：解：设设x1、x2、x3分别表示提升到分别表示提升到、级和级和录用到录用到级的新职工人数。对各目标确定的优先因级的新职工人数。对各目标确定的优先因子为：子为：P1不超过年工资总额不超过年工资总额60000元；元；P2每级的人数不超过定编规定的人数；每级的人数不超过定编规定的人数；P3、级的升级面尽可能达到现有人数级的升级面尽可能达到现有人数的的
28、20%。第三十二页，本课件共有76页 先分别建立各目标约束。先分别建立各目标约束。年工资总额不超过年工资总额不超过60000元：元：2000(10-100.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1-d1+=60000 每级的人数不超过定编规定的人数：每级的人数不超过定编规定的人数：对对级有级有 10(1-0.1)+x1+d2-d2+=12对对级有级有 12-x1+x2+d3-d3+=15对对级有级有 15-x2+x3+d4-d4+=15，级的升级面不大于现有人数的级的升级面不大于现有人数的20%，但尽可能多，但尽可能多提；提；对对级有级有 x1+d5-d5+
29、=120.2对对级有级有 x2+d6-d6+=150.2目标函数：目标函数：min z=P1 d1+P2(d2+d3+d4+)+P3(d5-+d6-)第三十三页，本课件共有76页第二节第二节 目标规划的图解法目标规划的图解法 对只具有两个决策变量的目标规划的数对只具有两个决策变量的目标规划的数学模型，我们可以用图解法来分析求解。通过学模型，我们可以用图解法来分析求解。通过图解示例，可以看到目标规划中优先因子，正、图解示例，可以看到目标规划中优先因子，正、负偏差变量及权系数等的几何意义。负偏差变量及权系数等的几何意义。例例6 Min S=d1+X1+2X2+d1-d1+=10 X1+2X2 6
30、X1+X2 4 X1,X2,d1-,d1+0第三十四页，本课件共有76页x1x204681021342X1+2X2 6第三十五页，本课件共有76页x1x204681021342X X1+X+X2 4 4第三十六页，本课件共有76页x1x204681021342第三十七页，本课件共有76页x1x204681021342第三十八页，本课件共有76页x1x204681021342x x1 1+2x+2x2 2=10=105d1 1+d1 1-AB(2,2)第三十九页，本课件共有76页x1x204681021342x x1 1+2x+2x2 2=10=105d1 1+d1 1-AB(2,2)当当 Mi
31、n S=d1+达到时达到时 d1+=0第四十页，本课件共有76页x1x204681021342x x1 1+2x+2x2 2=10=105d1 1-AB(2,2)当当 Min S=d1+达到时达到时 d1+=0第四十一页，本课件共有76页x1x204681021342x x1 1+2x+2x2 2+d1-=10 d1 1-=25d1 1-AB(2,2)当当 Min S=d1+达到时达到时 d1+=0第四十二页，本课件共有76页x1x204681021342x x1 1+2x+2x2+d1 1-=10 d=10 d1 1-=4=45d1 1-AB(2,2)有无穷多解：点（有无穷多解：点（0，3）
32、和点（和点（2，2）连线上的点）连线上的点都是最优解。都是最优解。(0,3)第四十三页，本课件共有76页x1x204681021342x1 1+2x+2x2 2+d1 1-=10 d1 1-=65d1 1-AB(2,2)有无穷多解：点（有无穷多解：点（4，0）和）和点（点（0，2）连线上的点都是）连线上的点都是最优解。最优解。(0,3)(4,0)(0,2)第四十四页，本课件共有76页x1x204681021342x1+2x2 2+d1 1-=10 d=10 d1 1-=7=75d1 1-AB(2,2)有无穷多解：点（有无穷多解：点（1，1）和点（和点（0，3/2）（3，0）连线上的点都是最优解
33、。连线上的点都是最优解。(0,3)(4,0)(1,1)第四十五页，本课件共有76页例例4-9 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)第四十六页，本课件共有76页x1x2020304050101030402050d1 1-d1 1+X X1 1+X+X2 2=40=40第四十七页，本课件共有76页x1x2020304050101030402050d1 1-d1 1+d2 2+d2 2-X X1 1+X+X2 2=50=5
34、0第四十八页，本课件共有76页x1x2020304050101030402050d1 1-d1 1+d2 2+d2 2-d3 3-X X1 1=30=30第四十九页，本课件共有76页x1x2020304050101030402050d1 1-d1 1+d2 2+d2 2-d3 3-d4 4-X X2 2=30=30第五十页，本课件共有76页x1x2020304050101030402050d1 1+d2 2+d2 2-d3 3-d4 4-Min d1-=0可行域如图可行域如图第五十一页，本课件共有76页x1x2020304050101030402050d1 1+d2 2-d3 3-d4 4-M
35、in d2+=0可行域如图可行域如图第五十二页，本课件共有76页x1x2020304050101030402050d1 1+d2 2-d4 4-Min d3-=0 线段线段AB是可行域是可行域AB第五十三页，本课件共有76页x1x2020304050101030402050d2 2-d4 4-Min d1+=0P=(30,10)唯一唯一最优解。最优解。d d2 2-=10 d d4 4-=20=20P第五十四页，本课件共有76页例例4-10 Min S=P1d1-+P2d2+P3d3-+P3d4-5X1+10X2+d1-d1+=100 2X1+X2+d2-d2+=14 X1 +d3-d3+=6
36、 X2+d4-d4+=10 X1,X2,di-,di+0(i=1,2,3,4)第五十五页，本课件共有76页x1x20101520255515201025d1 1+d1 1-5X5X1 1+10X+10X2 2=100=100第五十六页，本课件共有76页x1x20101520255515201025d1 1+d1 1-d2 2+d2 2-2X2X1 1+X+X2 2=14=14第五十七页，本课件共有76页x1x20101520255515201025d1 1+d1 1-d2 2+d2 2-d3 3+d3 3-X X1 1 =6=6第五十八页，本课件共有76页x1x2010152025551520
37、1025d1 1+d1 1-d2 2+d2 2-d3 3+d3 3-d4 4+d4 4-X X2 2=10=10第五十九页，本课件共有76页x1x20101520255515201025d1 1+d2 2+d2 2-d3 3+d3 3-d4 4+d4 4-Min d1-=0第六十页，本课件共有76页x1x20101520255515201025d1 1+d2 2-d3 3+d3 3-d4 4+d4 4-Min d2+=0可行域如图可行域如图第六十一页，本课件共有76页x1x20101520255515201025d1 1+d2 2-d3 3+d4 4+d4 4-Min d3-=0可行域为空如图
38、可行域为空如图第六十二页，本课件共有76页x1x20101520255515201025d1 1+d2 2-d3 3+d4 4+Min d3-0Min d4-=0可行域如图可行域如图d3 3-(2,10)第六十三页，本课件共有76页x1x20101520255515201025d1 1+d2 2-d3 3+d4 4+Min d3-=0Min d4-0可行域为空如图可行域为空如图d4 4-第六十四页，本课件共有76页对于目标对于目标P1与目标与目标P2很容易达到。目标很容易达到。目标P3的两个指标不能同时满足，否则无解。的两个指标不能同时满足，否则无解。又因为又因为P3中的两个目标同样重要，要讨
39、中的两个目标同样重要，要讨论论 （1）Min d3-=0 Min d4-0 原问题无解。原问题无解。（2）Min d3-0 Min d4-=0原问题原问题(2,10)是次优解。是次优解。第六十五页，本课件共有76页例例4-11 Min S=P1d1-+P1d2-X1 +d1-d1+=15 4X1+5X2+d2-d2+=200 3X1+4X2 120 X1-2X2 15 X1,X2,di-,di+0(i=1,2)第六十六页，本课件共有76页x1x2020304050101030402050d1 1+d1 1-X X1 1=15=15第六十七页，本课件共有76页x1x202030405010103
40、0402050d1 1+d1 1-d2 2+d2 2-4X4X1 1+5X+5X2 2=200=200第六十八页，本课件共有76页x1x2020304050101030402050d1 1+d1 1-d2 2+d2 2-3X3X1 1+4X+4X2 2 120 120第六十九页，本课件共有76页x1x2020304050101030402050d1 1+d1 1-d2 2+d2 2-X X1 1-2X-2X2 2 1515第七十页，本课件共有76页x1x2020304050101030402050d1 1+d1 1-d2 2+d2 2-第七十一页，本课件共有76页x1x202030405010
41、1030402050d1 1+d2 2+同时考虑同时考虑 d1-=0,d2-=0 原问题无解。原问题无解。第七十二页，本课件共有76页例例6已知有三个产地给四个销地供应某种产品，产销已知有三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价见表地之间的供需量和单位运价见表4.2。有关部门在研究调。有关部门在研究调运方案时依次考虑以下七项目标，并规定其相应的优运方案时依次考虑以下七项目标，并规定其相应的优先等级：先等级：P1B4是重点保证单位，必须全部满足其需要；是重点保证单位，必须全部满足其需要；P2A3向向B1提供的产量不少于提供的产量不少于100；P3每个销地的供应量不小于其需要量
42、的每个销地的供应量不小于其需要量的80%；P4所定调运方案的总运费不超过最小运费调运方案的所定调运方案的总运费不超过最小运费调运方案的10%；P5因路段的问题，尽量避免安排将因路段的问题，尽量避免安排将A2的产品往的产品往B4；P6给给B1和和B3的供应率要相同；的供应率要相同；P7力求总运费最省。力求总运费最省。建立目标规划模型。建立目标规划模型。第七十三页，本课件共有76页 表表4.2 销销地地产产地地B1B2B3B4产产量量A1A2A3534255642763300200400销销 量量200100450250900/1000第七十四页，本课件共有76页解：解：供应约束：供应约束：x11
43、+x12+x13+x14 300 x21+x22+x23+x24 200 x31+x32+x33+x34 400需求约束：需求约束：x11+x21+x31+d1-d1+=200 x12+x22+x32+d2-d2+=100 x13+x23+x33+d3-d3+=450 x14+x24+x34+d4-d4+=250A3向向B1提供的产品量不少于提供的产品量不少于100 x31+d5-d5+=100每个销地的供应量不小于其需要量的每个销地的供应量不小于其需要量的80%x11+x21+x31+d6-d6+=2000.8x12+x22+x32+d7-d7+=1000.8x13+x23+x33+d8-d
44、8+=4500.8x14+x24+x34+d9-d9+=2500.8第七十五页，本课件共有76页解：解：供应约束：供应约束：x11+x12+x13+x14 300 x21+x22+x23+x24 200 x31+x32+x33+x34 400需求约束：需求约束：x11+x21+x31+d1-d1+=200 x12+x22+x32+d2-d2+=100 x13+x23+x33+d3-d3+=450 x14+x24+x34+d4-d4+=250A3向向B1提供的产品量不少于提供的产品量不少于100 x31+d5-d5+=100每个销地的供应量不小于其需要量的每个销地的供应量不小于其需要量的80%x11+x21+x31+d6-d6+=2000.8x12+x22+x32+d7-d7+=1000.8x13+x23+x33+d8-d8+=4500.8x14+x24+x34+d9-d9+=2500.8第七十六页，本课件共有76页