§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