在最优化理论中，线性规划是最基础也是应用最广泛的问题之一。而单纯形法则是求解线性规划问题的经典方法之一，它通过迭代的方式逐步逼近最优解。本文将结合一个典型的线性规划问题，详细讲解如何使用单纯形法进行求解，并通过实例加深对这一算法的理解。
一、问题描述
我们考虑以下线性规划问题：
最大化：
$$ Z = 3x_1 + 5x_2 $$
约束条件为：
$$
\begin{cases}
x_1 \leq 4 \\
2x_2 \leq 12 \\
3x_1 + 2x_2 \leq 18 \\
x_1, x_2 \geq 0
\end{cases}
$$
目标是找到满足所有约束条件的 $ x_1 $ 和 $ x_2 $ 的值，使得目标函数 $ Z $ 达到最大值。
二、引入松弛变量并建立初始单纯形表
为了将不等式约束转化为等式，我们需要引入松弛变量（Slack Variables），记作 $ s_1, s_2, s_3 $，分别对应三个不等式约束。于是原问题变为：
最大化：
$$ Z = 3x_1 + 5x_2 + 0s_1 + 0s_2 + 0s_3 $$
约束条件为：
$$
\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}
$$
此时，我们可以构造初始的单纯形表如下：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | $ s_3 $ | RHS |
|--------|-----------|-----------|-----------|-----------|-----------|-----|
| $ s_1 $ | 1 | 0 | 1 | 0 | 0 | 4 |
| $ s_2 $ | 0 | 2 | 0 | 1 | 0 | 12|
| $ s_3 $ | 3 | 2 | 0 | 0 | 1 | 18|
| $ Z $| -3| -5| 0 | 0 | 0 | 0 |
三、确定入基变量和出基变量
在单纯形法中，我们首先选择非基变量中系数为负的行中的最小值对应的变量作为入基变量。观察目标函数行（Z行）中的系数，$ x_2 $ 的系数为 -5，是当前最小的，因此我们选择 $ x_2 $ 作为入基变量。
接下来，我们需要确定出基变量。这一步需要计算每个约束行中入基变量列的比值（RHS / 入基变量系数），并选择最小的正比值所对应的行作为出基变量。
- 对于 $ s_1 $ 行：$ 4 / 0 $ → 不可取（系数为0）
- 对于 $ s_2 $ 行：$ 12 / 2 = 6 $
- 对于 $ s_3 $ 行：$ 18 / 2 = 9 $
所以，选择 $ s_2 $ 作为出基变量，替换为 $ x_2 $。
四、进行行变换，更新单纯形表
现在，我们将以 $ x_2 $ 为新的基变量，进行行变换。首先将 $ s_2 $ 行除以 2，使其主元变为 1：
$$
x_2 + 0.5s_2 = 6
$$
接着，用这个新行去消去其他行中的 $ x_2 $ 项：
- 对于 $ s_1 $ 行：无变化
- 对于 $ s_3 $ 行：减去 2 × 新的 $ x_2 $ 行：
$$
3x_1 + 2x_2 + s_3 - 2(x_2 + 0.5s_2) = 18 - 2×6 = 6
$$
得到：$ 3x_1 + s_3 - s_2 = 6 $
- 对于目标函数行：加上 5 × 新的 $ x_2 $ 行：
$$
Z + 5(x_2 + 0.5s_2) = 0 + 5×6 = 30
$$
得到：$ Z + 5x_2 + 2.5s_2 = 30 $
更新后的单纯形表如下：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | $ s_3 $ | RHS |
|--------|-----------|-----------|-----------|-----------|-----------|-----|
| $ s_1 $ | 1 | 0 | 1 | 0 | 0 | 4 |
| $ x_2 $ | 0 | 1 | 0 | 0.5 | 0 | 6 |
| $ s_3 $ | 3 | 0 | 0 | -1| 1 | 6 |
| $ Z $| -3| 0 | 0 | 2.5 | 0 | 30|
五、继续迭代
再次检查目标函数行，当前 $ x_1 $ 的系数为 -3，仍然为负数，说明可以继续优化。因此，选择 $ x_1 $ 作为下一个入基变量。
计算比值：
- $ s_1 $ 行：$ 4 / 1 = 4 $
- $ x_2 $ 行：$ 6 / 0 $ → 不可取
- $ s_3 $ 行：$ 6 / 3 = 2 $
选择 $ s_3 $ 作为出基变量，替换为 $ x_1 $。
将 $ s_3 $ 行除以 3，得到：
$$
x_1 + 0s_1 - \frac{1}{3}s_2 + \frac{1}{3}s_3 = 2
$$
然后用该行消去其他行中的 $ x_1 $：
- $ s_1 $ 行：减去 1 × 新 $ x_1 $ 行：
$$
s_1 - (x_1 - \frac{1}{3}s_2 + \frac{1}{3}s_3) = 4 - 2 = 2
$$
得到：$ s_1 + \frac{1}{3}s_2 - \frac{1}{3}s_3 = 2 $
- 目标函数行：加上 3 × 新 $ x_1 $ 行：
$$
Z -3x_1 + 3(x_1 - \frac{1}{3}s_2 + \frac{1}{3}s_3) = 30 + 6 = 36
$$
得到：$ Z + 0x_1 - 1s_2 + 1s_3 = 36 $
最终的单纯形表如下：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | $ s_3 $ | RHS |
|--------|-----------|-----------|-----------|-----------|-----------|-----|
| $ s_1 $ | 0 | 0 | 1 | 1/3 | -1/3| 2 |
| $ x_2 $ | 0 | 1 | 0 | 0.5 | 0 | 6 |
| $ x_1 $ | 1 | 0 | 0 | -1/3| 1/3 | 2 |
| $ Z $| 0 | 0 | 0 | -1| 1 | 36|
此时，目标函数行中所有非基变量的系数均为非负，说明已经到达最优解。
六、结论
根据最终的单纯形表，我们得出：
- $ x_1 = 2 $
- $ x_2 = 6 $
- 最大目标函数值 $ Z = 36 $
因此，该线性规划问题的最优解为 $ x_1 = 2 $，$ x_2 = 6 $，最大值为 36。
七、总结
单纯形法是一种系统性的求解线性规划问题的方法，通过不断迭代，寻找使目标函数达到最优的解。本例中，我们通过引入松弛变量、构造初始单纯形表、选择入基和出基变量，并进行行变换，最终找到了最优解。掌握这种方法，有助于理解和解决实际工程和管理中的优化问题。
