(21)--2.5.2两阶段法运筹学运筹学.pdf

两阶段法

对于线性规划问题

maxzcxcxcx

1122nn

axaxaxb

1111221nn1



axaxaxb

2112222nn2



s.t.



axaxaxb

m11m22mnnm

x~x0,x~x0

1nn1nm



两阶段法就是把增加人工变量后的线性规划模型分成两

个阶段求解。

第一阶段：

求原线性规划问题的一个基可行解，构造辅助线性规划问题。

minwxxx

n1n2nm

axaxaxxb

1111221nnn11

人

axaxaxxb

2112222nnn22工



s.t.变



axaxaxxb量

m11m22mnnnmm

x~x0,x~x0

1nn1nm



单纯形法求解，若在最终表中有

m

**

minwxni0

i1

则说明原问题无可行解，否则转入第二阶段。

第二阶段：

从第一阶段的最终单纯形表出发，去掉人工变量，并按照

原来的目标函数，继续寻找问题的最优解，此时目标函数为

maxzcxcxcx

1122nn

例用两阶段法解下列线性规划

maxz-3xx