§6对偶单纯形法
在介绍对偶单纯形法之前,让我们先利用对偶理论来重温一下单纯形法的基本思想,以便给单纯形法一种新的解释。
考虑线性规划(LP)和其对偶规划(DP):
mi
cTx
maxwTb
Axb
LP
st
x0
我们已经知道,(LP)的单纯形表为
DPstwTAcT
基变量x1x2┄x
xB
B1A
B1b
f
cBTB1AcT
cBTB1b
定理1设LP的任一基本解为x0,它对应于基B,并作w0TcBTB1。若x0和w0分别是LP和(DP)的可行解,则x0和w0也分别是LP和(DP)的最优解。
证明因w0是(DP)的可行解,即w0TA≤cT
从而有
cBTB1AcT≤0
此式说明,x0是对应于基B的基本可行解,且所有的检验数
λj≤0故x0是(LP)的最优解。此外,还有
w0TbcBTB1bcBTxB0cx0从而由线性规划的对偶定理知,w0也是(DP)的最优解。
证毕。
由以上证明过程可看到:
x0((LP)的任一基本解)的检验数全部非正与w0TcBTB1是对偶问题(DP)的可行解等价。
据此我们可对单纯形法作如下解释:
从一个基本解x0出发迭代到另一个基本解,在迭代过程中始终保持解的可行性(基本可行解),同时使它所对应的对偶规划的解w0(满足(w0)TcBTB1)的不可行性逐步消失(即检验数逐步变为非正);直到w0是(DP)的可行解,x0就是(LP)的最优解。
因(LP)和(DP)互为对偶问题,故基于对称的想法,我们也可以把迭代过程建立在
满足对偶问题(DP)的可行解上,即在迭代过程中保持对应的对偶问题的解w0的可行性(从
而x0的检验数全部非正),逐步消除原问题(LP)的基本解x0的不可行性(即使x0非负),
最后达到双方同时为可行解,x0和w0也就同时为最优解了。这就是对偶单纯形法的基本思
想。
按照此设想,为求原问题(LP)的最优解,出发点将是一个不一定可行的基本解(某
些变量可能取负值),但满足最优性判别条件(所有λj≤0)。下面将讨论对偶单纯形法的迭代步骤。
设x0是(LP)的一个基本解(不一定可行),不失一般性,可设相应的典式为
1
fmi
f
f0
jxj
xi
jm1
aiijxj
jm1
xj0
i12mj12
其中λj≤0,ai可正可负。作单纯形表
xB
x1┄┄xm
xm1┄xl┄x
x1
1┄┄0
β1m1┄β1l┄β1
a1
┆
┆
┆┆
┆
xk
βkm1┄βkl┄βk
ak
┆
┆
┆┆
┆
xm
0┄┄1
βmm1┄βml┄βm
am
f
0┄┄0
λm1┄λl┄λ
f0
迭代的基本方式与单纯形法一样,只是离基变量与进基变量的选择方法不同。如果说原
始单纯形法是“按列选主元”的话,那末对偶单纯形法就是“按行r