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

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

标准形和基本解

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

$$\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$，变量可无限增大而目标持续改善，说明问题无界。

练习

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

查看解答

在标准形、当前解确实可行且 reduced cost 按 $\bar c_j=c_j-c_B^TB^{-1}A_j$ 定义的前提下，可以断言当前 BFS 最优。因为任意可行方向增加非基变量都会使目标增加或不变。

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

查看解答

该非基变量可以无限增加而不破坏非负性，且 reduced cost 为负会让最小化目标持续下降，因此问题无界，而不是“找不到出基变量”。

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

查看解答

边上的每个点都有同一个目标值，两个端点是角点。因此角点解仍是最优，只是最优解不唯一。

1

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

A.所有基变量都为零B.所有 reduced cost 非负C.目标函数系数全为正D.约束数量少于变量数量