【线性规划】单纯形法的4种特殊情形

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

 

【分析】

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

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

原因：存在多余的约束

 

【例 1】常规案例

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

 

【例 2】暂时性循环

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

 

【例 3】死循环

注：

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

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

 

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

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

 

【特殊情形 3】*解（unbounded）

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

 

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

现象：

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

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

 

【参考文献】

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