线性规划的单纯形法退化现象与Bland规则防止循环示例
题目描述
单纯形法是求解线性规划问题的经典算法，但在迭代过程中可能出现“退化”现象，即基变量取值为0，导致目标函数值不改变。在退化严重的情况下，单纯形法可能陷入无限循环，永远找不到最优解。Bland规则（也称为最小下标规则）是一种简单有效的防止循环的枢轴规则。本题将通过一个具体的退化线性规划问题，演示单纯形法如何陷入循环，并展示如何使用Bland规则选择进基变量和出基变量来避免循环，从而保证算法在有限步内终止。
问题建模
考虑以下经典的退化线性规划示例（Beale, 1955），该问题已知会在某些枢轴规则下导致单纯形法循环：
最大化目标函数：
\[ z = \frac{3}{4}x_1 - 150x_2 + \frac{1}{50}x_3 - 6x_4 \]
约束条件：
\[\begin{aligned} \frac{1}{4}x_1 - 60x_2 - \frac{1}{25}x_3 + 9x_4 + x_5 &= 0 \\ \frac{1}{2}x_1 - 90x_2 - \frac{1}{50}x_3 + 3x_4 + x_6 &= 0 \\ x_3 + x_7 &= 1 \\ x_1, x_2, x_3, x_4, x_5, x_6, x_7 &\geq 0 \end{aligned} \]
其中，\(x_5, x_6, x_7\) 是松弛变量。初始基可行解为 \((x_5, x_6, x_7) = (0, 0, 1)\)，这是一个退化解（因为基变量 \(x_5=0, x_6=0\)）。
解题过程
我们将分两步进行：首先展示使用常见的“最大检验数规则”选择进基变量时单纯形法陷入循环的过程；然后应用Bland规则，演示如何避免循环并找到最优解。
第一步：使用最大检验数规则导致循环
- 初始单纯形表（已化为标准型，目标函数为最大化）：
基变量：\(x_5, x_6, x_7\)，非基变量：\(x_1, x_2, x_3, x_4\)。
将约束代入目标函数消去基变量，得到初始检验数（即非基变量在目标函数中的系数）：
\[\tilde{c} = \left( \frac{3}{4}, -150, \frac{1}{50}, -6, 0, 0, 0 \right) \]
对应单纯形表（略去具体表格，关注迭代逻辑）。
- 迭代过程（最大检验数规则）：
- 规则：选择检验数最大的非基变量进基（若有多个正检验数，通常选下标最小者，但这里为演示循环，采用最大正值规则，不限定下标）。
- 第1次迭代：检验数中最大正值为 \(3/4\)，对应 \(x_1\) 进基。用最小比值法则确定出基变量：计算右端项与进基变量在约束中正系数的比值。在第一个约束中，\(x_1\) 系数为 \(1/4\)，比值 \(0/(1/4)=0\)；第二个约束比值也为0。此时出现“平局”，即两个比值同时最小。若任意选择 \(x_5\) 出基，则得到新基 \((x_1, x_6, x_7)\)，但目标函数值 \(z=0\) 未改变（退化）。
- 后续迭代：按照类似方式继续选择进基变量（例如 \(x_3, x_2, x_4\) 等），并在出基变量选择遇到平局时任意决定。可以验证，经过6次迭代后，基变量又回到初始的 \((x_5, x_6, x_7)\)，但目标函数值始终为0，形成循环。
第二步：应用Bland规则避免循环
Bland规则：在选择进基变量时，在所有检验数大于0的非基变量中，选择下标最小的变量进基；在选择出基变量时，当最小比值出现平局（多个比值同时最小）时，选择下标最小的基变量出基。
-
重新从初始解开始迭代：
初始基变量：\(x_5, x_6, x_7\)，非基变量：\(x_1, x_2, x_3, x_4\)。
检验数：\(\tilde{c}_1=3/4>0, \tilde{c}_2=-150<0, \tilde{c}_3=1/50>0, \tilde{c}_4=-6<0\)。
根据Bland规则，选择下标最小的正检验数变量进基，即 \(x_1\)（下标为1）。 -
确定出基变量：
计算比值：
约束1：\(x_1\) 系数 \(1/4>0\)，比值 \(0/(1/4)=0\)。
约束2：\(x_1\) 系数 \(1/2>0\)，比值 \(0/(1/2)=0\)。
约束3：\(x_1\) 系数为0，不考虑。
最小比值均为0，出现平局。根据Bland规则，选择下标最小的基变量出基，即 \(x_5\)（下标为5）。
枢轴元：约束1中 \(x_1\) 的系数 \(1/4\)。 -
第一次旋转运算：
以 \(1/4\) 为枢轴元，将约束1化为 \(x_1\) 的表达式，代入其他约束和目标函数。得到新单纯形表：
基变量变为 \((x_1, x_6, x_7)\)，值仍为 \((0,0,1)\)，目标函数值 \(z=0\)（退化未改善）。
重新计算检验数（过程略）：
\[ \tilde{c}_2 = -150 + (3/4) \times (-60)/(1/4) = -150 + (3/4) \times (-240) = -150 - 180 = -330 < 0 \]
\[ \tilde{c}_3 = 1/50 + (3/4) \times (-1/25)/(1/4) = 1/50 + (3/4) \times (-4/25) = 1/50 - 3/25 = -1/10 < 0 \]
\[ \tilde{c}_4 = -6 + (3/4) \times 9/(1/4) = -6 + (3/4) \times 36 = -6 + 27 = 21 > 0 \]
\[ \tilde{c}_5 = 0 + (3/4) \times 1/(1/4) = 0 + 3 = 3 > 0 \]
检验数中正值为 \(\tilde{c}_4=21\) 和 \(\tilde{c}_5=3\)。根据Bland规则，选择下标最小的正检验数变量进基，即 \(x_4\)（下标为4）。
-
第二次迭代：
计算比值确定出基变量：
在基变量 \(x_1, x_6, x_7\) 对应的约束中，\(x_4\) 的系数分别为：约束1（来自 \(x_1\) 表达式）系数为 \(9/(1/4)=36\)？需准确计算。实际上，从第一次旋转后的约束方程直接看：
原约束1变为 \(x_1 = 240x_2 + (4/25)x_3 - 36x_4 - 4x_5\)（推导略）。
代入原约束2得：\(x_6 = -30x_2 + (3/50)x_3 + 15x_4 + 2x_5\)。
约束3不变：\(x_7 = 1 - x_3\)。
于是，对进基变量 \(x_4\)，在约束1中系数为-36（负，不考虑），约束2中系数为15（正），比值 \(0/15=0\)；约束3中系数为0。最小比值为0，对应基变量 \(x_6\)（下标为6）。根据Bland规则，选择 \(x_6\) 出基。
枢轴元为15。 -
第二次旋转运算：
以15为枢轴元旋转，得到新基 \((x_1, x_4, x_7)\)，值仍为 \((0,0,1)\)，目标函数值 \(z=0\)。
计算新检验数（过程略）：
\[ \tilde{c}_2 = -330 + 21 \times (-30)/15 = -330 - 42 = -372 < 0 \]
\[ \tilde{c}_3 = -1/10 + 21 \times (3/50)/15 = -1/10 + 21 \times (1/250) = -1/10 + 21/250 = -4/250 < 0 \]
\[ \tilde{c}_5 = 3 + 21 \times 2/15 = 3 + 2.8 = 5.8 > 0 \]
\[ \tilde{c}_6 = 0 + 21 \times (1/15) = 1.4 > 0 \]
正检验数变量：\(x_5\)（下标5）和 \(x_6\)（下标6）。选择下标最小的 \(x_5\) 进基。
-
第三次迭代：
计算比值：在基变量 \(x_1, x_4, x_7\) 的约束中，\(x_5\) 的系数：约束1中为-4（负），约束2中为 \(2/15>0\)，比值 \(0/(2/15)=0\)，约束3中为0。最小比值0，对应基变量 \(x_4\)（下标6）和 \(x_7\)（下标7）？注意：约束2对应基变量 \(x_4\)，比值0；约束3对应基变量 \(x_7\)，但 \(x_5\) 系数为0，比值无定义（不考虑）。因此只有 \(x_4\) 的比值有效，故 \(x_4\) 出基。
但此时出基变量是唯一的，无需Bland规则断点。旋转后得到新基 \((x_1, x_5, x_7)\)，值仍为 \((0,0,1)\)。 -
继续迭代：
按照Bland规则继续，经过几次迭代后，最终所有检验数均非正，达到最优解。在此问题中，最优解为 \(x_1=0, x_2=0, x_3=1, x_4=0, x_5=0, x_6=0, x_7=0\)，目标函数值 \(z=1/50=0.02\)。
Bland规则的关键在于：当出现多个候选进基或出基变量时，固定选择下标最小的变量，从而避免了循环路径，确保每次迭代后基变量集合的指标按字典序严格增加，因此在有限步内必然终止。
结论
Bland规则通过一种确定性的、基于下标顺序的选择方式，打破了单纯形法在退化顶点处可能出现的循环。虽然在实际应用中，Bland规则可能不如某些启发式规则（如最大检验数规则）高效，但它提供了单纯形法有限步终止的理论保证。对于退化严重的线性规划问题，采用Bland规则是安全且可靠的选择。