线性规划的几何与单纯形思想

线性目标的等值线像一块平整的玻璃，在多面体可行域上平移。玻璃第一次碰到可行域的位置，常常是一个角点；如果一条边与玻璃重合，则整条边都可能最优。单纯形思想就是在这些结构化的角点之间移动。

二维线性规划的多面体、目标等值线与最优角点

标准形和基本解

为了统一推导，先看标准形最小化问题

\min c^Tx\quad\text{s.t. }Ax=b,\ x\ge0.

不等式可通过松弛变量变成等式；自由变量可写成两个非负变量之差。转换会增加变量，但不改变原模型的可行方案与最优值之间的对应关系。

不等式加入松弛变量转成标准形

设 $A$ 有 $m$ 行，从 $n$ 列中挑出线性无关的 $m$ 列组成基矩阵 $B$ ，其余列组成 $N$ 。令非基变量 $x_N=0$ ，则

x_B=B^{-1}b.

如果 $x_B\ge0$ ，便得到一个基本可行解（BFS）。几何上，许多约束同时取等的位置就是角点；代数上，它由一组独立列确定。退化时可能有多于 $m$ 条约束同时紧，但不同基仍对应同一个角点。

基变量与非基变量组成基本可行解的示意

为什么最优点可以在角点

可行域是凸多面体，目标是线性的。若一个最优点不是极点，它可以写成两个不同可行点的凸组合： $x=\alpha y+(1-\alpha)z$ 。线性性给出

c^Tx=\alpha c^Ty+(1-\alpha)c^Tz.

若 $x$ 已经是最小值，右侧的两个值都不能低于它，否则加权平均也会低于它。因此 $y,z$ 也必须最优；沿着分解继续，最终能找到极点最优解。这个结论需要可行域存在极点且问题有有限最优值；无界或不可行时不能硬套。

从可行域内部沿目标方向移动直到碰到角点

一次 pivot 为什么这样走

在当前基下，目标可以改写成

c^Tx=c_B^TB^{-1}b+\sum_{j\in N}\bar c_jx_j, \qquad \bar c_j=c_j-c_B^TB^{-1}A_j.

$\bar c_j$ 是 reduced cost。对最小化问题，若所有 $\bar c_j\ge0$ ，增加任何非基变量都会让目标不降，当前 BFS 最优。

若某个 $\bar c_j<0$ ，让 $x_j$ 增长可以改善目标。为保持 $Ax=b$ ，基变量沿

x_B=B^{-1}b-B^{-1}A_jx_j

变化。只要某个基变量会下降，就必须限制 $x_j$ 的最大增量：

\theta=\min_{i:\,d_i<0}\frac{x_{B_i}}{-d_i}, \qquad d=-B^{-1}A_j.

最小比值对应的基变量先到零，离开基； $x_j$ 入基。若所有 $d_i\ge0$ ，变量可无限增大而目标持续改善，说明问题无界。

reduced cost、入基变量和比值检验的关系

退化 pivot：基变化但点和目标值暂时不变

比值检验不是“选最小的商”这么简单：只对会让基变量下降的方向分量计算，而且分母必须是正的下降量。忘记符号条件，会把不可行的新点当成下一步。

练习

对最小化问题，当前 BFS 的所有 reduced cost 都非负。能否断言它最优？需要什么前提？

若某个改善方向的所有基变量变化量都非负，单纯形步骤应报告什么？

为什么线性目标在一条最优边上时，返回一个角点仍然合理？

在最小化标准形 LP 中，哪个条件直接给出当前 BFS 的最优性证书？