对偶单纯形法.doc

《对偶单纯形法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

4、变量可能取负值），但满足最优性判别条件（所有λj≤0）。下面将讨论对偶单纯形法的迭代步骤。设x0是（LP）的一个基本解（不一定可行），不失一般性，可设相应的典式为其中λj≤0，ai可正可负。作单纯形表xBx1┄┄xmxm+1┄xl┄xnx1┆xk┆xm1┄┄00┄┄1β1m+1┄β1l┄β1n┆┆┆βkm+1┄βkl┄βkn┆┆┆βmm+1┄βml┄βmna1┆ak┆amf0┄┄0λm+1┄λl┄λnf0迭代的基本方式与单纯形法一样，只是离基变量与进基变量的选择方法不同。如果说原始单纯形法是“按列选主元”的话，那末对偶单

5、纯形法就是“按行选主元”。具体步骤如下：step1)若，则为最优解；step2)设，可选择离基变量：。此时，若，则原问题是不可行的；否则转下一步；step3)选择进基变量，其要求是迭代后任满足。假设则选择是进基变量。（理由呢？）；step4)施行{k,l}旋转变换，使进基，离基，得到一个新的基本解（满足所有的），转step1)。注在step2)中，原问题是不可行的理由是：若，则方程没有解（即原问题的解不可行），否则方程的右边小于0（<），而左边不小于0（≥）。例1利用对偶单纯形法求解以下线性规划：minf=2x1+x2(

6、LP):s.t.解引入剩余变量x3,，x4，x5，则原问题变成minf=2x1+x2(LP1):s.t.将约束等式两端同乘以-1，就直接得到基变量x3，x4，x5，从而得到第一个单纯形表为x1x2x3x4x5x3x4x5-3-1100-4-3*010-1-2001-3-6-2f-2-10000这里a3=-3,a4=-6,a5=-2,最小值是a4，故x4为离基变量。在x4行中考虑比值,有min=所以x2取为进基变量。经旋转变换后得表x1x2x3x4x5x3x2x5-5/301-1/304/310-1/305/300-2/3

7、1-122f-2/300-1/302再取x3为离基变量，x1为进基变量，得表x1x2x3x4x5x1x2x510-3/51/50014/5-3/50001-113/56/51f00-2/5-1/5012/5至此，基变量值已全部非负，故已得最优解x=(3/5,6/5,0,0,1)T若用原始单纯形法求解，则需在问题（LP1）中再引进三个非负的人工变量，然后利用两阶段法求解。实际计算可知，这样做的计算量较大。从这个例题可以看到，对于某些线性规划问题来说，使用对偶单纯形法比用原始单纯形法更具优越性。一般来说，对偶单纯形法适合于求

8、解如下形式的线性规划问题（设b≥0）minbTys.t.在引入变量化为标准形之后，约束等式两端同乘以-1，能够立即得到检验数全部非正的原规划的基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。需要注意的是，对于有些线性规划模型，若在开始求解时，我们不能很快使所有检验数非正，最好还是采用原始单纯形表进行求解。因为