哈工大考研管理运筹学大M法和两阶段法

原模型：

max zCXAXbs.t.X0

0000其中X0(x10,x2,...,xm,xm1,....,xn)

人工模型：

max zCXLMXaAXIXabs..tX0

其中L(1,1,...,1), Xa为人工向量且Xaxa1,xa2,...,xam，M是一个很大的数.

m

下面证明：

定理1 如果人工模型的最优目标值为，那么就可判定原模型无解。 证明 用反证法证明。

0000设原问题有可行解，那么也存在基本可行解，设为X0(x10,x2,...,xm,xm1,....,xn)，那么

必有CX0。

0000显然X1(x10,x2,...,xm,xm1,....,xn,0,...,0)也是人工模型的一个基本可行解，那么有

m个CX1CX0

也就是CX1，这与人工模型的最优目标值为矛盾，从而原问题无解。

*******定理2 如果X*(x1那,x2,...,x*m,xm1,....,xn,xa1,xa2,...,xam)是人工模型的最优基可行解，*****么原模型的最优解为X#(x1,x2,...,xm,xm1,....,xn)。

********证明 设X*(x1,x2,...,xm,xm1,....,xn,xa1,xa2,...,xam)是人工模型的最优基可行解，那么

所有的非基变量的值都为0，否则人工模型的最优目标值将为。

*****,x2,...,xm,xm显最优基可行解然X#(x11,....,xn)也是原模型的一个基可行解。下面证明

X#也是原模型的最优基可行解。

P)是原模型的最优基可行如果X#不是原模型的最优基可行解，那么设Xp(x1p,x2p,...,xnP解，那么必有CXpCX#。这样一来，Xp1(x1p,x2p,...,xn,0,...,0)将是人工模型的一个基可

m个行解，这意味着Xp1是一个比X*还优的基可行解，这与X*是人工模型的最优基可行解矛盾，因而X#是原模型的最优基可行解。

两阶段法

原模型：

max zCXAXbs.t.X0

0000其中X0(x10,x2,...,xm,xm1,....,xn)

人工模型：

min zLXaAXIXab s..tX0,Xa0其中L(1,1,...,1), Xa为人工向量且Xaxa1,xa2,...,xam，M是一个很大的数.

m下面证明：

定理1 如果人工模型的最优目标值不为0，那么就可判定原模型无解。

证明 用反证法证明。只需证明原模型存在基可行解时，人工模型的最优目标函数值一定为0。

0000设原问题有可行解，那么也存在基本可行解，设为X0(x10,x2,...,xm,xm1,....,xn)。

0000显然X1(x10,x2,...,xm,xm1,....,xn,0,...,0)也是人工模型的一个基本可行解，那么人工模

m个型的目标函数值将为0。

由于Xa0，因而人工模型的最优目标函数值大于等于0。根据上述，X1将是人工模型的最优基可行解，相应的最优目标函数值为0。这说明如果原模型存在基可行解，那么人工模型的目标函数值一定为0，这与人工模型的最优目标值不为0矛盾，命题成立。

定理2 如果人工模型的最优基可行解中所有人工变量都为非基变量，且设这个最优基

********#*****可行解为X*(x1,x2,...,xm,xm1,....,xn,xa1,xa2,...,xam)，那么X(x1,x2,...,xm,xm1,....,xn)将是

原模型的一个基可行解。

***证明 由于人工变量xa1,xa2,...,xam为非基变量，那么xa1,xa2,...,xam的值均为0。 ********,x2,...,xm,xm又由于X*(x1那么X#1,....,xn,xa1,xa2,...,xam)是人工模型的最优基可行解，

无疑也是原模型的一个基可行解，命题得证。