单纯形法 | Codeboy's Blog

形式陈述

考虑标准形线性规划 $\min c^Tx$ ，约束为 $Ax=b,x\ge0$ 。设 $A$ 有 $m$ 个线性独立行。从其列中选 $m$ 个线性独立列构成可逆矩阵 $B$ ，即约束列空间的一组基。令其余非基变量为零，解 $Bx_B=b$ ；若 $x_B\ge0$ ，就得到一个基可行解。

给定基可行解，一次原始单纯形迭代按以下规则进行。

解 $B^Ty=c_B$ ，为每个非基列 $A_j$ 计算约化成本 $\bar c_j=c_j-A_j^Ty$ 。若全都非负，当前解最优，因为这时 $y$ 是与它目标值相同的对偶可行解，弱对偶即给出最优性证书。
选一个 $\bar c_j<0$ 的变量入基，解 $Bd=A_j$ 。把 $x_j$ 从零增至 $\theta$ 时，基变量变为 $x_B-\theta d$ ，目标改变 $\theta\bar c_j$ 。
若没有 $d_i>0$ ，则任意 $\theta\ge0$ 都保持可行，而目标不断下降，故问题无界。否则取 $\theta=\min_{i:d_i>0}(x_B)_i/d_i$ ，让达到最小值的基变量离基，再重复。

比值检验限制的是非负性：哪个基变量先降到零，就不能再继续沿此方向走。出现并列或零步长时，需要确定的枢轴规则；Bland 规则选择所有负约化成本的非基变量中原始编号最小者入基；在最小比值并列的候选中，选择原始变量编号最小的基变量离基。离基比较的是变量编号，而不是它在当前基矩阵中的行号；这套规则在精确算术下防止循环。

带上下界的变量

对 $Ax=b,\ l\le x\le u$ ，仍选可逆列基 $B$ ，但把每个非基变量固定在其有限下界或上界，再解 $Bx_B=b-A_Nx_N$ 。先消去 $l_j=u_j$ 的固定变量；完全自由的变量可拆成两个非负变量。基可行要求所有基变量也满足各自界。

约化成本仍为 $\bar c_j=c_j-A_j^Ty$ 。下界处的非基变量沿正方向移动，上界处沿负方向移动；记这个符号为 $\sigma\in\{1,-1\}$ ，选择 $\sigma\bar c_j<0$ 的改进方向。移动量 $\theta\ge0$ 使 $x_j$ 改变 $\sigma\theta$ ， $x_B$ 改变 $-\sigma\theta B^{-1}A_j$ 。比值检验同时考虑所有基变量的上下界和 $x_j$ 的另一端界：基变量先到界就换基；若 $x_j$ 严格先到另一端界，就只翻转它的上下界状态，列基保持不变，这称为 bound flip。并列时需规定一致的枢轴规则。若没有任何有限阻挡，才得到无界射线；若所有允许方向的约化成本都非负，则任意可行位移的目标差 $\sum_{j\in N}\bar c_j\Delta x_j\ge0$ ，证明当前解最优。网络单纯形使用的正是这种带界形式。

直觉

对上述非负标准形，可行域非空且最优值有限时，存在最优基可行解，因此单纯形法不扫描整个连续区域，而是在可行多面体的顶点（基可行解）之间沿边选择改进方向：每次选择能改善目标的入基变量，并用比值检验确定哪个基变量先降到零。这种边界行走有完整的几何依据；实践中它常很快，但存在精心构造的指数长枢轴路径。

例子与边界

两次枢轴到达最优点

求最大化 $3x+2y$ ，约束为 $x+y\le4,x\le2,y\le3,x,y\ge0$ 。引入松弛变量后，初始等式为 $s_1=4-x-y,s_2=2-x,s_3=3-y$ ，取 $x=y=0$ 得可行基 $(s_1,s_2,s_3)=(4,2,3)$ 。这里用最大化形式，故正的目标改进系数对应前节最小化形式的负约化成本。

先增加 $x$ ：它使 $s_1,s_2$ 同速下降，比值检验取 $\min(4,2)=2$ ，于是 $s_2$ 离基，达到 $(x,y)=(2,0)$ ，目标为 6。再增加 $y$ ，此时 $s_1=2-y,s_3=3-y$ ，最多走 2，令 $s_1$ 离基，到 $(2,2)$ ，目标为 10。

为什么可以停止？用非基变量 $s_1,s_2$ 表达当前基，有 $x=2-s_2,y=2-s_1+s_2$ ，所以目标为 $10-2s_1-s_2\le10$ 。非负性直接给出全局上界，而当前点达到它。这既展示枢轴轨迹，也给出独立可检查的最优性证书。二次规划活跃集法也会维护部分紧约束，但二次目标可以在一条边的内部取最优；它用面内二次方向与乘子符号调整工作集，不限于顶点枢轴。

初始化、退化与数值边界

加入松弛变量只有在所得右端项非负等条件成立时，才能直接得到可行初始基。否则可用两阶段法：第一阶段引入人工变量并最小化它们的总和；若最优值仍大于零，原问题不可行。不可行与沿可行方向无界是两种不同结论。

若某个基变量已经为零，比值检验可能给出零步长。此时换基却未移动几何顶点，目标也不改进；不防循环的规则可能反复访问旧基。一般多面体也不一定有顶点，例如整条直线，故“有限最优必在顶点取得”必须放在具有顶点的适当形式中使用。

浮点实现需分别设置可行性、约化成本与比值检验容差，并对量级悬殊的变量或约束作缩放。修正单纯形反复求解以 $B$ 为系数的系统，而不是显式计算逆矩阵。 $B$ 的条件性与数值分解中的枢轴及增长因子影响误差；它们与零基变量导致的几何退化并非同一问题。

推论与应用

线性规划给出多面体与目标，基给出顶点代数表示。最优终止时，最终基不仅给出原始变量，还通过对偶乘子和约化成本暴露约束的影子价格；在基保持最优且可行的范围内，还能读取目标系数或右端项变化的灵敏度区间。越出这些范围就可能换基，不能继续用同一局部价格作全局预测。单纯形法也适合暖启动，但经典枢轴规则没有多项式最坏步数保证；对偶单纯形、修正单纯形和内点法是不同求解器，不能把经验速度写成复杂度定理。

网络单纯形法利用流网络基的生成树结构专门求最小费用流，枢轴和可行性维护不同于通用稠密表。LP 松弛与舍入则先用 LP 值作上下界，再把分数解转成离散解并分析 integrality gap；它可以调用任意 LP 求解器，近似比不是单纯形沿边移动自动提供的。

参考资料

Carl W. Lee, Linear Programming Notes, University of Kentucky, 2003，§11.8：带上下界的非基状态、改进方向与比值检验。
Dimitris Bertsimas, Simplex Method I, MIT 15.093J, Lecture 3, 2009，约化成本、基方向、比值检验与无界判据。
Bernhard Korte and Jens Vygen, Combinatorial Optimization, 6th ed., Springer, 2018，Chs. 4–11。
Michel X. Goemans, Linear Programming Notes, MIT 18.310，§2.4.2、Theorem 2.2：Bland 最小变量编号规则与有限终止证明。

形式陈述 ​

带上下界的变量 ​

两次枢轴到达最优点 ​

初始化、退化与数值边界 ​

反向链接

形式陈述

带上下界的变量

两次枢轴到达最优点

初始化、退化与数值边界