单纯形法例题详解

单纯形法是线性规划的一种有效求解算法，其基本思想是通过不断调整顶点来寻找最优解。本文将结合例题详解单纯形法的求解过程以及其优劣势。

首先，我们来看一个例题：

Maximize f(x) = 5x1 + 3x2

Subject to:

2x1 + x2 <= 100

x1 + x2 <= 80

x1 <= 40

x2 <= 60

x1, x2 >= 0

该问题可以通过单纯形法求解，其步骤如下：

Step 1：将原问题转化为标准形式

首先需要将目标函数转化为最小化问题，即：

Minimize f(x) = -5x1 - 3x2

然后添加松弛变量将约束条件转化为等式形式：

2x1 + x2 + s1 = 100

x1 + x2 + s2 = 80

x1 + s3 = 40

x2 + s4 = 60

Step 2：构造初始单纯形表

构造初始单纯形表需要引入人工变量，因为该问题中有不满足非负性约束的变量。具体步骤如下：

变量 x1 x2 s1 s2 s3 s4 b

初始基变量 s3 s4 0 0 x1 x2 0

2 1 1 0 0 0 100

1 1 0 1 0 0 80

1 0 0 0 1 0 40

0 1 0 0 0 1 60

Step 3：迭代求解

首先，需要检验初始单纯形表是否满足最优性和可行性条件。在本例中，由于人工变量 s3 和 s4 为基变量，因此需要进行人工变量法的初试操作。即，将人工变量s3和s4有关的列作为主列，其对应的最小值行作为主元素行。

变量 x1 x2 s1 s2 s3 s4 b

初始基变量 s3 s4 0 0 x1 x2 0

2 1 1 0 0 0 100

1 1 0 1 0 0 80

1 0 0 0 1 0 40

0 1 0 0 0 1 60

由于主元素行 b3 最小，因此选择 s3 作为要脱离基变量。接下来，需要找到入基变量，即在主列中找到系数为正的变量，并计算各行 ratio （即右端项/主元素），选择 ratio 最小的行作为入基变量。

变量 x1 x2 s1 s2 s3 s4 b

初始基变量 x1 s4 0 0 x3 x2 40

1 1/2 1 0 -1/2 0 60

0 1/2 0 1 1/2 0 40

0 1/2 0 0 -1/2 1 20

然后进行高斯行变换，得到新的单纯形表。

变量 x1 x2 s1 s2 s3 s4 b

初始基变量 x1 s4 0 0 x3 x2 40

0 1/2 1 0 1/2 -1 20

0 0 0 1 1 -1 20

1 1/2 0 0 -1/2 1/2 20

继续迭代，找到要退出基变量 s2 和要进入基变量 x2，更新单纯形表。

变量 x1 x2 s1 s2 s3 s4 b

初始基变量 x1 x2 0 0 x3 s4 60

0 1/2 1 0 1/2 -1 20

0 1/2 0 1 1/2 -1 20

1 1/2 0 0 -1/2 1/2 20

再次迭代，找到要退出基变量 x1 和要进入基变量 s1，更新单纯形表。

变量 x1 x2 s1 s2 s3 s4 b

初始基变量 s1 x2 2 0 1 -3/2 20

1/2 1/4 1/2 0 1/4 -1/4 10

1/2 3/4 1/2 1 1/4 -1/4 30

1/2 -1/4 -1/2 0 -1/4 3/4 10

由于单纯形表中没有正的c元素，因此该线性规划问题的最优解为 f(x) = 30，x1 = 0，x2 = 30，满足约束条件。

通过上述例题，我们可以深入了解单纯形法的求解步骤。同时，也需要注意单纯形法的优劣势：

优点：

1. 对于一般的大型问题，单纯形法具有较好的求解速度。

2. 单纯形法较为直观，求解过程易于理解。

3. 单纯形法适用范围较广，可以求解线性规划问题中的多种约束形式。

缺点：

1. 单纯形法是一种暴力算法，其时间复杂度可以达到指数级别。

2. 单纯形法在求解过程中可能会出现循环、退化等问题，需要注意额外处理。

3. 单纯形法不适用于求解特殊的线性规划问题，如整数线性规划、混合整数线性规划等。