单纯形法步骤全面解析

单纯形法是一种求解线性规划问题的经典算法，由乔治·丹齐格于1947年提出。线性规划问题是在一组线性约束条件下，求解目标函数最优解的问题。单纯形法通过迭代的方式，在可行域的顶点上寻找目标函数的最优解。下面，我们就来详细解析单纯形法的各个步骤，用通俗易懂的语言带你走进这一算法的核心。

一、线性规划问题的标准形式

在介绍单纯形法之前，我们需要了解线性规划问题的标准形式。因为单纯形算法是通过线性规划的标准形来求解的。线性规划问题的标准形式通常表示为：

目标函数：最大化 z = c^T * x

约束条件：A * x ≤ b，x ≥ 0

其中，c是目标函数的系数向量，A是约束系数矩阵，b是约束的右端常数向量，x是非负决策变量向量。

为了使用单纯形法，我们需要将不等式约束转化为等式约束，这通常通过引入松弛变量来实现。例如，对于约束 A * x ≤ b，我们可以引入松弛变量 s ≥ 0，将其转化为 A * x + s = b。

二、单纯形法的核心思想

单纯形法的核心思想是通过设置不同的基向量，经过矩阵的线性变换，求得基可行解（可行域顶点），并判断该解是否最优。如果不是最优解，则继续设置另一组基向量，重复执行以上步骤，直到找到最优解。因此，单纯形法的求解过程是一个循环迭代的过程。

三、单纯形法的具体步骤

1. 引入松弛变量，构造初始单纯形表

首先，我们需要将不等式约束转化为等式约束，并构造初始单纯形表。初始单纯形表通常包括目标函数系数、约束系数、常数项以及基变量和非基变量的标识。

以线性规划问题“最大化 z = 3x1 + 5x2，约束条件为 x1 + 2x2 ≤ 8，2x1 + x2 ≤ 6，x1, x2 ≥ 0”为例。我们可以引入松弛变量 x3 和 x4，将约束转化为：

x1 + 2x2 + x3 = 8

2x1 + x2 + x4 = 6

然后，我们构造初始单纯形表如下：

| 变量 | c（目标函数系数） | x1 | x2 | x3 | x4 | 常数项b |

| | | | | | | |

| z | 3 5 0 0 | - - | - - | - - | - - | - |

| x1 | 0 0 1 0 | 1 2 | 0 0 | 1 0 | 0 0 | 8 |

| x2 | 0 0 0 1 | 0 1 | 2 1 | 0 1 | 0 0 | 6 |

注意，在初始单纯形表中，目标函数系数行的“-”表示该列对应的变量在当前基变量中未出现。

2. 选择入基变量和出基变量

接下来，我们需要选择入基变量和出基变量。入基变量是目标函数系数行中最负的系数对应的变量，因为增加该变量的值可以使得目标函数值增大（对于最大化问题）。出基变量则是通过最小比值法确定的，即选择使得基变量值最小的变量作为出基变量。

在上面的例子中，目标函数系数行中最负的系数是0（实际上，由于我们引入了松弛变量，初始时目标函数系数行中可能没有负数，这时可以选择检验数最小的列对应的变量作为入基变量），但我们可以假设为了说明问题而选择x1作为入基变量（在实际操作中，我们会通过迭代逐步找到最优的入基变量）。然后，我们使用最小比值法确定出基变量。对于约束x1 + 2x2 + x3 = 8，如果x1作为入基变量，那么出基变量应该是使得x1值最小的变量。通过计算可以发现，当x3=0时，x1=8/1=8；当x4=0时，x1=6/2=3。因此，我们选择x4对应的列作为出基列，即选择x4作为出基变量。

3. 更新单纯形表

确定了入基变量和出基变量后，我们需要更新单纯形表。这通常通过高斯消元法来实现，使得新的基变量对应的列成为单位列，而其他列中的元素通过线性变换变为0。同时，我们还需要更新目标函数系数行，以反映新的基变量对目标函数的影响。

在上面的例子中，我们选择x1作为入基变量，x4作为出基变量。然后，我们使用高斯消元法更新单纯形表如下：

| 变量 | c（目标函数系数） | x1 | x2 | x3 | x4 | 常数项b |

| | | | | | | |

| z | 3’ 5’ 0 0 | 1’ 0 | - - | - - | - - | 8’ |

| x1 | 0 0 1 0 | 1 0 | -2 -1 | 1 0 | 0 1 | 2 |

| x3 | 0 0 0 1’ | 0 1 | 1/2 1/2| 0 1 | -1 -1| 6-8=2 |

注意，这里的“’”表示该元素已经经过更新。更新后的单纯形表中，x1已经作为新的基变量出现，而x4已经被替换为x3。同时，目标函数系数行也已经更新，反映了新的基变量对目标函数的影响。

4. 判断最优性并迭代

最后，我们需要判断当前解是否最优。如果目标函数系数行中的所有系数都是非负的，则当前解为最优解。否则，我们需要继续选择入基变量和出基变量，并更新单纯形表，直到找到最优解为止。

在上面的例子中，我们可以看到更新后的单纯形表中目标函数系数行中仍然存在负数（即5’对应的列），因此当前解不是最优解。我们需要继续选择入基变量和出基变量，并更新单纯形表进行迭代。通过多次迭代后，我们可以找到最优解x1=2, x2=3, z=21。

四、总结

单纯形法是一种高效求解线性规划问题的算法。它通过迭代的方式在可行域的顶点上寻找最优解。在每次迭代中，我们需要选择入基变量和出基变量，并更新单纯形表。然后判断当前解是否最优，如果不是则继续迭代直到找到最优解为止。虽然单纯形法在最坏情况下可能遍历指数级的顶点数，但在实际应用中表现非常优异，特别是对于小规模线性规划问题具有非常高的效率。