【单纯形法步骤】在运筹学与线性规划领域，单纯形法是一种广泛应用的求解线性优化问题的方法。它由美国数学家乔治·丹齐格（George Dantzig）于1947年提出，至今仍是解决线性规划问题的核心算法之一。本文将详细介绍单纯形法的基本步骤，帮助读者更好地理解其原理与应用。
一、基本概念
单纯形法主要用于求解标准形式的线性规划问题，即：
最大化：
$$ \text{Max } Z = c_1x_1 + c_2x_2 + \cdots + c_nx_n $$
约束条件为：
$$ a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \leq b_1 $$
$$ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \leq b_2 $$
$$ \vdots $$
$$ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \leq b_m $$
$$ x_1, x_2, \ldots, x_n \geq 0 $$
二、单纯形法的步骤
步骤1：建立初始单纯形表
将线性规划问题转化为标准形式，并引入松弛变量或剩余变量，使所有不等式变为等式。然后构造初始单纯形表，其中包含目标函数系数、约束方程的系数以及常数项。
例如，对于以下问题：
$$
\begin{aligned}
\text{Max } & Z = 3x_1 + 5x_2 \\
\text{s.t. } & x_1 + 2x_2 \leq 4 \\
& 3x_1 + 2x_2 \leq 6 \\
& x_1, x_2 \geq 0
\end{aligned}
$$
引入松弛变量 $ s_1, s_2 $，得到：
$$
\begin{aligned}
x_1 + 2x_2 + s_1 &= 4 \\
3x_1 + 2x_2 + s_2 &= 6 \\
x_1, x_2, s_1, s_2 \geq 0
\end{aligned}
$$
此时，目标函数可以表示为：
$$
Z - 3x_1 - 5x_2 = 0
$$
构建初始单纯形表如下：
| 基变量 | $ x_1 $ | $ x_2 $ | $ s_1 $ | $ s_2 $ | RHS |
|--------|----------|----------|----------|----------|-----|
| $ s_1 $ | 1| 2| 1| 0| 4 |
| $ s_2 $ | 3| 2| 0| 1| 6 |
| $ Z $ | -3 | -5 | 0| 0| 0 |
步骤2：确定进入基变量
在当前的单纯形表中，检查目标行（Z行）的系数。如果存在正系数，则说明该变量可以增加以提高目标函数值。选择其中最大的正系数对应的变量作为进入基变量。
在上述例子中，$ x_2 $ 的系数为 -5，是负数，因此需要进一步分析。但若目标函数是最大化问题，通常会寻找非基变量中具有最大正系数的变量。这里可能需要调整符号，确保正确判断。
步骤3：确定离开基变量
使用最小比值规则来确定哪个基变量应该被替换出去。计算每个约束行中，当前基变量的系数除以该行中进入变量的系数（仅当系数为正时），取最小值对应的行作为离开基变量。
例如，在上述例子中，假设我们选择 $ x_2 $ 作为进入变量，那么计算：
- 对于第一行：$ 4 / 2 = 2 $
- 对于第二行：$ 6 / 2 = 3 $
因此，选择第一行中的 $ s_1 $ 作为离开变量。
步骤4：进行行变换
使用高斯消元法对单纯形表进行行变换，使得新的进入变量的系数在所选行中变为 1，其他行中该变量的系数变为 0。这样，就可以更新单纯形表，得到新的基变量和相应的系数。
步骤5：重复迭代
重复步骤2至步骤4，直到目标行中所有非基变量的系数均为非正（对于最大化问题）。此时，已达到最优解。
三、总结
单纯形法通过不断调整基变量，逐步逼近最优解。虽然在某些情况下可能存在退化或循环问题，但在实际应用中，大多数问题都能通过合理选择进入/离开变量顺利求解。
掌握单纯形法的步骤不仅有助于理解线性规划的求解过程，也为后续学习更复杂的优化方法打下坚实基础。希望本文能为你提供清晰的指导与参考。
