线性规划：标准形、基本解与极点

线性规划的难点不在“线性”二字，而在于把几何图形、矩阵中的基和算法中的换基看成同一件事。

标准形

课程采用的一个标准形式是

\min c^Tx,\qquad Ax=b,\qquad x\ge0,

其中 $A\in\mathbb R^{m\times n}$ 且通常假设 $\operatorname{rank}(A)=m$ 。

常见转换：

转换之后不要忘记：新变量只是算法工具，最终答案要还原到原变量。

从 $A$ 中选取 $m$ 个线性无关列构成基矩阵 $B$ ，其余列为 $N$ 。把变量相应分成 $x_B,x_N$ ：

Bx_B+Nx_N=b.

令非基变量 $x_N=0$ ，得到基本解

x_B=B^{-1}b.

若 $x_B\ge0$ ，它是基本可行解。若某个基本变量也为零，称为退化基本可行解；退化时多个基可能对应同一个几何点。

极点不能写成集合中两个不同点的严格凸组合。对

S=\{x:Ax=b,x\ge0\},

基本可行解的正分量对应列线性无关，因此无法同时沿某个非零方向正反移动还保持非负与等式，这正是“没有穿过该点的可行线段”。反过来，若正分量对应列相关，就存在 $Ad=0$ 的非零方向，并能在小范围内同时走 $x\pm\varepsilon d$ ，该点便不是极点。

于是得到核心对应：

\boxed{\text{基本可行解}\Longleftrightarrow\text{可行域极点}}.

对本节标准形

S=\{x:Ax=b,\ x\ge0\},

若 $S$ 非空且线性目标的有限最优值能够达到，则至少存在一个最优基本可行解，也就是最优极点。更一般地说这个结论时，必须补上“可行域（或最优面）含有极点”的前提；带直线、根本没有极点的多面体不能套用它。

直觉上，线性函数的等值面平行移动，最后接触标准形多面体时会碰到一个最优面，而这个最优面至少含一个极点。

注意结论不是“最优解一定唯一”或“所有最优解都是极点”。若等值面与一条边重合，整条边都最优，但端点仍是最优极点。

x_1+x_2+s_1=4,\qquad 2x_1+x_2+s_2=5,\qquad x\ge0.

取 $B=(s_1,s_2)$ 得 $x_1=x_2=0,s=(4,5)$ ，是基本可行解。取 $B=(x_1,x_2)$ ，解

\begin{bmatrix}1&1\\2&1\end{bmatrix} \begin{bmatrix}x_1\\x_2\end{bmatrix} =\begin{bmatrix}4\\5\end{bmatrix},

得到 $(x_1,x_2)=(1,3)$ ，仍为基本可行解。单纯形法就是在这些相邻极点之间移动。