第4章 线性规划灵敏度分析PPT讲稿.ppt
第4章 线性规划灵敏度分析1第1页，共95页，编辑于2022年，星期一 线性规划解除有线性规划解除有唯一最优解唯一最优解的情况外，还有如的情况外，还有如下几种情况下几种情况 无可行解无可行解无可行解无可行解退化退化退化退化无穷多解无穷多解无穷多解无穷多解 无界解无界解无界解无界解人工人工变量变量不能不能从基从基底中底中换出换出基可行基可行解中非解中非零元素零元素个数小个数小于基变于基变量数量数检验数检验数中零的中零的个数多个数多于基变于基变量的个量的个数数检验数大于检验数大于零，但对应零，但对应列元素小于列元素小于等于零，无等于零，无换出变量换出变量2第2页，共95页，编辑于2022年，星期一唯一最优解唯一最优解 否 否否 是是是添添加加松松弛弛变变量量、人人工工变变量量列出初始单纯形表列出初始单纯形表计算非基变量计算非基变量各列的检验数各列的检验数j所有所有j 0基变量中基变量中有非零的有非零的人工变量人工变量某非基某非基变量检变量检验数为验数为零零无可行解无可行解无穷多最优解无穷多最优解对任一对任一j0有有aik0无界解无界解令令k=maxjxk为换入变量为换入变量对对 所所 有有 aik 0计计 算算i i=bi/aik令令l=min=mini i 第第l l个个基基变变量量为为换换出出变变量，量，alk为主元素为主元素 迭代运算迭代运算.用非基变量用非基变量xk替换换出变量替换换出变量.对主元素行对主元素行(第第l行行)令令bl/alkbl;alj/alkajl对主元素列对主元素列(第第k列列)令令1alk;0;0其它其它元素表中其它行列元素元素表中其它行列元素令令aij-ali/alkaika aijij bi-bl/alkaikbi j-alj/alkk j否对目标函数求极大值标准型线性规划问对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图：题，单纯形法计算步骤的框图：3第3页，共95页，编辑于2022年，星期一第四章第四章 线性规划灵敏度分析线性规划灵敏度分析4.1灵敏度分析的基本原理灵敏度分析的基本原理4.2目标函数系数的灵敏度分析目标函数系数的灵敏度分析4.3右端常数的灵敏度分析右端常数的灵敏度分析4.4技术系数的灵敏度分析技术系数的灵敏度分析*4.5参数线性规划参数线性规划4第4页，共95页，编辑于2022年，星期一线线性性规规划划的的灵灵敏敏度度分分析析也也称称为为敏敏感感性性分分析析或或优优化化后后分分析析，它它是是研研究究和和分分析析参参数数（cj，bi，aij）的的波波动动对对最最优优解解的的影影响响程程度度，主主要要研研究究下下面面两个方面：两个方面：（1）参参数数在在什什么么范范围围内内变变化化时时，原原最最优优解解或或最最优优基基不不变变数数据据的的稳稳定区间；定区间；（2）当当参参数数超超出出（1）的的变变化化范范围围时时，最最优优解解或或最最优优基基有有何何变变化化如如何何求出新的最优解和最优基。求出新的最优解和最优基。当当模模型型的的参参数数发发生生变变化化后后，可可以以不不必必对对线线性性规规划划问问题题重重新新求求解解，而而用用灵灵敏敏度度分分析析方方法法直直接接在在原原线线性性规规划划取取得得的的最最优优结结果果的的基基础础上上进进行行分分析析或或求求解解，既既可可减减少少计计算算量量，又又可可事事先先知知道道参参数数的的变变化化范范围，及时对原决策作出调整和修正。围，及时对原决策作出调整和修正。4.1灵敏度分析的基本原理灵敏度分析的基本原理5第5页，共95页，编辑于2022年，星期一单纯形法：单纯形法：对应于基对应于基B的典则形式（典式）的典则形式（典式）.Ax=b基变量用非基变量表示：基变量用非基变量表示：代入目标函数：代入目标函数：6第6页，共95页，编辑于2022年，星期一初始单纯形表初始单纯形表 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页，编辑于2022年，星期一分析分析 变化对最优解的影响。变化对最优解的影响。CCBCNCBXBbXBXNCBXBB-1 b IB-1 NZ-CB B-1 b0CN-CB B-1 b最优单纯形表最优单纯形表8第8页，共95页，编辑于2022年，星期一上表中上表中6个常数个常数a1,a2,a3,b,1,2取值在什么范围可使取值在什么范围可使1、现可行解最优，且唯一？何时不唯一？、现可行解最优，且唯一？何时不唯一？2、现基本解不可行；、现基本解不可行；3、问题无可行解；、问题无可行解；4、无有限最优解；、无有限最优解；5、现基本解可行，由、现基本解可行，由x1取代取代x6目标函数可改善。目标函数可改善。cjB-1bcBxBx1x2x3x4x5x6x34a110a20bx4-1-501-102x6a3-300-413j1200-309第9页，共95页，编辑于2022年，星期一线性规划标准形式线性规划标准形式(1)、参数、参数A，b，C在什么范围内变动，对当前方案无影响？在什么范围内变动，对当前方案无影响？(2)、参数、参数A，b，C中的一个中的一个(几个几个)变动，对当前方案影响？变动，对当前方案影响？(3)、如果最优方案改变，如何用简便方法求新方案？、如果最优方案改变，如何用简便方法求新方案？当线性规划问题中的一个或几个参数变化时，可以用单纯形法当线性规划问题中的一个或几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。从头计算，看最优解有无变化，但这样做既麻烦又没有必要。10第10页，共95页，编辑于2022年，星期一4.1目标函数系数的灵敏度分析目标函数系数的灵敏度分析考虑检验数考虑检验数(1)若若cj 是非基变量的系数：是非基变量的系数：11第11页，共95页，编辑于2022年，星期一解：最优单纯形表解：最优单纯形表 例例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页，编辑于2022年，星期一从表中看到从表中看到c3=-4,3=-9/5可得到可得到c3-3=9/5时，即时，即c3-4+9/5=-11/5时原最优解不变。时原最优解不变。解：最优单纯形表解：最优单纯形表 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/513第13页，共95页，编辑于2022年，星期一(2)若若cj是基变量的系数是基变量的系数14第14页，共95页，编辑于2022年，星期一以下分两种情况讨论：以下分两种情况讨论：1如果如果 cr 0上式才有可能不成立上式才有可能不成立,因此有：因此有：2如果如果 cr 0,只有只有arj0，则问题的，则问题的最优解将发生变化，此时对原最终表适当修改后，应最优解将发生变化，此时对原最终表适当修改后，应用单纯形法继续计算得到问题的最优解。用单纯形法继续计算得到问题的最优解。16第16页，共95页，编辑于2022年，星期一例例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页，编辑于2022年，星期一C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/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第18页，共95页，编辑于2022年，星期一从表中看到从表中看到可得到可得到-3c21时，原最优解不变。时，原最优解不变。C i23+c2000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143+c2 x2 011/2-1/802j00-3/2-c2/2-1/8+c2/8014+2c219第19页，共95页，编辑于2022年，星期一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页，编辑于2022年，星期一已知最优表如下已知最优表如下例例3某企业利用两种资源生产三种产品的最优计划问题某企业利用两种资源生产三种产品的最优计划问题,归结为下列线性规划归结为下列线性规划cj54300CBXBbx1x2x3x4x545x2x140200110 232 1 11j26000 4 3 121第21页，共95页，编辑于2022年，星期一cj54300CBXBbx1x2x3x4x545x2x140200110 232 1 11j26000 4 3 1最优计划是两种产品分别生产最优计划是两种产品分别生产40单位与单位与20单位，最大产值单位，最大产值z*=260单单位。位。（1）确定）确定x2的价值系数的价值系数c2的变化范围，使原最优解保持最优。的变化范围，使原最优解保持最优。（2）c3在什么范围内变化，最优解不变？在什么范围内变化，最优解不变？（3）若）若c3从从3变为变为9，求新的最优计划。，求新的最优计划。22第22页，共95页，编辑于2022年，星期一解解（1）因为）因为x2为基变量，为基变量，c2的变换范围：的变换范围：因此当因此当x2的价值系数在的价值系数在即在区间即在区间2.5,5变化时，最优解不变。变化时，最优解不变。23第23页，共95页，编辑于2022年，星期一（2）因为）因为c3是是非基变量非基变量x3的价值系数，由公式得到的价值系数，由公式得到 c3+c3的变换范围：的变换范围：即当即当c3在在 c3+c33+4=7时，最优解不变。时，最优解不变。（3）当）当c3从从3变为变为9时，原最优解失去最优性，在表时，原最优解失去最优性，在表中作适当变动后（修改中作适当变动后（修改c3的值，重新计算检验数），的值，重新计算检验数），用单纯形法容易求得新的最优表如下：用单纯形法容易求得新的最优表如下：24第24页，共95页，编辑于2022年，星期一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，即随着第三种产品价格的上升，总产，即随着第三种产品价格的上升，总产值上升。值上升。25第25页，共95页，编辑于2022年，星期一设分量设分量br变化为变化为br+br，根据前面的讨论：，根据前面的讨论：最优解的基变量最优解的基变量XB=B-1b，那么只要保持，那么只要保持B-1(b+b)0则最优基不变，即基变量保持，只有值的变化；则最优基不变，即基变量保持，只有值的变化；否则，需要利用否则，需要利用对偶单纯形法对偶单纯形法继续计算。继续计算。4.2右端常数的灵敏度分析右端常数的灵敏度分析26第26页，共95页，编辑于2022年，星期一27第27页，共95页，编辑于2022年，星期一例例4已知前述例已知前述例2的最优解及最优单纯形表的最优解及最优单纯形表28第28页，共95页，编辑于2022年，星期一下表为最优单纯形表下表为最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2-1/801429第29页，共95页，编辑于2022年，星期一由最优单纯形表得由最优单纯形表得:30第30页，共95页，编辑于2022年，星期一31第31页，共95页，编辑于2022年，星期一不可行!用对偶单纯形法计算用对偶单纯形法计算将将b代入原最优单纯形表中，运用对偶单纯形法计算最优解。代入原最优单纯形表中，运用对偶单纯形法计算最优解。32第32页，共95页，编辑于2022年，星期一将将b代入原最优单纯形表中，运用对偶单纯形法计算最优解。代入原最优单纯形表中，运用对偶单纯形法计算最优解。经一次迭代后，求得新的最优解经一次迭代后，求得新的最优解:(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页，编辑于2022年，星期一(1)增加一个新变量增加一个新变量增加一个变新量，相当于系数矩阵增加一列。增加一个变新量，相当于系数矩阵增加一列。设增加变量设增加变量xn+1，则有相应的，则有相应的Pn+1,cn+1。计算出计算出Pn+1=B-1Pn+1,n+1=cn+1-cB Pn+1填入最优单纯形表填入最优单纯形表,若若 n+10则则最优解不变；最优解不变；否则，进一步用单纯形法求解。否则，进一步用单纯形法求解。4.3技术系数的灵敏度分析技术系数的灵敏度分析34第34页，共95页，编辑于2022年，星期一例例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-1/801435第35页，共95页，编辑于2022年，星期一36第36页，共95页，编辑于2022年，星期一用单纯形法进一步求解，可得：用单纯形法进一步求解，可得：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页，编辑于2022年，星期一(2)增加一个新约束条件增加一个新约束条件增加一个新约束条件相当于在系数矩阵中增加一行。增加一个新约束条件相当于在系数矩阵中增加一行。增加一个约束条件之后，应把最优解带入新的约束，若满足则增加一个约束条件之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为元素变为0，进一步用单纯形法或对偶单纯形法求解。，进一步用单纯形法或对偶单纯形法求解。38第38页，共95页，编辑于2022年，星期一例例6 求当增加求当增加3x1+2x215时，原最时，原最优解是否保持不变，若变动优解是否保持不变，若变动求出新的最优解。求出新的最优解。解解:下表为最优单纯形表下表为最优单纯形表C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2-1/801439第39页，共95页，编辑于2022年，星期一将将3x1+2x2+x6=15代入原最优单纯形表。代入原最优单纯形表。经经对偶单纯形法对偶单纯形法迭代一步，可得：迭代一步，可得：最优解为最优解为(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第40页，共95页，编辑于2022年，星期一(3)个别技术系数个别技术系数aij的改变的改变(计划生产的产品工艺结构改变计划生产的产品工艺结构改变)非基变量非基变量xj工艺改变工艺改变只影响单纯形表只影响单纯形表Pj 列列，j.关键看关键看 j 0?还是还是0?.用增加新变量类似方法解决。用增加新变量类似方法解决。基变量基变量xj工艺改变，复杂，根据具体情况讨论。工艺改变，复杂，根据具体情况讨论。41第41页，共95页，编辑于2022年，星期一分析分析:42第42页，共95页，编辑于2022年，星期一注注:Y可由最优单纯形表查得可由最优单纯形表查得43第43页，共95页，编辑于2022年，星期一最优单纯形表为最优单纯形表为求：（求：（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/52/5-2 x1 107/5-1/5-2/511/5j00-9/5-8/5-1/5-28/544第44页，共95页，编辑于2022年，星期一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页，编辑于2022年，星期一另解：（另解：（1）P3由由(-13)T改为改为(-12)T由最由单纯形表可知由最由单纯形表可知所以原最优解不变所以原最优解不变46第46页，共95页，编辑于2022年，星期一（2）P1由由(1，2)T改为改为(1，1)T，(x1为基变量为基变量)由最优单纯形表可知由最优单纯形表可知代入最优单纯形表，用代入最优单纯形表，用P1代替代替P147第47页，共95页，编辑于2022年，星期一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-59/7新的最优解为新的最优解为:(0,5/7,11/7,0,0)T最优值为：最优值为：59/748第48页，共95页，编辑于2022年，星期一最优单纯形表最优单纯形表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页，编辑于2022年，星期一例例8求例求例2中中 a24的变化范围的变化范围,使最优解不变使最优解不变.解解:50第50页，共95页，编辑于2022年，星期一例例9在例在例2的基础上，企业要增加一个的基础上，企业要增加一个新产品新产品,每件产品需每件产品需2个台时，原材料个台时，原材料A6kg，原材料原材料B3kg，利润，利润5元元/件，问如何安排各产件，问如何安排各产品的产量，使利润最大？品的产量，使利润最大？解：解：532利润12340料B16604料A8221设备b51第51页，共95页，编辑于2022年，星期一表明生产新品有利表明生产新品有利。52第52页，共95页，编辑于2022年，星期一5/40-1/8-3/200 1/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x2ix353第53页，共95页，编辑于2022年，星期一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第54页，共95页，编辑于2022年，星期一小结：灵敏度分析小结：灵敏度分析55第55页，共95页，编辑于2022年，星期一56第56页，共95页，编辑于2022年，星期一综合例题：考虑下列线性规划综合例题：考虑下列线性规划求求出出最最优优解解后后，分分别别对对下下列列各各种种变变化化进进行行灵灵敏敏度度分分析析，求求出出变变化化后的最优解。后的最优解。（1 1）将目标函数改为：）将目标函数改为：（2 2）改变右端常数为）改变右端常数为:57第57页，共95页，编辑于2022年，星期一（3）改变目标函数）改变目标函数x3的系数为的系数为c3=1;（4）改变目标函数中）改变目标函数中x2的系数为的系数为c2=2；（5）改变）改变x2的系数为的系数为（6）改变约束（）改变约束（1）为）为（7）增加新约束）增加新约束（8）增加新约束）增加新约束58第58页，共95页，编辑于2022年，星期一解：加入松弛变量解：加入松弛变量x4、x5、x6，用单纯形法计算，得最优表，用单纯形法计算，得最优表1：Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/701/74/7010 x60200111j031/702/720/70-10表表159第59页，共95页，编辑于2022年，星期一最优解最优解X=（1，0，2，0，0，1），最优值），最优值Z=10，最优基，最优基（1）等价于等价于，即将，即将cj改变为（改变为（2，1，4），其中），其中c1=2、c3=4是基变量的系数，是基变量的系数，c2=1是非基变量的系数，是非基变量的系数，求得检验数求得检验数60第60页，共95页，编辑于2022年，星期一这这里里表表1的的解解不不是是最最优优，将将上上述述检检验验数数代代替替表表1的的检检验验数数，再再单单纯纯形法继续迭代，计算结果如表形法继续迭代，计算结果如表2所示。所示。61第61页，共95页，编辑于2022年，星期一表表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页，编辑于2022年，星期一基变量的解为基变量的解为基基本本解解不不可可行行，将将求求得得的的XB代代替替表表1中中的的常常数数项项，用用对对偶偶单单纯纯形形法法求求解，其结果见表解，其结果见表3所示。所示。（2 2）改变右端常数为）改变右端常数为:63第63页，共95页，编辑于2022年，星期一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页，编辑于2022年，星期一由表由表1容易得到基变量容易得到基变量x3的系数的系数c3的增量变化范围是的增量变化范围是而而c3=1在在允允许许的的变变化化范范围围之之外外，故故表表1的的解解不不是是最最优优解解。非非基基变变量量的检验数的检验数x4进基，用单纯形法计算，得到表进基，用单纯形法计算，得到表4。（3）改变目标函数）改变目标函数x3的系数为的系数为c3=1;65第65页，共95页，编辑于2022年，星期一表表4XBx1x2x3x4x5x6bx305/711/73/702x112/701/74/701x60200111j016/701/711/70 x405713014x11110103x60200111j031020-6最优解为最优解为X=（3，0，0，14，0，1）T,最优值最优值z=6。66第66页，共95页，编辑于2022年，星期一c2是非基变量是非基变量x2的系数，由表的系数，由表3知，知，由由1变为变为2时，时，或直接求出或直接求出x2的检验数的检验数从而最优解不变，即从而最优解不变，即X=（1，0，2，0，0，1）。）。（4）改变目标函数中）改变目标函数中x2的系数为的系数为c2=2；67第67页，共95页，编辑于2022年，星期一这这时时目目标标函函数数的的系系数数和和约约束束条条件件的的系系数数都都变变化化了了，同同样样求求出出2判判别别最最优解是否改变。优解是否改变。x2进基，计算结果如表进基，计算结果如表5所示所示（5）改变）改变x2的系数为的系数为68第68页，共95页，编辑于2022年，星期一表表5Cj234000bCBXBx1x2x3x4x5x64x30011/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页，编辑于2022年，星期一（6）第一个约束变为）第一个约束变为实际上是改变了实际上是改变了a12及及b1，这时要求，这时要求2及及XB，判断解的情况。，判断解的情况。因为因为可行，所以最优解为可行，所以最优解为70第70页，共95页，编辑于2022年，星期一引入松弛变量引入松弛变量x7得得x1、x3是基变量，利用表是基变量，利用表1消去消去x1、x3，得，得x7为为新新的的基基变变量量，基基本本解解X=（1，0，2，0，0，1，2）不不可可行行，将上式加入表将上式加入表1中用对偶单纯形法迭代得到表中用对偶单纯形法迭代得到表6。（7）增加新约束）增加新约束71第71页，共95页，编辑于2022年，星期一表表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/110032/1102/11最优解最优解72第72页，共95页，编辑于2022年，星期一（8）将将原原最最优优解解代代入入约约束束的的左左边边有有5122=110，满足新约束，故最优解不变。，满足新约束，故最优解不变。上上述述cj及及bi的的最最大大允允许许变变化化范范围围是是假假定定其其它它参参数数不不变变的的前前提提下下，单单个个参参数数的的变变化化范范围围，当当几几个个参参数数同同时时在在各各自自范范围围内内变变化化时时，最最优优解解或或最最优优基基有可能改变。有可能改变。1.注意最优解与最优基不变的区别；注意最优解与最优基不变的区别；2.掌握某个参数变化后，最优表中哪些数据会发生变化，如何变化；掌握某个参数变化后，最优表中哪些数据会发生变化，如何变化；3.模型发生变化后不是重新求解，而是在原模型的最优表中求出变模型发生变化后不是重新求解，而是在原模型的最优表中求出变化后的数据，根据变化条件，选择合适的方法继续计算。化后的数据，根据变化条件，选择合适的方法继续计算。73第73页，共95页，编辑于2022年，星期一*4.4参数线性规划参数线性规划在线性规划的实际应用中，由于某种原因，线性规在线性规划的实际应用中，由于某种原因，线性规划问题的目标函数的价值系数划问题的目标函数的价值系数C 和约束条件的右端常和约束条件的右端常数数b会随着某个参数而连续变动。会随着某个参数而连续变动。当数据随着某个参数连续变化时，研究其对最优解的当数据随着某个参数连续变化时，研究其对最优解的影响，即为参数线性规划问题。影响，即为参数线性规划问题。目标函数的价值系数目标函数的价值系数c含有参数的线性规划问题含有参数的线性规划问题右端常数右端常数b含有参数的线性规划问题含有参数的线性规划问题74第74页，共95页，编辑于2022年，星期一(1)目标函数的价值系数含有参数的线性规划问题目标函数的价值系数含有参数的线性规划问题75第75页，共95页，编辑于2022年，星期一求解步骤：求解步骤：令令=0，求得最优解与最优基，求得最优解与最优基B；根据根据求得求得的区间；的区间；运用单纯形法求得其余区间的最优解。运用单纯形法求得其余区间的最优解。例例176第76页，共95页，编辑于2022年，星期一解：解：化为标准形；求化为标准形；求=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页，编辑于2022年，星期一 根据根据求得求得的区间的区间即当即当时最优解为时最优解为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第78页，共95页，编辑于2022年，星期一 运用单纯形法求得其余区间的最优解运用单纯形法求得其余区间的最优解当当时时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最优解为最优解为79第79页，共95页，编辑于2022年，星期一当当时时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页，编辑于2022年，星期一当当时时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/30460/3j0010/30-5/6-1/21780/3j0031/6019/125/4-3760/381第81页，共95页，编辑于2022年，星期一参变量的取值范围与最优解为参变量的取值范围与最优解为82第82页，共95页，编辑于2022年，星期一（2）右端常数含有参数的线性规划问题）右端常数含有参数的线性规划问题求解步骤：求解步骤：令令=0，求得最优解与最优基，求得最优解与最优基B；根据根据求得求得的区间；的区间；运用对偶单纯形法求得其余区间的最优解。运用对偶单纯形法求得其余区间的最优解。83第83页，共95页，编辑于2022年，星期一例例2解：解：化为标准形；求化为标准形；求=0的最优解与最优基的最优解与最优基B84第84页，共95页，编辑于2022年，星期一 根据根据求得求得的区间；的区间；则则=0时最优解为时最优解为(0,100,230,0,0,20)TC i325000B-1bCBXBx1x2x3x4x5x62x2-1/4101/2-1/401005x33/20101/202300 x6 200-21120j-400-1-20135085第85页，共95页，编辑于2022年，星期一最优解为最优解为C i325000B-1bb*CBXBx1x2x3x4x5x62x2-1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-786第86页，共95页，编辑于2022年，星期一当当时最优单纯形表为时最优单纯形表为运用单纯形法求得其余区间的最优解。运用单纯形法求得其余区间的最优解。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-1
