单纯形法的四种特殊情形

【特殊情形 1】退化（degeneracy）

【分析】

现象：迭代过程中出现基变量为 0

影响：迭代过程出现循环（暂时性循环、死循环）

原因：存在多余的约束

【例 1】常规案例

$\large max \ z = 3 x_{1} + 9 x_{2}$

$\large s.t.$

$\large x_{1} + 4 x_{2} \leq 8$

$\large x_{1} + 2 x_{2} \leq 4$

$\large x_{1}, x_{2} \geq 0$

注：第 1 个约束为多余约束

【例 2】暂时性循环

$\large max \ z = 3 x_{1} + 2 x_{2}$

$\large s.t.$

$\large 4 x_{1} - x_{2} \leq 8$

$\large 4 x_{1} + 3 x_{2} \leq 12$

$\large 4 x_{1} + x_{2} \leq 8$

$\large x_{1}, x_{2} \geq 0$

注：第 1 个约束为多余约束

【例 3】死循环

$\large max \ z = \frac{3}{4} x_{1} - 20 x_{2} + \frac{1}{2} x_{3} - 6 x_{4}$

$\large s.t.$

$\large \frac{1}{4} x_{1} - 8 x_{2} - x_{3} + 9 x_{4} \leq 0$

$\large \frac{1}{2} x_{1} - 12 x_{2} - \frac{1}{2} x_{3} + 3 x_{4} \leq 0$

$\large x_{3} \leq 1$

$\large x_{1}, x_{2}, x_{3}, x_{4} \geq 0$

注：

1. 该算例的迭代过程中，存在一个长度为 6 的循环；

2. 有趣的是，如果将所有系数同时乘一个合适的常数，转化为整数，则可避免循环的出现。

【特殊情形 2】无穷多个最优解（alternative optima）

现象：存在非基变量的检验数为 0，可作为换入变量入基。

【特殊情形 3】无界解（unbounded）

现象：单纯形表中，换入变量下方的所有系数均非正，即找不到换出变量，这意味着新的换入变量可以无约束地增加。

【特殊情形 4】无可行解（infeasible）

现象：

1. 所有约束均为 $\large \leq$ 的模型，不会出现这种情况，因为至少原点处是可行的；

2. 对于有人工变量的模型，若两阶段法的第一阶段结果中，人工变量存在非零解，则模型无解。

【参考文献】

Hamdy A. Taha. Operations Research an Introduction 初级篇 Chapter 3