线性规划基本定理证明：从几何直观到代数严谨
在运筹学与最优化理论中，线性规划基本定理（Fundamental Theorem of Linear Programming）占据着基石般的地位。它不仅是单纯形法（Simplex Method）的理论基础，更是连接代数计算与几何直观的桥梁。对于众多正在备考运筹学研究生或从事供应链优化的专业人士而言，深入理解该定理的证明过程，是掌握线性规划算法本质的关键。
本页面将不仅仅停留在结论的陈述，而是通过深度的逻辑推演，拆解线性规划基本定理证明的每一个环节。我们将探讨为何最优解总是“躲”在可行域的顶点？当问题出现退化时，定理依然成立吗？以及如何在实际应用中利用这一性质简化计算？
〓 核心结论
若可行域有界且非空，则目标函数的最优值必在某个顶点达到。这意味着我们无需搜索整个可行域，只需关注有限个顶点即可。
〓 关键概念
涉及基本可行解（Basic Feasible Solution）、基矩阵（Basis Matrix）、凸集（Convex Set）以及极方向（Extreme Direction）。
〓 应用场景
广泛应用于资源分配、生产计划、运输问题及投资组合优化。理解定理有助于快速判断解的唯一性与多重性。
线性规划基本定理证明深度解析
要证明线性规划基本定理，我们需要构建一个从代数定义到几何性质的严密逻辑链条。证明的核心在于建立基本可行解与可行域顶点之间的一一对应关系，并利用凸函数的性质确定极值位置。
1. 预备知识：标准型与基
首先，我们将线性规划问题转化为标准型：
Maximize Z = c^T x
Subject to Ax = b
x >= 0
其中，A 是 m×n 矩阵（m < n），秩为 m。b 是 m 维向量，且 b ≥ 0。x 是 n 维决策变量向量。
所谓基（Basis），是指矩阵 A 中 m 个线性无关的列向量组成的 m×m 非奇异子矩阵 B。对应的变量称为基变量（Basic Variables），记为 x_B；其余 n-m 个变量称为非基变量（Non-basic Variables），记为 x_N。令非基变量 x_N = 0，由 Ax = b 可唯一解出基变量 x_B = B⁻¹b。若 x_B ≥ 0，则称该解为基本可行解。
2. 定理陈述
线性规划基本定理包含三个主要部分：
- 若可行域 S 非空，则基本可行解存在。
- 点 x 是可行域 S 的顶点（极點），当且仅当 x 是基本可行解。
- 若存在最优解，则必存在一个基本可行解是最优解。
3. 证明过程概要
第一部分：基本可行解对应顶点
假设 x 是一个基本可行解，其对应的基为 B。我们要证明 x 是 S 的顶点。反证法：假设 x 可以表示为 S 中两个不同点 y 和 z 的严格凸组合，即 x = λy + (1-λ)z，其中 0 < λ < 1，y ≠ z。
由于 y, z ∈ S，故 Ay = b, Az = b 且 y, z ≥ 0。因为 x 是基本可行解，非基变量为 0。由于 y, z ≥ 0 且 x_N = 0，推导可得 y_N = z_N = 0。进而由 Ay = Az = b 及基矩阵 B 的非奇异性，推出 y_B = z_B = x_B。这与 y ≠ z 矛盾。因此，x 不能表示为其他两点的凸组合，故 x 是顶点。
第二部分：最优解在顶点取得
可行域 S 是一个凸多面体。目标函数 f(x) = c^T x 是线性函数，既是凸函数也是凹函数。根据凸分析理论，线性函数在有界凸多面体上的最大值必然在某个顶点处达到。
若可行域无界，需引入极方向（Extreme Direction）的概念。若目标函数在无界方向上无上界，则问题无界；否则，最优解仍会在某个顶点或包含顶点的面上达到。这证明了只需检查有限个基本可行解即可找到最优解。
| 概念 | 代数定义 | 几何意义 | 性质 |
|---|---|---|---|
| 基 (Basis) | A 的 m 个线性无关列 | 无直接对应 | 决定了解的结构 |
| 基本解 | 令非基变量为0解出基变量 | 超平面的交点 | 可能在可行域外 |
| 基本可行解 | 基本解且变量非负 | 可行域的顶点 | 单纯形法搜索对象 |
| 最优解 | 使目标函数最大/最小的解 | 支撑超平面的接触点 | 必含于顶点或面 |
标准型转化与典式处理
在实际应用中，原始问题往往不是标准型。理解如何将一般形式转化为标准型，是应用线性规划基本定理的前提。
不等式约束转化为等式
对于 ≤ 类型的约束，引入松弛变量（Slack Variable）；对于 ≥ 类型的约束，引入剩余变量（Surplus Variable）。
约束：2x₁ + 3x₂ ≤ 10
转化：2x₁ + 3x₂ + s₁ = 10，其中 s₁ ≥ 0。
此处 s₁ 即为松弛变量，代表未使用的资源量。
自由变量的处理
若变量 x_j 无符号限制（自由变量），可将其替换为两个非负变量之差：
x_j = x_j' - x_j''，其中 x_j' ≥ 0, x_j'' ≥ 0。
这种代换虽然增加了变量维度，但保证了问题符合标准型要求，从而可以应用基本定理。
右端项 b 为负数的处理
若 b_i < 0，可将第 i 个约束方程两边同时乘以 -1，使右端项变为正数。这是为了后续构造初始基本可行解（如使用大M法或两阶段法）做准备。
典式（Canonical Form）的重要性
在单纯形法迭代过程中，我们将方程组转化为关于当前基的典式。在典式中，基变量在目标函数中的系数为 0。这种形式使得我们可以直接读取当前的目标函数值和检验数（Reduced Cost），从而判断当前解是否最优。
单纯形法：定理的工程实现
线性规划基本定理证明不仅仅是一个理论命题，它直接指导了乔治·丹齐格（George Dantzig）提出的单纯形法。单纯形法的搜索策略正是基于“从一个顶点移动到相邻的、使目标函数值更优的顶点”这一逻辑。
找到一个初始基本可行解（顶点）。通常通过引入人工变量或使用松弛变量直接获得。
计算非基变量的检验数 σ_j = c_j - z_j。若所有 σ_j ≤ 0（最大化问题），则当前解为最优解，算法终止。这基于定理：若所有相邻顶点的目标值都不优于当前值，则当前顶点即为全局最优。
若存在 σ_j > 0，选择最大的正检验数对应的变量进基。确定出基变量以保持可行性（最小比值规则）。进行高斯消元更新表。
回到步骤 2，直到找到最优解或判定问题无界。
退化与循环问题
当基本可行解中有一个或多个基变量为 0 时，称为退化（Degeneracy）。退化可能导致单纯形法在迭代过程中目标函数值不增加，甚至出现循环（Cycling），即无限重复相同的基本解序列。虽然概率极低，但Bland规则（选择下标最小的进基和出基变量）可以从理论上保证有限步终止。
线性规划基本定理常见问题解答 (FAQ)
线性规划基本定理证明不仅揭示了线性规划问题的几何结构，更为我们提供了高效的算法基础。从标准型的转化，到基本可行解的定义，再到单纯形法的迭代逻辑，每一个环节都紧密相连。理解这些核心概念，能够帮助我们在面对复杂的优化问题时，透过现象看本质，做出更科学的决策。
无论是学术研究还是工程实践，掌握线性规划的基本原理都是不可或缺的。希望本文的深入解析能为您的学习之路提供清晰的指引。