运筹学第三版清华大学出版社第4章目标规划课件.ppt

1、第第 4 4 章章目目 标标 规规 划划第第4章章 目标规划目标规划 在科学研究、经济建设和生产实践中，人在科学研究、经济建设和生产实践中，人们经常遇到一类含有多个目标的数学规划问题，们经常遇到一类含有多个目标的数学规划问题，我们称之为多目标规划。本章介绍一种特殊的多我们称之为多目标规划。本章介绍一种特殊的多目标规划叫目标规划目标规划叫目标规划(goal programming)，这这是美国学者是美国学者Charnes等在等在1952年提出来的。目标年提出来的。目标规划在实践中的应用十分广泛，它的重要特点是规划在实践中的应用十分广泛，它的重要特点是对各个目标分级加权与逐级优化，这符合人们处对各

2、个目标分级加权与逐级优化，这符合人们处理问题要分别轻重缓急保证重点的思考方式。理问题要分别轻重缓急保证重点的思考方式。本章分目标规划模型、目标规划的几何意义本章分目标规划模型、目标规划的几何意义与图解法和求解目标规划的单纯形方法等三个部与图解法和求解目标规划的单纯形方法等三个部分进行介绍。分进行介绍。第第1节节 目标规划的数学模型目标规划的数学模型 1.问题提出问题提出 为了便于理解目标规划数学模型的特征及为了便于理解目标规划数学模型的特征及建模思路建模思路,我们首先举一个简单的例子来说明我们首先举一个简单的例子来说明.例例4.1 某公司分厂用一条生产线生产两种某公司分厂用一条生产线生产两种产

3、品产品A和和B，每周生产线运行时间为每周生产线运行时间为60小时，小时，生产一台生产一台A产品需要产品需要4小时，生产一台小时，生产一台B产品需产品需要要6小时根据市场预测，小时根据市场预测，A、B产品平均销售产品平均销售量分别为每周量分别为每周9、8台，它们销售利润分别为台，它们销售利润分别为12、18万元。在制定生产计划时，经理考虑下述万元。在制定生产计划时，经理考虑下述4项目标：项目标：目标规划模型目标规划模型 1.问题提出问题提出(续续)首先，产量不能超过市场预测的销售量；首先，产量不能超过市场预测的销售量；其次，工人加班时间最少；其次，工人加班时间最少；第三，希望总利润最大；第三，希

4、望总利润最大；最后，要尽可能满足市场需求最后，要尽可能满足市场需求,当不能满当不能满足时足时,市场认为市场认为B产品的重要性是产品的重要性是A产品的产品的2倍倍 试建立这个问题的数学模型试建立这个问题的数学模型讨论：讨论：若把总利润最大看作目标，而把产量不能若把总利润最大看作目标，而把产量不能超过市场预测超过市场预测目标规划模型目标规划模型 1.问题提出问题提出(续续)的销售量、工人加班时间最少和要尽可能满足的销售量、工人加班时间最少和要尽可能满足市场需求的目标看作约束，则可建立一个单目市场需求的目标看作约束，则可建立一个单目标线性规划模型标线性规划模型 设决策变量设决策变量 x1，x2 分别

5、为产品分别为产品A，B的产量的产量 Max Z=12x1+18x2 s.t.4x1+6x2 60 x1 9 x2 8 x1,x2 0目标规划模型目标规划模型 1.问题提出问题提出(续续)容易求得上述线性规划的最优解为容易求得上述线性规划的最优解为(9,4)T 到到(3,8)T 所在线段上的点所在线段上的点,最优目标值为最优目标值为Z*=180,即可选方案有多种即可选方案有多种.在实际上在实际上,这个结果并非完全符合决策者这个结果并非完全符合决策者的要求的要求,它只实现了经理的第一、二、三条目它只实现了经理的第一、二、三条目标，而没有达到最后的一个目标。进一步分标，而没有达到最后的一个目标。进一

6、步分析可知，要实现全体目标是不可能的。析可知，要实现全体目标是不可能的。目标规划模型目标规划模型 2.目标规划模型的基本概念目标规划模型的基本概念 把例把例4.1的的4个目标表示为不等式个目标表示为不等式.仍设决仍设决策变量策变量 x1，x2 分别为产品分别为产品A，B的产量的产量.那麽那麽,第一个目标为第一个目标为:x1 9，x2 8；第二个目标为第二个目标为:4x1+6x2 60；第三个目标为第三个目标为:希望总利润最大，要表示成希望总利润最大，要表示成不等式需要找到一个目标上界，这里可以估不等式需要找到一个目标上界，这里可以估计为计为252（=12 9+18 8），于是有），于是有 12

7、x1+18x2 252；第四个目标为第四个目标为:x1 9，x2 8；目标规划模型目标规划模型 2.目标规划模型的基本概念目标规划模型的基本概念（续）（续）下面引入与建立目标规划数学模型有关的概下面引入与建立目标规划数学模型有关的概念念 （1）正、负偏差变量）正、负偏差变量d+，d-我们用正偏差变量我们用正偏差变量d+表示决策值超过目标值表示决策值超过目标值的部分；负偏差变量的部分；负偏差变量d-表示决策值不足目标值的部表示决策值不足目标值的部分。因决策值不可能既超过目标值同时又末达到目分。因决策值不可能既超过目标值同时又末达到目标值，故恒有标值，故恒有 d+d-0 （2）绝对约束和目标约束绝

8、对约束和目标约束 我们把所有等式、不等式约束分为两部分：绝我们把所有等式、不等式约束分为两部分：绝对约束和目标约束。对约束和目标约束。目标规划模型目标规划模型 2.目标规划模型的基本概念目标规划模型的基本概念（续）（续）绝对约束绝对约束是指必须严格满足的等式约束和是指必须严格满足的等式约束和不等式约束；如在线性规划问题中考虑的约不等式约束；如在线性规划问题中考虑的约束条件，不能满足这些约束条件的解称为非束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。设例可行解，所以它们是硬约束。设例7.1.1 中生中生产产A，B产品所需原材料数量有限制，并且无产品所需原材料数量有限制，并且无法

9、从其它渠道予以补充，则构成绝对约束。法从其它渠道予以补充，则构成绝对约束。目标约束目标约束是目标规划特有的，我们可以把是目标规划特有的，我们可以把约束右端项看作要努力追求的目标值，但允约束右端项看作要努力追求的目标值，但允许发生正式负偏差，用在约束中加入正、负许发生正式负偏差，用在约束中加入正、负偏差变量来表示，于是称它们是软约束。偏差变量来表示，于是称它们是软约束。目标规划模型目标规划模型 2.目标规划模型的基本概念目标规划模型的基本概念（续）（续）对于例对于例4.1,我们有如下目标约束我们有如下目标约束 x1 +d1-d1+=9 (4-1)x2+d2-d2+=8 (4-2)4x1+6x2+

10、d3-d3+=60 (4-3)12x1+18x2+d4-d4+=252 (4-4)目标规划模型目标规划模型 2.目标规划模型的基本概念目标规划模型的基本概念（续）（续）(3)优先因子与权系数优先因子与权系数 对于多目标问题，设有对于多目标问题，设有L个目标函数个目标函数f1,f2,fL,决策者在要求达到这些目标时，一决策者在要求达到这些目标时，一般有主次之分。为此，我们引入优先因子般有主次之分。为此，我们引入优先因子Pi，i=1,2,L.无妨设预期的目标函数优先顺序无妨设预期的目标函数优先顺序为为f1,f2,fL,我们把要求第一位达到的目标赋我们把要求第一位达到的目标赋于优先因子于优先因子P1

11、，次位的目标赋于优先因子次位的目标赋于优先因子P2、，并规定并规定 Pi Pi+1，i=1,2,L-1.目标规划模型目标规划模型 2.目标规划模型的基本概念目标规划模型的基本概念（续）（续）即在计算过程中即在计算过程中,首先保证首先保证P1级目标的实现，级目标的实现，这时可不考虑次级目标；而这时可不考虑次级目标；而P2级目标是在实现级目标是在实现P1级目标的基础上考虑的，以此类推。当需要级目标的基础上考虑的，以此类推。当需要区别具有相同优先因子的若干个目标的差别时，区别具有相同优先因子的若干个目标的差别时，可分别赋于它们不同的权系数可分别赋于它们不同的权系数wj。优先因子及优先因子及权系数的值

12、，均由决策者按具体情况来确定权系数的值，均由决策者按具体情况来确定 （4）目标规划的目标函效）目标规划的目标函效 目标规划的目标函数是通过各目标约束的目标规划的目标函数是通过各目标约束的正、负偏差变量和赋于相应的优先等级来构造正、负偏差变量和赋于相应的优先等级来构造的的目标规划模型目标规划模型 2.目标规划模型的基本概念目标规划模型的基本概念（续）（续）决策者的要求是尽可能从某个方向缩小偏决策者的要求是尽可能从某个方向缩小偏离目标的数值。于是，目标规划的目标函数离目标的数值。于是，目标规划的目标函数应该是求极小：应该是求极小：min f f（d+，d-)其基本形式有三种其基本形式有三种：（1）

13、要求恰好达到目标值，即使相要求恰好达到目标值，即使相应目标约束的正、负偏差变量都要尽可应目标约束的正、负偏差变量都要尽可能地小。这时取能地小。这时取 min（d+d-)；（2）要求不超过目标值，即使相应要求不超过目标值，即使相应目标约束的正偏差变量要尽可能地小。目标约束的正偏差变量要尽可能地小。这时取这时取 min（d+)；目标规划模型目标规划模型 2.目标规划模型的基本概念目标规划模型的基本概念（续）（续）（3）要求不低于目标值，即使相应目标约要求不低于目标值，即使相应目标约束的负偏差变量要尽可能地小。这时取束的负偏差变量要尽可能地小。这时取 min（d-)；对于例对于例4.1,我们根据决策

14、者的考虑知我们根据决策者的考虑知 第一优先级要求第一优先级要求 min（d1+d2+)；第二优先级要求第二优先级要求 min（d3+)；第三优先级要求第三优先级要求 min（d4-)；第四优先级要求第四优先级要求 min（d1-+2d2-)，这里这里,当当不能满足市场需求时不能满足市场需求时,市场认为市场认为B产品的重要性是产品的重要性是A产品的产品的2倍即减少倍即减少B产品的影响是产品的影响是A产品的产品的2倍，倍，因此我们引入了因此我们引入了2:1的权系数。的权系数。目标规划模型目标规划模型 2.目标规划模型的基本概念目标规划模型的基本概念（续）（续）综合上述分析，我们可得到下列目标规划模

15、型综合上述分析，我们可得到下列目标规划模型 Min f=P1（d1+d2+)+P2 d3+P3 d4-+P4（d1-+2d2-)s.t.x1 +d1-d1+=9 x2+d2-d2+=8 4x1+6x2+d3-d3+=60 (4.1.5)12x1+18x2+d4-d4+=252 x1,x2,di-,di+0 ,i=1,2,3,4.目标规划模型目标规划模型 3.目标规划模型的一般形式目标规划模型的一般形式 根据上面讨论根据上面讨论,我们可以得到目标规划的一我们可以得到目标规划的一般形式如下般形式如下（LGP）中的第二行是中的第二行是K个目标约束，第三行是个目标约束，第三行是m个绝对约束，个绝对约束

16、，ckj 和和gk 是目标参数。是目标参数。KknjddxmibxaKkgddxcddPkkjnjijijnjkkkjkjLlKkklkklkl,2,1,2,1,0,2,1,),(,2,1,.s.t)(min)LGP(1111第第2节节 目标规划的图解法目标规划的图解法 对只具有两个决策变量的目对只具有两个决策变量的目标规划的数学模型，我们可以用图标规划的数学模型，我们可以用图解法来分析求解通过图解示例，解法来分析求解通过图解示例，可以看到目标规划中优先因子，正、可以看到目标规划中优先因子，正、负偏差变量及权系数等的几何意义。负偏差变量及权系数等的几何意义。下面用图解法来求解例下面用图解法来求

17、解例4-1。我们先在平面直角坐标系的第一象我们先在平面直角坐标系的第一象限内，作出与各约束条件对应的直线，限内，作出与各约束条件对应的直线，然后在这些直线旁分别标上然后在这些直线旁分别标上 G-i，i=1，2，3，4。图中图中x，y分别表示问题（分别表示问题（4-5）的的x1和和x2；各直线移动使之函数值变大、各直线移动使之函数值变大、变小的方向用变小的方向用+、-表示表示 di+,di-（如图如图4-1所示）所示）目标规划的几何意义及图解法目标规划的几何意义及图解法0 5 10 15 20 y x2015105+-G-1+-G-2+-G-4+-G-3图4-1 下面我们根据目标函数的优先因子来

18、分析下面我们根据目标函数的优先因子来分析求解首先考虑第一级具有求解首先考虑第一级具有P1优先因子的目优先因子的目标的实现，在目标函数中要求实现标的实现，在目标函数中要求实现min（d1+d2+),取取d1+=d2+=0.图图 4 2 中阴影部分即表示中阴影部分即表示出该最优解集合的所有点。出该最优解集合的所有点。我们在第一级目标的最优解集合中找满足我们在第一级目标的最优解集合中找满足第二优先级要求第二优先级要求min（d3+)的最优解的最优解.取取d3+=0,可得到图可得到图 4 3 中阴影部分即是满足第一、中阴影部分即是满足第一、第二优先级要求的最优解集合。第二优先级要求的最优解集合。目标规

19、划的几何意义及图解法目标规划的几何意义及图解法图4-20 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)图4 3 0 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)目标规划的几何意义及图解法目标规划的几何意义及图解法 第三优先级要求第三优先级要求 min（d4-)，根据图示可根据图示可知，知，d4-不可能取不可能取0值，我们取使值，我们取使d4-最小的值最小的值72得到图得到图44 中两阴影部分的交线中两阴影部分的交线(黑色粗线黑色粗线)，其表示满足第一、第二及第三优先级要求的最其表示满足第一、第二及第

20、三优先级要求的最优解集合。优解集合。最后，考虑第四优先级要求最后，考虑第四优先级要求 min（d1-+2d2-)，即要在黑色粗线段中找出最优解。由于即要在黑色粗线段中找出最优解。由于d1-的权因子小于的权因子小于d2-，因此在这里可以考虑取因此在这里可以考虑取d2-=0。于是解得于是解得d1-=6，最优解为最优解为A点点x=3，y=8。图4 4 0 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)目标规划的图解法目标规划的图解法1)首先作出绝对约束的直线和区域；首先作出绝对约束的直线和区域；2)其次作出目标等式约束的直线其次作出目标等式约束的直线(去

21、掉正负偏差量去掉正负偏差量)；3)对于对于2)所作的直线两侧标上正负偏差量的方向；所作的直线两侧标上正负偏差量的方向；4)根据目标函数中的优先级和权重根据目标函数中的优先级和权重,依次确定各偏差量依次确定各偏差量.iixxxxddxxxxddxxddx x ddi1212111212221233122211()+0()2+10(10)810+56(56),0,1,2,3材材料料严严限限要要要要用用足足要要不不小小于于下面求解：下面求解：1122233min()zPdP ddP dx1O468102268410ABCd1d1d2d2EDd3d3JGGD上上所所有有点点都都是是最最优优解解(满满意

22、意解解).1122233min()zPdP ddP dxxdd1211+0 xxdd12222+10 xxdd1233810+5612211xx1122334min(2)zPdP dPddiixxddxxddxddxddx x ddi1211122213324412+=40+50+24+30,0,1,2,3 4，例例 用图解法求下目标规划的解用图解法求下目标规划的解s.t 解：作图如下解：作图如下在满足前两个目标下在满足前两个目标下,只能在只能在HE连线上连线上x1x2O20304050101030402050 xx12=40d1d1xx1250d2d2x124d3d3x230d4d4ABCD

23、dddddddd4444333340,44,0取取值值范范围围当当当当即即有有HEQPdd334min(2)3343434min24,0,4Pdddddd434,dd令令代代入入上上式式,得得33344min4,=0,=4.Pddd当当这这样样推推得得xx*12=24,=26.对目标对目标的要求的要求,实为求解如下线性规划实为求解如下线性规划满意解为满意解为(E点点)第第3节节.解目标规划的单纯形方法解目标规划的单纯形方法 目标规划的数学模型目标规划的数学模型,特别是约束的结构与特别是约束的结构与线性规划模型没有本质的区别，只是它的目线性规划模型没有本质的区别，只是它的目标不止是一个标不止是一

24、个,虽然其利用优先因子和权系数虽然其利用优先因子和权系数把目标写成一个函数的形式把目标写成一个函数的形式,但在计算中无法但在计算中无法按单目标处理按单目标处理,所以可用单纯形法进行适当改所以可用单纯形法进行适当改进后求解。在组织、构造算法时，我们要考进后求解。在组织、构造算法时，我们要考虑目标规划的数学模型一些特点，作以下规虑目标规划的数学模型一些特点，作以下规定：定：(1)因为目标规划问题的目标函数都是求因为目标规划问题的目标函数都是求最小化，所以检验数的最优准则与线性规划最小化，所以检验数的最优准则与线性规划是相同的；是相同的；3.解目标规划的单纯形方法解目标规划的单纯形方法(续续)(2)

25、因为非基变量的检验数中含有不同等级因为非基变量的检验数中含有不同等级的优先因子，的优先因子，Pi Pi+1，i=1,2,L-1.于是从于是从每个检验数的整体来看：每个检验数的整体来看：Pi+1（i=1,2,L-1）优先级第优先级第k个检验数的正、负首先决定于个检验数的正、负首先决定于 P1，P2，Pi 优先级第优先级第k个检验数的正、负。若个检验数的正、负。若P1 级第级第k个检验数为个检验数为0，则此检验数的正、负取决于，则此检验数的正、负取决于P2级第级第k个检验数；若个检验数；若P2 级第级第k个检验数仍为个检验数仍为0，则此检验数的正、负取决于则此检验数的正、负取决于P3级第级第k个检

26、验数，个检验数，依次类推。换一句话说，当某依次类推。换一句话说，当某Pi 级第级第k个检验数个检验数为负数时，计算中不必再考察为负数时，计算中不必再考察Pj（j i）级第级第k个检验数的正、负情况；个检验数的正、负情况；3.解目标规划的单纯形方法解目标规划的单纯形方法(续续)（3）根据（）根据（LGP）模型特征，当不含绝对约束时，模型特征，当不含绝对约束时，di-（i=1,2,K）构成了一组基本可行解。在寻找单构成了一组基本可行解。在寻找单纯形法初始可行点时，这个特点是很有用的。纯形法初始可行点时，这个特点是很有用的。解目标规划问题的单纯形法的计算步骤解目标规划问题的单纯形法的计算步骤：(1)

27、建立初始单纯形表在表中将检验数行按优先建立初始单纯形表在表中将检验数行按优先因子个数分别列成因子个数分别列成K行。初始的检验数需根据初始可行。初始的检验数需根据初始可行解计算出来，方法同基本单纯形法。当不含绝对约行解计算出来，方法同基本单纯形法。当不含绝对约束时，束时，di-（i=1,2,K）构成了一组基本可行解，这构成了一组基本可行解，这时只需利用相应单位向量把各级目标行中对应时只需利用相应单位向量把各级目标行中对应di-（i=1,2,K）的量消成的量消成0即可得到初始单纯形表。置即可得到初始单纯形表。置k 1；3.解目标规划的单纯形方法解目标规划的单纯形方法(续续)(2)检查当前第检查当前

28、第k行中是否存在大于行中是否存在大于0，且对，且对应的前应的前k-1行的同列检验数为零的检验数。若有行的同列检验数为零的检验数。若有取其中最大者对应的变量为换入变量，转取其中最大者对应的变量为换入变量，转(3)。若无这样的检验数，则转若无这样的检验数，则转(5)；(3)按单纯形法中的最小比值规则确定换出按单纯形法中的最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量，时，选取具有较高优先级别的变量为换出变量，转（转（4）；）；3.解目标规划的单纯形方法解目标规划的单纯形方法(续续)(4)按单纯形法进行基变

29、换运算，建立新按单纯形法进行基变换运算，建立新的单纯形表，（注意：要对所有的行进行转的单纯形表，（注意：要对所有的行进行转轴运算）返回轴运算）返回(2)；(5)当当k K 时，计算结束。表中的解即时，计算结束。表中的解即为满意解。否则置为满意解。否则置k=k+1，返回（返回（2）。）。3.求解目标规划的单纯形方法求解目标规划的单纯形方法(续续)例例4.2 试用单纯形法来求解例试用单纯形法来求解例4-1的目标规划模型的目标规划模型(47-5)Min f=P1（d1+d2+)+P2 d3+P3 d4-+P4（d1-+2d2-)s.t.x1 +d1-d1+=9 x2+d2-d2+=8 4x1+6x2

30、+d3-d3+=60 12x1+18x2+d4-d4+=252 x1,x2,di-,di+0 ,i=1,2,3,4.求解目标规划的单纯形方法求解目标规划的单纯形方法(续续)解解:首先处理初始基本可行解对应的各级检首先处理初始基本可行解对应的各级检验数。验数。由于由于P1,P2 优先级对应的目标函数中不优先级对应的目标函数中不含含di-,所以其检验数只需取系数负值。分别为所以其检验数只需取系数负值。分别为 (0，0，0，-1，0，-1，0，0，0，0；0)和和 (0，0，0，0，0，0，0，-1，0，0；0)x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHS P1000-10-100

31、000 P20000000-1000 P300000000-100 P400-10-2000000 d1-101-10000009 d2-01001-100008d3-4600001-10060d4-12180000001-1252 x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHS P1000-10-100000 P20000000-1000 P312180000000-1252 P400-10-2000000 d1-101-10000009 d2-0*1001-100008d3-4600001-10060d4-12180000001-12523.解目标规划的单纯形方法解目标规划

32、的单纯形方法(续续)P3 优先级对应的目标函数中含优先级对应的目标函数中含d4-,所以其检所以其检验数需要把第四个约束行加到取负值的这一行上，验数需要把第四个约束行加到取负值的这一行上，得到得到 (12，18，0，0，0，0，0，0，0，-1；252)T P4 优先级对应的目标函数中含（优先级对应的目标函数中含（d1-+2d2-)，所以其检验数需要把第一个约束行与第二个约束所以其检验数需要把第一个约束行与第二个约束行的行的2倍加到取系数负值的这一行上，得到倍加到取系数负值的这一行上，得到 (1，2，0，-1，0，-2，0，0，0，0；25)。列目标规划的初始单纯形表列目标规划的初始单纯形表 x

33、1x2d1-d1+d2-d2+d3-d3+d4-d4+RHS P1000-10-100000 P20000000-1000 P312180000000-1252 P4120-10-2000025 d1-101-10000009 d2-0*1001-1000088d3-4600001-1006010d4-12180000001-1252143.解目标规划的单纯形方法解目标规划的单纯形方法(续续)（1）k=1，在初始单纯形表中基变量为在初始单纯形表中基变量为 （d1-,d2-,d3-,d4-)T=（9，8,60，252)T；（2）因为因为P1与与P2优先级的检验数均已经为优先级的检验数均已经为非正

34、，所以这个单纯形表对非正，所以这个单纯形表对P1与与P2优先级是优先级是最优单纯形表；最优单纯形表；（3）下面考虑）下面考虑P3优先级，第二列的检验数优先级，第二列的检验数为为18，此为进基变量，计算相应的比值，此为进基变量，计算相应的比值 bi/aij 写在写在 列。通过比较，得到列。通过比较，得到d2-对应的比值最对应的比值最小，于是取小，于是取a22（标为标为*号）为转轴元进行矩号）为转轴元进行矩阵行变换得到新的单纯形表；阵行变换得到新的单纯形表；x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHS P1000-10-100000 P20000000-1000 P312000-

35、1818000-1108 P4100-1-2000009 d1-101-100000099x201001-100008 d3-*4000-661-100123d4-12000-1818001-110893.解目标规划的单纯形方法解目标规划的单纯形方法(续续)（4）下面继续考虑）下面继续考虑P3优先级，第一优先级，第一列的检验数为列的检验数为18，此为进基变量，计，此为进基变量，计算相应的比值算相应的比值 bi/aij 写在写在 列。通过比列。通过比较，得到较，得到d3-对应的比值最小，于是取对应的比值最小，于是取a31（标为标为*号）为转轴元进行矩阵行号）为转轴元进行矩阵行变换得到新的单纯形表

36、；变换得到新的单纯形表；x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHS P1000-10-100000 P20000000-1000 P3000000-330-172 P4000-1-0.5-1.5-.25.25006 d1-001-11.5-1.5-.25.25006 x201001-100008 x11000-1.51.5.25-.25003 d4-000000-331-172 3.解目标规划的单纯形方法解目标规划的单纯形方法(续续)（5）当前的单纯形表各优先级的检验）当前的单纯形表各优先级的检验数均满足了上述条件数均满足了上述条件,故为最优单纯形表。故为最优单纯形表。我们

37、得到最优解我们得到最优解x1=3，x2=8。第4节 灵敏度分析*改变优等级的分析*目标规划的灵敏度分析方法与线性规划类似，这里除了分析各项系数的变化外，还要考虑优先因子的变化问题。LINGO使用简介使用简介Ex1:线性规划问题线性规划问题 12max810zxx121212211210,0 xxxxxx的最优解为：的最优解为：x1*=4;x2*=3;z*=62.LINGO解法为解法为(8.0版版)max=8*x1+10*x2 s.t.2*x1+x2=11x1+2*x2=10endEx2:目标规划目标规划 1122233min()zPdP ddP d1212111222123312211+02+

38、10810+56,0,1,2,3iixxxxddxxddxxddxx ddi图解图解G(2,4)D(10/3,10/3).LINGO解法为解法为(8.0版版)min=300*d12+200*d21+200*d22+d31;2*x1+x2=11;x1-x2+d11-d12=0;x1+2*x2+d21-d22=10;8*x1+10*x2+d31-d32=56;endEx3:问题问题1122334min(2)zPdP dPdd1211122213324412+=40+50+24+30,0,iixxddxxddxddxddxx dd的解为的解为 xx*12=24,=26min=300*d11+200*

39、d22+2*d31+d41;x1+x2+d11-d12=40;X1-x2+d21-d22=50;x1+d31-d32=24;x2+d41-d42=30;end练习：对下列目标规划问题 1123231min,(2),PdPddPd12111222331221504040,0,1,2,3iixxddxddxddx x ddi(1)用图解法解;(2)写出Lindo8的解题程序,并用此程序解出;(3)试交换条件的书写各种次序,仍用Lindo8来解,结果是否一样?怎么解释?第5节 应用举例 例例1.职工的调资方案问题职工的调资方案问题 1）问题的提出 某单位领导在考虑本单位职工的升级调资方案时，要求相关

40、部门遵守以下的规定：（1）年工资总额不超过60000元；（2）每级的人数不超过定编规定的人数；（3）、级的升级面尽可能达到现有人数的20%；（4）级不足编制的人数可录用新职工，又I级的职工中有10%的人要退休。相关资料汇总于下表中，试为单位领导拟定一个满足要求的调资方案。等 级工资额（元/年）现有人数编制人数I20001012150012151000155合 计37422）模型分析与变量假设这是一个多目标规划的决策问题，适于用目标规划模型求解，故需要确定该问题与之对应的决策变量、目标值、优先等级及权系数等 1x2x3x设、分别表示提升到I、级和录用到级的新职工人数 由题设要求可确定各目标的优先

41、因子为：1P年工资总额不超过60000元；2P每级的人数不超过定编规定的人数 3P、级的升级面尽可能达到现有人数的20%3）模型的建立）模型的建立)()(min653432211ddPdddPdPz)6,5,4,3,2,1 ;3,2,1(0 ,3 4.2 0 3 3 60000)15(1000)12(1500)9(2000662551443233212211132211jiddxddxddxddxxddxxddxddxxxxxjji例2.物资的调运安排问题1）问题的提出有一供需不平衡（供应量需求量）的物资调运问题如下表所示 请为其制订物资调运方案，使之满足以下的目标要求：1P尽量保证满足重点客

42、户3B的需求指标；2P要求总运费不超过预算指标41066元；3P至少满足客户 321 ,BBB需求指标的80%；4P由 3A至 1B的运输量按合同规定不少于1万吨；5P1A至 3B的道路危险，运量要减少到最低点。客户运价仓库B1B2B3供应量（万吨）A1C11C12C135A2C21C22C238A3C31C32C337需求量（万吨）86102）设从仓库 调拨到客户 货运量为)3,2,1(iAi)3,2,1(jBjijx10594876352441)()(mindPdPdddPdPddPz1068333231323222121312111dxxxdxxxdxxx1044332313ddxxx 31314551066ijijijddxc88.44.6883323137732221266312111ddxxxddxxxddxxx19931ddx01013dx785333231232221131211xxxxxxxxx0,kkijddx