基于线性规划的退化问题处理示例
题目描述
考虑线性规划问题：
最大化 \(z = 3x_1 + 2x_2\)
满足约束：
- \(x_1 + x_2 \leq 4\)
- \(2x_1 + x_2 \leq 6\)
- \(x_1 + 2x_2 \leq 6\)
- \(x_1, x_2 \geq 0\)
该问题的可行域存在多个约束交于同一点的情况，可能导致单纯形法迭代中出现退化（基变量取值为0），从而可能引发循环。要求通过Bland规则避免循环，并完成求解。
解题过程
1. 标准化问题
引入松弛变量 \(x_3, x_4, x_5 \geq 0\)，将不等式转为等式：
\[\begin{aligned} x_1 + x_2 + x_3 &= 4 \\ 2x_1 + x_2 + x_4 &= 6 \\ x_1 + 2x_2 + x_5 &= 6 \\ z - 3x_1 - 2x_2 &= 0 \end{aligned} \]
初始基变量为 \(\{x_3, x_4, x_5\}\)，初始基本可行解： \((x_1, x_2, x_3, x_4, x_5) = (0, 0, 4, 6, 6)\)。
2. 识别退化风险
观察约束交点：
- 约束1与2的交点：解 \(x_1 = 2, x_2 = 2\) 代入约束3得 \(2 + 4 = 6\)，满足所有约束。
- 此时三个约束交于同一点 \((2,2)\)，意味着该点对应多个基（基变量可能包含零值），即退化现象。
3. 应用Bland规则避免循环
Bland规则要求：
- 进基变量选择：选择下标最小的非基变量中检验数为正者。
- 出基变量选择：若多个比值相同（最小比值退化），选择下标最小的基变量出基。
初始单纯形表（步骤0）
\[\begin{array}{c|ccccc|c} & x_1 & x_2 & x_3 & x_4 & x_5 & \text{RHS} \\ \hline x_3 & 1 & 1 & 1 & 0 & 0 & 4 \\ x_4 & 2 & 1 & 0 & 1 & 0 & 6 \\ x_5 & 1 & 2 & 0 & 0 & 1 & 6 \\ \hline z & -3 & -2 & 0 & 0 & 0 & 0 \\ \end{array} \]
检验数 \(\sigma_1 = -3, \sigma_2 = -2\) 均负？等等，这里需要检查：标准形中目标函数是 \(z - 3x_1 - 2x_2 = 0\)，所以检验数是 \(-3, -2\)，但单纯形法通常写作 \(z = 3x_1 + 2x_2 + 0\)，检验数应取负号吗？
修正：在单纯形表中，最后一行通常表示 \(z - c^T x = 0\)，所以系数为 \(-c_j\)。但常见教材展示时最后行直接写检验数 \(c_j - z_j\)（最大化问题）。我们按后一种惯例：
重制表格（最后行显示检验数 \(c_j - z_j\)）：
\[\begin{array}{c|ccccc|c} & x_1 & x_2 & x_3 & x_4 & x_5 & \text{RHS} \\ \hline x_3 & 1 & 1 & 1 & 0 & 0 & 4 \\ x_4 & 2 & 1 & 0 & 1 & 0 & 6 \\ x_5 & 1 & 2 & 0 & 0 & 1 & 6 \\ \hline z & 3 & 2 & 0 & 0 & 0 & 0 \\ \end{array} \]
但这是初始？不对，初始基变量 \(x_3, x_4, x_5\) 在基中，\(z\) 行应已消除基变量系数。
正确构造：
初始表（规范形）：
\[\begin{array}{c|ccccc|c} \text{基} & x_1 & x_2 & x_3 & x_4 & x_5 & \text{b} \\ \hline x_3 & 1 & 1 & 1 & 0 & 0 & 4 \\ x_4 & 2 & 1 & 0 & 1 & 0 & 6 \\ x_5 & 1 & 2 & 0 & 0 & 1 & 6 \\ \hline & -3 & -2 & 0 & 0 & 0 & 0 \\ \end{array} \]
最后行是 \(z\) 行系数（即 \(-c_j\) 格式，因为 \(z = 3x_1+2x_2\) 改写为 \(z - 3x_1 - 2x_2 = 0\)，所以此行是 \(0 - (3,2,0,0,0)\) 在基变量处已消元？其实初始时基变量系数已是0，因松弛变量在目标函数系数为0）。
我们按常见表格式：最后行写检验数 \(\sigma_j = c_j - z_j\)（最大化），初始时 \( z_j=0\)，所以 \(\sigma = (3,2,0,0,0)\)。但基变量检验数应为0，所以需要把基变量对应的检验数消为0。
实际上标准单纯形表：
\[\begin{array}{c|ccccc|c} \text{BV} & x_1 & x_2 & x_3 & x_4 & x_5 & \text{RHS} \\ \hline x_3 & 1 & 1 & 1 & 0 & 0 & 4 \\ x_4 & 2 & 1 & 0 & 1 & 0 & 6 \\ x_5 & 1 & 2 & 0 & 0 & 1 & 6 \\ \hline & -3 & -2 & 0 & 0 & 0 & 0 \\ \end{array} \]
此行是 \(z - 3x_1 - 2x_2 = 0\) 的系数，即负的检验数？不，检验数在最大化时是 \(c_j - z_j\)，初始 \( z_j=0\) 所以是 (3,2,0,0,0)，但表中常见是最后一行显示 \(- (c_j - z_j)\) 吗？有点混乱。
我们按标准：单纯形表最后一行是目标函数行 \(z = \cdots\)，但基变量系数须为0。所以初始：
\[z = 3x_1 + 2x_2 + 0x_3 + 0x_4 + 0x_5 \]
但 \(x_3, x_4, x_5\) 是基变量，要用非基变量表示：
从约束：
\(x_3 = 4 - x_1 - x_2\)
\(x_4 = 6 - 2x_1 - x_2\)
\(x_5 = 6 - x_1 - 2x_2\)
代入 \(z\)：
\(z = 3x_1 + 2x_2\)
所以最后一行系数： \(3, 2, 0,0,0\) 对应 \(x_1, x_2, x_3, x_4, x_5\)。但基变量检验数应为0，这里 \(x_3, x_4, x_5\) 的检验数已是0，OK。
所以初始表：
\[\begin{array}{c|ccccc|c} & x_1 & x_2 & x_3 & x_4 & x_5 & \text{RHS} \\ \hline x_3 & 1 & 1 & 1 & 0 & 0 & 4 \\ x_4 & 2 & 1 & 0 & 1 & 0 & 6 \\ x_5 & 1 & 2 & 0 & 0 & 1 & 6 \\ \hline z & 3 & 2 & 0 & 0 & 0 & 0 \\ \end{array} \]
检验数 \(\sigma_1=3>0, \sigma_2=2>0\)。按Bland规则，选下标最小的非基变量 \(x_1\) 进基。
4. 迭代1
比值检验：
\(x_3: 4/1 = 4\)
\(x_4: 6/2 = 3\)
\(x_5: 6/1 = 6\)
最小比值3，对应 \(x_4\) 出基。
主元行（第2行）除以2：
\(x_1 + 0.5x_2 + 0.5x_4 = 3\)
替换后其他行消元：
第1行减新第2行：
\(x_3: (1-1)x_1 + (1-0.5)x_2 + (1-0)x_3 + (0-0.5)x_4 = 4-3\)
得 \(0x_1 + 0.5x_2 + x_3 - 0.5x_4 = 1\)
第3行减新第2行：
\((1-1)x_1 + (2-0.5)x_2 + (0-0)x_3 + (0-0.5)x_4 + x_5 = 6-3\)
得 \(0x_1 + 1.5x_2 - 0.5x_4 + x_5 = 3\)
\(z\) 行：原 \(z = 3x_1 + 2x_2\)
用 \(x_1 = 3 - 0.5x_2 - 0.5x_4\) 代入：
\(z = 3(3 - 0.5x_2 - 0.5x_4) + 2x_2 = 9 - 1.5x_2 - 1.5x_4 + 2x_2 = 9 + 0.5x_2 - 1.5x_4\)
所以检验数： \(\sigma_2 = 0.5, \sigma_4 = -1.5\)，其余0。
新表：
\[\begin{array}{c|ccccc|c} \text{基} & x_1 & x_2 & x_3 & x_4 & x_5 & \text{b} \\ \hline x_3 & 0 & 0.5 & 1 & -0.5 & 0 & 1 \\ x_1 & 1 & 0.5 & 0 & 0.5 & 0 & 3 \\ x_5 & 0 & 1.5 & 0 & -0.5 & 1 & 3 \\ \hline z & 0 & 0.5 & 0 & -1.5 & 0 & 9 \\ \end{array} \]
检验数 \(\sigma_2 = 0.5 > 0\)，选 \(x_2\) 进基。
5. 迭代2（退化发生）
比值：
\(x_3: 1 / 0.5 = 2\)
\(x_1: 3 / 0.5 = 6\)
\(x_5: 3 / 1.5 = 2\)
最小比值2，出现平局（\(x_3\) 与 \(x_5\) 比值相同）。按Bland规则，选下标最小的基变量 \(x_3\) 出基。
主元行（第1行）乘2： \(x_2 + 2x_3 - x_4 = 2\)
替换：
第2行减0.5×新第1行：
\(x_1 + 0.5(x_2) - 0.5(x_2 + 2x_3 - x_4) = 3 - 0.5×2\)
\(x_1 + 0.5x_2 - 0.5x_2 - x_3 + 0.5x_4 = 2\)
得 \(x_1 - x_3 + 0.5x_4 = 2\)
第3行减1.5×新第1行：
\(1.5x_2 - 1.5(x_2 + 2x_3 - x_4) + x_5 = 3 - 1.5×2\)
\(1.5x_2 - 1.5x_2 - 3x_3 + 1.5x_4 + x_5 = 0\)
得 \(-3x_3 + 1.5x_4 + x_5 = 0\)
\(z\) 行：用 \(x_2 = 2 - 2x_3 + x_4\) 代入 \(z = 9 + 0.5x_2 - 1.5x_4\)
\(z = 9 + 0.5(2 - 2x_3 + x_4) - 1.5x_4 = 9 + 1 - x_3 + 0.5x_4 - 1.5x_4 = 10 - x_3 - x_4\)
新表：
\[\begin{array}{c|ccccc|c} \text{基} & x_1 & x_2 & x_3 & x_4 & x_5 & \text{b} \\ \hline x_2 & 0 & 1 & 2 & -1 & 0 & 2 \\ x_1 & 1 & 0 & -1 & 0.5 & 0 & 2 \\ x_5 & 0 & 0 & -3 & 1.5 & 1 & 0 \\ \hline z & 0 & 0 & -1 & -1 & 0 & 10 \\ \end{array} \]
注意 \(x_5 = 0\)（退化）。检验数 \(\sigma_3 = -1 < 0, \sigma_4 = -1 < 0\)，所有检验数非正，达到最优。
6. 结论
最优解 \(x_1 = 2, x_2 = 2, x_5 = 0\)，最大值 \(z = 3×2 + 2×2 = 10\)。
退化发生在顶点 \((2,2)\)，但Bland规则通过选择下标最小的出基变量避免了循环，顺利得到最优解。