第2章 单纯形法：单纯形表、大 M 法与两阶段法

1. 单纯形法在做什么

第1章说过：最优解一定在某个基本可行解（顶点）上。单纯形法就是从一个基本可行解出发，每次换掉一个基变量，走到相邻且目标更好的顶点，直到没有更好的邻居为止。

拖动滑块，再点“下一步”，看单纯形法如何沿着顶点走到最优：

每一次迭代只回答三个问题：

1. 往哪走？ 哪个非基变量增大能让目标改进最快——选它进基。
2. 走多远？ 进基变量增大时，哪个基变量最先降到 0——它出基。
3. 怎么到？ 用初等行变换把进基变量那一列变成单位列（主元消元）。

2. 单纯形表从哪来

把问题写成标准型（第1章）：

设当前基变量组成 $X_0$，它们的目标系数组成 $C_0$。初始时基变量是松弛变量或人工变量，对应的列恰好构成单位矩阵，于是单纯形表是

最后一行每个元素叫检验数（reduced cost），表示“这个变量增加 1 单位，目标 $z$ 改变多少”。最后一行最后一列是 $-z$ 的当前值。

对最小化问题：

• 某个检验数为负，说明让该变量进基能让 $z$ 下降——还没到最优。
• 所有检验数都 $\ge0$ 时，任何变量进基都不会让 $z$ 更小——当前解最优。

最大化问题有两种等价处理：一是把目标乘 $-1$ 变成最小化，解完再把最优值乘 $-1$；二是把检验行的符号全部取反（即 $C_0^{T}A-C^{T}$），判别规则不变——仍然是“有负数就继续，全部非负就停”。

3. 单纯形法的五步

1. 在检验行（不含最后一列）找最负的数，它所在的列叫工作列，对应变量进基。
2. 用工作列中大于 0 的系数去除同一行的右端，最小比值所在行的元素是主元，该行的基变量出基。若工作列没有正系数，问题无界。
3. 用初等行变换把主元化为 1，把工作列其他元素（包括检验行）都化为 0。
4. 在基变量栏中用进基变量替换出基变量。
5. 重复，直到检验行没有负数。此时基变量取右端的值，其余变量为 0。

4. 手算主线例子

最大化 $40x_1+30x_2$ 等价于最小化 $z=-40x_1-30x_2$。加松弛变量 $s_1,s_2$，初始基 $X_0=(s_1,s_2)$，$C_0=(0,0)$，检验行就是 $C^{T}=(-40,-30,0,0)$。

表 0：在原点 $(0,0)$。

最负检验数 −40，$x_1$ 进基；最小比值 50，$s_1$ 出基；主元 2。

表 1：走到 $(50,0)$。 第一行除以 2，再用它消去 $s_2$ 行和检验行的 $x_1$：

右下角 2000 是 $-z$，即当前利润 2000。$x_2$ 的检验数 −10 还为负，$x_2$ 进基，$s_2$ 出基，主元 3/2。

表 2：走到 $(40,20)$，最优。

检验行全部非负，停止。最优解 $x_1=40,\ x_2=20$，最大利润 2200。 两条资源都用满（$s_1=s_2=0$）。

5. 大 M 法

当约束含 $\ge$ 或 $=$ 时，需要人工变量当初始基（第1章第5节）。为了让人工变量最终为 0，在目标中给它们大惩罚：最小化加 $+Ma$，最大化加 $-Ma$。

例1： $\min\ z=2x_1+3x_2$，$x_1+x_2\ge4$，$x_1+3x_2\ge6$，$x_1,x_2\ge0$。

标准型：$x_1+x_2-e_1+a_1=4$，$x_1+3x_2-e_2+a_2=6$，目标 $z=2x_1+3x_2+Ma_1+Ma_2$。初始基 $(a_1,a_2)$，$C_0=(M,M)$。

检验行 $C^{T}-C_0^{T}A$ 中每一项都形如“常数 + 系数·$M$”。把它拆成两行会清楚得多：上面一行放不含 $M$ 的部分，下面一行放 $M$ 的系数。

表 0：

例如 $x_1$ 列的检验数是 $2-M\cdot1-M\cdot1=2-2M$，拆成常数 2 和 $M$ 系数 −2。

选进基变量时先看 M 行：$M$ 远大于任何常数，所以 M 行最负的 −4 决定 $x_2$ 进基。比值 4/1 = 4、6/3 = 2，$a_2$ 出基。

表 1：

M 行最负的是 −2/3，$x_1$ 进基；比值 $2\div\frac23=3$、$2\div\frac13=6$，$a_1$ 出基。

表 2：

M 行已没有负数，人工变量全部出基；再看常数行中 M 行为 0 的位置（$x_1,x_2,e_1,e_2$），也都非负——最优。**$x_1=3,\ x_2=1$，$z=9$**（右下角 −9 是 $-z$）。$a_1,a_2$ 列的常数行虽然是负数，但它们的 M 行系数为 1，真实检验数是 $M-\frac32>0$，不会进基。

6. 两阶段法

把“先看 M 行，再看常数行”的规则单独写出来，就是两阶段法：

• 第一阶段： 只看 M 行（相当于最小化人工变量之和 $a_1+a_2+\cdots$），用单纯形法把所有人工变量赶出基、取 0。人工变量一旦出基，就把它的整列删掉，不再让它回来。若第一阶段最优值为 0，但仍有取值为 0 的人工变量留在基中，应先用非人工列把它换出；该行若无可用主元，则它是可删除的冗余约束。
• 第二阶段： M 行全为 0 后把它删掉，从此时的基本可行解出发，按常数行（原目标）继续单纯形法，直到常数行没有负数。

规则汇总：

最大化问题的人工变量系数怎么定？ 在原目标里，最大化问题给人工变量 $-M$（越大越亏），最小化问题给 $+M$。如果先把最大化乘 $-1$ 改成最小化，那么人工变量的系数也随之变成 $+M$，第一阶段的目标始终是“最小化人工变量之和”。两种写法指向同一件事：人工变量越大，目标越差。

例2：含等式约束。

标准型：$x_1+x_2+a_1=8$，$x_1+2x_2-e_1+a_2=10$，$x_1+s_1=6$。初始基 $(a_1,a_2,s_1)$。

M 行 −3 最负，$x_2$ 进基；比值 8、5，$a_2$ 出基，删去 $a_2$ 列：

M 行 $x_1$ 和 $e_1$ 并列 −1/2，取 $x_1$。比值 $3\div\frac12=6$、$5\div\frac12=10$、$6\div1=6$——$a_1$ 与 $s_1$ 并列最小，任选其一；选 $a_1$ 出基，删去 $a_1$ 列，M 行变为全 0，删去：

常数行全部非负，最优：**$x_1=6,\ x_2=2$，$z=34$。** 注意基变量 $s_1=0$——这就是比值并列带来的退化：顶点 $(6,2)$ 上同时有三条约束取等号（$x_1+x_2=8$、$x_1+2x_2=10$、$x_1=6$）。

7. 从表上识别特殊情况

无可行解。 $\min\ z=x_1+x_2$，$x_1+x_2\le2$，$2x_1+3x_2\ge12$。

$x_2$ 进基，比值 2 与 4，$s_1$ 出基，得到

M 行已无负数，第一阶段结束，但人工变量 $a_1=6$ 仍在基中且为正——原问题无可行解。几何上，$x_1+x_2\le2$ 的区域里 $2x_1+3x_2$ 最大只有 6，达不到 12。

无界。 $\min\ z=-2x_1-x_2$，$x_1-x_2\le2$，$-2x_1+x_2\le4$。一次迭代后（$x_1$ 进基、$s_1$ 出基）：

$x_2$ 检验数 −3 要进基，但它这一列没有正系数，比值检验做不下去：$x_2$ 可以无限增大而所有基变量都不会降到 0，$z$ 可以无限减小——问题无界。

多重最优。 最终表中，如果某个非基变量的检验数为 0，并且沿该方向能走正的步长，就能得到另一个不同的最优解。若只能做零步长的退化换基，还不能仅凭零检验数断定有不同的最优解。第1章例1把利润改成 $40x+40y$ 就会出现这种情况。

退化。 某个基变量取值为 0（如例2的 $s_1$）。退化时迭代可能“原地换基”而目标不变，极少数情况下会循环。实际手算中遇到比值并列，任选其一通常就能继续；要严格避免循环，可用 Bland 规则：在所有检验数为负的可入基变量中选下标最小的，再在最小比值并列时选下标最小的基变量出基；只对并列情况打破平局还不是完整规则。

8. 小结

• 单纯形表 = $[A\ |\ B]$ + 检验行 $C^{T}-C_0^{T}A$；右下角是 $-z$。
• 最小化：检验数有负就继续，全部非负就停。最大化：乘 $-1$ 变成最小化，或把检验行取反。
• 一轮迭代：最负检验数进基 → 最小正比值出基 → 主元消元。
• 人工变量要么用 $\pm M$ 惩罚（大 M 法），要么先单独最小化它们的和（两阶段法）；把 M 行单独写出来，两者就是同一套计算。
• 第一阶段结束人工变量仍为正 → 无可行解；进基列无正系数 → 无界；非基检验数为 0 → 多重最优；基变量为 0 → 退化。

自测