线性规划单纯形法的几何解释与退化顶点处理

阶段一：理解单纯形法的几何本质

1. 将问题转化为几何模型

写出一个标准的线性规划问题形式：
目标为最大化或最小化一个线性函数，约束为一系列线性不等式。每个不等式在空间中对应一个半空间，所有半空间的交集形成一个凸多面体（可行域）。线性规划的目标就是在这个凸多面体上找到使目标函数值最优的点。

2. 记住一个核心定理

线性规划的最优解一定出现在凸多面体的顶点上（如果可行域有顶点且最优解存在）。因此，寻找最优解等价于在顶点中搜索。

3. 理解单纯形法的行走方式

单纯形法从某个顶点出发，沿着一条边移动到另一个顶点，每次移动都使目标函数值得到改善（最大化时增加，最小化时减少）。这里的“边”对应约束中一个非基变量从 0 变为正数，同时强制一个基变量降为 0（即转轴操作）。几何上，就是从一个顶点沿棱走到相邻顶点。

4. 想象一个二维例子

假设可行域是一个多边形，顶点按顺序排列。单纯形法从任意一个顶点开始，检查每条边，如果走某条边能提高目标值，就沿着那条边走到下一个顶点。重复直到到达一个顶点，其所有相邻顶点都无法再改善目标值，此时该点就是最优解。

阶段二：认识退化顶点

1. 退化现象的定义

在非退化情况下，每个顶点恰好由 n 个线性无关的约束取等号确定（n 是变量个数），并且有 n 个基变量都大于 0。退化发生时，某个顶点由多于 n 个约束取等号，导致至少一个基变量值为 0。几何上，退化顶点是多个多面体面的交点，使得从该顶点出发的边少于预期。

2. 退化带来的问题

当迭代到退化顶点时，转轴操作可能不改变顶点本身（只改变基变量集合，但几何位置相同）。目标函数值保持不变，继续沿边移动可能又回到同一个顶点，导致循环（cycling）——永远无法到达最优解。

3. 用一个简单例子说明

考虑二维平面，可行域是一个三角形，但其一个顶点恰好是三条线的交点（三条线交于一点，而正常情况只需两条线）。假设从该顶点出发，按普通规则选择进基变量，可能发生：转轴后仍停留在同一个点（因为基变量值为0），目标值不变，然后下次又选择另一个进基变量，转轴后仍不动，形成无限循环。

阶段三：掌握退化顶点的处理方法

1. 检测退化

在每一步单纯形表中，检查基变量的值。如果有一个或多个基变量值为 0，则当前顶点是退化的。记录哪些基变量取0，并进入特殊处理流程。

2. 应用Bland最小索引规则（避免循环）

Bland规则是处理退化最经典的算法之一，确保迭代能够在有限步内终止。规则如下：

• 进基变量选择：在所有能使目标改善的非基变量中，选择下标最小的那个。
• 出基变量选择：在所有可能被驱出的基变量中，选择下标最小的那个（即使多个基变量同时达到最小值，也选下标最小的）。

步骤分解：
在每次迭代中，找到所有检验数大于0（最大化问题）的非基变量，记下标集合。选取其中下标最小的作为进基变量。然后计算所有正约束的比值，找到使比值最小的基变量集合，选取其中下标最小的作为出基变量。执行转轴。

3. 理解为什么Bland规则有效

Bland规则破坏了循环的对称性。它强制进基和出基时优先选择索引小的变量，这相当于在退化顶点附近设定了一个字典序偏序，保证每次迭代后基变量的总字典序严格递增（或递减），从而不可能无限循环。

4. 另一种实用方法：扰动法

在实际求解器中，常用随机扰动（Perturbation）来解决退化。对约束右端项b添加极小的随机数，使得所有顶点变成非退化。求解后再恢复原值。这种方法实现简单，但在严格理论分析上不如Bland规则严谨。

5. 编写伪代码（理解逻辑）

输入：初始基 B，初始解 x
while 存在非基变量检验数大于0:
    for 每个非基变量 j:
        if 检验数 σ_j > 0:
            记录候选集合
    选择候选集合中下标最小的 j* 作为进基变量
    for 每个基变量 i:
        计算比值 θ = x_B_i / a_i_j*  (a_i_j* > 0)
    选择使 θ 最小的基变量集合中下标最小的 i* 作为出基变量
    执行转轴操作，更新 B 和 x
输出：最优解 x

阶段四：通过一个数值示例巩固（3个变量，2个约束）

1. 列出问题

最大化 z = 3x1 + 2x2 + x3
满足约束：
x1 + x2 + x3 ≤ 10
2x1 + x2 - x3 ≤ 5
x1, x2, x3 ≥ 0

2. 引入松弛变量转为标准形

x4 和 x5 为松弛变量。初始基：x4, x5，基变量值：x4=10, x5=5，非基变量 x1, x2, x3 均为0。此顶点非退化（基变量均>0）。

3. 正常迭代（略）

假设第一次迭代后到达一个退化顶点。例如，某步后基变量为 x1, x2, x3 且 x2=0。此时当前解为顶点（例如 x1=2, x2=0, x3=8，松弛变量为0），该点由三条约束（x2=0, x4=0, x5=0）交于一点，是退化顶点。

4. 应用Bland规则

假设检验数：σ_x4 = 1, σ_x5 = 2（进基候选）。选择下标最小的 x4 进基。计算比值：对于 x4 列，正系数对应基变量 x1, x2, x3，假设比值分别为 θ1=3, θ2=0(因x2=0), θ3=2。选择使比值最小的基变量集合：x2（比值为0）和 x3（比值为2），选下标最小的 x2 出基。执行转轴后，新基为 x1, x4, x3，解仍为同一顶点（因 x2=0 被替换，但几何点不变）。但由于选择了最小下标，下一步会继续移动，避免循环。

5. 验证

重复上述规则，最终会跳出退化区域，进入非退化边，朝最优解移动。

阶段五：总结关键操作要点

• 开始迭代前，确认当前顶点是否退化（基变量是否为0）。若退化，准备使用Bland规则。
• 每一步，按照最小下标选择进基和出基变量，而非按照常规的“改善最大”或“最小比值”。
• 如果手动计算时遇到目标值不变且基未变（循环），立即切换到Bland规则。
• 对于软件实现，Bland规则几乎零开销，建议默认开启以防止退化导致的无限循环。