# 单纯形法 (Simplex Method)
单纯形法 (Simplex Method) 是一种用于求解{{{线性规划}}} (Linear Programming, LP) 问题的有效算法。它由美国数学家[[乔治·丹齐格]] (George Dantzig) 在1947年提出，是{{{运筹学}}} (Operations Research) 和{{{最优化理论}}} (Optimization Theory) 中最重要和最基础的算法之一。单纯形法的核心思想是在由线性约束条件定义的多维可行域的顶点之间进行迭代搜索，每一步都移动到使得{{{目标函数}}}值更优的相邻顶点，直至找到{{{最优解}}}。
## 线性规划的标准形式
为了应用单纯形法，一个线性规划问题通常需要被转换成 标准形式 (Standard Form)。一个最大化问题的标准形式具有以下特征：
1. 目标函数：问题旨在最大化一个线性目标函数。 2. 约束条件：所有约束条件都是“小于等于”($\leq$) 的不等式（除了变量的非负性约束）。 3. 非负变量：所有决策变量都必须大于或等于零。
一个典型的标准形式问题如下：
最大化: $$ Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n $$
服从于: $$ a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n \leq b_1 $$ $$ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n \leq b_2 $$ $$ \vdots $$ $$ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n \leq b_m $$ $$ x_1, x_2, \ldots, x_n \geq 0 $$ 其中 $b_i \geq 0$ 对所有 $i=1, \ldots, m$ 成立。
为了将不等式约束转换为等式约束以便于代数操作，我们引入 {{{松弛变量}}} (Slack Variables)。对于每一个 $\leq$ 约束，我们添加一个非负的松弛变量，将其变为等式。例如，约束 $x_1 + 2x_2 \leq 10$ 可以被重写为 $x_1 + 2x_2 + s_1 = 10$，其中 $s_1 \geq 0$。松弛变量代表了该项约束下未被利用的资源量。
加入松弛变量后，上述问题变为： 最大化: $$ Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n $$ 服从于: $$ a_{11} x_1 + \cdots + a_{1n} x_n + s_1 = b_1 $$ $$ a_{21} x_1 + \cdots + a_{2n} x_n + s_2 = b_2 $$ $$ \vdots $$ $$ a_{m1} x_1 + \cdots + a_{mn} x_n + s_m = b_m $$ $$ x_1, \ldots, x_n, s_1, \ldots, s_m \geq 0 $$
这个等式形式是构建 单纯形表 (Simplex Tableau) 的基础。
## 算法的核心逻辑
### 几何解释 线性规划问题的{{{可行域}}} (Feasible Region) 是一个{{{凸多胞体}}} (Convex Polytope)。这是一个在高维空间中的多边形或多面体。一个重要的基本定理指出：如果一个线性规划问题存在最优解，那么至少有一个最优解位于该凸多胞体的一个 {{{顶点}}} (Vertex) 上。
单纯形法利用了这一特性： 1. 起始：从可行域的一个顶点开始。在标准形式中，原点（所有决策变量为0）通常是一个方便的起始顶点。 2. 移动：沿着连接当前顶点和另一个相邻顶点的边移动，选择能使目标函数值改善最大的方向。 3. 迭代：重复移动过程，从一个顶点到另一个更好的顶点。由于每一步目标函数值都在增加（或保持不变），且顶点的数量是有限的，该过程最终会收敛。 4. 终止：当到达一个顶点，其所有相邻顶点的目标函数值都不比当前值更优时，算法终止。该顶点即为最优解。
### 代数解释：单纯形表与基解 几何上的顶点在代数上对应一个 {{{基本可行解}}} (Basic Feasible Solution, BFS)。在一个有 $m$ 个约束和 $n$ 个决策变量（总共 $n+m$ 个变量，包括松弛变量）的系统中，一个基本解是通过将 $n$ 个变量设为0并解出其余 $m$ 个变量得到的。 * 被设为0的变量称为 {{{非基变量}}} (Non-basic Variables)。 * 被解出的 $m$ 个变量称为 {{{基变量}}} (Basic Variables)。 如果一个基本解中所有变量都满足非负性，它就是一个基本可行解（BFS）。
单纯形法通过 旋转 (Pivoting) 操作，在代数上实现从一个BFS到另一个BFS的转换。这个过程在单纯形表中进行。
## 单纯形法的迭代步骤
我们将通过一个具体的例子来展示算法的步骤。考虑以下问题： 最大化: $$ Z = 3x_1 + 5x_2 $$ 服从于: $$ \begin{align*} x_1 & \leq 4 \\ 2x_2 & \leq 12 \\ 3x_1 + 2x_2 & \leq 18 \\ x_1, x_2 & \geq 0 \end{align*} $$
第一步：转换为标准形式并建立初始单纯形表
引入松弛变量 $s_1, s_2, s_3$，并将目标函数改写为 $Z - 3x_1 - 5x_2 = 0$。 $$ \begin{align*} x_1 + s_1 & = 4 \\ 2x_2 + s_2 & = 12 \\ 3x_1 + 2x_2 + s_3 & = 18 \end{align*} $$ 初始单纯形表如下：
| 基变量 | $Z$ | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | RHS (解) | | :---: | :-: | :---: | :---: | :---: | :---: | :---: | :---: | | $Z$ | 1 | -3 | -5 | 0 | 0 | 0 | 0 | | $s_1$ | 0 | 1 | 0 | 1 | 0 | 0 | 4 | | $s_2$ | 0 | 0 | 2 | 0 | 1 | 0 | 12 | | $s_3$ | 0 | 3 | 2 | 0 | 0 | 1 | 18 |
当前BFS为：基变量 $(s_1, s_2, s_3) = (4, 12, 18)$，非基变量 $(x_1, x_2) = (0, 0)$。目标函数值 $Z=0$。
第二步：检查最优性
查看目标函数行（$Z$ 行）。只要存在负系数，当前解就不是最优的。这里 -3 和 -5 都是负数。
第三步：选择入基变量 (Entering Variable)
选择目标函数行中系数最负的变量作为 入基变量。这是因为该变量每增加一个单位，对目标函数的贡献最大。这里我们选择 $x_2$（系数为-5）。$x_2$ 所在的列被称为 主列 (Pivot Column)。
第四步：选择出基变量 (Leaving Variable)
为了确定哪个基变量将离开基，我们进行 {{{最小比率测试}}} (Minimum Ratio Test)。用RHS列的每个值除以主列中对应的正数： * $s_1$ 行：比率不适用（主列系数为0）。 * $s_2$ 行：$12 / 2 = 6$ * $s_3$ 行：$18 / 2 = 9$
选择其中最小的非负比率。这里最小比率是6，对应于 $s_2$ 行。因此，$s_2$ 是 出基变量。$s_2$ 所在的行被称为 主行 (Pivot Row)。 最小比率测试确保了在变量替换后，新的解仍然是可行的（所有变量值非负）。
第五步：执行旋转操作
主列和主行的交叉点元素称为 主元 (Pivot Element)，这里是2。我们的目标是利用{{{高斯消元法}}}的行操作，将主元变为1，并将主列的其他所有元素变为0。 1. 将主行（$s_2$ 行）除以主元2： `[0, 0, 2, 0, 1, 0, 12]` 变为 `[0, 0, 1, 0, 1/2, 0, 6]`。 2. 更新其他行： * 新 $Z$ 行 = 旧 $Z$ 行 + 5 * (新 $s_2$ 行) `[1, -3, -5, 0, 0, 0, 0]` + 5 * `[0, 0, 1, 0, 1/2, 0, 6]` = `[1, -3, 0, 0, 5/2, 0, 30]` * 新 $s_1$ 行不变，因为其主列元素为0。 * 新 $s_3$ 行 = 旧 $s_3$ 行 - 2 * (新 $s_2$ 行) `[0, 3, 2, 0, 0, 1, 18]` - 2 * `[0, 0, 1, 0, 1/2, 0, 6]` = `[0, 3, 0, 0, -1, 1, 6]`
我们得到新的单纯形表（第一次迭代后）：
| 基变量 | $Z$ | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | RHS | | :---: | :-: | :---: | :---: | :---: | :---: | :---: | :-: | | Z | 1 | -3 | 0 | 0 | 5/2 | 0 | 30 | | $s_1$ | 0 | 1 | 0 | 1 | 0 | 0 | 4 | | $x_2$ | 0 | 0 | 1 | 0 | 1/2 | 0 | 6 | | $s_3$ | 0 | 3 | 0 | 0 | -1 | 1 | 6 |
现在，BFS为：基变量 $(s_1, x_2, s_3) = (4, 6, 6)$，非基变量 $(x_1, s_2)=(0,0)$。目标函数值 $Z=30$。
第六步：重复迭代
我们回到第二步，再次检查最优性。$Z$ 行仍有负数（-3），所以继续迭代。 * 入基变量：$x_1$ (主列)。 * 出基变量：进行最小比率测试。 * $s_1$ 行: $4 / 1 = 4$ * $x_2$ 行: 比率不适用（主列系数为0）。 * $s_3$ 行: $6 / 3 = 2$ 最小比率是2，对应 $s_3$ 行。所以 $s_3$ 是出基变量。主元是3。 * 旋转操作： 1. 新 $s_3$ 行 = 旧 $s_3$ 行 / 3 → `[0, 1, 0, 0, -1/3, 1/3, 2]` 2. 新 $Z$ 行 = 旧 $Z$ 行 + 3 * (新 $s_3$ 行) → `[1, 0, 0, 0, 3/2, 1, 36]` 3. 新 $s_1$ 行 = 旧 $s_1$ 行 - 1 * (新 $s_3$ 行) → `[0, 0, 0, 1, 1/3, -1/3, 2]` 4. 新 $x_2$ 行不变。
最终的单纯形表如下：
| 基变量 | $Z$ | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | RHS | | :---: | :-: | :---: | :---: | :---: | :---: | :---: | :-: | | Z | 1 | 0 | 0 | 0 | 3/2 | 1 | 36 | | $s_1$ | 0 | 0 | 0 | 1 | 1/3 | -1/3 | 2 | | $x_2$ | 0 | 0 | 1 | 0 | 1/2 | 0 | 6 | | $x_1$ | 0 | 1 | 0 | 0 | -1/3 | 1/3 | 2 |
第七步：得出结论
再次检查 $Z$ 行，所有系数都为非负数 (0, 3/2, 1)。这表明已达到最优解。 最终解可以从表中读出： * 基变量的值即为RHS列对应的值：$x_1 = 2$, $x_2 = 6$, $s_1=2$。 * 非基变量的值为0：$s_2=0, s_3=0$。 * 最优目标函数值为 $Z=36$。
## 特殊情况
* {{{无界解}}} (Unbounded Solution)：如果在选择出基变量时，主列的所有元素都小于或等于0，这意味着入基变量可以无限增加而不违反任何约束，导致目标函数无限增大。 * {{{退化}}} (Degeneracy)：如果在最小比率测试中出现平局，下一个基本可行解中会有一个或多个基变量的值为0。这可能（尽管很少）导致{{{循环}}} (Cycling)，即算法在一系列解中循环而无法达到最优。{{{布兰德规则}}} (Bland's Rule) 等方法可以避免循环。 * 多重最优解 (Multiple Optimal Solutions)：如果最优表中，某个非基变量在目标函数行中的系数为0，这表明该非基变量可以入基而不改变目标函数的最优值。这揭示了存在无穷多个最优解。 * 不可行问题 (Infeasible Problem)：对于初始解不是原点的问题（如有 $\geq$ 或 $=$ 约束），需要引入{{{人工变量}}} (Artificial Variables)，并使用{{{两阶段法}}} (Two-Phase Method) 或{{{大M法}}} (Big M Method)。如果在算法结束时，人工变量仍以正值存在于基中，则原问题没有可行解。
单纯形法虽然在最坏情况下的{{{计算复杂性}}}是指数级的，但在实践中，它对于绝大多数问题都非常高效。它不仅是一个求解工具，其背后的{{{对偶理论}}} (Duality Theory) 和{{{灵敏度分析}}} (Sensitivity Analysis) 也为经济决策和管理提供了深刻的洞察。