单纯形法求解线性规划问题例题

好的，以下是一个线性规划问题的例题和单纯形法的求解步骤：

假设有一家化工公司要生产两种产品 A 和 B。生产一个单位的 A 需要 1 个单位的原料 X 和 2 个单位的原料 Y；生产一个单位的 B 需要 2 个单位的原料 X 和 1 个单位的原料 Y。公司现在有 100 个单位的 X 和 80 个单位的 Y，而且 A 和 B 的销售利润分别是 5 和 4。问这家公司应该如何安排生产才能最大化利润？

我们可以用线性规划模型来描述这个问题：

目标函数：Maximize 5A + 4B

约束条件：

A + 2B <= 100 （原料 X 的限制）

2A + B <= 80 （原料 Y 的限制）

A, B >= 0 （非负性约束）

接下来，我们可以用单纯形法来求解这个问题。

首先，将约束条件转化为标准形式：

A + 2B + S1 = 100

2A + B + S2 = 80

A, B, S1, S2 >= 0

其中，S1 和 S2 是人造变量，它们的系数都为 1。

然后，构造初始单纯形表：

| 基变量 | 非基变量 | 系数 | 系数 | 系数 | 右端常数 |
|--------|----------|------|------|------|----------|
| S1 | A | 1 | 2 | 0 | 100 |
| S2 | B | 2 | 1 | 0 | 80 |
| Z | | -5 | -4 | 0 | 0 |

其中，Z 表示目标函数，基变量是 S1 和 S2，非基变量是 A 和 B。

接下来，我们要进行迭代，找到最优解。

第一步，选择进入变量。根据单纯形法的规则，我们需要选择目标函数系数最小的非基变量作为进入变量。在这个例子中，B 的系数最小，因此选择 B 作为进入变量。

第二步，选择离开变量。根据单纯形法的规则，我们需要选择进入变量系数为正的约束条件中，右端常数最小的那个约束条件对应的基变量作为离开变量。在这个例子中，第二个约束条件对应的基变量 S2 的右端常数最小，因此选择 S2 作为离开变量。

第三步，进行行变换。根据单纯形法的规则，我们需要将离开变量所在的行变换为新的基变量。具体来说，我们需要将 S2 所在的行除以 S2 的系数，并让 S2 的系数变为 1。其他行需要进行相应的调整，使得非基变量的系数都为 0。行变换后，新的单纯形表如下：

| 基变量 | 非基变量 | 系数 | 系数 | 系数 | 右端常数 |
|--------|----------|------|-------|------|----------|
| S1 | A | 4/5 | 3/5 | 0 | 60 |
| B | S2 | 2/5 | 1/5 | 0 | 40 |
| Z | | -2 | -11/5 | 0 | -160 |

第四步，检查最优性。如果目标函数系数都为负数，那么当前解就是最优解。否则，返回第一步继续迭代。

在这个例子中，目标函数系数不全为负数，因此需要继续迭代。重复上述步骤，选择 A 作为进入变量，S1 作为离开变量，进行行变换，得到新的单纯形表：

| 基变量 | 非基变量 | 系数 | 系数 | 系数 | 右端常数 |
|--------|----------|------|-------|------|----------|
| A | S1 | 5/4 | 1/4 | 0 | 25 |
| B | S2 | 1/4 | -1/4 | 0 | 15 |
| Z | | -9/4 | -7/4 | 0 | -125 |

此时，目标函数系数都为负数，因此当前解就是最优解。最优解是在 A = 25，B = 15 时取得的，此时目标函数值为 5*25 + 4*15 = 155，即这家公司应该生产 25 个单位的 A 和 15 个单位的 B，才能最大化利润。