运筹学07对偶单纯形法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,对偶理论的基本定理,对称性,弱对偶性,最优性,对偶定理,互补松弛定理,原问题检验数 对偶问题基本解,6,对偶单纯形法,1,检验数性质：原问题检验数行对应其对偶问题的一个,基解, 关系如下:,X,B,X,N,X,s,0 C,N,-C,B,B,-1,N -C,B,B,-1,Y,s1,- Y,s2,-Y,2,原问题 对偶问题 max z =CX min,=Yb AX+ X,s,=b YA-Y,s,=C X, X,s,0 Y, Y,s,0,设B是原问题的一个可行基, A=(B,N),max z=C,B,X,B,+C,N,X,N,min =Yb,BX,B,+NX,N,+X,S,=b YB-Y,s1,=C,B,X,B, X,N,，X,s,0,YN-Y,s2,=C,N,Y, Y,s1,，Y,s2,0,Y,S,=（Y,S1,，Y,S2,）,令Y=C,B,B,-1,，得,Y,s1,=0，,-Y,s2,= C,N,-C,B,B,-1,N,3,检验数性质：原问题检验数行对应其对偶问题的一个,基解, 关系如下:,X,B,X,N,X,s,0 C,N,-C,B,B,-1,N -C,B,B,-1,Y,s1,- Y,s2,-Y,4,在原来的单纯形表中进行迭代时，前提要求右端项b, 0(,基可行解),，迭代过程中,在b列中得到的是原问题的基可行解，在检验数行得到的是对偶问题的基解。当检验数行也是对偶问题的基可行解时，原问题与对偶问题都得到最优解。,对偶单纯形法原理：,根据对偶问题的对称性，保持对偶问题的解是基可行解，即c,j,-C,B,B,-1,P,j, 0，同时取消对解答列元素非负的限制，在原问题非可行解的基础上,通过逐步迭代得到基可行解，这样就得到了最优解,。,其优点是原问题的初始解不一定要求是基可行解，可从非可行解开始迭代。简言之，不必引进人工变量寻找基底。,5,方法：,设原问题 max z = CX,AX = b,X, 0,设B是一个基，令B=(P,1,P,2,P,m,)，它对应的变量为 X,B,= (,x,1,x,2,x,m,),当非基变量都为零时，可以得到X,B,= B,-1,b。若在B,-1,b中至少有一个,负分量,，设(B,-1,b),i, 0, 并且在单纯形表的检验数行中的检验数,都为非正,，即对偶问题保持可行解，它的各分量是,1、对应基变量x,1,，x,2,，,，x,m,的检验数是,i,= c,i, z,i,= c,i,- C,B,B,-1,P,i,= 0，i = 1 ,2 ,m,2、对应非基变量x,m+1,，,，x,n,的检验数是,j,= c,j, z,j,= c,j,- C,B,B,-1,P,j,0，j = m+1 ,n,6,每次迭代时，将基变量中的负分量x,s,取出（换出变量）, 去替换非基变量中的x,k,，要求在所有检验数仍保持非正（对偶问题可行性）的前提下，进行基变换。,从原问题来看，经过每次迭代, 原问题由非可行解往可行解更靠近，当原问题得到可行解时，便得到了最优解（原问题、对偶问题）。,注意,：,1. 对偶单纯形法不是解对偶问题的单纯形法，而是应用对偶原理求解原问题最优解的一种方法。当然，当求解得到原问题的最优解的同时，也就得到对偶问题的最优解。,2.在具体计算中，不另外构造单纯形表格，而是在原始问题的单纯形表格基础上进行对偶处理。,7,对偶单纯形法的计算步骤:,(1),根据线性规划问题，列出初始单纯形表，检查b列的数值，若,都为非负,，,并且检验数都为非正,，则已得到最优解。停止计算；若b 列的数值至少还有一个,负分量,，检验数保持,非正,，那么进行计算。,(3),确定换入变量：,检查x,s,所在行的各系数a,sj,(j = 1,2,n)。,若所有的 a,sj,0,则无可行解，停止计算,。,(2),先确定换出变量：若,min(B,-1,b),i,|(B,-1,b),i,0 = (B,-1,b),s,对应的基变量x,s,为换出变量。（实际上，可取任何一个取负值的基变量作为换出变量。取最小的含义是尽快）,8,若存在a,sj, 0,(j = 1,2,n)，计算,按规则所对应的非基变量,x,k,为换入变量(保持对偶问题解的可行性)。,(4) 以a,sk,为主元素，进行迭代，即进行矩阵行变换。得新的单纯形表。重复（1）-（4）步，直到求出最优解为止。,为什么要用,原因如下：,确定换入变量呢？,9,第,s,行变成：,行变换将P,k,变成单位向量，因为b,s,0，,一定要求b,s,/a,sk,0, 要选主元素a,sk,0。,检验数变成（行变换）,要保证可行性，就要有,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,10,令T=j|a,sj,0,当jT时， a,sj,0，,从而,jnew,= ,j,-,a,sj,/,a,sk,k,0，满足可行性。,当jT时，,jnew,= ,j,-,a,sj,/,a,sk,k,=,a,s j,j,/,a,sj,-,k,/,a,sk,由于,j,，,k,，,a,sk,，,a,sj,均小于0，从而上述括号内的比值均大于0。,又由于,a,sj,0，为保证,jnew,0， （ jT）,故只要选取,就能有方括号内大于等于0，从而,jnew,0。,11,解: 先将这问题转化（此时b可以是负的）,以便得到对偶问题的初始可行基,max z = -2,x,1,- 3x,2,- 4x,3,-,x,1,- 2x,2,- x,3,+ x,4,= -3,-2,x,1,+ x,2,- 3x,3,+ x,5,= -4,x,j, 0,j = 1,2,3,4,5,建立这个问题的初始单纯形表,例：用对偶单纯形法求解：,min = 2,x,1,+ 3x,2,+ 4x,3,x,1,+ 2x,2,+ x,3, 3,2,x,1,- x,2,+ 3x,3, 4,x,1, x,2, x,3, 0,12,则,X,*,=（11/5，2/5，0，0，0）,T,为原问题的最优解。同时,Y,*,=（y,1,*,，y,2,*,）=（8/5，1/5）,13,对偶单纯形法特点,:,(1),简化计算：,不引入人工变量将线性规划化成标准型,构造,初始单纯形表,(,初始解是非可行解,),只要检验数非负,(,最优检,验数,),就可以进行基的转换；,(2),适于变量多于约束条件：,当变量少于约束方程的个数时，,可考虑变成对偶问题后，再用对偶单纯形法；,(3),局限性：,多数问题很难找到检验数为负,(,最优检验数,),的初,始可行解。但可用于灵敏度分析中简化计算。,14,