运筹学07对偶单纯形法.ppt

1、对偶理论的基本定理,对称性 弱对偶性 最优性 对偶定理 互补松弛定理 原问题检验数 对偶问题基本解,6 对偶单纯形法,检验数性质：原问题检验数行对应其对偶问题的一个 基解, 关系如下:,原问题 对偶问题 max z =CX min =Yb AX+ Xs =b YA-Ys=C X, Xs 0 Y, Ys0,设B是原问题的一个可行基, A=(B,N) max z=CBXB+CNXN min =Yb BXB+NXN+XS=b YB-Ys1=CB XB, XN，Xs0 YN-Ys2=CN Y, Ys1，Ys20 YS=（YS1，YS2）,令Y=CBB-1，得 Ys1=0， -Ys2= CN-CBB-1

2、N,检验数性质：原问题检验数行对应其对偶问题的一个 基解, 关系如下:,在原来的单纯形表中进行迭代时，前提要求右端项b 0(基可行解)，迭代过程中在b列中得到的是原问题的基可行解，在检验数行得到的是对偶问题的基解。当检验数行也是对偶问题的基可行解时，原问题与对偶问题都得到最优解。,对偶单纯形法原理：根据对偶问题的对称性，保持对偶问题的解是基可行解，即cj-CBB-1Pj 0，同时取消对解答列元素非负的限制，在原问题非可行解的基础上, 通过逐步迭代得到基可行解，这样就得到了最优解。,其优点是原问题的初始解不一定要求是基可行解，可从非可行解开始迭代。简言之，不必引进人工变量寻找基底。,方法：设原问

3、题 max z = CX AX = b X 0,设B是一个基，令B=(P1 ,P2 , ,Pm)，它对应的变量为 XB = ( x1 ,x2 , ,xm),当非基变量都为零时，可以得到XB = B-1b。若在B-1b中至少有一个负分量，设(B-1b)i 0, 并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是,1、对应基变量x1，x2， ，xm的检验数是 i = ci zi = ci - CB B-1Pi = 0，i = 1 ,2 , ,m 2、对应非基变量xm+1， ，xn的检验数是 j = cj zj = cj - CB B-1Pj 0，j = m+1 , ,n

4、,每次迭代时，将基变量中的负分量xs取出（换出变量）, 去替换非基变量中的xk，要求在所有检验数仍保持非正（对偶问题可行性）的前提下，进行基变换。从原问题来看，经过每次迭代, 原问题由非可行解往可行解更靠近，当原问题得到可行解时，便得到了最优解（原问题、对偶问题）。,注意： 1. 对偶单纯形法不是解对偶问题的单纯形法，而是应用对偶原理求解原问题最优解的一种方法。当然，当求解得到原问题的最优解的同时，也就得到对偶问题的最优解。,2.在具体计算中，不另外构造单纯形表格，而是在原始问题的单纯形表格基础上进行对偶处理。,对偶单纯形法的计算步骤:,(1) 根据线性规划问题，列出初始单纯形表，检查b列的数

5、值，若都为非负，并且检验数都为非正，则已得到最优解。停止计算；若b 列的数值至少还有一个负分量，检验数保持非正，那么进行计算。,(3) 确定换入变量： 检查xs所在行的各系数asj(j = 1,2,n)。 若所有的 asj0,则无可行解，停止计算。,(2) 先确定换出变量：若 min(B-1b)i|(B-1b)i 0 = (B-1b)s 对应的基变量xs为换出变量。（实际上，可取任何一个取负值的基变量作为换出变量。取最小的含义是尽快）,若存在asj 0,(j = 1,2,n)，计算,按规则所对应的非基变量xk为换入变量(保持对偶问题解的可行性)。,(4) 以ask为主元素，进行迭代，即进行矩阵

6、行变换。得新的单纯形表。重复（1）-（4）步，直到求出最优解为止。,为什么要用,原因如下：,确定换入变量呢？,第s行变成：,行变换将Pk变成单位向量，因为bs0，一定要求bs/ask0, 要选主元素ask0。,检验数变成（行变换）,要保证可行性，就要有jnew 0，j=1,n,),1,0,0,1, .,0,0,(,sn,1,sk,sk,sm,sk,sk,s,a,a,a,a,a,a,b,L,L,L,L,+,),0,0,0,0,0,(,sn,1,1,k,sk,n,k,sk,sm,m,sk,k,a,a,a,a,a,s,s,s,s,s,-,-,-,+,+,L,L,L,L,令T=j|asj0 当jT时，

7、 asj 0，从而jnew= j-asj/askk 0，满足可行性。 当jT时， jnew= j-asj/askk = as jj /asj- k /ask 由于j ，k， ask ，asj均小于0，从而上述括号内的比值均大于0。 又由于asj0，为保证jnew 0， （ jT） 故只要选取,就能有方括号内大于等于0，从而jnew 0。,解: 先将这问题转化（此时b可以是负的）,以便得到对偶问题的初始可行基 max z = -2x1 - 3x2 - 4x3 -x1 - 2x2 - x3 + x4 = -3 -2x1 + x2 - 3x3 + x5 = -4 xj 0,j = 1,2,3,4,5 建立这个问题的初始单纯形表,例：用对偶单纯形法求解： min = 2x1 + 3x2 + 4x3 x1 + 2x2 + x3 3 2x1 - x2 + 3x3 4 x1 , x2 , x3 0,则 X*=（11/5，2/5，0，0，0）T 为原问题的最优解。同时 Y*=（y1*，y2*）=（8/5，1/5）,对偶单纯形法特点,:,(1),简化计算：,不引入人工变量将线性规划化成标准型,构造,初始单纯形表,(,初始解是非可行解,),只要检验数非负,(,最优检,验数,