在运筹学中，单纯形法是一种非常重要的优化算法，主要用于解决线性规划问题。它通过迭代的方式逐步寻找最优解，最终达到目标函数的最大化或最小化。本文将通过一个具体的例子来详细讲解单纯形法的应用。
例题背景
假设我们有一个简单的线性规划问题：
最大化目标函数：
\[ Z = 3x_1 + 2x_2 \]
约束条件为：
\[ x_1 + x_2 \leq 4 \]
\[ 2x_1 + x_2 \leq 5 \]
\[ x_1, x_2 \geq 0 \]
单纯形法步骤
第一步：标准化问题
首先，我们需要将不等式约束转化为等式约束。为此，我们引入松弛变量 \( s_1 \) 和 \( s_2 \)，使得每个约束都成为等式：
\[ x_1 + x_2 + s_1 = 4 \]
\[ 2x_1 + x_2 + s_2 = 5 \]
目标函数保持不变：
\[ Z = 3x_1 + 2x_2 \]
第二步：建立初始单纯形表
我们将变量 \( x_1, x_2, s_1, s_2 \) 和 \( Z \) 的系数填入初始单纯形表中：
| 基变量 | \( x_1 \) | \( x_2 \) | \( s_1 \) | \( s_2 \) | 右侧常数 |
|--------|------------|------------|------------|------------|------------|
| \( s_1 \) | 1| 1| 1| 0| 4|
| \( s_2 \) | 2| 1| 0| 1| 5|
| \( Z \) | -3 | -2 | 0| 0| 0|
第三步：选择进入基变量
根据单纯形法的原则，我们选择目标函数中具有最大负系数的变量作为进入基变量。在这里，\( x_1 \) 的系数为 -3，是最大的负值，因此 \( x_1 \) 将进入基变量。
第四步：计算最小比值
为了确定哪一行的变量将离开基变量，我们需要计算每行的最小比值。最小比值的计算公式为：
\[ \text{最小比值} = \frac{\text{右侧常数}}{\text{对应列的正系数}} \]
对于 \( s_1 \) 行，比值为 \( \frac{4}{1} = 4 \)；
对于 \( s_2 \) 行，比值为 \( \frac{5}{2} = 2.5 \)。
因此，\( s_2 \) 将离开基变量。
第五步：更新单纯形表
接下来，我们进行高斯消元以更新单纯形表。具体操作如下：
1. 将 \( x_1 \) 替换为 \( s_2 \) 作为新的基变量。
2. 对 \( s_2 \) 行进行归一化处理，使其主元素（即 \( x_1 \) 列的系数）变为 1。
3. 对其他行进行消元，使 \( x_1 \) 列的其他元素变为 0。
经过计算后，更新后的单纯形表如下：
| 基变量 | \( x_1 \) | \( x_2 \) | \( s_1 \) | \( s_2 \) | 右侧常数 |
|--------|------------|------------|------------|------------|------------|
| \( x_1 \) | 1| 0.5| 0.5| 0.5| 2.5|
| \( s_1 \) | 0| 0.5| 0.5| -0.5 | 1.5|
| \( Z \) | 0| -0.5 | 1.5| 1.5| 7.5|
第六步：重复步骤
我们再次检查目标函数行，发现所有系数均为非负，说明当前解已经是最优解。
最优解
从更新后的单纯形表中，我们可以读取最优解：
\[ x_1 = 2.5, \quad x_2 = 1.5, \quad Z = 7.5 \]
结论
通过以上步骤，我们成功应用单纯形法解决了这个线性规划问题，并得到了最优解。单纯形法的核心在于不断调整基变量，通过迭代找到全局最优解。
希望这个例子能帮助大家更好地理解单纯形法的基本原理和应用方法。
