单纯形法（一）：换基、检验数与单纯形表

单纯形法每一步只做一件事：从当前极点沿一条边走到更好的相邻极点。矩阵语言中，这就是换掉基中的一列。

目标函数在当前基下的表达

标准形

$$\min c_B^Tx_B+c_N^Tx_N,\qquad Bx_B+Nx_N=b$$

给出

$$x_B=B^{-1}b-B^{-1}Nx_N.$$

代入目标：

$$z=c_B^TB^{-1}b+ \left(c_N^T-c_B^TB^{-1}N\right)x_N.$$

若定义

$$\sigma_j=z_j-c_j=c_B^TB^{-1}A_j-c_j,$$

则最小化问题中，$\sigma_j>0$ 表示增大非基变量 $x_j$ 会降低目标，适合进基；所有 $\sigma_j\le0$ 时当前基最优。

有的教材定义相反的 $c_j-z_j$。两套都能用，但进基判据也会反过来，不能混写。

进基与出基

选定进基列 $A_k$ 后，令

$$y=B^{-1}A_k,\qquad \bar b=B^{-1}b.$$

增大 $x_k=\theta$ 时

$$x_B=\bar b-y\theta.$$

为了保持 $x_B\ge0$，只能对 $y_i>0$ 的行要求

$$\theta\le\frac{\bar b_i}{y_i}.$$

因此用最小比值检验

$$\theta^*=\min_{i:y_i>0}\frac{\bar b_i}{y_i}.$$

达到最小比值的基变量先降到零，负责出基。若进基列 $y\le0$，目标可以沿该方向无限改善，问题无界。

完整算例

$$\begin{aligned} \min\quad &-10x_1-5x_2\\ \text{s.t.}\quad &3x_1+4x_2+x_3=9,\\ &5x_1+2x_2+x_4=8,\\ &x\ge0. \end{aligned}$$

初始基 $(x_3,x_4)$ 给出 $(0,0,9,8)$。$x_1$ 的目标改善更快，令其进基。主元列为 $(3,5)^T$，比值为

$$9/3=3,\qquad 8/5=1.6,$$

所以 $x_4$ 出基，走到 $x_1=8/5$。完成主元行归一化并消去同列其他元素后，重新计算检验数；若仍有正检验数，就继续换基。

这个例子中，比值检验不是在比较“哪个约束更重要”，而是在问沿该边走多远会最先撞到可行域边界。

表格计算的自检

每次主元变换后检查：

1. 基变量列是否恢复为单位阵；
2. 右端是否仍非负；
3. 基变量对应检验数是否为零；
4. 当前目标值是否按期望方向改善；
5. 原变量代回原约束是否成立。

考试要点

• 必须写进基、出基和比值，不能只给最终表。
• 最小比值只考虑主元列中的正元素。
• 没有正元素且检验数可改善，结论是无界。
• 并列最小比值可能导致退化；可按 Bland 规则用最小编号打破并列，避免循环。