线性规划的两阶段法求解示例
题目描述：
考虑以下线性规划问题：
最大化：\(z = 3x_1 + 2x_2\)
约束条件：
- \(2x_1 + x_2 \geq 4\)
- \(3x_1 + 4x_2 \geq 6\)
- \(x_1 + x_2 \leq 3\)
- \(x_1 \geq 0, x_2 \geq 0\)
注意，这个问题包含“≥”和“≤”两种类型的不等式约束，并且目标函数是最大化。我们将使用两阶段法来求解。
解题过程：
第一阶段：引入人工变量，构建辅助问题。
-
将约束转化为标准形式。
对于“≥”约束，我们减去一个剩余变量（也称为松弛变量，但用于“≥”）。同时，为了获得一个初始基本可行解，我们需要引入人工变量。- 约束1：\(2x_1 + x_2 \geq 4\) 变为 \(2x_1 + x_2 - s_1 = 4\)（引入剩余变量 \(s_1 \geq 0\)）。为了在基变量中包含这个约束，我们添加人工变量 \(a_1 \geq 0\)，得到 \(2x_1 + x_2 - s_1 + a_1 = 4\)。
- 约束2：\(3x_1 + 4x_2 \geq 6\) 变为 \(3x_1 + 4x_2 - s_2 = 6\)（引入剩余变量 \(s_2 \geq 0\)）。添加人工变量 \(a_2 \geq 0\)，得到 \(3x_1 + 4x_2 - s_2 + a_2 = 6\)。
- 约束3：\(x_1 + x_2 \leq 3\) 变为 \(x_1 + x_2 + s_3 = 3\)（引入松弛变量 \(s_3 \geq 0\)）。这个约束不需要人工变量，因为松弛变量 \(s_3\) 可以直接作为基变量。
-
构建辅助问题（第一阶段问题）。
目标是最小化所有人工变量的和，即 \(w = a_1 + a_2\)。
约束条件为：
\(2x_1 + x_2 - s_1 + a_1 = 4\)
\(3x_1 + 4x_2 - s_2 + a_2 = 6\)
\(x_1 + x_2 + s_3 = 3\)
\(x_1, x_2, s_1, s_2, s_3, a_1, a_2 \geq 0\)为了使用单纯形法，我们需要用非基变量（初始时为 \(x_1, x_2, s_1, s_2\)）表示目标函数 \(w\)。
从约束方程可得：\(a_1 = 4 - 2x_1 - x_2 + s_1\), \(a_2 = 6 - 3x_1 - 4x_2 + s_2\)。
代入 \(w\)：\(w = a_1 + a_2 = (4 - 2x_1 - x_2 + s_1) + (6 - 3x_1 - 4x_2 + s_2) = 10 - 5x_1 - 5x_2 + s_1 + s_2\)。
所以，第一阶段问题表示为：最小化 \(w = 10 - 5x_1 - 5x_2 + s_1 + s_2\)，等价于最大化 \(-w = -10 + 5x_1 + 5x_2 - s_1 - s_2\)。我们使用单纯形法求解这个最大化问题。 -
构建第一阶段的初始单纯形表。
初始基变量是 \(a_1, a_2, s_3\)。
我们将目标函数行表示为 \(-w + 5x_1 + 5x_2 - s_1 - s_2 = -10\)。
| 基变量 | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | \(a_1\) | \(a_2\) | 右端项 |
|---|---|---|---|---|---|---|---|---|
| \(a_1\) | 2 | 1 | -1 | 0 | 0 | 1 | 0 | 4 |
| \(a_2\) | 3 | 4 | 0 | -1 | 0 | 0 | 1 | 6 |
| \(s_3\) | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 3 |
| \(-w\) | 5 | 5 | -1 | -1 | 0 | 0 | 0 | -10 |
- 进行第一阶段的单纯形迭代。
-
迭代1：选择检验数最大的正数对应的变量入基。\(x_1\) 和 \(x_2\) 的检验数都是5，任意选择，比如选 \(x_1\) 入基。
计算比率：\(a_1\) 行：4/2=2；\(a_2\) 行：6/3=2；\(s_3\) 行：3/1=3。最小正比率为2，有两个，任意选择，比如选 \(a_1\) 行作为主元行。主元是2。
进行行变换，使 \(x_1\) 列变为单位向量，主元行变为1，其他行该列元素变为0。- 将 \(a_1\) 行除以2：\([1, 0.5, -0.5, 0, 0, 0.5, 0, 2]\)
- 新的 \(a_2\) 行 = 旧 \(a_2\) 行 - 3 * 新 \(a_1\) 行：\([0, 2.5, 1.5, -1, 0, -1.5, 1, 0]\)
- 新的 \(s_3\) 行 = 旧 \(s_3\) 行 - 1 * 新 \(a_1\) 行：\([0, 0.5, 0.5, 0, 1, -0.5, 0, 1]\)
- 新的 \(-w\) 行 = 旧 \(-w\) 行 - 5 * 新 \(a_1\) 行：\([0, 2.5, 1.5, -1, 0, -2.5, 0, -20]\)
更新基变量：\(a_1\) 出基，\(x_1\) 入基。新的基变量是 \(x_1, a_2, s_3\)。
新的单纯形表：
-
| 基变量 | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | \(a_1\) | \(a_2\) | 右端项 |
|---|---|---|---|---|---|---|---|---|
| \(x_1\) | 1 | 0.5 | -0.5 | 0 | 0 | 0.5 | 0 | 2 |
| \(a_2\) | 0 | 2.5 | 1.5 | -1 | 0 | -1.5 | 1 | 0 |
| \(s_3\) | 0 | 0.5 | 0.5 | 0 | 1 | -0.5 | 0 | 1 |
| \(-w\) | 0 | 2.5 | 1.5 | -1 | 0 | -2.5 | 0 | -20 |
-
迭代2：检验数中仍有正数，\(x_2\) 的检验数为2.5，选择 \(x_2\) 入基。
计算比率：\(x_1\) 行：2/0.5=4；\(a_2\) 行：0/2.5=0（比率为0或负数通常不考虑，因为可能不满足可行性或代表无界）；\(s_3\) 行：1/0.5=2。最小正比率为2（来自 \(s_3\) 行）。主元是0.5。
进行行变换：- 将 \(s_3\) 行除以0.5：\([0, 1, 1, 0, 2, -1, 0, 2]\)
- 新的 \(x_1\) 行 = 旧 \(x_1\) 行 - 0.5 * 新 \(s_3\) 行：\([1, 0, -1, 0, -1, 1, 0, 1]\)
- 新的 \(a_2\) 行 = 旧 \(a_2\) 行 - 2.5 * 新 \(s_3\) 行：\([0, 0, -1, -1, -5, 1, 1, -5]\) （注意右端项变为负数，这可能会在后续导致问题，我们先继续）
- 新的 \(-w\) 行 = 旧 \(-w\) 行 - 2.5 * 新 \(s_3\) 行：\([0, 0, -1, -1, -5, 0, 0, -25]\)
更新基变量：\(s_3\) 出基，\(x_2\) 入基。新的基变量是 \(x_1, a_2, x_2\)。
新的单纯形表：
| 基变量 | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | \(a_1\) | \(a_2\) | 右端项 |
|---|---|---|---|---|---|---|---|---|
| \(x_1\) | 1 | 0 | -1 | 0 | -1 | 1 | 0 | 1 |
| \(a_2\) | 0 | 0 | -1 | -1 | -5 | 1 | 1 | -5 |
| \(x_2\) | 0 | 1 | 1 | 0 | 2 | -1 | 0 | 2 |
| \(-w\) | 0 | 0 | -1 | -1 | -5 | 0 | 0 | -25 |
现在，我们发现基变量 \(a_2\) 的值是-5，小于0，这违反了可行性条件。但是我们的目标是最小化 \(w\)（即最大化 \(-w\)）。观察 \(-w\) 行，所有非基变量（\(s_1, s_2, s_3, a_1\)）的检验数都是非正的（-1, -1, -5, 0），已经满足最优性条件（对于最大化问题，检验数≤0）。然而，基变量中含有取负值的人工变量 \(a_2\)，并且右端项为负，这意味着辅助问题的最优值 \(w = 25 > 0\)。根据两阶段法原理，如果第一阶段最终的最优值 \(w > 0\)，则原问题无可行解。
因此，我们得出结论：原线性规划问题无可行解。
总结：
在这个例子中，我们使用两阶段法求解一个线性规划问题。第一阶段的目标是判断原问题是否存在可行解。我们通过引入人工变量构建了一个辅助问题，并利用单纯形法求解。求解过程中，虽然单纯形表的检验数行满足了最优性条件，但基变量中的人工变量仍未完全被驱赶出基，且辅助目标函数的最优值大于零。这表明不存在一组变量能同时满足所有原始约束条件（包括非负约束），因此原问题无可行解。两阶段法的第一阶段有效地帮助我们识别了这种情况。