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

《第4章 线性规划灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1线性规划解除有唯一最优解的情况外，还有如下几种情况无可行解退化无穷多解无界解人工变量不能从基底中换出基可行解中非零元素个数小于基变量数检验数中零的个数多于基变量的个数检验数大于零，但对应列元素小于等于零，无换出变量2唯一最优解否否否是是是添加松弛变量、人工变量列出初始单纯形表计算非基变量各列的检验数бj所有бj0基变量中有非零的人工变量某非基变量检验数为零无可行解无穷多最优解对任一бj≥0有aik≤0无界解令бk=max{бj}xk为换入变量对所有aik>0计算θi=bi/aik令θl=min{θi}第l个基变量为换出变量，alk为主元素迭代运算.用非基变量xk替换换出

2、变量.对主元素行(第l行)令bl/alk→bl;alj/alk→ajl对主元素列(第k列)令1→alk;0→其它元素表中其它行列元素令aij-ali/alk·aik→aijbi-bl/alk·aik→biбj-alj/alk·бk→бj否对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图：3第四章线性规划灵敏度分析§4.1灵敏度分析的基本原理§4.2目标函数系数的灵敏度分析§4.3右端常数的灵敏度分析§4.4技术系数的灵敏度分析*§4.5参数线性规划4线性规划的灵敏度分析也称为敏感性分析或优化后分析，它是研究和分析参数（cj，bi，aij）的波动对最优解的影响程度

3、，主要研究下面两个方面：（1）参数在什么范围内变化时，原最优解或最优基不变——数据的稳定区间；（2）当参数超出（1）的变化范围时，最优解或最优基有何变化——如何求出新的最优解和最优基。当模型的参数发生变化后，可以不必对线性规划问题重新求解，而用灵敏度分析方法直接在原线性规划取得的最优结果的基础上进行分析或求解，既可减少计算量，又可事先知道参数的变化范围，及时对原决策作出调整和修正。§4.1灵敏度分析的基本原理5单纯形法：对应于基B的典则形式（典式）.Ax=b基变量用非基变量表示：代入目标函数：6初始单纯形表cc1c2cmcm+1cm+2cncBxBbx1x2xmxm+1xm

4、+2xnθc1c2cmx1x2xmb’1b’2b’m100a’1m+1a’1m+2a’1n010a’2m+1a’2m+2a’2n001a’mm+1a’mm+2a’mn-z(0)000σm+1σm+2σn7分析变化对最优解的影响。CCBCNCBXBbXBXNCBXBB-1bIB-1NZ-CBB-1b0CN-CBB-1b最优单纯形表8上表中6个常数a1,a2,a3,b,1,2取值在什么范围可使1、现可行解最优，且唯一？何时不唯一？2、现基本解不可行；3、问题无可行解；4、无有限最优解；5、现基本解可行，由x1取代x6目标函数可改善。cjB-1bcBxBx1x2x3x4x5x

5、6x34a110a20bx4-1-501-102x6a3-300-413σjσ1σ200-309线性规划标准形式(1)、参数A，b，C在什么范围内变动，对当前方案无影响？(2)、参数A，b，C中的一个(几个)变动，对当前方案影响？(3)、如果最优方案改变，如何用简便方法求新方案？当线性规划问题中的一个或几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。10§4.1目标函数系数的灵敏度分析考虑检验数(1)若cj是非基变量的系数：11解：最优单纯形表例1试求c3在多大范围内变动时，原最优解保持不变。cj-2-3-400B-1bcBxBx1x2x

6、3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5σj00-9/5-8/5-1/5-28/512从表中看到c3=-4,σ3=-9/5可得到Δc3≤-σ3=9/5时，即c’3≤-4+9/5=-11/5时原最优解不变。解：最优单纯形表cj-2-3-400B-1bcBxBx1x2x3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5σj00-9/5-8/5-1/5-28/513(2)若cj是基变量的系数14以下分两种情况讨论：1．如果cr<0,只有a’rj>0上式才有可能不成立,因此有：2．如果

7、cr>0,只有a’rj<0上式才有可能不成立,因此有：15因此可得cr的变化范围：当cr在上述变化范围内变化时：目标函数值的改变量：z=crxr；对偶解的改变量：y=CBB-1，原问题的最优基和最优解不会改变。当cr的变化超出该范围时，必定有σr>0，则问题的最优解将发生变化，此时对原最终表适当修改后，应用单纯形法继续计算得到问题的最优解。16例2已知问题的最优单纯形表，(1)求c2在什么范围内变动时，原最优解保持不变；(2)c2=5时，求新的最优解。最优单纯形表Ci23000B-1bCBXBx1x2