线性规划的旋转算法求解示例
我将为您详细讲解线性规划中一个较为特殊的算法——旋转算法。这个算法与单纯形法有相似之处，但采用了不同的几何视角和操作方式。
1. 问题描述
考虑以下线性规划问题：
最大化： \(z = 3x_1 + 2x_2\)
约束条件：
- \(2x_1 + x_2 \leq 4\)
- \(x_1 + 2x_2 \leq 5\)
- \(x_1 \geq 0\)
- \(x_2 \geq 0\)
我们的目标是在满足所有约束条件的前提下，找到一组决策变量 \(x_1\) 和 \(x_2\) 的值，使得目标函数 \(z\) 的值达到最大。
2. 算法引入：什么是旋转算法？
旋转算法是求解线性规划问题的一种方法，它从一个可行解（通常是原点，如果原点可行的话）出发，通过一系列“旋转”操作，沿着可行域的边缘移动，逐步向最优解靠近。这里的“旋转”可以理解为从一个基可行解转换到相邻的基可行解的过程，这与单纯形法的“转轴”操作在思想上类似，但旋转算法更强调从几何角度看待约束边界。在本例中，我们将从一个特定的顶点开始，通过检查相邻顶点是否能使目标函数值增大，来决定“旋转”到哪个顶点。
3. 解题过程详解
步骤1：将问题转化为标准形式
为了应用旋转算法（以及大多数线性规划算法），我们首先需要引入松弛变量，将不等式约束转化为等式约束。松弛变量代表了未被使用的资源，其值也必须非负。
- 对于约束 \(2x_1 + x_2 \leq 4\)，我们引入松弛变量 \(s_1 \geq 0\)，得到： \(2x_1 + x_2 + s_1 = 4\)
- 对于约束 \(x_1 + 2x_2 \leq 5\)，我们引入松弛变量 \(s_2 \geq 0\)，得到： \(x_1 + 2x_2 + s_2 = 5\)
此时，原问题转化为如下标准形式：
最大化： \(z = 3x_1 + 2x_2 + 0 \cdot s_1 + 0 \cdot s_2\)
约束条件：
- \(2x_1 + x_2 + s_1 = 4\)
- \(x_1 + 2x_2 + s_2 = 5\)
- \(x_1, x_2, s_1, s_2 \geq 0\)
步骤2：选择初始基可行解
一个简单的起点是令决策变量 \(x_1 = 0\), \(x_2 = 0\)（即原点）。将其代入等式约束：
- \(s_1 = 4 - 2(0) - (0) = 4\)
- \(s_2 = 5 - (0) - 2(0) = 5\)
所有变量均非负，因此 \((x_1, x_2, s_1, s_2) = (0, 0, 4, 5)\) 是一个基可行解。在这个解中，取正值的变量 \(s_1, s_2\) 称为基变量，取零值的变量 \(x_1, x_2\) 称为非基变量。此时，目标函数值 \(z = 3(0) + 2(0) = 0\)。
步骤3：第一次旋转——确定进基变量
我们需要判断当前解是否最优。检查目标函数 \(z = 3x_1 + 2x_2\)。如果增加 \(x_1\) 或 \(x_2\) 的值，\(z\) 都会增大，因为它们的系数（3和2）都是正数。我们通常选择能使目标函数增长最快的变量进入基，即选择系数最大的变量。这里，\(x_1\) 的系数3大于 \(x_2\) 的系数2，所以我们选择 \(x_1\) 作为进基变量（即将从非基变量变为基变量）。
步骤4：第一次旋转——确定离基变量
现在我们要决定哪个基变量（\(s_1\) 或 \(s_2\)）要离开基（变为非基变量）。原则是：在增加 \(x_1\) 的同时，必须保证所有变量（包括当前的基变量）仍然非负。
我们从约束方程中看 \(x_1\) 能增大多少：
由约束1： \(2x_1 + s_1 = 4\) （因为 \(x_2=0\)），得 \(s_1 = 4 - 2x_1\)。为保证 \(s_1 \geq 0\)，需 \(x_1 \leq 4/2 = 2\)。
由约束2： \(x_1 + s_2 = 5\)，得 \(s_2 = 5 - x_1\)。为保证 \(s_2 \geq 0\)，需 \(x_1 \leq 5/1 = 5\)。
为了同时满足两个约束，\(x_1\) 的最大增加值取更严格的那个限制，即 \(x_1 \leq min(2, 5) = 2\)。这个最小值2是由约束1（即变量 \(s_1\)）决定的。因此，当 \(x_1\) 增加到2时，\(s_1\) 将首先减少到0。所以，我们选择 \(s_1\) 作为离基变量。
步骤5：第一次旋转——高斯消元得到新解
现在，我们进行“旋转”操作。我们要用进基变量 \(x_1\) 来替换离基变量 \(s_1\) 在基中的位置。这需要通过高斯消元法，将约束方程组改写成用新的非基变量（\(s_1\) 和 \(x_2\)）表示新的基变量（\(x_1\) 和 \(s_2\)）的形式。
当前方程组：
(1) \(2x_1 + x_2 + s_1 = 4\)
(2) \(x_1 + 2x_2 + s_2 = 5\)
- 将方程(1)除以2，使得 \(x_1\) 的系数变为1：
\(x_1 + \frac{1}{2}x_2 + \frac{1}{2}s_1 = 2\) ... (1') - 用方程(2)减去方程(1')，消去 \(x_1\)：
(2) - (1'): \((x_1 - x_1) + (2x_2 - \frac{1}{2}x_2) + (s_2 - 0) + (0 - \frac{1}{2}s_1) = 5 - 2\)
得到： \(\frac{3}{2}x_2 + s_2 - \frac{1}{2}s_1 = 3\) ... (2')
新的方程组为：
(1') \(x_1 + \frac{1}{2}x_2 + \frac{1}{2}s_1 = 2\)
(2') \(\frac{3}{2}x_2 + s_2 - \frac{1}{2}s_1 = 3\)
令新的非基变量 \(x_2 = 0\), \(s_1 = 0\)，代入方程：
由(1')得： \(x_1 = 2\)
由(2')得： \(s_2 = 3\)
于是，我们得到了新的基可行解： \((x_1, x_2, s_1, s_2) = (2, 0, 0, 3)\)。此时目标函数值 \(z = 3(2) + 2(0) = 6\)，比初始解（z=0）有了显著提高。
步骤6：第二次旋转——判断与进基选择
我们再次检查是否达到最优。我们需要将目标函数也用当前的非基变量（\(x_2\) 和 \(s_1\)）表示。
从方程(1')可得： \(x_1 = 2 - \frac{1}{2}x_2 - \frac{1}{2}s_1\)
将其代入目标函数 \(z = 3x_1 + 2x_2\)：
\(z = 3(2 - \frac{1}{2}x_2 - \frac{1}{2}s_1) + 2x_2\)
\(z = 6 - \frac{3}{2}x_2 - \frac{3}{2}s_1 + 2x_2\)
\(z = 6 + (-\frac{3}{2} + 2)x_2 - \frac{3}{2}s_1\)
\(z = 6 + \frac{1}{2}x_2 - \frac{3}{2}s_1\)
观察目标函数的表达式： \(z = 6 + \frac{1}{2}x_2 - \frac{3}{2}s_1\)。非基变量 \(x_2\) 的系数是 \(\frac{1}{2}\)（正数），这意味着如果增加 \(x_2\) 的值，目标函数 \(z\) 还能继续增大。因此，当前解 (2, 0, 0, 3) 不是最优解。我们选择系数为正的非基变量 \(x_2\) 作为进基变量。
步骤7：第二次旋转——确定离基变量
现在决定哪个基变量（\(x_1\) 或 \(s_2\)）要离开基。同样，我们要在增加 \(x_2\) 的同时，保持所有变量非负。
从新的约束方程看：
由(1')： \(x_1 = 2 - \frac{1}{2}x_2\) （因 \(s_1=0\)），为保证 \(x_1 \geq 0\)，需 \(x_2 \leq 2 / (1/2) = 4\)。
由(2')： \(s_2 = 3 - \frac{3}{2}x_2\) （因 \(s_1=0\)），为保证 \(s_2 \geq 0\)，需 \(x_2 \leq 3 / (3/2) = 2\)。
取更严格的限制： \(x_2 \leq min(4, 2) = 2\)。这个最小值2是由约束(2')（即变量 \(s_2\)）决定的。因此，当 \(x_2\) 增加到2时，\(s_2\) 将首先减少到0。所以，我们选择 \(s_2\) 作为离基变量。
步骤8：第二次旋转——高斯消元得到新解
现在我们进行第二次旋转操作，用 \(x_2\) 替换 \(s_2\) 在基中的位置。
当前方程组：
(1') \(x_1 + \frac{1}{2}x_2 + \frac{1}{2}s_1 = 2\)
(2') \(\frac{3}{2}x_2 + s_2 - \frac{1}{2}s_1 = 3\)
- 将方程(2')乘以 \(\frac{2}{3}\)，使得 \(x_2\) 的系数变为1：
\(x_2 + \frac{2}{3}s_2 - \frac{1}{3}s_1 = 2\) ... (2'') - 用方程(1')减去 \(\frac{1}{2}\) 倍的方程(2'')，消去 \(x_2\)：
(1') - \(\frac{1}{2}\)*(2''): \(x_1 + (\frac{1}{2}x_2 - \frac{1}{2}x_2) + (\frac{1}{2}s_1 - (-\frac{1}{2} * -\frac{1}{3})s_1?) + (0 - \frac{1}{2}*\frac{2}{3}s_2) = 2 - \frac{1}{2}*2\)
让我们仔细计算：
\(x_1 + \frac{1}{2}s_1 - (-\frac{1}{2} * -\frac{1}{3}s_1) - \frac{1}{3}s_2 = 2 - 1\)
\(x_1 + \frac{1}{2}s_1 - \frac{1}{6}s_1 - \frac{1}{3}s_2 = 1\)
\(x_1 + \frac{1}{3}s_1 - \frac{1}{3}s_2 = 1\) ... (1'')
新的方程组为：
(1'') \(x_1 + \frac{1}{3}s_1 - \frac{1}{3}s_2 = 1\)
(2'') \(x_2 + \frac{2}{3}s_2 - \frac{1}{3}s_1 = 2\)
令新的非基变量 \(s_1 = 0\), \(s_2 = 0\)，代入方程：
由(1'')得： \(x_1 = 1\)
由(2'')得： \(x_2 = 2\)
于是，我们得到了新的基可行解： \((x_1, x_2, s_1, s_2) = (1, 2, 0, 0)\)。此时目标函数值 \(z = 3(1) + 2(2) = 7\)。
步骤9：最优性检验
我们再次将目标函数用当前的非基变量（\(s_1\) 和 \(s_2\)）表示。
从(1'')和(2'')解出 \(x_1\) 和 \(x_2\) 代入 \(z\)：
\(z = 3x_1 + 2x_2 = 3(1 - \frac{1}{3}s_1 + \frac{1}{3}s_2) + 2(2 + \frac{1}{3}s_1 - \frac{2}{3}s_2)\)
\(z = 3 - s_1 + s_2 + 4 + \frac{2}{3}s_1 - \frac{4}{3}s_2\)
\(z = 7 + (-\frac{1}{3}s_1) + (-\frac{1}{3}s_2)\)
目标函数表达式为： \(z = 7 - \frac{1}{3}s_1 - \frac{1}{3}s_2\)。非基变量 \(s_1\) 和 \(s_2\) 的系数都是负数（\(-\frac{1}{3}\)）。这意味着任何非基变量取正值（\(s_1 > 0\) 或 \(s_2 > 0\)）都只会使目标函数值减小。因此，当前解已经是最优解，无法再改进。
4. 结论
通过两次旋转操作，我们找到了该线性规划问题的最优解：
\(x_1^* = 1\), \(x_2^* = 2\)
最大化的目标函数值为 \(z^* = 7\)。
这个求解过程清晰地展示了旋转算法的核心思想：从一个基可行解出发，通过选择能使目标函数改善的进基变量，并根据资源限制确定离基变量，然后通过高斯消元（旋转）得到相邻的、更优的基可行解，直至找不到能改善目标函数的进基变量（即达到最优解）为止。