线性规划的旋转算法求解示例
题目描述：
考虑以下线性规划问题：
\[\begin{aligned} \text{最大化} \quad & z = 3x_1 + 2x_2 \\ \text{约束条件} \quad & x_1 + x_2 \leq 4 \\ & 2x_1 + x_2 \leq 5 \\ & x_1, x_2 \geq 0 \end{aligned} \]
要求使用旋转算法（即单纯形法的核心操作）求解该问题，并通过逐步旋转枢轴（pivot）找到最优解。
解题过程
步骤1：转化为标准型
线性规划的标准型要求约束条件为等式，且所有变量非负。引入松弛变量 \(x_3, x_4 \geq 0\)：
\[\begin{aligned} x_1 + x_2 + x_3 &= 4 \\ 2x_1 + x_2 + x_4 &= 5 \\ z - 3x_1 - 2x_2 &= 0 \end{aligned} \]
步骤2：构造初始单纯形表
将方程组写成表格形式，基变量为 \(x_3, x_4\)，非基变量为 \(x_1, x_2\)：
| 基变量 | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | 右端项 |
|---|---|---|---|---|---|
| \(x_3\) | 1 | 1 | 1 | 0 | 4 |
| \(x_4\) | 2 | 1 | 0 | 1 | 5 |
| \(z\) | -3 | -2 | 0 | 0 | 0 |
最后一行称为目标函数行，其中负值表示目标函数可进一步优化。
步骤3：选择枢轴列（进基变量）
目标函数行中，\(x_1\) 的系数为 \(-3\)（绝对值最大），因此选择 \(x_1\) 作为进基变量。
步骤4：选择枢轴行（出基变量）
计算右端项与枢轴列正系数的比值，选择最小比值对应的行：
- \(x_3\) 行：\(4 / 1 = 4\)
- \(x_4\) 行：\(5 / 2 = 2.5\)
最小比值为 \(2.5\)，对应 \(x_4\) 行，因此 \(x_4\) 为出基变量。
枢轴元素为第2行第1列的 \(2\)（标为圆圈）。
步骤5：执行旋转操作
目标：使枢轴列变为单位向量，枢轴元素变为1，其他元素变为0。
-
将枢轴行除以2：
\(x_4\) 行变为：\([1, 0.5, 0, 0.5, 2.5]\)，基变量改为 \(x_1\)。 -
更新其他行：
- \(x_3\) 行：减去新 \(x_1\) 行的1倍：
\((1-1, 1-0.5, 1-0, 0-0.5, 4-2.5) = [0, 0.5, 1, -0.5, 1.5]\) - \(z\) 行：加上新 \(x_1\) 行的3倍：
\((-3+3, -2+1.5, 0+0, 0+1.5, 0+7.5) = [0, -0.5, 0, 1.5, 7.5]\)
- \(x_3\) 行：减去新 \(x_1\) 行的1倍：
更新后的单纯形表：
| 基变量 | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | 右端项 |
|---|---|---|---|---|---|
| \(x_3\) | 0 | 0.5 | 1 | -0.5 | 1.5 |
| \(x_1\) | 1 | 0.5 | 0 | 0.5 | 2.5 |
| \(z\) | 0 | -0.5 | 0 | 1.5 | 7.5 |
步骤6：再次选择枢轴列
目标函数行中，\(x_2\) 的系数为 \(-0.5\)（仍为负），因此选择 \(x_2\) 进基。
步骤7：选择枢轴行
计算比值：
- \(x_3\) 行：\(1.5 / 0.5 = 3\)
- \(x_1\) 行：\(2.5 / 0.5 = 5\)
最小比值为 \(3\)，对应 \(x_3\) 行，出基变量为 \(x_3\)。
枢轴元素为第1行第2列的 \(0.5\)。
步骤8：执行第二次旋转
-
将枢轴行除以0.5：
\(x_3\) 行变为：\([0, 1, 2, -1, 3]\)，基变量改为 \(x_2\)。 -
更新其他行：
- \(x_1\) 行：减去新 \(x_2\) 行的0.5倍：
\((1-0, 0.5-0.5, 0-1, 0.5+0.5, 2.5-1.5) = [1, 0, -1, 1, 1]\) - \(z\) 行：加上新 \(x_2\) 行的0.5倍：
\((0, -0.5+0.5, 0+1, 1.5-0.5, 7.5+1.5) = [0, 0, 1, 1, 9]\)
- \(x_1\) 行：减去新 \(x_2\) 行的0.5倍：
最终单纯形表：
| 基变量 | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | 右端项 |
|---|---|---|---|---|---|
| \(x_2\) | 0 | 1 | 2 | -1 | 3 |
| \(x_1\) | 1 | 0 | -1 | 1 | 1 |
| \(z\) | 0 | 0 | 1 | 1 | 9 |
步骤9：解读结果
目标函数行系数均为非负，达到最优解：
- \(x_1 = 1, x_2 = 3\)
- 最优值 \(z = 9\)
验证约束：
- \(1 + 3 = 4 \leq 4\)
- \(2 \times 1 + 3 = 5 \leq 5\)
符合要求。
总结：旋转算法通过两次枢轴操作，将初始可行解逐步优化至最优解，体现了单纯形法的核心思想。