单纯形法的灵敏度分析与对偶

《单纯形法的灵敏度分析与对偶》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章*单纯形法的灵敏度分析与对偶单纯形表的灵敏度分析线性规划的对偶问题对偶单纯形法第六章*单纯形法的灵敏度分析与对偶如何利用最优单纯形表进行灵敏度分析。。单纯形表--求解结果：迭代次数基变量CBx1X2s1s2S3b比值501000000x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50第1节单纯形表的灵敏度分析一.目标函数中变量系数Ck灵敏度分析现要利用单纯形表法来进行Ck的灵敏度分析。由于目标函数变量分为基与非基变量，故讨论时,分两类来讨论。1.在最终的单纯形表里,xK非基变量.2.在最终的单纯形表里,xK基变

2、量.第1节单纯形表的灵敏度分析1.在最终的单纯形表里,xK非基变量。由于约束条件（方程）系数增广矩阵在迭代中只是其本身的行的初等变换与CK没有任何关系，所以当CK变为CK+△CK时，在最终单纯形表中其系数的增广矩阵不变，又因为xK是非基变量，所以基变量的目标函数的系数不变，即CB不变，可知ZK也不变，只是CK变为CK+△CK。这时σK=CK－ZK变成了CK+△CK－ZK=σK+△CK.要使得原来的最优解仍为最优解，只要σK+△CK≤0即可，也就是△CK≤－σK即可。第1节单纯形表的灵敏度分析２.在最终的单纯形表里,xK为基变量。由于约束条件（方程）系数增广矩阵在迭代中只是其本身的行的初等变换与

3、CK没有任何关系，所以当CK变为CK+△CK时，在最终单纯形表中其系数的增广矩阵不变，但基变量在目标函数的系数CB变了，则Zj也变了，相应地，σＪ也变了。变化规律为：目标函数：maxz=50x1+100x2x1+x2≤3002x1+x2≤400x1≥0,x2≥0s.t.x2≤250maxz=50x1+100x2x1+x2+s1=3002x1+x2+s2=400x1≥0,x2≥0,si≥0s.t.x2+s3=250一、线性规划问题解的基本概念基及基本解:maxz=50x1+100x2+0s1+0s2+0s31x1+1x2+1s1+0s2+0s3=3002x1+1x2+0s1+1s2+0s3=40

4、0x1≥0,x2≥0,s1≥0，s2≥0，s3≥0s.t.0x1+1x2+0s1+0s2+1s3=250表解形式的单纯形法例子:初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50（１）先分析非基变量s1:c3σ3由于是非基变量，故套用公式（1）当△C3≤-σ3,时最优解不变;已知σ3=-50,△C3≤－（－50）=50；c’=c+△C<=0+50=50最优解不变。（2）再分析基变量的系数分析：从表中获得了:a11=1,a12=0,a13=1,a

5、14=0,a15=-1例如对基变量X1的系数C1进行灵敏度分析：单纯形表灵敏度分析迭代次数基变量CBx1X2s1s2S3b比值501000002x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-500---50L--50R缩小区间故，max{-50}≤△C1≤min{50}，左半径和右半径[保证区间半径最小]则当-50≤△C1≤50时最优解不变，即x1的目标函数系数C’有：50-50=c1+L≤C‘=C1+△C1≤c1+R=50+50，0≤C‘≤100时，最优解不变。**********************最优解如下

6、*************************目标函数最优值为:27500变量最优解相差值-----------------------x1500x22500约束松弛/剩余变量对偶价格----------------------------105025003050目标函数系数范围:变量下限当前值上限-------------------------------x1050100x250100无上限常数项数范围:约束下限当前值上限-------------------------------12503003252350400无上限3200250300LPOPTIMUMFOUNDATSTEP2O

7、BJECTIVEFUNCTIONVALUE1)27500.00VARIABLEVALUEREDUCEDCOSTX150.0000000.000000X2250.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000050.0000003)50.0000000.0000004)0.00000050.000000NO.ITERATIONS=2RANGESI