第6章 单纯形法的灵敏度分析与对偶.pptVIP免费

1/43第六章单纯形法的灵敏度分析与对偶•§1单纯形表的灵敏度分析•§2线性规划的对偶问题•§3对偶规划的基本性质•§4对偶单纯形法2/43§1单纯形表的灵敏度分析一、目标函数中变量Ck系数灵敏度分析1.在最终的单纯形表里，Xk是非基变量由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系，所以当Ck变成Ck+Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变成了Ck+Ck。这时K=Ck-Zk就变成了Ck+Ck-Zk=K+Ck。要使原来的最优解仍为最优解，只要K+Ck≤0即可，也就是Ck的增量Ck≤-K。2.在最终的单纯形表中，Xk是基变量当Ck变成Ck+Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目标函数的系数CB变了，则ZJ(J=1,2,…..,N)一般也变了，不妨设CB=(CB1,CB2。。。,Ck,…，CBm),当CB变成=(CB1,CB2。。。,Ck+Ck,…,CBm),则：ZJ=(CB1,CB2。。。,Ck,…，CBm)(a’1j,a’2j,…,a’Kj,…,a’mj)Z’J=(CB1,CB2。。。,Ck+Ck,…，CBm)(a’1j,a’2j,…,a’Kj,…,a’mj)=ZJ+Cka’KjTT3/43§1单纯形表的灵敏度分析根据上式可知检验数J(J=1,2,…..,m)变成了’J,有’J=CJ-Z’J=J+CKa’Kj。要使最优解不变，只要当JK时，’J<=00a'a'δMinΔC0a'a'δMaxΔCa'δΔCa'0a'δΔCa'0a'0δ'1a'0δX,a'ΔCZΔCC'ZΔCCδ'kj;0a'δ,a'δΔC,0a';0a'δ,a'δΔC,0a'δa'ΔC0,a'ΔCδkjkjjkkjkjjkkjjkkjkjjkkjkkkkkkKkkkkkkkkkkkjjkjjkkjkjjkjjkkjjkjkkjkj的变化范围为，所以可知满足的，所有小于，满足的以外的所有大于于除了要使得最优解不变，对。，可知，知是基变量，因为时，当这里时当这里时当4/43§1单纯形表的灵敏度分析例：目标函数：Maxz=50X1+100X2约束条件：X1+X2≤3002X1+X2≤400X2≤250X1，X2≥0最优单纯形表如下迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-505/43§1单纯形表的灵敏度分析我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。这里δ3=-50，所以当c3的增量Δc3≤50，最优解不变。再对基变量x1的目标函数的系数c1进行灵敏度分析。在a11’,a12’,a13’,a14’,a15’中，除了知道a11’和a13’大于0，a15’小...