【运筹学单纯形法的例题】在运筹学中，线性规划是解决资源分配问题的重要工具。而单纯形法则是求解线性规划问题的一种经典算法，它通过迭代的方式逐步逼近最优解。本文将通过一个典型的例题，详细讲解如何运用单纯形法进行求解。
一、问题描述
某工厂生产两种产品A和B，每种产品的生产需要消耗一定的原材料和工时。已知：
- 每生产一件A产品，需要消耗2单位原材料和3单位工时；
- 每生产一件B产品，需要消耗1单位原材料和4单位工时；
- 原材料总共有8单位，工时总共有12单位；
- A产品的利润为5元/件，B产品的利润为6元/件。
要求：在满足资源限制的前提下，最大化利润。
二、建立线性规划模型
设：
- $ x_1 $：生产A产品的数量
- $ x_2 $：生产B产品的数量
目标函数（利润最大化）为：
$$
\text{Max } Z = 5x_1 + 6x_2
$$
约束条件为：
$$
\begin{cases}
2x_1 + x_2 \leq 8 \\
3x_1 + 4x_2 \leq 12 \\
x_1, x_2 \geq 0
\end{cases}
$$
三、引入松弛变量并转换为标准形式
为了使用单纯形法，我们需要将不等式约束转化为等式。为此，分别引入两个松弛变量 $ s_1 $ 和 $ s_2 $，表示未被使用的原材料和工时。
标准形式如下：
$$
\begin{cases}
2x_1 + x_2 + s_1 = 8 \\
3x_1 + 4x_2 + s_2 = 12 \\
x_1, x_2, s_1, s_2 \geq 0
\end{cases}
$$
目标函数变为：
$$
\text{Max } Z = 5x_1 + 6x_2 + 0s_1 + 0s_2
$$
四、构建初始单纯形表
我们以初始基变量 $ s_1 $ 和 $ s_2 $ 构建初始单纯形表：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS |
|--------|----------|----------|----------|----------|-----|
| $ s_1 $ | 2| 1| 1| 0| 8 |
| $ s_2 $ | 3| 4| 0| 1| 12|
| $ Z $ | -5 | -6 | 0| 0| 0 |
五、第一次迭代：选择进基变量与出基变量
1. 选择进基变量：目标函数行中系数最大的负数对应的变量是 $ x_2 $，因此选择 $ x_2 $ 进基。
2. 选择出基变量：计算各约束行中 $ x_2 $ 的系数与 RHS 的比值：
$$
\frac{8}{1} = 8,\quad \frac{12}{4} = 3
$$
最小比值为3，对应的是 $ s_2 $ 行，因此 $ s_2 $ 出基。
六、更新单纯形表
用 $ x_2 $ 替换 $ s_2 $，并对该行进行归一化处理：
原 $ s_2 $ 行：$ 3x_1 + 4x_2 + s_2 = 12 $
除以4得：
$$
\frac{3}{4}x_1 + x_2 + \frac{1}{4}s_2 = 3
$$
然后，用新行替换原 $ s_2 $ 行，并消去其他行中的 $ x_2 $。
最终得到新的单纯形表：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS |
|--------|----------|----------|----------|----------|-----|
| $ s_1 $ | 2| 1| 1| 0| 8 |
| $ x_2 $ | 3/4| 1| 0| 1/4| 3 |
| $ Z $ | -5 + 6(3/4) = -5 + 4.5 = -0.5 | 0 | 0 | -6(1/4) = -1.5 | 18 |
简化后：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS |
|--------|----------|----------|----------|----------|-----|
| $ s_1 $ | 2| 1| 1| 0| 8 |
| $ x_2 $ | 0.75 | 1| 0| 0.25 | 3 |
| $ Z $ | -0.5 | 0| 0| -1.5 | 18|
七、第二次迭代
1. 选择进基变量：当前目标函数行中，$ x_1 $ 系数为 -0.5，是最小的负数，因此 $ x_1 $ 进基。
2. 选择出基变量：计算比值：
$$
\frac{8}{2} = 4,\quad \frac{3}{0.75} = 4
$$
两个比值相等，任选其一即可，这里选择 $ s_1 $ 出基。
八、更新单纯形表
用 $ x_1 $ 替换 $ s_1 $，对第一行进行归一化处理：
原 $ s_1 $ 行：$ 2x_1 + x_2 + s_1 = 8 $
除以2得：
$$
x_1 + 0.5x_2 + 0.5s_1 = 4
$$
然后消去其他行中的 $ x_1 $，得到最终单纯形表：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS |
|--------|----------|----------|----------|----------|-----|
| $ x_1 $ | 1| 0.5| 0.5| 0| 4 |
| $ x_2 $ | 0.75 | 1| 0| 0.25 | 3 |
| $ Z $ | 0| 0| 0| -1.5 | 22|
九、结果分析
此时，所有非基变量的目标函数系数均为非负，说明已达到最优解。
最终解为：
- $ x_1 = 4 $
- $ x_2 = 3 $
- 最大利润 $ Z = 22 $ 元
十、结论
通过单纯形法的逐步迭代，我们成功地找到了使利润最大化的生产方案。这不仅展示了单纯形法的基本操作流程，也体现了其在实际问题中的应用价值。对于类似的问题，可以采用相同的方法进行求解，从而实现资源的最优配置。
