【精品（最优化单纯形法例题讲解）】在最优化理论中，线性规划是一种常见的数学建模方法，而单纯形法则是求解线性规划问题的经典算法之一。本文将通过一个具体的例题，详细讲解如何运用单纯形法进行求解，帮助读者更好地理解该方法的原理与操作步骤。
一、问题描述
我们考虑如下线性规划问题：
最大化目标函数：
$$
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 + s_1 = 4$
- 第二个约束：$2x_2 + s_2 = 12$
- 第三个约束：$3x_1 + 2x_2 + s_3 = 18$
其中，$s_1, s_2, s_3$ 是松弛变量，且均为非负。
目标函数保持不变：
$$
Z = 3x_1 + 5x_2 + 0s_1 + 0s_2 + 0s_3
$$
三、建立初始单纯形表
我们将上述模型整理成初始单纯形表：
| 基变量 | $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$ 作为入基变量。
第二步：选择出基变量
对 $x_2$ 所在列（第二列），计算各约束行 RHS 除以对应系数的比值：
- $s_1$ 行：无 $x_2$，忽略
- $s_2$ 行：$12 / 2 = 6$
- $s_3$ 行：$18 / 2 = 9$
最小比值为 6，对应的是 $s_2$ 行，因此 $s_2$ 出基。
第三步：进行矩阵变换
用 $x_2$ 替换 $s_2$，并进行行变换，使 $x_2$ 在该列中变为 1，其他行中的 $x_2$ 系数变为 0。
新的表格如下：
| 基变量 | $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| 2| 0| 0| 1| 18 |
| $Z$ | -3 | 0| 0| 2.5| 0| 30 |
五、继续迭代
此时，目标行中仍有负系数（$x_1$ 为 -3），继续选择入基变量。
第一步：选择入基变量
选择 $x_1$ 作为入基变量。
第二步：选择出基变量
对 $x_1$ 列计算比值：
- $s_1$ 行：$4 / 1 = 4$
- $x_2$ 行：无 $x_1$，忽略
- $s_3$ 行：$18 / 3 = 6$
最小比值为 4，对应 $s_1$ 行，因此 $s_1$ 出基。
第三步：进行矩阵变换
用 $x_1$ 替换 $s_1$，并调整其他行。
最终得到新表格：
| 基变量 | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | RHS|
|--------|--------|--------|--------|--------|--------|------|
| $x_1$ | 1| 0| 1| 0| 0| 4|
| $x_2$ | 0| 1| 0| 0.5| 0| 6|
| $s_3$ | 0| 2| -3 | 0| 1| 6|
| $Z$ | 0| 0| 3| 2.5| 0| 42 |
六、结果分析
此时，目标行中所有非基变量的系数均为非负，说明已达到最优解。
最优解为：
- $x_1 = 4$
- $x_2 = 6$
- $Z = 3×4 + 5×6 = 12 + 30 = 42$
七、总结
通过以上步骤，我们成功地利用单纯形法解决了该线性规划问题。整个过程中，关键是正确识别入基和出基变量，并进行适当的行变换。掌握这些技巧后，可以高效地处理更复杂的线性规划问题。
如需进一步学习或练习，建议结合更多例题进行巩固，逐步提升对单纯形法的理解与应用能力。
