两阶段法

---

线性规划问题中，当约束条件中加入人工变量后的另一种处理算法(计算效果同“大M法”)。

对引入了人工变量的线性规划问题，分两阶段求解。

第一阶段：先求解辅助线性规划问题，判断原线性规划问题是否存在基本可行解。

设原模型约束条件标准化后为：

其中x_n+1…X_n+m为引入的人工变量

则辅助规划问题为在上述约束下，求解目标函数为：

MinZ′=X_n+1+X_n+2+…+X_n+m的线性规划问题。

若求解得到Z′=0，表示原问题已得到一个基本可行解，可转入第二阶段运算。若求解得Z′＞0，表示原问题无可行解，应停止运算。

第二阶段：将第一阶段最终计算表中的目标函数系数行的数字，换成原问题的目标函数系数的数字(人工变量此时可去掉)。这就得到了求解原问题的初始计算表，再按正常方法求解。

例，对“大M法”中所举例题用“两阶段法”求解。

第一阶段：求解模型

求解出

X₁=0，

X₂=1，

X₃=1，

X₄=12，

X₅=0，

X₆=X₇=0，

Z′=0。

以上述最终表转入第二阶段计算：

最优解为：X₁^*=4，X₂^*=1，X₃^*=9，Z^*=－2