【线性规划】两阶段法的特殊情形

【分析】

第一阶段最小化人工变量之和，若人工变量为非零基，则无解；

若人工变量为零基，且在第二阶段可以换出，选择换入变量时，可以选择系数为正数或负数的非人工变量；

若人工变量为零基，且在第二阶段不可换出，则退化（degeneracy），模型中存在多余约束，可以同时去掉该人工变量所在的行和列。

 

【例 1】

注：

1. 选择换入变量时，可以选择系数负数的非人工变量

2. 该算例的可行域为1个点

 

【例 2】

注：

1. 该算例为退化，有多余约束

2. 该算例的可行域为1个点，与例1类似

 

【参考文献】

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