【运筹学单纯形法例题四和详解】在运筹学中，单纯形法是求解线性规划问题的一种经典方法。本文将通过一个典型的例题，详细讲解如何使用单纯形法进行求解，并以表格形式展示每一步的计算过程，帮助读者更好地理解该方法的应用。
一、例题描述
某工厂生产两种产品A和B，生产每单位产品A需要消耗3个工时和2个原材料单位，生产每单位产品B需要消耗2个工时和4个原材料单位。工厂每天最多有18个工时和16个原材料单位可用。产品A的利润为每单位5元，产品B的利润为每单位4元。试问如何安排生产，使利润最大？
二、建立数学模型
设：
- $ x_1 $：产品A的产量
- $ x_2 $：产品B的产量
目标函数（最大化利润）：
$$
\text{Max } Z = 5x_1 + 4x_2
$$
约束条件：
$$
\begin{cases}
3x_1 + 2x_2 \leq 18 \\
2x_1 + 4x_2 \leq 16 \\
x_1, x_2 \geq 0
\end{cases}
$$
引入松弛变量 $ s_1 $ 和 $ s_2 $，将不等式转化为等式：
$$
\begin{cases}
3x_1 + 2x_2 + s_1 = 18 \\
2x_1 + 4x_2 + s_2 = 16 \\
x_1, x_2, s_1, s_2 \geq 0
\end{cases}
$$
三、初始单纯形表
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS |
| $ s_1 $ | 3 | 2 | 1 | 0 | 18 |
| $ s_2 $ | 2 | 4 | 0 | 1 | 16 |
| $ Z $ | -5 | -4 | 0 | 0 | 0 |
四、迭代步骤
第一次迭代：
- 进基变量：$ x_1 $（因为系数最小值为-5）
- 出基变量：选择最小比值 $ \min(18/3, 16/2) = \min(6, 8) = 6 $，对应行是 $ s_1 $
换入 $ x_1 $，换出 $ s_1 $
更新后的表格如下：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS |
| $ x_1 $ | 1 | 2/3 | 1/3 | 0 | 6 |
| $ s_2 $ | 0 | 8/3 | -2/3 | 1 | 4 |
| $ Z $ | 0 | -2/3 | 5/3 | 0 | 30 |
第二次迭代：
- 进基变量：$ x_2 $（系数最小值为-2/3）
- 出基变量：选择最小比值 $ \min(6/(2/3), 4/(8/3)) = \min(9, 1.5) = 1.5 $，对应行是 $ s_2 $
换入 $ x_2 $，换出 $ s_2 $
更新后的表格如下：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS |
| $ x_1 $ | 1 | 0 | 1/4 | -1/4 | 4.5 |
| $ x_2 $ | 0 | 1 | -1/4 | 3/4 | 1.5 |
| $ Z $ | 0 | 0 | 1.25 | 1.5 | 31 |
五、最终结果
此时所有检验数均为非负，说明已达到最优解。
- $ x_1 = 4.5 $
- $ x_2 = 1.5 $
- 最大利润 $ Z = 31 $
六、总结与表格
| 步骤 | 进基变量 | 出基变量 | 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS | Z值 |
| 初始 | - | - | $ s_1 $, $ s_2 $ | 3 | 2 | 1 | 0 | 18 | 0 |
| $ x_1 $ | $ s_1 $ | $ x_1 $, $ s_2 $ | 1 | 2/3 | 1/3 | 0 | 6 | 30 | |
| $ x_2 $ | $ s_2 $ | $ x_1 $, $ x_2 $ | 1 | 0 | 1/4 | -1/4 | 4.5 | 31 |
七、结论
通过单纯形法的逐步迭代，我们得到了最优解：生产4.5单位产品A和1.5单位产品B，可以获得最大利润31元。此过程展示了单纯形法的基本原理和应用步骤，适用于类似线性规划问题的求解。
