《管理运筹学》(第2版)610章教案

40 第六章 单纯形法的灵敏度分析与对偶 • §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) T = ZJ + ΔCk a’Kj 根据上式可知 检验数δJ (J=1,2,… ..,M)变成了δ’J，有δ’ J=CJ-Z’J=δJ+ΔCK a’Kj 。要使最优解不变，只要当J≠K时，δ’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的变化范围为，所以可知满足的，所有小于，满足的以外的所有大于于除了要使得最优解不变，对。，可知，知是基变量，因为时，当这里时当这里时当 41 例： 目标函数：Max Z=50X1+100X2 约束条件：X1+X2≤300 2X1+X2≤400 X2≤250 X1，X2≥0 最优单纯形表如下 表6—1 我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。 这里δ3= -50，所以当c3的增量Δc3≤50，最优解不变。 再对基变量x1的目标函数的系数c1进行灵敏度分析。 在a11¡ ,a12¡ ,a13¡ ,a14¡ ,a15¡ 中 ，除 了 知 道 a11¡ 和 a13¡ 大 于 0， a15¡...