第4章 线性规划灵敏度分析精选PPT.ppt

《第4章 线性规划灵敏度分析精选PPT.ppt》由会员分享，可在线阅读，更多相关《第4章 线性规划灵敏度分析精选PPT.ppt（95页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第4章 线性规划灵敏度分析1第1页，本讲稿共95页 线性规划解除有线性规划解除有唯一最优解唯一最优解的情况外，还有如下的情况外，还有如下几种情况几种情况 无可行解无可行解无可行解无可行解退化退化退化退化无穷多解无穷多解无穷多解无穷多解 无界解无界解无界解无界解人工人工变量变量不能不能从基从基底中底中换出换出基可行基可行解中非解中非零元素零元素个数小个数小于基变于基变量数量数检验数检验数中零的中零的个数多个数多于基变于基变量的个量的个数数检验数大检验数大于零，但于零，但对应列元对应列元素小于等素小于等于零，无于零，无换出变量换出变量2第2页，本讲稿共95页唯一最优解唯一最优解 否 否否 是是是添

2、添加加松松弛弛变变量量、人人工工变变量量列出初始单纯形表列出初始单纯形表计算非基变量计算非基变量各列的检验数各列的检验数j所有所有j 0基变量中基变量中有非零的有非零的人工变量人工变量某非基某非基变量检变量检验数为验数为零零无可行解无可行解无穷多最优解无穷多最优解对任一对任一j0有有aik0无界解无界解令令k=maxjxk为换入变量为换入变量对对 所所 有有 aik 0计计 算算i i=bi/aik令令l=min=mini i 第第l l个个基基变变量量为为换换出出变变量，量，alk为主元素为主元素 迭代运算迭代运算.用非基变量用非基变量xk替换换出变量替换换出变量.对主元素行对主元素行(第第

3、l行行)令令bl/alkbl;alj/alkajl对主元素列对主元素列(第第k列列)令令1alk;0;0其它其它元素表中其它行列元素元素表中其它行列元素令令aij-ali/alkaika aijij bi-bl/alkaikbi j-alj/alkk j否对目标函数求极大值标准型线性规划问题，对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图：单纯形法计算步骤的框图：3第3页，本讲稿共95页第四章第四章 线性规划灵敏度分析线性规划灵敏度分析4.1灵敏度分析的基本原理灵敏度分析的基本原理4.2目标函数系数的灵敏度分析目标函数系数的灵敏度分析4.3右端常数的灵敏度分析右端常数的灵敏度分析

4、4.4技术系数的灵敏度分析技术系数的灵敏度分析*4.5参数线性规划参数线性规划4第4页，本讲稿共95页线线性性规规划划的的灵灵敏敏度度分分析析也也称称为为敏敏感感性性分分析析或或优优化化后后分分析析，它它是是研研究究和和分分析析参参数数（cj，bi，aij）的的波波动动对对最最优优解解的的影影响响程程度度，主主要要研研究究下下面面两两个个方方面：面：（1）参参数数在在什什么么范范围围内内变变化化时时，原原最最优优解解或或最最优优基基不不变变数数据据的的稳定区间；稳定区间；（2）当当参参数数超超出出（1）的的变变化化范范围围时时，最最优优解解或或最最优优基基有有何何变变化化如如何求出新的最优解和

5、最优基。何求出新的最优解和最优基。当当模模型型的的参参数数发发生生变变化化后后，可可以以不不必必对对线线性性规规划划问问题题重重新新求求解解，而而用用灵灵敏敏度度分分析析方方法法直直接接在在原原线线性性规规划划取取得得的的最最优优结结果果的的基基础础上上进进行行分分析析或或求求解解，既既可可减减少少计计算算量量，又又可可事事先先知知道道参参数数的的变变化化范范围围，及及时时对原决策作出调整和修正。对原决策作出调整和修正。4.1灵敏度分析的基本原理灵敏度分析的基本原理5第5页，本讲稿共95页单纯形法：单纯形法：对应于基对应于基B的典则形式（典式）的典则形式（典式）.Ax=b基变量用非基变量表示：

6、基变量用非基变量表示：代入目标函数：代入目标函数：6第6页，本讲稿共95页初始单纯形表初始单纯形表 c c1 c2 cm cm+1 cm+2 cncBxBb x1 x2 xm xm+1 xm+2 xnc1c2cmx1x2xmb1b2bm 100 a1m+1 a1m+2 a1n 010 a2m+1 a2m+2 a2n 001 amm+1 amm+2 amn-z(0)000m+1 m+2 n7第7页，本讲稿共95页分析分析 变化对最优解的影响。变化对最优解的影响。CCBCNCBXBbXBXNCBXBB-1 b IB-1 NZ-CB B-1 b0CN-CB B-1 b最优单纯形表最优单纯形表8第8页

7、，本讲稿共95页上表中上表中6个常数个常数a1,a2,a3,b,1,2取值在什么范围可使取值在什么范围可使1、现可行解最优，且唯一？何时不唯一？、现可行解最优，且唯一？何时不唯一？2、现基本解不可行；、现基本解不可行；3、问题无可行解；、问题无可行解；4、无有限最优解；、无有限最优解；5、现基本解可行，由、现基本解可行，由x1取代取代x6目标函数可改善。目标函数可改善。cjB-1bcBxBx1x2x3x4x5x6x34a110a20bx4-1-501-102x6a3-300-413j1200-309第9页，本讲稿共95页线性规划标准形式线性规划标准形式(1)、参数、参数A，b，C在什么范围内变

8、动，对当前方案无影响？在什么范围内变动，对当前方案无影响？(2)、参数、参数A，b，C中的一个中的一个(几个几个)变动，对当前方案影响？变动，对当前方案影响？(3)、如果最优方案改变，如何用简便方法求新方案？、如果最优方案改变，如何用简便方法求新方案？当线性规划问题中的一个或几个参数变化时，可以用单纯形当线性规划问题中的一个或几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。要。10第10页，本讲稿共95页4.1目标函数系数的灵敏度分析目标函数系数的灵敏度分析考虑检验数考虑检验数(1)若若cj 是非基变量的系

9、数：是非基变量的系数：11第11页，本讲稿共95页解：最优单纯形表解：最优单纯形表 例例1试求试求 c3 在多大范围内变动时，原最优解保持不变。在多大范围内变动时，原最优解保持不变。cj-2-3-400B-1bcBxBx1x2x3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5j00-9/5-8/5-1/5-28/512第12页，本讲稿共95页从表中看到从表中看到c3=-4,3=-9/5可得到可得到c3-3=9/5时，即时，即c3-4+9/5=-11/5时原最优解不变。时原最优解不变。解：最优单纯形表解：最优单纯形表 cj-2-3-400B-1bcBx

10、Bx1x2x3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5j00-9/5-8/5-1/5-28/513第13页，本讲稿共95页(2)若若cj是基变量的系数是基变量的系数14第14页，本讲稿共95页以下分两种情况讨论：以下分两种情况讨论：1如果如果 cr 0上式才有可能不成立上式才有可能不成立,因此有：因此有：2如果如果 cr 0,只有只有arj0，则问，则问题的最优解将发生变化，此时对原最终表适当修改题的最优解将发生变化，此时对原最终表适当修改后，应用单纯形法继续计算得到问题的最优解。后，应用单纯形法继续计算得到问题的最优解。16第16页，本讲稿共

11、95页例例2已知问题的已知问题的最优单纯形表，最优单纯形表，(1)求求c2在什么范围内变动时，在什么范围内变动时，原最优解保持不变；原最优解保持不变；(2)c2=5时，求新的最优解。时，求新的最优解。最优单纯形表最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2-1/8014最优解：最优解：最优值：最优值：17第17页，本讲稿共95页C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/

12、2-1/8014C i23+c2000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143+c2 x2 011/2-1/802j00-3/2-c2/2-1/8+c2/8014+2c2(1)求求c2的变动范围，使原最优解保持不变；的变动范围，使原最优解保持不变；c2=c2+c218第18页，本讲稿共95页从表中看到从表中看到可得到可得到-3c21时，原最优解不变。时，原最优解不变。C i23+c2000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143+c2 x2 011/2-1/802j00-3/2-c2/2-1

13、/8+c2/8014+2c219第19页，本讲稿共95页C i25000B-1bCBXBx1x2x3x4x52 x1 1001/404160 x5 00-21/21485 x2 011/2-1/802-j00-5/25/8018（2）c2=2，即，即c2由由3变为变为5时，求新的最优解时，求新的最优解C i25000B-1bCBXBx1x2x3x4x52 x1 1010-1/220 x4 00-41285 x2 010-1/8-1/43j00-20-7/419新的最优解：新的最优解：最优值：最优值：20第20页，本讲稿共95页已知最优表如下已知最优表如下例例3某企业利用两种资源生产三种产品的最

14、优计划问题某企业利用两种资源生产三种产品的最优计划问题,归结为下列线性规划归结为下列线性规划cj54300CBXBbx1x2x3x4x545x2x140200110 232 1 11j26000 4 3 121第21页，本讲稿共95页cj54300CBXBbx1x2x3x4x545x2x140200110 232 1 11j26000 4 3 1最优计划是两种产品分别生产最优计划是两种产品分别生产40单位与单位与20单位，最大产值单位，最大产值z*=260单位。单位。（1）确定）确定x2的价值系数的价值系数c2的变化范围，使原最优解保持最优。的变化范围，使原最优解保持最优。（2）c3在什么范围

15、内变化，最优解不变？在什么范围内变化，最优解不变？（3）若）若c3从从3变为变为9，求新的最优计划。，求新的最优计划。22第22页，本讲稿共95页解解（1）因为）因为x2为基变量，为基变量，c2的变换范围：的变换范围：因此当因此当x2的价值系数在的价值系数在即在区间即在区间2.5,5变化时，最优解不变。变化时，最优解不变。23第23页，本讲稿共95页（2）因为）因为c3是是非基变量非基变量x3的价值系数，由公式的价值系数，由公式得到得到 c3+c3的变换范围：的变换范围：即当即当c3在在 c3+c33+4=7时，最优解不变。时，最优解不变。（3）当）当c3从从3变为变为9时，原最优解失去最优性

16、，时，原最优解失去最优性，在表中作适当变动后（修改在表中作适当变动后（修改c3的值，重新计算检的值，重新计算检验数），用单纯形法容易求得新的最优表如下：验数），用单纯形法容易求得新的最优表如下：24第24页，本讲稿共95页cj54900CBXBbx1x2x3x4x545x2x140200110 232 1 11j260002 3 149x2x3160/320/32/31/310014/3 1/3 1/31/3j820/3 2/300 7/3 5/3故新的最优解为故新的最优解为X*=(0,160/3,20/3,0,0）最优值最优值z*=820/3，即随着第三种产品价格的上升，总，即随着第三种产品

17、价格的上升，总产值上升。产值上升。25第25页，本讲稿共95页设分量设分量br变化为变化为br+br，根据前面的讨论：，根据前面的讨论：最优解的基变量最优解的基变量XB=B-1b，那么只要保持，那么只要保持B-1(b+b)0则最优基不变，即基变量保持，只有值的变化；则最优基不变，即基变量保持，只有值的变化；否则，需要利用否则，需要利用对偶单纯形法对偶单纯形法继续计算。继续计算。4.2右端常数的灵敏度分析右端常数的灵敏度分析26第26页，本讲稿共95页27第27页，本讲稿共95页例例4已知前述例已知前述例2的最优解及最优单纯形表的最优解及最优单纯形表28第28页，本讲稿共95页下表为最优单纯形表

18、下表为最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2-1/801429第29页，本讲稿共95页由最优单纯形表得由最优单纯形表得:30第30页，本讲稿共95页31第31页，本讲稿共95页不可行!用对偶单纯形法计算用对偶单纯形法计算将将b代入原最优单纯形表中，运用对偶单纯形法计算最优解。代入原最优单纯形表中，运用对偶单纯形法计算最优解。32第32页，本讲稿共95页将将b代入原最优单纯形表中，运用对偶单纯形法计算最优解。代入原最优单纯形表中，运用对偶单纯形法计算最优解。经一次迭代后，

19、求得新的最优解经一次迭代后，求得新的最优解:(4 3 2 0 0)TC i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/21-43 x2 011/2-1/804j00-3/2-1/80143/42 x1 1001/4040 x3 001-1/4-1/223 x2 01001/43j000-1/2-3/41733第33页，本讲稿共95页(1)增加一个新变量增加一个新变量增加一个变新量，相当于系数矩阵增加一列。增加一个变新量，相当于系数矩阵增加一列。设增加变量设增加变量xn+1，则有相应的，则有相应的Pn+1,cn+1。计算出计算出Pn+1=B-1P

20、n+1,n+1=cn+1-cB Pn+1填入最优单纯形表填入最优单纯形表,若若 n+10则则最优解不变；最优解不变；否则，进一步用单纯形法求解。否则，进一步用单纯形法求解。4.3技术系数的灵敏度分析技术系数的灵敏度分析34第34页，本讲稿共95页例例5 求当增加求当增加x6,P6=(2,6,3)T,c6=5时，原最优解是否保持时，原最优解是否保持不变，若变动求出新的最优不变，若变动求出新的最优解。解。解解:下表为最优单纯形表下表为最优单纯形表C j23000B-1bcBxBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2-

21、1/801435第35页，本讲稿共95页36第36页，本讲稿共95页用单纯形法进一步求解，可得：用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)T z*=16.5C i230005B-1bCBXBx1x2x3x4x5x62 x1 1001/403/248/30 x5 00-21/212423 x2 011/2-1/801/428j00-3/2-1/805/4142 x1 103/2-1/8-3/4015 x6 00-11/41/2123 x2 013/4-3/16-1/403/2j00-1/4-7/160033/237第37页，本讲稿共95页(2)增加一个新约束条件增加一个新约

22、束条件增加一个新约束条件相当于在系数矩阵中增加一行。增加一个新约束条件相当于在系数矩阵中增加一行。增加一个约束条件之后，应把最优解带入新的约束，若满足则最优增加一个约束条件之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。，进一步用

23、单纯形法或对偶单纯形法求解。38第38页，本讲稿共95页例例6 求当增加求当增加3x1+2x215时，原最时，原最优解是否保持不变，若变动求优解是否保持不变，若变动求出新的最优解。出新的最优解。解解:下表为最优单纯形表下表为最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2-1/801439第39页，本讲稿共95页将将3x1+2x2+x6=15代入原最优单纯形表。代入原最优单纯形表。经经对偶单纯形法对偶单纯形法迭代一步，可得：迭代一步，可得：最优解为最优解为(3.5,2.25,0,

24、0,3,2)T，最优值为，最优值为13.75C i230000B-1bCBXBx1x2x3x4x5x62 x1 1001/40040 x5 00-21/21043 x2 011/2-1/80020 x632000115j00-3/2-1/800142 x1 1001/40040 x5 00-21/21043 x2 011/2-1/80020 x600-1-1/201-1j00-3/2-1/8001440第40页，本讲稿共95页(3)个别技术系数个别技术系数aij的改变的改变(计划生产的产品工艺结构改变计划生产的产品工艺结构改变)非基变量非基变量xj工艺改变工艺改变只影响单纯形表只影响单纯形表P

25、j 列列，j.关键看关键看 j 0?还是还是0?.用增加新变量类似方法解决。用增加新变量类似方法解决。基变量基变量xj工艺改变，复杂，根据具体情况讨论。工艺改变，复杂，根据具体情况讨论。41第41页，本讲稿共95页分析分析:42第42页，本讲稿共95页注注:Y可由最优单纯形表查得可由最优单纯形表查得43第43页，本讲稿共95页最优单纯形表为最优单纯形表为求：（求：（1）P3由由(1,3)T改为改为(1,2)T；（2）P1由由(1,2)T改为改为(1,1)T，最优解的变化情况。，最优解的变化情况。例例7C i-2-3-400B-1bCBXBx1x2x3x4x5-3 x2 01-1/5-2/51/

26、52/5-2 x1 107/5-1/5-2/511/5j00-9/5-8/5-1/5-28/544第44页，本讲稿共95页C i-2-3-400B-1bCBXBx1x2x3x4x5-3 x2 01-1/5-2/51/52/5-2 x1 107/5-1/5-2/511/5j00-9/5-8/5-1/5-28/5解：（解：（1）P1由由(12)T改为改为(11)T，由最优单纯形表可知，由最优单纯形表可知所以原最优解不变所以原最优解不变45第45页，本讲稿共95页另解：（另解：（1）P3由由(-13)T改为改为(-12)T由最由单纯形表可知由最由单纯形表可知所以原最优解不变所以原最优解不变46第46

27、页，本讲稿共95页（2）P1由由(1，2)T改为改为(1，1)T，(x1为基变量为基变量)由最优单纯形表可知由最优单纯形表可知代入最优单纯形表，用代入最优单纯形表，用P1代替代替P147第47页，本讲稿共95页C i-2-3-400B-1bCBXBx1x2x3x4x5-3 x2-3/51-1/5-2/51/52/5-2 x1 1/507/5-1/5-2/511/5j-28/5-3 x2 014-1-177/4-2 x1 107-1-21111/7j0022-5-7-43-3 x2-4/710-3/71/75/7-4 x3 1/701-1/7-2/711/7j-22/700-13/7-5/7-5

28、9/7新的最优解为新的最优解为:(0,5/7,11/7,0,0)T最优值为：最优值为：59/748第48页，本讲稿共95页最优单纯形表最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2-1/8014例例8求例求例2中中 a24的变化范围的变化范围,使最优解不变使最优解不变.49第49页，本讲稿共95页例例8求例求例2中中 a24的变化范围的变化范围,使最优解不变使最优解不变.解解:50第50页，本讲稿共95页例例9在例在例2的基础上，企业要增加一个的基础上，企业要增加一个新产品新产

29、品,每件产品需每件产品需2个台时，原材料个台时，原材料A6kg，原材料原材料B3kg，利润，利润5元元/件，问如何安排各产件，问如何安排各产品的产量，使利润最大？品的产量，使利润最大？解：解：532利润12340料B16604料A8221设备b51第51页，本讲稿共95页表明生产新品有利表明生产新品有利。52第52页，本讲稿共95页5/40-1/8-3/200 1/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x2ix353第53页，本讲稿共95页5/40-1/8-3/200 1/40-1/81/21023211/2-

30、2004x503/201/40014x12x5x4x3x2x1bXBCB500032x28/34/28ix320-5/8-7/16-1/400 0-1/8-3/163/4103/2311/21/4-10020-3/4-1/83/2011x12x5x4x3x2x1bXBCB500032x2ix3x3554第54页，本讲稿共95页小结：灵敏度分析小结：灵敏度分析55第55页，本讲稿共95页56第56页，本讲稿共95页综合例题：考虑下列线性规划综合例题：考虑下列线性规划求求出出最最优优解解后后，分分别别对对下下列列各各种种变变化化进进行行灵灵敏敏度度分分析析，求求出出变变化化后后的的最优解。最优解。

31、（1 1）将目标函数改为：）将目标函数改为：（2 2）改变右端常数为）改变右端常数为:57第57页，本讲稿共95页（3）改变目标函数）改变目标函数x3的系数为的系数为c3=1;（4）改变目标函数中）改变目标函数中x2的系数为的系数为c2=2；（5）改变）改变x2的系数为的系数为（6）改变约束（）改变约束（1）为）为（7）增加新约束）增加新约束（8）增加新约束）增加新约束58第58页，本讲稿共95页解：加入松弛变量解：加入松弛变量x4、x5、x6，用单纯形法计算，得最优表，用单纯形法计算，得最优表1：Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/

32、701/74/7010 x60200111j031/702/720/70-10表表159第59页，本讲稿共95页最优解最优解X=（1，0，2，0，0，1），最优值），最优值Z=10，最优基，最优基（1）等价于等价于，即将，即将cj改变为（改变为（2，1，4），其中），其中c1=2、c3=4是基变量的系数，是基变量的系数，c2=1是非基变量的系数，是非基变量的系数，求得检验数求得检验数60第60页，本讲稿共95页这这里里表表1的的解解不不是是最最优优，将将上上述述检检验验数数代代替替表表1的的检检验验数数，再再单单纯纯形形法继续迭代，计算结果如表法继续迭代，计算结果如表2所示。所示。61第61页

33、，本讲稿共95页表表2 2cj214000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/701/74/7010 x60200111j031/702/720/701x2017/51/53/5014/52x1102/51/52/501/50 x60014/52/51/5033/5j0031/53/51/501x23/2121/2005/20 x55/2011/2101/20 x61/2031/20113/2j1/2061/200最优解最优解62第62页，本讲稿共95页基变量的解为基变量的解为基基本本解解不不可可行行，将将求求得得的的XB代代替替表表1中中的的常常数数

34、项项，用用对对偶偶单单纯纯形形法法求解，其结果见表求解，其结果见表3所示。所示。（2 2）改变右端常数为）改变右端常数为:63第63页，本讲稿共95页Cj214000bCBXBx1x2x3x4x5x64x305/711/73/7022/72x112/701/74/706/70 x60200112j031/702/720/704x30011/71/145/1417/72x11001/73/71/74/71x201001/21/21j0002/79/1431/14-69/7表表3最优解最优解64第64页，本讲稿共95页由表由表1容易得到基变量容易得到基变量x3的系数的系数c3的增量变化范围是的增量

35、变化范围是而而c3=1在在允允许许的的变变化化范范围围之之外外，故故表表1的的解解不不是是最最优优解解。非非基基变变量量的的检检验数验数x4进基，用单纯形法计算，得到表进基，用单纯形法计算，得到表4。（3）改变目标函数）改变目标函数x3的系数为的系数为c3=1;65第65页，本讲稿共95页表表4XBx1x2x3x4x5x6bx305/711/73/702x112/701/74/701x60200111j016/701/711/70 x405713014x11110103x60200111j031020-6最优解为最优解为X=（3，0，0，14，0，1）T,最优值最优值z=6。66第66页，本讲

36、稿共95页c2是非基变量是非基变量x2的系数，由表的系数，由表3知，知，由由1变为变为2时，时，或直接求出或直接求出x2的检验数的检验数从而最优解不变，即从而最优解不变，即X=（1，0，2，0，0，1）。）。（4）改变目标函数中）改变目标函数中x2的系数为的系数为c2=2；67第67页，本讲稿共95页这这时时目目标标函函数数的的系系数数和和约约束束条条件件的的系系数数都都变变化化了了，同同样样求求出出2判判别别最最优解是否改变。优解是否改变。x2进基，计算结果如表进基，计算结果如表5所示所示（5）改变）改变x2的系数为的系数为68第68页，本讲稿共95页表表5Cj234000bCBXBx1x2

37、x3x4x5x64x30011/73/7022x11101/74/7010 x60300111j0502/720/70 x30011/73/702x11001/75/211/34/3x201001/31/31/3j0002/725/215/3-35/3最优解最优解69第69页，本讲稿共95页（6）第一个约束变为）第一个约束变为实际上是改变了实际上是改变了a12及及b1，这时要求，这时要求2及及XB，判断解的情况。，判断解的情况。因为因为可行，所以最优解为可行，所以最优解为70第70页，本讲稿共95页引入松弛变量引入松弛变量x7得得x1、x3是基变量，利用表是基变量，利用表1消去消去x1、x3，

38、得，得x7为为新新的的基基变变量量，基基本本解解X=（1，0，2，0，0，1，2）不不可可行行，将将上式加入表上式加入表1中用对偶单纯形法迭代得到表中用对偶单纯形法迭代得到表6。（7）增加新约束）增加新约束71第71页，本讲稿共95页表表6XBx1x2x3x4x5x6x7bx305/711/73/7002x112/701/74/7001x6x700213/700011/712/7100112j031/702/720/700 x306/11105/1101/1120/11x115/11006/1101/1113/11x6x400213/11000112/111007/11114/11j045/1

39、10032/1102/11最优解最优解72第72页，本讲稿共95页（8）将将原原最最优优解解代代入入约约束束的的左左边边有有5122=110，满足新约束，故最优解不变。，满足新约束，故最优解不变。上上述述cj及及bi的的最最大大允允许许变变化化范范围围是是假假定定其其它它参参数数不不变变的的前前提提下下，单单个个参参数数的的变变化化范范围围，当当几几个个参参数数同同时时在在各各自自范范围围内内变变化化时时，最最优优解解或或最最优优基有可能改变。基有可能改变。1.注意最优解与最优基不变的区别；注意最优解与最优基不变的区别；2.掌握某个参数变化后，最优表中哪些数据会发生变化，如何变化；掌握某个参数

40、变化后，最优表中哪些数据会发生变化，如何变化；3.模型发生变化后不是重新求解，而是在原模型的最优表中求出变化后模型发生变化后不是重新求解，而是在原模型的最优表中求出变化后的数据，根据变化条件，选择合适的方法继续计算。的数据，根据变化条件，选择合适的方法继续计算。73第73页，本讲稿共95页*4.4参数线性规划参数线性规划在线性规划的实际应用中，由于某种原因，线性规划在线性规划的实际应用中，由于某种原因，线性规划问题的目标函数的价值系数问题的目标函数的价值系数C 和约束条件的右端常数和约束条件的右端常数b会随着某个参数而连续变动。会随着某个参数而连续变动。当数据随着某个参数连续变化时，研究其对最

41、优解的影响，当数据随着某个参数连续变化时，研究其对最优解的影响，即为参数线性规划问题。即为参数线性规划问题。目标函数的价值系数目标函数的价值系数c含有参数的线性规划问题含有参数的线性规划问题右端常数右端常数b含有参数的线性规划问题含有参数的线性规划问题74第74页，本讲稿共95页(1)目标函数的价值系数含有参数的线性规划问题目标函数的价值系数含有参数的线性规划问题75第75页，本讲稿共95页求解步骤：求解步骤：令令=0，求得最优解与最优基，求得最优解与最优基B；根据根据求得求得的区间；的区间；运用单纯形法求得其余区间的最优解。运用单纯形法求得其余区间的最优解。例例176第76页，本讲稿共95页

42、解：解：化为标准形；求化为标准形；求=0的最优解与最优基的最优解与最优基B则则=0时最优解为时最优解为(0 100 230 0 0 20)TC i325000B-1bCBXBx1x2x3x4x5x62x2-1/4101/2-1/401005x33/20101/202300 x6 200-21120j-400-1-20135077第77页，本讲稿共95页 根据根据求得求得的区间的区间即当即当时最优解为时最优解为C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52 x2-1/4101/2-1/4010025x33/20101/2023000 x6 200-21

43、120j-400-1-201350j-41/4005/2-9/40-4078第78页，本讲稿共95页 运用单纯形法求得其余区间的最优解运用单纯形法求得其余区间的最优解当当时时C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2-1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-4000 x4-1/2201-1/2020025x33/20101/2023000 x6 140001420j-9/2200-5/201150j-9-500-10460最优

44、解为最优解为79第79页，本讲稿共95页当当时时C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2-1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-40-52x2 0101/4-1/81/8205/225x30013/2-1/4-3/4215-63x1 100-11/21/210j0005001310j000-31/423/80-285/280第80页，本讲稿共95页当当时时C i-6-52000B-1bC i325000CBCBXBx1x2

45、x3x4x5x6-52x2 0101/4-1/81/8205/225x30013/2-1/4-3/4215-63x1 100-11/21/210j0005001310j000-31/423/80-285/2-52x2 01-1/60-1/121/4200/300 x4002/31-1/6-1/2430/3-63x1 102/301/30460/3j0010/30-5/6-1/21780/3j0031/6019/125/4-3760/381第81页，本讲稿共95页参变量的取值范围与最优解为参变量的取值范围与最优解为82第82页，本讲稿共95页（2）右端常数含有参数的线性规划问题）右端常数含有参数

46、的线性规划问题求解步骤：求解步骤：令令=0，求得最优解与最优基，求得最优解与最优基B；根据根据求得求得的区间；的区间；运用对偶单纯形法求得其余区间的最优解。运用对偶单纯形法求得其余区间的最优解。83第83页，本讲稿共95页例例2解：解：化为标准形；求化为标准形；求=0的最优解与最优基的最优解与最优基B84第84页，本讲稿共95页 根据根据求得求得的区间；的区间；则则=0时最优解为时最优解为(0,100,230,0,0,20)TC i325000B-1bCBXBx1x2x3x4x5x62x2-1/4101/2-1/401005x33/20101/202300 x6 200-21120j-400-

47、1-20135085第85页，本讲稿共95页最优解为最优解为C i325000B-1bb*CBXBx1x2x3x4x5x62x2-1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-786第86页，本讲稿共95页当当时最优单纯形表为时最优单纯形表为运用单纯形法求得其余区间的最优解。运用单纯形法求得其余区间的最优解。C i325000B-1bb*CBXBx1x2x3x4x5x62x2-1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-20

48、1350-72x2 1/410001/4105-15x33/20101/20230-20 x4-1001-1/21/2-105j-5000-5/2-1/21360-12时，最优解为时，最优解为当当87第87页，本讲稿共95页当当时最优单纯形表为时最优单纯形表为C i325000B-1bb*CBXBx1x2x3x4x5x62x2-1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-70 x5 1-40-210-400-65x312110043010 x6 140-3/201420-4j-2-80-5002150

49、5最优解为最优解为88第88页，本讲稿共95页参变量的取值范围与最优解为参变量的取值范围与最优解为89第89页，本讲稿共95页CBXBx1x2x3x4x5b2x213100 x50-1-210090第90页，本讲稿共95页CBXBx1x2x3x4x5b2x2-11310100 x580-1-21500-2-202091第91页，本讲稿共95页Cj-224005bCBXBx1x2x3x4x52x2-113102100 x580-1-21-7500-2-201205-1/21/23/21/20150 x59/27/219/23/210401/2-1/2-7/2-5/20025508/923/92/

50、31/9185/9-2x117/919/91/32/9080/90-8/9-41/9-8/3-1/90265/992第92页，本讲稿共95页CBXBX1X2X3X4X5X6X7b0X5011/4-114X4001-125X210-3/41-Z00-1/4-1-1393第93页，本讲稿共95页CBXBX1X2X3X4X5X6X7b0X5-10-27/4011/4-114X410-2101-125X21115/400-3/411-Z-70-39/400-1/4-1-1394第94页，本讲稿共95页CBXBX1X2X3X4X5X6X7b0X5-10-27/4011/4-1214X410-2101-1