【运筹学单纯形法例题一和详解】在运筹学中，单纯形法是一种用于求解线性规划问题的经典算法。本文将通过一个典型的例题，详细讲解如何运用单纯形法求解线性规划问题，并以加表格的形式展示整个过程。
一、题目描述
某工厂生产两种产品A和B，每单位产品A可获利5元，每单位产品B可获利4元。该工厂的资源限制如下：
- 资源1：最多可用20单位；
- 资源2：最多可用30单位；
- 资源3：最多可用15单位；
每个产品的资源消耗如下表所示：
| 资源/产品 | A（单位） | B（单位） |
| 资源1 | 2 | 3 |
| 资源2 | 3 | 2 |
| 资源3 | 1 | 1 |
要求：最大化利润。
二、建立数学模型
设生产A产品x₁单位，B产品x₂单位，则目标函数为：
$$
\text{Max } Z = 5x_1 + 4x_2
$$
约束条件为：
$$
\begin{cases}
2x_1 + 3x_2 \leq 20 \\
3x_1 + 2x_2 \leq 30 \\
x_1 + x_2 \leq 15 \\
x_1, x_2 \geq 0
\end{cases}
$$
为了使用单纯形法，我们引入松弛变量s₁、s₂、s₃，将不等式转化为等式：
$$
\begin{cases}
2x_1 + 3x_2 + s_1 = 20 \\
3x_1 + 2x_2 + s_2 = 30 \\
x_1 + x_2 + s_3 = 15 \\
x_1, x_2, s_1, s_2, s_3 \geq 0
\end{cases}
$$
目标函数变为：
$$
Z = 5x_1 + 4x_2 + 0s_1 + 0s_2 + 0s_3
$$
三、初始单纯形表
构造初始单纯形表如下：
| 基变量 | x₁ | x₂ | s₁ | s₂ | s₃ | RHS |
| s₁ | 2 | 3 | 1 | 0 | 0 | 20 |
| s₂ | 3 | 2 | 0 | 1 | 0 | 30 |
| s₃ | 1 | 1 | 0 | 0 | 1 | 15 |
| Z | -5 | -4 | 0 | 0 | 0 | 0 |
四、迭代步骤
第一步：确定进基变量
选择系数为负的列中绝对值最大的变量作为进基变量。这里，x₁的系数为-5，x₂为-4，因此选择x₁进基。
第二步：确定出基变量
计算各约束行中RHS与x₁系数的比值：
- s₁: 20 / 2 = 10
- s₂: 30 / 3 = 10
- s₃: 15 / 1 = 15
最小比值为10，对应两个行，任选其一（这里选s₁）作为出基变量。
第三步：进行行变换
将x₁替换s₁，进行行变换，得到新的单纯形表：
| 基变量 | x₁ | x₂ | s₁ | s₂ | s₃ | RHS |
| x₁ | 1 | 1.5 | 0.5 | 0 | 0 | 10 |
| s₂ | 0 | -2.5 | -1.5 | 1 | 0 | 0 |
| s₃ | 0 | -0.5 | -0.5 | 0 | 1 | 5 |
| Z | 0 | 3.5 | 2.5 | 0 | 0 | 50 |
五、继续迭代
当前Z行中仍有正系数，继续迭代。
进基变量：x₂（系数3.5）
出基变量：s₂（RHS=0，无法参与比值计算，故直接换出）
进行行变换，得到最终单纯形表：
| 基变量 | x₁ | x₂ | s₁ | s₂ | s₃ | RHS |
| x₁ | 1 | 0 | 0.2 | 0.6 | 0 | 8 |
| x₂ | 0 | 1 | 0.6 | -0.4 | 0 | 2 |
| s₃ | 0 | 0 | 0.2 | 0.2 | 1 | 4 |
| Z | 0 | 0 | 2.8 | 1.4 | 0 | 52 |
六、最终结果
此时所有非基变量的系数均为非正，说明已达到最优解。
- 最优解为：x₁ = 8，x₂ = 2
- 最大利润为：Z = 5×8 + 4×2 = 40 + 8 = 52元
七、总结与表格
| 步骤 | 进基变量 | 出基变量 | 基变量 | x₁ | x₂ | s₁ | s₂ | s₃ | RHS | Z值 |
| 初始 | - | - | s₁,s₂,s₃ | 2 | 3 | 1 | 0 | 0 | 20 | 0 |
| 1 | x₁ | s₁ | x₁,s₂,s₃ | 1 | 1.5 | 0.5 | 0 | 0 | 10 | 50 |
| 2 | x₂ | s₂ | x₁,x₂,s₃ | 1 | 0 | 0.2 | 0.6 | 0 | 8 | 52 |
八、结论
通过单纯形法的逐步迭代，我们成功求得了该线性规划问题的最优解。此方法不仅适用于本题，也可推广到更复杂的线性规划问题中。理解并掌握单纯形法的步骤和逻辑，是解决实际优化问题的重要基础。
