极点与基可行解的等价性定理
在运筹学与线性规划的理论体系中，极点与基可行解的等价性定理（Theorem of Equivalence between Extreme Points and Basic Feasible Solutions）占据着基石般的地位。该定理不仅揭示了线性规划问题解的代数结构与几何形态之间的深刻联系，更为后续单纯形法（Simplex Method）的有效性提供了严格的数学证明基础。
⚡ 定理核心陈述
对于标准形式的线性规划问题，若其可行域 S 为非空有界凸多面体，则以下命题等价：
- 代数视角：向量 X 是该问题的一个基可行解（Basic Feasible Solution, BFS）。
- 几何视角：向量 X 是该可行域 S 的一个极点（Extreme Point）或顶点（Vertex）。
这意味着，我们不需要在连续的可行域中盲目搜索最优解，而只需关注有限个极点即可。
前置知识：解的代数与几何定义
在深入理解等价性之前，我们必须明确两个关键概念的定义。许多学习者常混淆“可行解”、“基解”与“基可行解”的界限。
1. 可行解 (Feasible Solution)
满足所有约束条件（包括线性等式/不等式及非负约束）的解向量 X。所有可行解构成的集合称为可行域。
2. 基可行解 (BFS)
由约束方程组的系数矩阵 A 的基矩阵 B 确定的解。若令非基变量为0，解出的基变量值均非负（≥0），则该解为基可行解。
3. 极点 (Extreme Point)
几何上，若点 X 不能表示为可行域内两个不同点 X1 和 X2 的严格凸组合（即 X ≠ λX1 + (1-λ)X2, 0<λ<1），则 X 为极点。
为什么需要这个定理？
线性规划的可行域是一个连续的凸集。如果最优解可能在可行域内部的任意一点，那么求解将变得极其困难。等价性定理告诉我们，最优解一定存在于极点之上（如果存在最优解的话）。这极大地缩小了搜索空间，从无限连续空间缩小到了有限离散点集。
定理的逻辑推导与证明思路
证明该定理通常分为两个方向：充分性（基可行解 ⇒ 极点）和 必要性（极点 ⇒ 基可行解）。以下是简化的逻辑链条：
步骤一：基可行解 ⇒ 极点
反证法思路：假设基可行解 X 不是极点，则存在两个不同的可行点 X1, X2 使得 X 是它们的凸组合。通过代数推导，这将导致 X 中基变量对应的列向量线性相关，这与“基”的定义（线性无关）矛盾。因此，X 必为极点。
步骤二：极点 ⇒ 基可行解
构造法思路：设 X 为极点，其非零分量对应的列向量为 Pj。若这些向量线性相关，则存在非零向量 Y 使得 AY=0。我们可以构造 X±εY 和 X∓εY，这两个点仍在可行域内且 X 是它们的中心，这与 X 是极点矛盾。因此，非零分量对应的列向量必线性无关，从而构成基，X 为基可行解。
结论：一一对应关系
对于非退化线性规划问题，基可行解与极点之间存在一一对应关系。对于退化情况，一个极点对应多个基可行解，但几何位置重合。
实例演示：二维平面上的直观理解
通过一个简单的二维线性规划问题，我们可以直观地看到极点与基可行解的对应关系。
问题描述
Max Z = 3x1 + 2x2 s.t. x1 + x2 ≤ 4 2x1 + x2 ≤ 5 x1, x2 ≥ 0
标准化与基的寻找
引入松弛变量 x3, x4，将不等式转化为等式：
x1 + x2 + x3 = 4 2x1 + x2 + x4 = 5
系数矩阵 A 为 2×4 矩阵。我们需要选择2个基变量。可能的基组合有 C(4,2)=6 种。
基可行解计算表
| 基变量 | 非基变量 (设为0) | 解向量 (x1, x2, x3, x4) | 是否可行 (≥0?) | 对应几何点 |
|---|---|---|---|---|
| x3, x4 | x1=0, x2=0 | (0, 0, 4, 5) | 是 | O (原点) |
| x2, x4 | x1=0, x3=0 | (0, 4, 0, 1) | 是 | A (0,4) |
| x1, x4 | x2=0, x3=0 | (2.5, 0, 1.5, 0) | 是 | B (2.5,0) |
| x1, x2 | x3=0, x4=0 | (1, 3, 0, 0) | 是 | C (1,3) |
| x2, x1 | x3=0, x4=0 | (2, -3, 2, 0) | 否 (x2<0) | 不可行点 |
| x3, x1 | x2=0, x4=0 | (2.5, 0, 1.5, 0) | 是 | B (退化情况) |
从表中可见，只有4个解是基可行解，它们恰好构成了可行域多边形的4个顶点（极点）。单纯形法就是在这些点之间进行“邻居”搜索，寻找使目标函数Z最大的点。
对单纯形法的核心意义
极点与基可行解的等价性定理直接决定了单纯形法（Simplex Algorithm）的设计逻辑：
1. 搜索空间的离散化
由于最优解必在极点，算法无需考虑可行域内部或边界上的其他点，只需在有限个基可行解之间跳跃。
2. 邻接移动策略
定理隐含了极点的邻接性质：任意两个相邻极点之间的连线必在可行域边界上。单纯形法通过基变换（Pivot），从一个极点移动到相邻的、目标函数值更优的极点。
3. 终止条件判定
当所有非基变量的检验数均非正（最大化问题）时，当前基可行解即为全局最优解。这是因为没有相邻极点能提供更优的目标值，而凸函数在凸集极值点上的性质保证了局部最优即全局最优。
❓ 常见问题解答 (FAQ)
Q: 如果可行域是无界的，极点与基可行解的等价性还成立吗？
A: 成立。无论可行域是否有界，只要它是多面体（由线性不等式定义），其极点与基可行解的一一对应关系依然保持。区别在于，无界多面体可能有无穷多个极点，或者存在无界射线。
Q: 如何快速判断一个点是否为极点？
A: 在几何直观上，极点就是多边形的“角”。在代数上，检查该点是否满足：1. 所有约束；2. 线性无关的活跃约束（Active Constraints，即取等号的约束）数量等于变量维数。
Q: 为什么最优解不一定唯一？
A: 如果目标函数的梯度方向与可行域的某条边（或面）平行，则这条边（或面）上的所有点都是最优解。此时，至少有两个极点是最优解，且它们连线上的点也是最优解。