对偶单纯形法

1、6 对偶单纯形法在介绍对偶单纯形法之前，让我们先利用对偶理论来重温一下单纯形法的基本思想，以便给单纯形法一种新的解释。考虑线性规划（LP）和其对偶规划（DP）： (LP) s.t (DP) s.t 我们已经知道，（LP）的单纯形表为 基变量 x1 x2 x n xB B-1 A B-1b f cBT B-1 A cT cBT B1b定理1 设(LP)的任一基本解为x0，它对应于基B，并作(w0 )T= cBT B1。若x0 和w0 分别是(LP)和（DP）的可行解，则x0 和w 0 也分别是(LP)和（DP）的最优解。证明 因w0 是（DP）的可行解，即 (w0 )T A cT 从而有 cBT

2、 B1A - cT 0此式说明，x0是对应于基B的基本可行解，且所有的检验数j 0故x0是（LP）的最优解。此外，还有(w0 )T b = cBT B1 b = cBT xB0 = c x0从而由线性规划的对偶定理知，w 0 也是（DP）的最优解。 证毕。由以上证明过程可看到：x0（LP）的任一基本解）的检验数全部非正与(w0 )T= cBT B1是对偶问题（DP）的可行解等价。据此我们可对单纯形法作如下解释：从一个基本解x0出发迭代到另一个基本解，在迭代过程中始终保持解的可行性（基本可行解），同时使它所对应的对偶规划的解w0（满足（w0 ）T= cBT B1 ）的不可行性逐步消失（即检验数逐

3、步变为非正）；直到w0是（DP）的可行解，x0就是（LP）的最优解。因（LP）和（DP）互为对偶问题，故基于对称的想法，我们也可以把迭代过程建立在满足对偶问题（DP）的可行解上，即在迭代过程中保持对应的对偶问题的解w0的可行性（从而x0的检验数全部非正），逐步消除原问题（LP）的基本解x0的不可行性（即使x0非负），最后达到双方同时为可行解，x0和w0也就同时为最优解了。这就是对偶单纯形法的基本思想。按照此设想，为求原问题（LP）的最优解，出发点将是一个不一定可行的基本解（某些变量可能取负值），但满足最优性判别条件（所有j 0）。下面将讨论对偶单纯形法的迭代步骤。 设x0是（LP）的一个基本解

4、（不一定可行），不失一般性，可设相应的典式为其中j 0，ai 可正可负。作单纯形表xBx1 x mxm+1 xl x nx1xkxm1 00 11 m+1 1l 1 n k m+1 k l k n m m+1 m l m na1a ka mf0 0m+1 l nf 0迭代的基本方式与单纯形法一样，只是离基变量与进基变量的选择方法不同。如果说原始单纯形法是“按列选主元”的话，那末对偶单纯形法就是“按行选主元”。具体步骤如下：step1) 若，则为最优解；step2) 设，可选择离基变量：。此时，若，则原问题是不可行的；否则转下一步；step3) 选择进基变量，其要求是迭代后任满足。假设则选择是进

5、基变量。（理由呢？）；step4) 施行 k, l 旋转变换，使进基，离基，得到一个新的基本解（满足所有的），转step1)。注 在step2)中，原问题是不可行的理由是：若，则方程没有解（即原问题的解不可行），否则方程的右边小于0（），而左边不小于0（）。例1 利用对偶单纯形法求解以下线性规划：min f=2x1+x2 (LP): s.t. 解 引入剩余变量x3,，x4，x5，则原问题变成min f=2x1+x2 (LP1) : s.t. 将约束等式两端同乘以-1，就直接得到基变量x3，x4，x5，从而得到第一个单纯形表为 x1 x2 x3 x4 x5 x3x4x5 -3 -1 1 0 0

6、-4 -3* 0 1 0 -1 -2 0 0 1-3-6-2 f -2 -1 0 0 0 0 这里a3=-3, a4=-6, a5=-2, 最小值是a4，故x4为离基变量。在x4行中考虑比值,有 min =所以x2取为进基变量。经旋转变换后得表 x1 x2 x3 x4 x5 x3x2x5 -5/3 0 1 -1/3 0 4/3 1 0 -1/3 0 5/3 0 0 -2/3 1-122 f -2/3 0 0 -1/3 0 2再取x3为离基变量，x1为进基变量，得表 x1 x2 x3 x4 x5 x1x2x5 1 0 -3/5 1/5 0 0 1 4/5 -3/5 0 0 0 1 -1 13/5

7、6/51 f 0 0 -2/5 -1/5 012/5至此，基变量值已全部非负，故已得最优解x= ( 3/5, 6/5, 0, 0, 1 )T若用原始单纯形法求解，则需在问题（LP1）中再引进三个非负的人工变量，然后利用两阶段法求解。实际计算可知，这样做的计算量较大。从这个例题可以看到，对于某些线性规划问题来说，使用对偶单纯形法比用原始单纯形法更具优越性。一般来说，对偶单纯形法适合于求解如下形式的线性规划问题（设b0） min bT y s.t. 在引入变量化为标准形之后，约束等式两端同乘以-1，能够立即得到检验数全部非正的原规划的基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。需要注意的是，对于有些线性规划模型，若在开始求解时，我们不能很快使所有检验数非正