【运筹学单纯形法例题二和详解】在运筹学中，单纯形法是一种用于求解线性规划问题的算法。本文将以一个典型的线性规划问题为例，详细展示如何使用单纯形法进行求解，并通过表格形式对计算过程进行总结。
一、题目描述
某工厂生产两种产品A和B，每单位产品A可获利3元，每单位产品B可获利5元。生产过程中需要消耗原材料和工时，具体如下：
- 每生产1单位A需要消耗2个单位的原材料和4小时工时；
- 每生产1单位B需要消耗3个单位的原材料和2小时工时；
- 工厂每天最多可用原材料为18个单位，工时为16小时。
要求：求出使利润最大的生产方案。
二、建立模型
设：
- $ x_1 $：产品A的日产量
- $ x_2 $：产品B的日产量
目标函数（最大化利润）：
$$
\text{Max } Z = 3x_1 + 5x_2
$$
约束条件：
$$
\begin{cases}
2x_1 + 3x_2 \leq 18 \\
4x_1 + 2x_2 \leq 16 \\
x_1, x_2 \geq 0
\end{cases}
$$
引入松弛变量 $ s_1, s_2 $，将不等式转化为等式：
$$
\begin{cases}
2x_1 + 3x_2 + s_1 = 18 \\
4x_1 + 2x_2 + s_2 = 16 \\
x_1, x_2, s_1, s_2 \geq 0
\end{cases}
$$
三、单纯形法求解步骤
步骤1：初始单纯形表
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS |
| $ s_1 $ | 2 | 3 | 1 | 0 | 18 |
| $ s_2 $ | 4 | 2 | 0 | 1 | 16 |
| $ Z $ | -3 | -5 | 0 | 0 | 0 |
步骤2：选择进基变量
在目标行中，$ x_2 $ 的系数为 -5，是最负的，因此选择 $ x_2 $ 作为进基变量。
步骤3：选择出基变量
计算各约束行中 $ x_2 $ 系数与 RHS 的比值：
- $ s_1 $ 行：18 ÷ 3 = 6
- $ s_2 $ 行：16 ÷ 2 = 8
最小比值为6，对应 $ s_1 $ 行，因此 $ s_1 $ 为出基变量。
步骤4：迭代更新表
用 $ x_2 $ 替换 $ s_1 $，并进行行变换：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS |
| $ x_2 $ | 2/3 | 1 | 1/3 | 0 | 6 |
| $ s_2 $ | 4 - 2(2/3) = 8/3 | 0 | -2/3 | 1 | 16 - 26 = 4 |
| $ Z $ | -3 + 5(2/3) = 1/3 | 0 | -5/3 | 0 | 30 |
步骤5：检查是否最优
当前目标行中所有非基变量系数均为正或零，说明已达到最优解。
四、最终结果
| 变量 | 值 |
| $ x_1 $ | 0 |
| $ x_2 $ | 6 |
| $ s_1 $ | 0 |
| $ s_2 $ | 4 |
| 最大利润 | 30 |
五、总结表格
| 步骤 | 进基变量 | 出基变量 | 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS | 目标函数值 |
| 初始 | - | - | $ s_1 $ | 2 | 3 | 1 | 0 | 18 | 0 |
| - | - | $ s_2 $ | 4 | 2 | 0 | 1 | 16 | ||
| 第一次迭代 | $ x_2 $ | $ s_1 $ | $ x_2 $ | 2/3 | 1 | 1/3 | 0 | 6 | 30 |
| - | - | $ s_2 $ | 8/3 | 0 | -2/3 | 1 | 4 | ||
| 最终 | - | - | $ x_2 $ | 2/3 | 1 | 1/3 | 0 | 6 | 30 |
| - | - | $ s_2 $ | 8/3 | 0 | -2/3 | 1 | 4 |
六、结论
通过单纯形法的逐步迭代，我们得出最优解为：生产6单位产品B，0单位产品A，最大利润为30元。此解满足所有约束条件，且在可行域内取得最大值。
