单纯形法的灵敏度分析与对偶(学术型研究生).ppt

单纯形法的灵敏度分析与对偶 §1 单纯形表的灵敏度分析 §2 线性规划的对偶问题 §3 对偶规划的基本性质 §4 对偶单纯形法 §1 单纯形表的灵敏度分析 一、目标函数中变量Ck系数灵敏度分析 1.在最终的单纯形表里，X k是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与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.在最终的单纯形表中， X k是基变量 当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 + Ck a’Kj §1 单纯形表的灵敏度分析 根据上式可知 检验数 J (J=1,2,…..,M)变成了 ’J,有 ’ J=CJ-Z’J= J+ CK a’Kj 。要使最优解不变，只要当J K时， ’J =0 §1 单纯形表的灵敏度分析 例： 目标函数：Max z=50X1+100X2 约束条件：X1+X2≤300 2X1+X2≤400 X2≤250 X1，X2≥0 最优单纯形表如下 §1 单纯形表的灵敏度分析 我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。 这里δ3=-50，所以当c3的增量Δc3≤50，最优解不变。 再对基变量x1的目标函数的系数c1进行灵敏度分析。 在a11’,a12’,a13’,a14’,a15’中，除了知道a11’和 a13’大于 0， a15’小于0，可知 ，有 。同样有 。这样可以知道当-50≤Δc1≤50时，也就是x1的 目标函数c1’在0≤c1’≤100时最优解不变。 在最终的单纯形表中，用C’1代替原来的C1=50,计算得表 §1 单纯形表的灵敏度分析 §1 单纯形表的灵敏度分析 二、约束方程中常数项的灵敏度分析 从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最 优解中S2 =50是基变量，即为，原料A有50千克没用完，再增加A原料是不会增 加利润的， A的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的 对偶价格为0。 §1 单纯形表的灵敏度分析 可以看出，上题中对于设备台时数约束来说，当其松弛变量在目标函数 中从0变到Z3=50时，也就是只要当前余下一台时数设备从不能获利变成获利 50元时，譬如有人愿意出50元买一个设备时，我们就不必为生产Ι、П产品 而使用完所有的设备台时了，这说明了设备台时数的对偶价格就是Z3=50元。 对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时 这个约束条件的对偶价格就和这个剩余变量的 有关了。这将使得最优目 标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取 值的相反 数- 。 对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方 程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变 量的 值。 §1 单纯形表的灵敏度分析 下表给出了一个由最终单纯形表对于不同