运筹学-第四章-lp灵敏度

《运筹学-第四章-lp灵敏度》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章LP灵敏度分析SensitivityAnalysisofLP§4-1目标函数系数的变化§4-2右端常数项的变化§4-3系数矩阵A的变化§4-4灵敏度报告和影子价格制作与教学河北工业大学管理学院孔造杰kongzj@sina.comExit2003年9月13日12时24分§4-1目标函数系数的变化∑通过单纯形方法或计算软件求得了LP问题的最优解，应该明确所得到的最优解是在系数项A、b、C的当前值条件下得到的。当其中某一个系数发生改变时会对当前最优解产生怎样的影响则是本章所要研究的内容。∑首先讨论目标函数系数C的变化所产生的影响。1.C是非基变量x的目标系数jj由单纯形方法可知，非基变

2、量的目标系数c的变化仅仅影响到jx的检验数。j−1非基变量xj的检验数为：σj=cj−CBBPj'−1当变c化了∆c后：σj=cj+∆cj−CBBPjjj'如果cj变化后当前最优解不变，则：σj≤0河北工业大学管理学院孔造杰制作Page2of432003年9月13日12时24分§4-1目标函数系数的变化——基变量目标系数C的变化r−1即：c+∆c−CBP≤0jjBj−1∴∆c≤CBP−cjBjj由此可见，c向小的方向变，不会影响最优解；向大的方向j变，其最大值为YP。j2.Cr是基变量xr的目标系数−1单纯形表中的检验数为:σj=cj−CBBPj由于c是基变量的系数，所以它的变化不仅影

3、响其对应变量的r检验数，而且影响到C的变化，进而影响除基变量之外的所有变B量的检验数。河北工业大学管理学院孔造杰制作Page3of432003年9月13日12时24分§4-1目标函数系数的变化——基变量目标系数C的变化r'变化后的CB=CB+∆CB其中∆CB=(0,...,∆cr,...,0)''−1变化后的检验数为：σ=c−CBPjjBj−1=c−(C+∆C)BPjBBj−1−1=c−CBP−∆CBPjBjBj−1=σ−(0,...,∆c,...,0)BPjrj'=σ−(0,...,∆c,...,0)Pjrj'=σ−∆cajrrj''若当前最优基不变，则应有σj≤0，由此得：σj−∆

4、crarj≤0'即：∆ca≥σrrjj'其中arj为最终单纯形表中对应基变量xr的第r行第j列的数值，j=1,…,n河北工业大学管理学院孔造杰制作Page4of432003年9月13日12时24分§4-1目标函数系数的变化——基变量目标系数C的变化rσ'j当arj<0时，有∆cr≤'arjσ'j当arj>0时，有∆cr≥'arj由此得到∆c的变化范围为：r''''max{σ/aa>0}≤∆c≤min{σ/aa<0}jrjrjrjrjrjjj注：①；σ≤0j②∆c大于等于负值中最大，小于等于正值中最小；r③计算过程可以在单纯形表中完成。河北工业大学管理学院孔造杰制作Page5of4320

5、03年9月13日12时24分§4-1目标函数系数的变化——基变量目标系数C的变化r∑例4-1：以第一章例1-1为例，求c2的变化范围。¾其最终单纯形表如下：C23000jCXxxxxxbθBB123452x1011/4041加0x00－21/214入5△3x2011/2－1/802C2c－z00－3/2－1/8014jjC23+△C000j2CXxxxxxbθBB123452x1011/40410x00－21/21453+△Cx011/2－1/80222c－z00－3/2-1/2△C－1/8+1/8△C014jj22河北工业大学管理学院孔造杰制作Page6of432003年9月13日1

6、2时24分§4-1目标函数系数的变化——基变量目标系数C的变化r∑若当前最优基不变，则所有检验数仍大于等于零，所以有：21由−−∆c≤0，得∆c2≥−323211由−+∆c≤0，得∆c≤12288∴基变量x2在目标函数的系数c2当前值的可变化范围是：−3≤∆c≤12∴基变量x的目标系数c的取值范围为[0，4]，在此范围内22变化，可以不影响当前最优解。河北工业大学管理学院孔造杰制作ExitPage7of432003年9月13日12时24分§4-2右端常数项的变化−−1∑在单纯形表的最终表中，基变量的取值为：X=Bb=bB'若b中第r个分量br变化了∆br，即新的右端项为：b=b+∆bT

7、其中：∆b=(0,...,∆b,...,0)r'−1'−1∑则变化后的基变量取值为：X=Bb=B(b+∆b)B−1−1=Bb+B∆b−1()T=b+B0L∆bL0rb1a1r⋅∆brb2a2r⋅∆br=+MMba⋅∆bmmrr河北工业大学管理学院孔造杰制作Page8of432003年9月13日12时24分§4-2右端常数项的变化'∑若保持当前最优基不变，则应有：X≥0B∴b+∆b.a≥0i