《修正对偶》PPT课件

3.9线性规划的对偶问题,第三章线性规划,1对偶问题的提出,4对偶单纯形法,2对偶规划的形式,3.8修正单纯形法,3对偶定理,MaxZ=CXs.t.AX=bX0,j=CBTB-1pj-cj,3.8修正单纯形法,（1）检验数：（2）基变量值：（3）主列元素：,定理3.8.1设在单纯形法某次迭代中的可行基为B，作了r,s旋转基变换后，则下一个新基的逆为,其中,改进单纯形法的计算步骤,（1）求单纯形乘子：,（2）计算：若则停，得最优解否则转（3）,j=CBTB-1pj-cj,（3）计算向量：若所有，则停，无最优解；否则转（4）,（4）计算：,（5）形成变换矩阵：,Ers,（6）计算：以代，以代，转（1）,例MaxZ=x12x2-x3S.t.x1x2+x34-x1+2x2-2x362x1+x25x1,x2,x30,解MaxZ=x12x2-x3S.t.x1x2+x3+x44-x1+2x2-2x3+x562x1+x2+x65x1,x2,x3x4,x5,x60,111100-12-2010210001,（1）,（2）,S=2,（3）,第一次迭代,（4）,（5）,（6）,令,转(1),第二次迭代,（1）,（2）,S=1,转(3),（3）计算,（4）,（5）,（6）,令,转(1),第三次迭代,（1）,（2）,例:某工厂要安排生产甲、乙两种产品.生产单位产品所需设备台时及A,B两种原材料的消耗量，每件产品可以获得的利润以及设备可利用的时数,可用的原材料如下表所示：,1、对偶问题的提出：,3.9线性规划的对偶问题,若有一公司有一订单要生产甲、乙两种产品,需要向工厂租用设备.公司决策者就要考虑给每种设备如何定价,才最有竞争力？,Maxz=2x1+3x2s.t.x1+2x284x1164x212x1,x20,A(4,2),Minf=8y1+16y2+12y3,设y1，y2，y3分别为出租单位设备台时和出让原材料A、B的费用。,Maxz=2x1+3x2s.t.x1+2x284x1164x212原问题x1,x20,s.t.y1+4y22（不少于甲产品的利润）,2y1+4y33（不少于乙产品的利润）,y1,y2,y30对偶问题,Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1，x2，xn0,2、对偶规划的形式(1)对称形式的对偶关系(规范型的线性规划),Minf=b1y1+b2y2+bnyms.t.a11y1+a21y2+am1ymc1a12y1+a22y2+am2ymc2a1ny1+a2ny2+amnymcny1，y2，ym0,一对对称形式的对偶规划之间具有下面的对应关系。原问题记为LP,对偶问题记为DP,LP问题为目标最大化，DP问题为最小化;,LP问题的约束为“”,DP问题的约束为“”;,LP的价值系数ci,在DP问题中恰好为约束右端项;,LP的约束右端项bi,在DP问题中恰好为价值系数;,LP中的每个约束条件对应着DP问题中的一个变量,而LP中的每个决策变量对应着DP问题中的一个约束;,Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1，x2，xn0,Minf=b1y1+b2y2+bnyms.t.a11y1+a21y2+am1ymc1a12y1+a22y2+am2ymc2a1ny1+a2ny2+amnymcny1，y2，ym0,1)2)3)4)5),(LP)Maxz=CTXs.t.AXbX0,Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1，x2，xn0,Maxf=b1y1+b2y2+bmyms.t.a11y1+a21y2+am1ymc1a12y1+a22y2+am2ymc2a1ny1+a2ny2+amnymcmy1，y2，ym0,LP与DP的矩阵的形式,(DP)Minf=bTys.t.ATyCy0,(2)非对称形式的对偶关系,Maxz=2x1+4x2s.t.x1+x2=1-3x1+2x23x1,x20,Maxz=2x1+4x2s.t.x1+x21-x1-x21-3x1+2x23,Miny1-y2+3y3s.t.y1-y2-3y32y1-y2+2y34y1,y2,y3,0,令y1-y2=y4,Miny4+3y3s.t.y4-3y32y4+2y34y30,若LP问题的某个约束条件为等式约束，则在对偶DP问题中与此约束对应着一个变量且那个变量取值无非负限制；,Miny1+3y2s.t.y1-3y22y1+2y24y20,Maxz=2x1+4x2s.t.x1+x2=1-3x1+2x23x1,x20,Maxz=2x1+3x2s.t.x1+x21-3x1+2x23x10,令x/2x/2=x2,Maxz=2x1+3x/23x/2s.t.x1+x/2x/21-3x1+2x/22x/23x1,x/2,x/20,Miny1+3y2s.t.y1-3y22y1+2y23-y1-2y2-3y1y20,Miny1+3y2s.t.y1-3y22y1+2y2=3y1y20,若LP问题的某个变量的值没有非负限制，则在对偶DP问题中与此变量对应的那个约束为等式。,（1）将模型统一为“max，”或“min，”的形式对于其中的等式约束按下面(2)、(3)中的方法处理；,对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划:,（2）若LP问题的某个约束条件为等式约束，则在对偶DP问题中与此约束对应着一个变量且那个变量取值无非负限制；（3）若LP问题的某个变量的值没有非负限制，则在对偶DP问题中与此变量对应的那个约束为等式。,例写出下面线性规划的对偶规划模型,解先将约束条件变形为“”形式，再根据非对称形式的对应关系，写出对偶规划,1.对称性2.弱对偶性3.最优性准则定理,定理3.对偶问题的对偶是原问题.,定理3.9.1若X,Y分别为（LP)和（DP）的任意可行解，那么CTXbTY.,3对偶定理,证:AXb,XTATYbTY;ATYC,XTATYXTC,那么CTXbTY.,推论3.9.2若(LP)和(DP)同时有可行解那么(LP)和(DP)均有最优解.,4.最优解存在的一个充分条件5.无界性,推论3.9.1若X(0),Y(0)分别为（LP)和(DP)的可行解，且CTX(0)=bTY(0).那么X(0),Y(0)分别为(LP)和(DP)的最优解.,证:CTXbTY(0)=CTX(0);bTY(0)=CTX(0)bTY.,定理3.若原问题的目标无界,则其对偶问题必无可行解.,证:若对偶问题有可行解Y(0),则CTXbTY(0)与原问题的目标无界矛盾.,6.强对偶性7.原问题与对偶问题的解之间只有以下三种可能的关系,定理3.9.2若(LP)和(DP)中有一个有最优解,则另一个问题也必存在最优解,且两个问题的最优解的目标函数值必相等.,(1)两个问题都有可行解,从而都有最优解;(2)一个问题有可行解而目标为无界,另一个问题必无可行解;(3)两个问题都无可行解.,Maxz=CTXs.t.AXbX0,证,Maxz=CTX+CTXs.t.AX+IX=bX0,X0,最优解X*=X*0,X*T,X*B=B-1b.X*0为原问题变量,j0,即j=CBTB-1Pj-cj0.j=1,2,n+1,n+m,CBTB-1(p1,p2,pnpn+1,pn+m)-(c1,c2,cncn+1,cn+m)0,原问题变量检验数CBTB-1(p1,p2,pn)-(c1,c2,cn)0(1),松弛变量的检验数CBTB-1(pn+1,pn+m)-(cn+1,cn+m)0(2),由(1)CBTB-1A-CT0,得CBTB-1ACT,记Y*=(CBTB-1)T,则ATY*C即Y*满足对偶问题的约束,又由(2)知CBTB-1I-(0,0,0)0(3)得CBTB-10,即Y*0,Y*满足对偶问题的非负条件.,Minf=bTYs.t.ATYCY0,故Y*=(CBTB-1)T为对偶问题的可行解.且有,bTY*=(Y*Tb)T=(CBTB-1b)T=X*BTCB=CBTXB*(4)下证两个问题的目标最优值相等,从而Y*为最优解:,将原问题最优值Z*按基变量X*B与非基变量X*N表示:将原问题最优值Z*按最优解X*=X0*,X*T表示:,对偶问题目标函数在可行解Y*=(CBB-1)T的目标值为f*=bTY*,再由(4)(5)有:,Z*=CX*0=Y*b=f*,X*0,Y*分别为原问题与对偶问题的可行解且目标值相等,由推论3.9.2,X*0,Y*必为各自问题的最优解.,Z*=CBTX*B+CNTX*N=CBTX*B,Z*=CTX*0+CTX*=CTX*0,故CBTX*B=CTX*0(5),由上述证明过程可以得出:,推论1若线性规划原问题有最优解,最优基为B,则Y*=(CBTB-1)T就是其对偶问题的一个最优解.,推论2对于对称形式的线性规划原问题,若有最优解,则在其最优单纯形表中,松弛变量的检验数就是对偶问题的一个最优解.,若X*,W*分别为（LP）和（DP）的最优解，那么，CX*=W*b。根据f=W*b=b1w1*+b2w2*+bmwm*可知f/bi=wi*wi*表示bi变化1个单位对目标f产生的影响（在不改变原最优基情况下），即若原问题的某个约束的右端项bi每增加一个单位而引起的最优目标函数值的增加量就等于该约束条件相对应的对偶变量的最优解。称wi*为bi的影子价格。注意：B是最优基，影子价格它表示最优目标值随相应资源数量变化的变化率。,对偶解的经济解释,Maxz=2x1+3x2s.t.x1+2x284x1164x212x1,x20 x1*=4,x2*=2z*=14,Minf=8w1+16w2+12w3s.t.w1+4w222w1+4w33w1,w2,w30,由互补定理,将x1*,x2*代入第三个约束，为严格不等号，故w*3=0；又x1*,x2*严格大于零故对应的对偶约束为等号w*1+4w*2=2,2w*1+4w*3=3解得w*1=1.5,w*2=0.125,w*3=0,B(4,2.5),z=15.5,比原目标增1.5,C(4.25,2.875),z=14.125,比原目标增0.125,一、对偶单纯形法的基本思想(1)基本思想,4.对偶单纯形法,从原问题的一个基本解(不一定是可行解)出发,它对应着一个对偶可行解（检验数非负），也可以说是从一个对偶可行解出发；然后检验原问题的基本解是否可行，即是否有负的分量，如果有负的分量，则求另一个基本解，此基本解对应着另一个对偶可行解（检验数非负）。如果得到的基本解的分量皆非负，则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性，使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。,(2)离基变量与进基变量的选择,选取负值的基变量出基:br=minbi0,xr为出基变量,1)若第r行所有元素arj0则原问题无可行解.xr=br(ar1x1+arjxj+),jJN,2)若第r行有ark0,有利于向可行解转化,但还需考虑保证对偶解的可行性,即新检验数j/0,于是取k/ark=maxj/arj|arj0,jJN则j/=j(arj/ark)k=j(k/ark)arjj(j/arj)arj=0此时xr为出基变量.,1)建立初始对偶单纯形表,对应一个基本解,所有检验数均非负,转2；,二、对偶单纯形法求解线性规划问题步骤,2)若b0,则得到最优解,停止;否则,若有bk0,由br=minbk0,基变量xr为出基变量,Ar为主行.转3,3)若所有arj0(j=1,2,n)，则原问题无可行解,停止;否则,若有arj0，则选=maxj/arjarj0=k/ark那么xk为进基变量,Pk为主列,转4；,4)以ark为主元,作矩阵行变换使其变为1,该列其它元变为0,转2.,对偶单纯形法优缺点：,优点:1)原问题的初始解可以是非可行解.当检验数都是非负时,就可以进行基变换,不需要加入