基于线性规划的旋转算法求解示例
题目描述
旋转算法（Pivoting Algorithm）是单纯形法的一种几何直观解释，通过迭代调整基变量来逐步逼近线性规划问题的最优解。其核心思想是：在可行域的顶点间进行“旋转”移动，每次移动都沿着目标函数梯度方向改善解的值。本示例问题如下：
最大化
\[ z = 3x_1 + 2x_2 \]
约束条件
\[ x_1 + x_2 \leq 4 \]
\[ 2x_1 + x_2 \leq 5 \]
\[ x_1, x_2 \geq 0 \]
解题步骤
步骤1：标准化问题
引入松弛变量 \(s_1, s_2 \geq 0\)，将不等式转为等式：
\[\begin{aligned} x_1 + x_2 + s_1 &= 4 \\ 2x_1 + x_2 + s_2 &= 5 \\ z - 3x_1 - 2x_2 &= 0 \quad (\text{目标函数写成方程形式}) \end{aligned} \]
初始基变量为 \(s_1, s_2\)，非基变量为 \(x_1, x_2\)，初始解：\(x_1=0, x_2=0, s_1=4, s_2=5, z=0\)。
步骤2：选择进基变量
目标函数中系数最负的非基变量对应目标函数提升最快的方向。当前 \(z = 0 + 3x_1 + 2x_2\)，\(x_1\) 的系数 \(-3\) 最负（对 \(z\) 贡献最大），故选 \(x_1\) 进基。
步骤3：选择离基变量
计算当前约束下 \(x_1\) 的最大可行值：
- 从 \(s_1\) 约束：\(x_1 \leq 4/1 = 4\)
- 从 \(s_2\) 约束：\(x_1 \leq 5/2 = 2.5\)
取最小值 \(2.5\)，对应 \(s_2\) 约束最紧，因此 \(s_2\) 离基。
步骤4：旋转操作（更新方程组）
以 \(x_1\) 替换 \(s_2\) 作为基变量，通过高斯消元更新方程组：
- 将 \(s_2\) 约束（第二行）化为 \(x_1\) 的表达式：
\[ 2x_1 + x_2 + s_2 = 5 \implies x_1 = 2.5 - 0.5x_2 - 0.5s_2 \]
- 代入其他方程：
- \(s_1\) 约束：
\[ (2.5 - 0.5x_2 - 0.5s_2) + x_2 + s_1 = 4 \implies s_1 = 1.5 - 0.5x_2 + 0.5s_2 \]
- 目标函数：
\[ z - 3(2.5 - 0.5x_2 - 0.5s_2) - 2x_2 = 0 \implies z = 7.5 + 0.5x_2 - 1.5s_2 \]
新方程组：
\[\begin{aligned} s_1 &= 1.5 - 0.5x_2 + 0.5s_2 \\ x_1 &= 2.5 - 0.5x_2 - 0.5s_2 \\ z &= 7.5 + 0.5x_2 - 1.5s_2 \end{aligned} \]
当前解：\(x_1=2.5, x_2=0, s_1=1.5, s_2=0, z=7.5\)。
步骤5：迭代检查
目标函数中非基变量 \(x_2\) 的系数为 \(0.5 > 0\)，但 \(s_2\) 的系数为 \(-1.5 < 0\)，说明增加 \(s_2\) 可提升 \(z\)（因 \(s_2\) 当前为0，增加其值会减少 \(z\) 的负项）。但需注意：\(s_2\) 是松弛变量，增加它不会直接改善解，需检查其他非基变量。实际上，应仅考虑原始变量和松弛变量中系数为负的非基变量。这里 \(s_2\) 系数为负，但其增加受约束限制吗？
重读目标函数：\(z = 7.5 + 0.5x_2 - 1.5s_2\)。若增加 \(s_2\)，\(z\) 下降，故不应选 \(s_2\) 进基。但 \(x_2\) 系数为正，可选 \(x_2\) 进基。
步骤6：第二次旋转
- 进基变量：\(x_2\)（系数 \(0.5 > 0\)）。
- 离基变量：从约束中找 \(x_2\) 的极限值：
- \(s_1\) 约束：\(x_2 \leq 1.5 / 0.5 = 3\)
- \(x_1\) 约束：\(x_2 \leq 2.5 / 0.5 = 5\)
取最小值 \(3\)，对应 \(s_1\) 离基。
- 旋转更新：
- 从 \(s_1\) 约束得：\(x_2 = 3 - 2s_1 + s_2\)
- 代入 \(x_1\) 约束：
\[ x_1 = 2.5 - 0.5(3 - 2s_1 + s_2) - 0.5s_2 = 1 + s_1 - s_2 \]
- 代入目标函数：
\[ z = 7.5 + 0.5(3 - 2s_1 + s_2) - 1.5s_2 = 9 - s_1 - s_2 \]
新方程组：
\[\begin{aligned} x_2 &= 3 - 2s_1 + s_2 \\ x_1 &= 1 + s_1 - s_2 \\ z &= 9 - s_1 - s_2 \end{aligned} \]
当前解：\(x_1=1, x_2=3, s_1=0, s_2=0, z=9\)。
步骤7：终止条件
目标函数中所有非基变量 \(s_1, s_2\) 的系数均非正（均为 \(-1\)），说明当前解已最优，无法进一步改善。
结论
最优解为 \(x_1=1, x_2=3\)，最大值 \(z=9\)。旋转算法通过两次基变换（从 \((s_1,s_2)\) 到 \((x_1,s_2)\) 再到 \((x_1,x_2)\)）实现了最优顶点的移动。