两阶段单纯形法的优化方案

两阶段单纯形法(以下简称两阶段法)是处理人工变量的另一种方法,是将加入人工变量后的线性规划问题划分成两个阶段进行求解。

第一阶段:加入人工变量后构造辅助的线性规划问题。目标函数求最小值,人工变量系数均为－1,原变量系数均为0。若min W′＝0,则得到原问题的初始基可行解,可进入第二阶段。若min W′≠0,则表明原问题不可行。

第二阶段:首先在第一阶段最终单纯形表中将目标函数换成原问题目标函数,同时划去人工变量所在列,然后用单纯形法计算,直至求出最优解。

【例1-20】用两阶段法求解下面线性规划问题:

解:

①引进松弛变量x4,将原问题化为标准形式:

单纯形法求解过程如表1-27所示。

表1-27

结果表明,x5＝0,min W′＝0,X＝(0,0,0,15,10)T可作为原问题的初始基可行解进入第二阶段计算,过程如表1-28所示,求解结果为唯一最优解:X∗＝(2,0,0,25,0)T,Z∗＝20。

表1-28

【例1-21】用两阶段法求解下面线性规划问题:

(www.xing528.com)

解:

①引进松弛变量x3,x4和x5,将原问题化为标准形式:

系数矩阵:

加入人工变量x6,系数矩阵变为:

②第一阶段。

加入变量x5,构造新的目标函数,模型变为:

标准化:

单纯形法求解过程如表1-29所示,因为x6大于零,目标函数不为零,所以该问题不可行。

表1-29