对偶单纯形法：保持对偶可行的换基过程

原始单纯形法始终保持 $B^{-1}b\ge0$ ，逐步修复检验数；对偶单纯形法反过来，始终保持检验数满足最优性符号，逐步修复负的基本变量。

什么时候用

对最小化问题，若某张表满足

\sigma_j=z_j-c_j\le0

但右端有负数，即

B^{-1}b\not\ge0,

当前解原不可行、对偶可行，正适合对偶单纯形法。

最典型场景是：已经求出一个 LP 的最优表，现在只改变右端 $b$ 。检验数完全不变，原最优基可能只因右端变负而失去可行性，从旧表继续做对偶单纯形远比重算快。

设最负的右端位于第 $r$ 行，选该基本变量出基。为了把右端修成非负，需要从该行中选一个允许的非基变量进基。

在课程使用的 $\sigma_j=z_j-c_j\le0$ 约定下，只考虑 $a_{rj}<0$ 的列，并比较

\theta_j=\frac{\sigma_j}{a_{rj}}\ge0.

在这些候选列中取最小的非负比值。若改用约化成本

\bar c_j=c_j-z_j=-\sigma_j\ge0,

同一个规则就是

\theta_j=\frac{\bar c_j}{-a_{rj}}.

为什么取最小值？主元变换相当于先让出基行对应的对偶变量变化；某个非基变量的约化成本最先降到零时，它正好可以进基。若越过这个最小比值，至少一个 $\bar c_j$ 会变负，也就是 $\sigma_j$ 变正，对偶可行性被破坏。

不同教材的表头与检验数定义可能让比值写成 $\bar c_j/(-a_{rj})$ 。不要硬套外观，推导原则只有一个：换基后既要改善负右端，又不能破坏对偶可行性。

每次换基保持对偶可行。若最终全部右端非负，则原、对偶同时可行，强对偶意味着当前表最优。若选定出基行中没有任何合适的负系数列，则无法恢复原可行性，原问题不可行。

假设一张最优表改变右端后出现

x_{B_1}=-2-x_3+2x_4,\qquad x_{B_2}=3+x_3-x_4.

第一行基本变量为负，先让它出基。由字典式可直接看出：增大 $x_3$ 会让 $x_{B_1}$ 更小，增大 $x_4$ 才会通过 $2x_4$ 抬高它。因此候选进基变量是 $x_4$ 。

若把字典统一写成 $x_B=b-\bar A x_N$ ，第一行的 $x_4$ 系数对应 $a_{r4}=-2<0$ ，与前面的候选列规则一致。最后还要用 $\sigma_4/a_{r4}$ 与其他候选列比较，确认换基后全部检验数仍不大于零。