[理学]第02章 线性规划的对偶理论与灵敏度分析.ppt

例2.21 线性规划及最优单纯形表如下 。求当b1在由8变动为12时，原最优性是否保持不变，若变动求出新的最优解。 * * * * 可得到Δc3 ≤ 3 时，原最优解不变。 当 -3+Δc3 ≤0最优解不变 例2.18 线性规划及最优单纯形表如下 试求 c3 在多大范围内变动时，原最优解保持不变。 -28/5 11/5 2/5 B-1b -1/5 -8/5 -9/5 0 0 σj -2/5 -1/5 7/5 0 1 x1 -2 1/5 -2/5 -1/5 1 0 x2 -3 x5 x4 x3 x2 x1 xB cB 0 0 -4 -3 -2 cj 可得到Δc3 ≤ 9/5 时，原最优解不变。 -28/5 11/5 2/5 B-1b -1/5 -8/5 -9/5+Δc3 0 0 σj -2/5 -1/5 7/5 0 1 x1 -2 1/5 -2/5 -1/5 1 0 x2 -3 x5 x4 x3 x2 x1 xB cB 0 0 -4Δc3 -3 -2 cj 下表为最优单纯形表（考虑基变量系数c1发生变化） -3 +Δc1 ≤0 -5 - 4Δc1 ≤0 -1 + Δc1 ≤0 最优解不变 （2）基变量的系数发生变化 可得到 -5/4 ≤ΔC1 ≤1 时，原最优解不变。最优值将会出现相应的变化。 Max Z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5 x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 ≥ 0 例2.18 下表为最优单纯形表（考虑基变量系数c2发生变化） 可得到 -3≤Δc2≤1 时，原最优解不变。 例2.19 已知线性规划的标准形式为 其最优单纯形表如下 Cj －1 2 1 0 0 CB XB b X1 x2 x3 x4 x5 2 0 x2 x5 6 10 1 3 1 0 1 1 1 1 0 1 -Z -12 -3 0 -1 -2 0 问：(1) 当C1由－1变为4时，求新问题的最优解。 　　(2) 讨论C2在什么范围内变化时，原有的最优解仍是最优解。 解：由表可知，C1是非基变量的价值系数，因此C1的改变只影响σ1，可见最优性准则已不满足，继续迭代 Cj 4 2 1 0 0 CB XB b x1 x2 x3 x4 x5 2 0 x2 x5 6 10 1 [3] 1 0 1 1 1 1 0 1 6 10/3 -Z -12 2 0 -1 -2 0 2 4 x2 x1 8/3 10/3 0 1 1 0 2/3 1/3 2/3 1/3 -1/3 1/3 -Z -56/3 0 0 -5/3 -8/3 -2/3 （2） 要使原最优解仍为最优解，只要在新的条件下满足σ≤0成立，因为x2是基变量，所以所有的σ值都将发生变化，即 则△c2≥-1，所以当x2的系数△c2≥-1时，原最优解仍能保持为最优解。 －3－ △c2 ≤0 －１－ △c2 ≤0 －２－ △c2 ≤0 例2.20 线性规划及最优单纯形表如下 ，问b3由12变为12+ Δb3 最优性不变。 Max Z = 2x1 + 3x2 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12+ Δb3 x1 , x2 , x3 , x4 , x5 ≥ 0 2、右端项 b 发生变化 0 0 1 0 x5 0 14 -1/8 -3/2 0 0 σj 2 -1/8 1/2 1 0 x2 3 4 1/2 -2 0 0 x5 0 4 1/4 0 0 1 x1 2 B-1b x4 x3 x2 x1 XB CB 0 0 3 2 C i 比如第三个式子中，由4+Δb3 ≥0，解得Δb3≥ -4 时最优性不变 若Δb 3 = - 8，则 4+（-8）= -4 0，改变了最优性，只要再继续迭代即可。 0 0 1 0 x5 0 14 -1/8 -3/2 0 0 σj 2 -1/8 1/2 1 0 x2 3 4 1/2 -2 0 0 x5 0 4 1/4 0 0 1 x1 2 B-1b x4 x3 x2 x1 XB CB 0 0 3 2 C i 将b’代入原最优单纯形表中，运用对偶单纯形法计算最优解。 -4 1 1/2 -2 0 0 x5 0 4 0 -1/8 1/2 1 0 x2 3 14 0 -1/8 -3/2 0 0 σj 0 x5