【单纯形表法详细讲解】单纯形表法是线性规划问题中求解最优解的一种经典算法，适用于求解标准形式的线性规划问题。该方法通过构造一个称为“单纯形表”的表格，逐步迭代寻找可行解中的最优解。以下是对单纯形表法的详细讲解，结合文字说明与表格展示。
一、单纯形表法的基本概念
单纯形表法是一种基于基变量和非基变量的迭代方法。其核心思想是：从一个初始可行解出发，通过选择合适的进基变量和出基变量，不断调整当前解，直到找到最优解为止。
- 基变量（Basic Variables）：在当前解中取非零值的变量。
- 非基变量（Non-basic Variables）：在当前解中取零值的变量。
- 目标函数（Objective Function）：需要最大化或最小化的函数。
- 约束条件（Constraints）：由不等式或等式构成的线性方程组。
二、单纯形表的结构
单纯形表通常包括以下几个部分：
| 基变量 | 系数列（Cj） | x₁ | x₂ | … | xn | b（常数项） |
其中：
- 基变量：当前的基变量名称。
- Cj：目标函数中对应变量的系数。
- x₁, x₂, ..., xn：各变量的系数列。
- b：约束方程右边的常数项。
三、单纯形表法的步骤
1. 建立初始单纯形表
- 将线性规划问题转化为标准形式（如引入松弛变量或人工变量）。
- 构造初始单纯形表，其中基变量为松弛变量或人工变量。
2. 计算检验数（Zj - Cj）
- 检验数表示每增加一个单位的非基变量对目标函数的影响。
- 若所有检验数 ≤ 0（对于最大化问题），则当前解为最优解。
3. 选择进基变量
- 在检验数大于0的变量中，选择最大值对应的变量作为进基变量。
4. 选择出基变量
- 用最小比值法（即 b / 进基变量列中的正系数）确定出基变量。
- 若所有系数 ≤ 0，则问题无界。
5. 进行行变换
- 通过初等行变换，将进基变量的系数变为1，并消去其他行中该变量的系数。
6. 重复步骤2~5
- 直到所有检验数 ≤ 0（最大化问题）或 ≥ 0（最小化问题）。
四、单纯形表法示例（以最大化问题为例）
考虑如下线性规划问题：
$$
\text{Maximize } Z = 3x_1 + 5x_2
$$
$$
\text{Subject to: }
\begin{cases}
x_1 \leq 4 \\
2x_2 \leq 12 \\
3x_1 + 2x_2 \leq 18 \\
x_1, x_2 \geq 0
\end{cases}
$$
将其转换为标准形式，引入松弛变量 $s_1, s_2, s_3$，得到：
$$
\text{Maximize } Z = 3x_1 + 5x_2 + 0s_1 + 0s_2 + 0s_3
$$
$$
\text{Subject to: }
\begin{cases}
x_1 + s_1 = 4 \\
2x_2 + s_2 = 12 \\
3x_1 + 2x_2 + s_3 = 18 \\
x_1, x_2, s_1, s_2, s_3 \geq 0
\end{cases}
$$
构建初始单纯形表如下：
| 基变量 | Cj | x₁ | x₂ | s₁ | s₂ | s₃ | b |
| s₁ | 0 | 1 | 0 | 1 | 0 | 0 | 4 |
| s₂ | 0 | 0 | 2 | 0 | 1 | 0 | 12 |
| s₃ | 0 | 3 | 2 | 0 | 0 | 1 | 18 |
| Zj | 0 | 0 | 0 | 0 | 0 | 0 | |
| Cj-Zj | 3 | 5 | 0 | 0 | 0 |
第一次迭代：
- 进基变量：x₂（Cj-Zj = 5 > 0）
- 出基变量：s₂（最小比值：12/2 = 6）
进行行变换后，得到新的单纯形表：
| 基变量 | Cj | x₁ | x₂ | s₁ | s₂ | s₃ | b |
| s₁ | 0 | 1 | 0 | 1 | 0 | 0 | 4 |
| x₂ | 5 | 0 | 1 | 0 | 0.5 | 0 | 6 |
| s₃ | 0 | 3 | 0 | 0 | -1 | 1 | 6 |
| Zj | 0 | 5 | 0 | 2.5 | 0 | 30 | |
| Cj-Zj | 3 | 0 | 0 | -2.5 | 0 |
第二次迭代：
- 进基变量：x₁（Cj-Zj = 3 > 0）
- 出基变量：s₃（最小比值：6/3 = 2）
经过行变换后，最终得到最优解：
| 基变量 | Cj | x₁ | x₂ | s₁ | s₂ | s₃ | b |
| s₁ | 0 | 0 | 0 | 1 | 0.67 | -0.33 | 2 |
| x₂ | 5 | 0 | 1 | 0 | 0.5 | 0 | 6 |
| x₁ | 3 | 1 | 0 | 0 | -0.33 | 0.33 | 2 |
| Zj | 3 | 5 | 0 | 2.33 | 1 | 36 | |
| Cj-Zj | 0 | 0 | 0 | -2.33 | -1 |
此时所有检验数均小于等于0，达到最优解。
五、总结
单纯形表法是一种系统、高效的线性规划求解方法，通过构造和更新单纯形表逐步逼近最优解。掌握其基本原理和操作步骤，有助于快速解决实际优化问题。在实践中，还需注意处理退化、多重解等情况，确保算法稳定性和结果准确性。