【单纯形表法详细讲解】单纯形表法（Simplex Method）是线性规划中求解最优解的一种经典算法，广泛应用于资源分配、生产计划、运输调度等实际问题中。该方法通过迭代的方式逐步逼近最优解，其核心思想是利用线性规划的约束条件和目标函数，将问题转化为一个表格形式，便于计算与分析。
一、单纯形表法的基本原理
单纯形表法是一种基于代数运算的优化方法，适用于标准形式的线性规划问题：
标准形式：
- 目标函数：最大化 $ Z = c_1x_1 + c_2x_2 + \cdots + c_nx_n $
- 约束条件：$ a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 $
- $ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2 $
- ...
- $ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n = b_m $
- 所有变量 $ x_i \geq 0 $
在单纯形表中，我们引入松弛变量或人工变量来将不等式转换为等式，并构建初始可行解。
二、单纯形表的结构
单纯形表通常包括以下几列：
| 基变量 | $ x_1 $ | $ x_2 $ | ... | $ x_n $ | 松弛变量 | 右端项（RHS） | 检验数（Cj - Zj） |
其中：
- 基变量：当前解中的非零变量。
- 系数列：对应变量在各个约束方程中的系数。
- 右端项（RHS）：表示当前解的值。
- 检验数（Cj - Zj）：用于判断是否达到最优解。
三、单纯形表法的步骤总结
1. 建立初始单纯形表
将线性规划问题转化为标准形式，引入松弛变量或人工变量，构造初始单纯形表。
2. 确定入基变量
选择检验数为正的最大值对应的变量作为入基变量（对于最大化问题）。
3. 确定出基变量
对于入基变量所在的列，计算各非零行的比值（RHS / 系数），选择最小的比值对应的行作为出基变量。
4. 进行行变换
将入基变量所在的行化为单位向量，其他行相应调整，使新的基变量替换旧的基变量。
5. 检查最优性
如果所有检验数均小于等于0，则当前解为最优解；否则重复步骤2~4。
四、示例说明（以简单线性规划为例）
考虑如下线性规划问题：
最大化：$ Z = 3x_1 + 5x_2 $
约束条件：
$$
\begin{cases}
x_1 + 2x_2 \leq 4 \\
3x_1 + 2x_2 \leq 6 \\
x_1, x_2 \geq 0
\end{cases}$$
引入松弛变量 $ s_1, s_2 $，将其转化为标准形式：
$$
\begin{cases}
x_1 + 2x_2 + s_1 = 4 \\
3x_1 + 2x_2 + s_2 = 6 \\
x_1, x_2, s_1, s_2 \geq 0
\end{cases}$$
初始单纯形表如下：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS | Cj - Zj |
| $ s_1 $ | 1 | 2 | 1 | 0 | 4 | -3 |
| $ s_2 $ | 3 | 2 | 0 | 1 | 6 | -5 |
| $ Z $ | 0 | 0 | 0 | 0 | 0 |
第一次迭代：
- 入基变量：$ x_2 $（Cj - Zj = -5 最小）
- 出基变量：$ s_1 $（RHS/2 = 2，RHS/2 = 3 → 选 $ s_1 $）
更新后单纯形表：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS | Cj - Zj |
| $ x_2 $ | 0.5 | 1 | 0.5 | 0 | 2 | 0 |
| $ s_2 $ | 2 | 0 | -1 | 1 | 2 | -5 |
| $ Z $ | 2.5 | 5 | 2.5 | 0 | 10 |
第二次迭代：
- 入基变量：$ x_1 $（Cj - Zj = -5 最小）
- 出基变量：$ s_2 $（RHS/2 = 1）
最终单纯形表：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS | Cj - Zj |
| $ x_2 $ | 0 | 1 | 0.75 | -0.25 | 1.5 | 0 |
| $ x_1 $ | 1 | 0 | -0.5 | 0.5 | 1 | 0 |
| $ Z $ | 3 | 5 | 1.25 | 1.25 | 13 |
此时所有检验数均为0，停止迭代，得到最优解：
- $ x_1 = 1 $，$ x_2 = 1.5 $，最大值 $ Z = 13 $
五、总结
单纯形表法是一种系统化、结构清晰的求解线性规划问题的方法，通过不断迭代，逐步逼近最优解。其关键在于正确识别入基与出基变量，并合理进行行变换。虽然在某些情况下可能需要处理退化或循环问题，但总体而言，它仍然是解决线性规划问题最有效的方法之一。
| 单纯形法步骤 | 内容 |
| 1. 构建初始表 | 引入松弛变量，构造初始基变量 |
| 2. 判断入基变量 | 选择检验数最大的变量 |
| 3. 判断出基变量 | 计算比值，选择最小比值对应的行 |
| 4. 行变换 | 调整表中行，使新基变量为单位向量 |
| 5. 判断最优性 | 所有检验数 ≤ 0 时停止 |
通过上述步骤和表格展示，可以清晰地理解单纯形表法的运作机制，帮助初学者快速掌握这一经典算法的核心思想。