第3章 对偶与灵敏度分析：最终单纯形表还能回答什么

1. 先把主线例子解出来

加松弛变量 $s_1,s_2,s_3$，按第2章（化为最小化 $-z$）迭代两次得到最终表：

最优解 $x_1=2,\ x_2=0,\ x_3=1$，$z=13$。第一、三种资源用满（$s_1=s_3=0$），第二种剩 1 个单位（$s_2=1$）。

这张表里藏着两样东西，本章反复使用：

• $S$ 矩阵：最终表中松弛变量 $s_1,s_2,s_3$ 那三列，$$S=\begin{pmatrix}2&0&-1\\-2&1&0\\-3&0&2\end{pmatrix}.$$ 它记录了单纯形法做过的全部行变换：最终表的任何一列都等于 $S$ 乘以初始表的对应列，最终右端 $=S\,B$。
• $y^{T}$：检验行中松弛变量那三格，$y^{T}=(1,0,1)$。它等于 $C_B^{T}S$，其中 $C_B=(5,0,3)$ 是当前基变量 $(x_1,s_2,x_3)$ 的目标系数。$y$ 就是下面要讲的对偶解。

2. 写出对偶

每个线性规划都有一个“影子问题”——对偶。对称形式下：

反过来，$\min\ C^{T}X,\ AX\ge B,\ X\ge0$ 的对偶是 $\max\ B^{T}W,\ A^{T}W\le C,\ W\ge0$。对偶的对偶就是原问题。

记忆方法是“转置三件套”：

1. 原问题的每条约束对应一个对偶变量 $w_i$；原问题的每个变量对应一条对偶约束。
2. 目标系数和右端互换：原目标系数 $C$ 变成对偶约束右端，原右端 $B$ 变成对偶目标系数。
3. 系数矩阵转置：原约束的行变成对偶约束的列。

主线例子的对偶：

非对称形式（约束方向不统一、有等式或自由变量）按下表处理，以原问题是最大化为例：

3. 对偶定理与影子价格

弱对偶： 对任意原问题可行解 $X$ 和对偶可行解 $W$，有 $C^{T}X\le B^{T}W$（原问题是最大化时）。也就是说，对偶的任何可行目标值都是原问题最优值的上界。

对偶定理： 如果原问题或对偶之一有最优解，另一个也有，并且两个最优值相等。

主线例子中，$W=y=(1,0,1)$ 代入对偶约束：$2+0+3=5\ge5$，$3+0+4=7\ge4$，$1+0+2=3\ge3$，可行；目标 $5\cdot1+11\cdot0+8\cdot1=13$，正好等于原问题最优值 13。

从哪张表读对偶解？ 本章采用最大化目标、约束加松弛变量、检验行为 $y^{T}A-C^{T}$ 的约定，因此松弛变量列中的检验数就是对偶最优解。若是最小化目标、减去剩余变量或把约束乘过 $-1$，必须按列的符号还原，不能一律原样抄数。反过来解对偶时，也可通过检验数与松弛/剩余列的对应关系恢复原问题的解。这在原问题有很多 $\ge$ 约束时很有用——直接解它要引入大量人工变量，解它的对偶却往往只需要松弛变量。

影子价格的含义： $w_i$ 表示第 $i$ 种资源再多 1 单位，最优值增加多少（在最优基不变的范围内）。主线例子里：

• $w_1=1$：资源 1 多 1 单位，利润多 1；
• $w_2=0$：资源 2 本来就没用完，多给也没用；
• $w_3=1$：资源 3 多 1 单位，利润多 1。

所以如果要花钱买资源，单价低于影子价格才划算。

4. 互补松弛

设 $X^*$、$W^*$ 分别是原问题和对偶的可行解。它们同时最优，当且仅当：

其中 $s_i$ 是原问题第 $i$ 条约束的松弛，$e_j$ 是对偶第 $j$ 条约束的剩余。意思是：一边有“余量”，另一边对应的量就必须为 0。

主线例子中：

$e_2=3$ 也有含义：按影子价格计算，生产一件产品 2 要“占用”价值 7 的资源，却只卖 4，所以不生产它。这个 3 正是最终表中 $x_2$ 的检验数。

5. 灵敏度分析的总思路

问题参数小改一点，最优解还成立吗？不需要重解。如果单纯形法对新数据做同样的行变换，最终表会变成：

其中 $A^*$、$C^*$ 是原变量（不含松弛）的系数。只改右端或非基列、非基目标系数时，基矩阵及其目标系数不变，$S$ 和 $y$ 可以沿用；若改了基变量的目标系数，要重算 $y$；若改了基列，还要重算基逆矩阵 $S$。下面先讨论可直接沿用它们的情况，检查两件事：

• 可行性： 右端 $SB$ 是否仍然全部 $\ge0$；
• 最优性： 检验行是否仍然全部 $\ge0$。

都满足，原来的基仍然最优；不满足，就从修订后的表继续单纯形法。

6. 右端 $b_i$ 变化

设 $b_2\to b_2+\Delta$，即 $B\to B+\Delta e_2$。新右端为 $SB+\Delta\,S e_2$，$Se_2$ 就是 $S$ 的第二列。检验行不受影响，只需检查可行性。

例1：资源 1 的允许范围。 $S$ 第一列为 $(2,-2,-3)^{T}$：

所以 $b_1\in[4,\ 16/3]$ 时最优基不变。在此范围内最优值为 $13+w_1\Delta=13+\Delta$。

例2：资源 2 最多能削减多少？ $S$ 第二列为 $(0,1,0)^{T}$，新右端 $(2,\ 1+\Delta,\ 1)$，只要求 $1+\Delta\ge0$，即 $\Delta\ge-1$。资源 2 最多削减 1 单位（从 11 降到 10）而当前解仍可行——正好等于它的剩余量 $s_2=1$。这类问题的本质就是：非紧约束最多能削减到刚好用满为止。

例3：资源 3。 $S$ 第三列 $(-1,0,2)^{T}$，新右端 $(2-\Delta,\ 1,\ 1+2\Delta)\ge0$，得 $-\tfrac12\le\Delta\le2$，即 $b_3\in[7.5,\ 10]$。

7. 非基变量的系数变化

$x_2$ 是非基变量（取值 0），改动它的系数不影响可行性，只可能影响最优性——看它的检验数 $y^{T}A_2^*-c_2$ 是否仍 $\ge0$。

例4：$c_2$ 的范围。 $y^{T}A_2^*=1\cdot3+0\cdot1+1\cdot4=7$，检验数 $7-c_2\ge0$，所以 $c_2\le7$ 时当前解仍最优。原来 $c_2=4$，还差 3——正是最终表中 $x_2$ 的检验数。产品 2 的单价涨过 7，才值得生产。

例5：整列一起变。 若产品 2 改进工艺，系数列从 $(3,1,4)^{T}$ 变为 $(2,1,3)^{T}$，同时售价变为 6：

检验数变负，当前解不再最优。修订表中 $x_2$ 列为 $S A_2^{*c}=(1,-3,0)^{T}$，从这里让 $x_2$ 进基继续迭代即可（新最优值为 15）。

用对偶的语言说：一个基可行解最优，当且仅当对应的对偶解可行。 改动非基变量 $x_2$ 只改变第二条对偶约束，用 $W^*=(1,0,1)$ 代进去检查是否仍成立即可，和上面的计算完全一样。

8. 基变量的目标系数变化

$x_1$ 是基变量。$c_1\to5+\Delta$ 时，$C_B$ 变了，整个检验行都会变。最快的算法是：检验行加上 $\Delta$ 乘以 $x_1$ 所在行（只对非基列有意义）。

$x_1$ 行为 $(1,\ 2,\ 0,\ 2,\ 0,\ -1)$，非基变量是 $x_2,s_1,s_3$：

取交集 $-\tfrac12\le\Delta\le1$，即 $c_1\in[4.5,\ 6]$ 时当前解仍最优，最优值为 $13+2\Delta$（$x_1=2$）。

如果基变量的系数列也一起变了，修订表中它所在的列不再是单位列，要先用行变换把它恢复成单位列，再检查可行性和最优性；不满足时继续单纯形法。

9. 小结

• 对偶：约束 ↔ 变量，目标系数 ↔ 右端，矩阵转置；max 的 $\le$ 对应 min 的 $\ge$。
• 原、对偶的最优值相等；对偶解可从松弛/剩余列的检验数恢复，但要核对目标与列的符号约定，含义是影子价格。
• 互补松弛：有余量的一方，对应的另一方为 0。
• 修订最终表：右端变成 $SB$，检验行变成 $y^{T}A^*-C^{*T}$。
• 右端变化只看可行性，非基系数变化只看最优性，基变量系数变化要先恢复单位列再看两者。

自测