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

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

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

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本讲稿第三页，共九十五页第四章第四章 线性规划灵敏度分析线性规划灵敏度分析4.1灵敏度分析的基本原理灵敏度分析的基本原理4.2目标函数系数的灵敏度分析目标函数系数的灵敏度分析4.3右端常数的灵敏度分析右端常数的灵敏

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

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

6、基变量表示：基变量用非基变量表示：代入目标函数：代入目标函数：6本讲稿第六页，共九十五页初始单纯形表初始单纯形表 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本讲稿第七页，共九十五页分析分析 变化对最优解的影响。变化对最优解的影响。CCBCNCBXBbXBXNCBXBB-1 b IB-1 NZ-CB B-1 b0CN-CB B-1 b最优单纯形表最优

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

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

9、cj 是非基变量的系数：是非基变量的系数：11本讲稿第十一页，共九十五页解：最优单纯形表解：最优单纯形表 例例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本讲稿第十二页，共九十五页从表中看到从表中看到c3=-4,3=-9/5可得到可得到c3-3=9/5时，即时，即c3-4+9/5=-11/5时原最优解不变。时原最优解不变。解：最优单纯形表解：最优单纯形表 cj-2-

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

11、优解。16本讲稿第十六页，共九十五页例例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本讲稿第十七页，共九十五页C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 0

12、11/2-1/802j00-3/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本讲稿第十八页，共九十五页从表中看到从表中看到可得到可得到-3c21时，原最优解不变。时，原最优解不变。C i23+c2000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143+c2 x2 011/2-1/

13、802j00-3/2-c2/2-1/8+c2/8014+2c219本讲稿第十九页，共九十五页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本讲稿第二十页，共九十五页已知最优表如下已知最优表如下例

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

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

16、）当）当c3从从3变为变为9时，原最优解失去最优性，在时，原最优解失去最优性，在表中作适当变动后（修改表中作适当变动后（修改c3的值，重新计算检验数）的值，重新计算检验数），用单纯形法容易求得新的最优表如下：，用单纯形法容易求得新的最优表如下：24本讲稿第二十四页，共九十五页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

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

18、最优解及最优单纯形表28本讲稿第二十八页，共九十五页下表为最优单纯形表下表为最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2-1/801429本讲稿第二十九页，共九十五页由最优单纯形表得由最优单纯形表得:30本讲稿第三十页，共九十五页31本讲稿第三十一页，共九十五页不可行!用对偶单纯形法计算用对偶单纯形法计算将将b代入原最优单纯形表中，运用对偶单纯形法计算最优解。代入原最优单纯形表中，运用对偶单纯形法计算最优解。32本讲稿第三十二页，共九十五页将将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本讲稿第三十三页，共九十五页(1)增加一个新变量增加一个新变量增加一个变新量，相当于系数矩阵增加一列。增加一个变新量，相当于系数矩阵增加一列。设增加变量设增

20、加变量xn+1，则有相应的，则有相应的Pn+1,cn+1。计算出计算出Pn+1=B-1Pn+1,n+1=cn+1-cB Pn+1填入最优单纯形表填入最优单纯形表,若若 n+10则则最优解不变；最优解不变；否则，进一步用单纯形法求解。否则，进一步用单纯形法求解。4.3技术系数的灵敏度分析技术系数的灵敏度分析34本讲稿第三十四页，共九十五页例例5 求当增加求当增加x6,P6=(2,6,3)T,c6=5时，原最优解是否保持时，原最优解是否保持不变，若变动求出新的最不变，若变动求出新的最优解。优解。解解:下表为最优单纯形表下表为最优单纯形表C j23000B-1bcBxBx1x2x3x4x52 x1

21、1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2-1/801435本讲稿第三十五页，共九十五页36本讲稿第三十六页，共九十五页用单纯形法进一步求解，可得：用单纯形法进一步求解，可得：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/2

22、j00-1/4-7/160033/237本讲稿第三十七页，共九十五页(2)增加一个新约束条件增加一个新约束条件增加一个新约束条件相当于在系数矩阵中增加一行。增加一个新约束条件相当于在系数矩阵中增加一行。增加一个约束条件之后，应把最优解带入新的约束，若满足增加一个约束条件之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变负松弛变量，否则引入非负人工变量），并通过矩

23、阵行变换把对应基变量的元素变为换把对应基变量的元素变为0，进一步用单纯形法或对偶单，进一步用单纯形法或对偶单纯形法求解。纯形法求解。38本讲稿第三十八页，共九十五页例例6 求当增加求当增加3x1+2x215时，原时，原最优解是否保持不变，若变最优解是否保持不变，若变动求出新的最优解。动求出新的最优解。解解:下表为最优单纯形表下表为最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2-1/801439本讲稿第三十九页，共九十五页将将3x1+2x2+x6=15代入原最优单纯形表。代入原最

24、优单纯形表。经经对偶单纯形法对偶单纯形法迭代一步，可得：迭代一步，可得：最优解为最优解为(3.5,2.25,0,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本讲稿第四十页，共九十五页(3)个别技术系数个别技术系数aij的改变的改变(计划生

25、产的产品工艺结构改变计划生产的产品工艺结构改变)非基变量非基变量xj工艺改变工艺改变只影响单纯形表只影响单纯形表Pj 列列，j.关键看关键看 j 0?还是还是0?.用增加新变量类似方法解决。用增加新变量类似方法解决。基变量基变量xj工艺改变，复杂，根据具体情况讨论。工艺改变，复杂，根据具体情况讨论。41本讲稿第四十一页，共九十五页分析分析:42本讲稿第四十二页，共九十五页注注:Y可由最优单纯形表查得可由最优单纯形表查得43本讲稿第四十三页，共九十五页最优单纯形表为最优单纯形表为求：（求：（1）P3由由(1,3)T改为改为(1,2)T；（2）P1由由(1,2)T改为改为(1,1)T，最优解的变化

26、情况。，最优解的变化情况。例例7C 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/544本讲稿第四十四页，共九十五页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本讲稿第四十五页，共九十五页另解

27、：（另解：（1）P3由由(-13)T改为改为(-12)T由最由单纯形表可知由最由单纯形表可知所以原最优解不变所以原最优解不变46本讲稿第四十六页，共九十五页（2）P1由由(1，2)T改为改为(1，1)T，(x1为基变量为基变量)由最优单纯形表可知由最优单纯形表可知代入最优单纯形表，用代入最优单纯形表，用P1代替代替P147本讲稿第四十七页，共九十五页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/7j002

28、2-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-59/7新的最优解为新的最优解为:(0,5/7,11/7,0,0)T最优值为：最优值为：59/748本讲稿第四十八页，共九十五页最优单纯形表最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2-1/8014例例8求例求例2中中 a24的变化范围的变化范围,使最优解不变使最优解不变.49本讲稿第四十九页，共九十五页例例8求例求例2中中 a24的变化

29、范围的变化范围,使最优解不变使最优解不变.解解:50本讲稿第五十页，共九十五页例例9在例在例2的基础上，企业要增加一个的基础上，企业要增加一个新产品新产品,每件产品需每件产品需2个台时，原材料个台时，原材料A6kg，原材料原材料B3kg，利润，利润5元元/件，问如何安排各产件，问如何安排各产品的产量，使利润最大？品的产量，使利润最大？解：解：532利润12340料B16604料A8221设备b51本讲稿第五十一页，共九十五页表明生产新品有利表明生产新品有利。52本讲稿第五十二页，共九十五页5/40-1/8-3/200 1/40-1/81/21023211/2-2004x503/201/4001

30、4x12x5x4x3x2x1bXBCB500032x2ix353本讲稿第五十三页，共九十五页5/40-1/8-3/200 1/40-1/81/21023211/2-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本讲稿第五十四页，共九十五页小结：灵敏度分析小结：灵敏度分析55本讲稿第五十五页，共九十五页56本讲稿第五十六页，共九十五页综合例题

31、：考虑下列线性规划综合例题：考虑下列线性规划求求出出最最优优解解后后，分分别别对对下下列列各各种种变变化化进进行行灵灵敏敏度度分分析析，求求出出变变化化后后的最优解。的最优解。（1 1）将目标函数改为：）将目标函数改为：（2 2）改变右端常数为）改变右端常数为:57本讲稿第五十七页，共九十五页（3）改变目标函数）改变目标函数x3的系数为的系数为c3=1;（4）改变目标函数中）改变目标函数中x2的系数为的系数为c2=2；（5）改变）改变x2的系数为的系数为（6）改变约束（）改变约束（1）为）为（7）增加新约束）增加新约束（8）增加新约束）增加新约束58本讲稿第五十八页，共九十五页解：加入松弛变量

32、解：加入松弛变量x4、x5、x6，用单纯形法计算，得最优表，用单纯形法计算，得最优表1：Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/701/74/7010 x60200111j031/702/720/70-10表表159本讲稿第五十九页，共九十五页最优解最优解X=（1，0，2，0，0，1），最优值），最优值Z=10，最优基，最优基（1）等价于等价于，即将，即将cj改变为（改变为（2，1，4），其中），其中c1=2、c3=4是基变量的系数，是基变量的系数，c2=1是非基变量的系数，是非基变量的系数，求得检验数求得检验数60本讲稿第六十页，共九十

33、五页这这里里表表1的的解解不不是是最最优优，将将上上述述检检验验数数代代替替表表1的的检检验验数数，再再单单纯纯形法继续迭代，计算结果如表形法继续迭代，计算结果如表2所示。所示。61本讲稿第六十一页，共九十五页表表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

34、x61/2031/20113/2j1/2061/200最优解最优解62本讲稿第六十二页，共九十五页基变量的解为基变量的解为基基本本解解不不可可行行，将将求求得得的的XB代代替替表表1中中的的常常数数项项，用用对对偶偶单单纯纯形形法法求解，其结果见表求解，其结果见表3所示。所示。（2 2）改变右端常数为）改变右端常数为:63本讲稿第六十三页，共九十五页Cj214000bCBXBx1x2x3x4x5x64x305/711/73/7022/72x112/701/74/706/70 x60200112j031/702/720/704x30011/71/145/1417/72x11001/73/71/7

35、4/71x201001/21/21j0002/79/1431/14-69/7表表3最优解最优解64本讲稿第六十四页，共九十五页由表由表1容易得到基变量容易得到基变量x3的系数的系数c3的增量变化范围是的增量变化范围是而而c3=1在在允允许许的的变变化化范范围围之之外外，故故表表1的的解解不不是是最最优优解解。非非基基变变量量的的检验数检验数x4进基，用单纯形法计算，得到表进基，用单纯形法计算，得到表4。（3）改变目标函数）改变目标函数x3的系数为的系数为c3=1;65本讲稿第六十五页，共九十五页表表4XBx1x2x3x4x5x6bx305/711/73/702x112/701/74/701x6

36、0200111j016/701/711/70 x405713014x11110103x60200111j031020-6最优解为最优解为X=（3，0，0，14，0，1）T,最优值最优值z=6。66本讲稿第六十六页，共九十五页c2是非基变量是非基变量x2的系数，由表的系数，由表3知，知，由由1变为变为2时，时，或直接求出或直接求出x2的检验数的检验数从而最优解不变，即从而最优解不变，即X=（1，0，2，0，0，1）。）。（4）改变目标函数中）改变目标函数中x2的系数为的系数为c2=2；67本讲稿第六十七页，共九十五页这这时时目目标标函函数数的的系系数数和和约约束束条条件件的的系系数数都都变变化化

37、了了，同同样样求求出出2判别最优解是否改变。判别最优解是否改变。x2进基，计算结果如表进基，计算结果如表5所示所示（5）改变）改变x2的系数为的系数为68本讲稿第六十八页，共九十五页表表5Cj234000bCBXBx1x2x3x4x5x64x30011/73/7022x11101/74/7010 x60300111j0502/720/70 x30011/73/702x11001/75/211/34/3x201001/31/31/3j0002/725/215/3-35/3最优解最优解69本讲稿第六十九页，共九十五页（6）第一个约束变为）第一个约束变为实际上是改变了实际上是改变了a12及及b1，这

38、时要求，这时要求2及及XB，判断解的情况。，判断解的情况。因为因为可行，所以最优解为可行，所以最优解为70本讲稿第七十页，共九十五页引入松弛变量引入松弛变量x7得得x1、x3是基变量，利用表是基变量，利用表1消去消去x1、x3，得，得x7为为新新的的基基变变量量，基基本本解解X=（1，0，2，0，0，1，2）不不可可行，将上式加入表行，将上式加入表1中用对偶单纯形法迭代得到表中用对偶单纯形法迭代得到表6。（7）增加新约束）增加新约束71本讲稿第七十一页，共九十五页表表6XBx1x2x3x4x5x6x7bx305/711/73/7002x112/701/74/7001x6x700213/7000

39、11/712/7100112j031/702/720/700 x306/11105/1101/1120/11x115/11006/1101/1113/11x6x400213/11000112/111007/11114/11j045/110032/1102/11最优解最优解72本讲稿第七十二页，共九十五页（8）将将原原最最优优解解代代入入约约束束的的左左边边有有5122=110，满足新约束，故最优解不变。，满足新约束，故最优解不变。上上述述cj及及bi的的最最大大允允许许变变化化范范围围是是假假定定其其它它参参数数不不变变的的前前提提下下，单单个个参参数数的的变变化化范范围围，当当几几个个参参数

40、数同同时时在在各各自自范范围围内内变变化化时时，最最优优解解或或最最优优基基有有可可能改变。能改变。1.注意最优解与最优基不变的区别；注意最优解与最优基不变的区别；2.掌握某个参数变化后，最优表中哪些数据会发生变化，如何变化；掌握某个参数变化后，最优表中哪些数据会发生变化，如何变化；3.模型发生变化后不是重新求解，而是在原模型的最优表中求出模型发生变化后不是重新求解，而是在原模型的最优表中求出变化后的数据，根据变化条件，选择合适的方法继续计算。变化后的数据，根据变化条件，选择合适的方法继续计算。73本讲稿第七十三页，共九十五页*4.4参数线性规划参数线性规划在线性规划的实际应用中，由于某种原因

41、，线性规划在线性规划的实际应用中，由于某种原因，线性规划问题的目标函数的价值系数问题的目标函数的价值系数C 和约束条件的右端常数和约束条件的右端常数b会随着某个参数而连续变动。会随着某个参数而连续变动。当数据随着某个参数连续变化时，研究其对最优解的影响，当数据随着某个参数连续变化时，研究其对最优解的影响，即为参数线性规划问题。即为参数线性规划问题。目标函数的价值系数目标函数的价值系数c含有参数的线性规划问题含有参数的线性规划问题右端常数右端常数b含有参数的线性规划问题含有参数的线性规划问题74本讲稿第七十四页，共九十五页(1)目标函数的价值系数含有参数的线性规划问题目标函数的价值系数含有参数的

42、线性规划问题75本讲稿第七十五页，共九十五页求解步骤：求解步骤：令令=0，求得最优解与最优基，求得最优解与最优基B；根据根据求得求得的区间；的区间；运用单纯形法求得其余区间的最优解。运用单纯形法求得其余区间的最优解。例例176本讲稿第七十六页，共九十五页解：解：化为标准形；求化为标准形；求=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本讲稿第七十七页

43、，共九十五页 根据根据求得求得的区间的区间即当即当时最优解为时最优解为C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52 x2-1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-4078本讲稿第七十八页，共九十五页 运用单纯形法求得其余区间的最优解运用单纯形法求得其余区间的最优解当当时时C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2-1/4101/2-1/4010025x33/20101/202300

44、0 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最优解为最优解为79本讲稿第七十九页，共九十五页当当时时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

45、/81/8205/225x30013/2-1/4-3/4215-63x1 100-11/21/210j0005001310j000-31/423/80-285/280本讲稿第八十页，共九十五页当当时时C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-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

46、/30460/3j0010/30-5/6-1/21780/3j0031/6019/125/4-3760/381本讲稿第八十一页，共九十五页参变量的取值范围与最优解为参变量的取值范围与最优解为82本讲稿第八十二页，共九十五页（2）右端常数含有参数的线性规划问题）右端常数含有参数的线性规划问题求解步骤：求解步骤：令令=0，求得最优解与最优基，求得最优解与最优基B；根据根据求得求得的区间；的区间；运用对偶单纯形法求得其余区间的最优解。运用对偶单纯形法求得其余区间的最优解。83本讲稿第八十三页，共九十五页例例2解：解：化为标准形；求化为标准形；求=0的最优解与最优基的最优解与最优基B84本讲稿第八十四

47、页，共九十五页 根据根据求得求得的区间；的区间；则则=0时最优解为时最优解为(0,100,230,0,0,20)TC i325000B-1bCBXBx1x2x3x4x5x62x2-1/4101/2-1/401005x33/20101/202300 x6 200-21120j-400-1-20135085本讲稿第八十五页，共九十五页最优解为最优解为C i325000B-1bb*CBXBx1x2x3x4x5x62x2-1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-786本讲稿第八十六页，共九十五页当当时最优

48、单纯形表为时最优单纯形表为运用单纯形法求得其余区间的最优解。运用单纯形法求得其余区间的最优解。C i325000B-1bb*CBXBx1x2x3x4x5x62x2-1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-72x2 1/410001/4105-15x33/20101/20230-20 x4-1001-1/21/2-105j-5000-5/2-1/21360-12时，最优解为时，最优解为当当87本讲稿第八十七页，共九十五页当当时最优单纯形表为时最优单纯形表为C i325000B-1bb*CBXBx1x

49、2x3x4x5x62x2-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-50021505最优解为最优解为88本讲稿第八十八页，共九十五页参变量的取值范围与最优解为参变量的取值范围与最优解为89本讲稿第八十九页，共九十五页CBXBx1x2x3x4x5b2x213100 x50-1-210090本讲稿第九十页，共九十五页CBXBx1x2x3x4x5b2x2-11310100 x580-1-2

50、1500-2-202091本讲稿第九十一页，共九十五页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/31/9185/9-2x117/919/91/32/9080/90-8/9-41/9-8/3-1/90265/992本讲稿第九十二页，共九十五页CBXBX1X2X3X4X5X6X7b0X5011/4-114X4001-125X210-3/41-Z00-1/4-1-1393本讲稿第九十三页，