修正对偶课件

,上一页,下一页,返回,3.9 线性规划的对偶问题,第三章 线性规划,1 对偶问题的提出,4 对偶单纯形法,2 对偶规划的形式,3.8 修正单纯形法,3 对偶定理,Max Z,=,C X,s.t.,AX,=,b,X,0,j,=,C,B,T,B,-1,p,j,-c,j,3.8 修正单纯形法,（1）检验数：,（,2,）基变量值：,（,3,）主列元素：,定理3.8.1 设在单纯形法某次迭代中的可行基,为,B,，作了r,s,旋转基变换后，则下一个新基,的逆为 ,其中,改进单纯形法的计算步骤,（1） 求单纯形乘子：,（2） 计算：,若 则停，得最优解,否则 转（3）,j,=,C,B,T,B,-1,p,j,-c,j,（3） 计算向量：,若所有 ，则停，无最优解；否则转（4）,（4） 计算：,（5） 形成变换矩阵：,E,rs,（6） 计算：,以 代 ，以,代 ，转（1）,例,Max Z =,x,1,2,x,2,-,x,3,S.t.,x,1,x,2,+,x,3,4,-,x,1,+ 2,x,2,- 2,x,3,6,2,x,1,+,x,2,5,x,1,x,2,x,3,0,解,Max Z =,x,1,2,x,2,-,x,3,S.t.,x,1,x,2,+,x,3,+,x,4,4,-,x,1,+ 2,x,2,- 2,x,3,+,x,5,6,2,x,1,+,x,2,+,x,6,5,x,1,x,2,x,3,x,4,x,5,x,6,0,1 1 1 1 0 0,-1 2 -2 0 1 0,2 1 0 0 0 1,（1）,（2）,S=2,（3）,第一次迭代,（4）,（5）,（6）,令,转(1),第二次迭代,（1）,（2）,S=1, 转(3),（3）计算,（4）,（5）,（6）,令,转(1),第三次迭代,（1）,（2）,例:某工厂要安排生产甲、乙两种产品.生产单位产品所需设备台时及A,B两种原材料的消耗量，每件产品可以获得的利润以及设备可利用的时数,可用的原材料如下表所示：,1、对偶问题的提出：,产品甲,产品乙,设备能力,设备,1,2,8台时,原材料,A,4,0,16kg,原材料,B,0,4,12kg,利润（百元/件）,2,3,3.9 线性规划的对偶问题,若有一公司有一订单要生产甲、乙两种产品,需要向工厂租用设备.公司决策者就要考虑给每种设备如何定价,才最有竞争力？,Max,z,=2,x,1,+3,x,2,s.t.,x,1,+2,x,2, 8,4,x,1, 16,4,x,2, 12,x,1,x,2,0,x,1,x,2,O,x,1,+2,x,2,=8,x,1,=4,x,2,=8,2,x,1,+3,x,2,=C,A(4,2),Min,f,= 8,y,1,+ 16,y,2,+ 12,y,3,设,y,1,，,y,2,，,y,3,分别为出租单位设备台时和出让原材料,A、B,的费用。,Max,z,=2,x,1,+3,x,2,s.t.,x,1,+2,x,2, 8,4,x,1, 16,4,x,2, 12,原问题,x,1,x,2,0,s.t.,y,1,+4,y,2,2 （不少于甲产品的利润）,2,y,1,+4,y,3,3 （不少于乙产品的利润）,y,1,y,2,y,3, 0,对偶问题,Max,z,=,c,1,x,1,+,c,2,x,2,+ +,c,n,x,n,s.t.,a,11,x,1,+,a,12,x,2,+ +,a,1,n,x,n,b,1,a,21,x,1,+,a,22,x,2,+ +,a,2,n,x,n,b,2, ,a,m,1,x,1,+,a,m,2,x,2,+ +,a,mn,x,n,b,m,x,1,，,x,2,， ，,x,n, 0,2、对偶规划的形式,(1),对称形式的对偶关系(规范型的线性规划),Min,f,=,b,1,y,1,+,b,2,y,2,+ +,b,n,y,m,s.t.,a,11,y,1,+,a,21,y,2,+ +,a,m,1,y,m,c,1,a,12,y,1,+,a,22,y,2,+ +,a,m,2,y,m,c,2, ,a,1,n,y,1,+,a,2,n,y,2,+ +,a,mn,y,m,c,n,y,1,，,y,2,， ，,y,m, 0,一对对称形式的对偶规划之间具有下面的对应关系。原问题记为LP,对偶问题记为DP,LP问题为目标最大化，DP问题为最小化;,LP问题的约束为“,”,DP问题的约束为“,”;,LP的价值系数,c,i,在DP问题中恰好为约束右端项;,LP的约束右端项,b,i,在DP问题中恰好为价值系数;,LP中的每个约束条件对应着DP问题中的一个变量,而LP中的每个决策变量对应着DP问题中的一个约束;,Max,z,=,c,1,x,1,+,c,2,x,2,+ +,c,n,x,n,s.t.,a,11,x,1,+,a,12,x,2,+ +,a,1,n,x,n,b,1,a,21,x,1,+,a,22,x,2,+ +,a,2,n,x,n,b,2, ,a,m,1,x,1,+,a,m,2,x,2,+ +,a,mn,x,n,b,m,x,1,，,x,2,， ，,x,n, 0,Min,f,=,b,1,y,1,+,b,2,y,2,+ +,b,n,y,m,s.t.,a,11,y,1,+,a,21,y,2,+ +,a,m,1,y,m,c,1,a,12,y,1,+,a,22,y,2,+ +,a,m,2,y,m,c,2, ,a,1,n,y,1,+,a,2,n,y,2,+ +,a,mn,y,m,c,n,y,1,，,y,2,， ，,y,m, 0,1),2),3),4),5),(LP) Max,z,=,C,T,X,s.t.,AX,b,X,0,Max,z,=,c,1,x,1,+,c,2,x,2,+ +,c,n,x,n,s.t.,a,11,x,1,+,a,12,x,2,+ +,a,1,n,x,n,b,1,a,21,x,1,+,a,22,x,2,+ +,a,2,n,x,n,b,2, ,a,m,1,x,1,+,a,m,2,x,2,+ +,a,mn,x,n,b,m,x,1,，,x,2,， ，,x,n, 0,Max,f,=,b,1,y,1,+,b,2,y,2,+ +,b,m,y,m,s.t.,a,11,y,1,+,a,21,y,2,+ +,a,m,1,y,m,c,1,a,12,y,1,+,a,22,y,2,+ +,a,m,2,y,m,c,2, ,a,1,n,y,1,+,a,2,n,y,2,+ +,a,mn,y,m,c,m,y,1,，,y,2,， ，,y,m, 0,LP与DP的矩阵的形式,(DP) Min,f,=,b,T,y,s.t.,A,T,y,C,y,0,(2)非对称形式的对偶关系,Max,z,= 2,x,1,+ 4,x,2,s.t.,x,1,+,x,2,= 1,-3,x,1,+ 2,x,2,3,x,1,x,2,0,Max,z,= 2,x,1,+ 4,x,2,s.t.,x,1,+,x,2,1,-,x,1,-,x,2, 1,-3,x,1,+ 2,x,2,3,Min,y,1,-,y,2,+3,y,3,s.t.,y,1,-,y,2,- 3,y,3,2,y,1,-,y,2,+2,y,3,4,y,1,y,2,y,3,0,令,y,1,-,y,2,=,y,4,Min,y,4,+3,y,3,s.t.,y,4,- 3,y,3,2,y,4,+2,y,3,4,y,3,0,若LP问题的某个约束条件为等式约束，则在对偶DP问题中与此约束对应着一个变量且那个变量取值无非负限制；,Min,y,1,+3,y,2,s.t.,y,1,- 3,y,2,2,y,1,+2,y,2,4,y,2,0,Max,z,= 2,x,1,+ 4,x,2,s.t.,x,1,+,x,2,= 1,-3,x,1,+ 2,x,2,3,x,1,x,2,0,Max,z,= 2,x,1,+ 3,x,2,s.t.,x,1,+,x,2,1,-3,x,1,+ 2,x,2,3,x,1,0,令,x,/,2,x,/,2,=,x,2,Max,z,= 2,x,1,+ 3,x,/,2, 3,x,/,2,s.t.,x,1,+,x,/,2,x,/,2,1,-3,x,1,+ 2,x,/,2,2,x,/,2,3,x,1,x,/,2,x,/,2,0,Min,y,1,+3,y,2,s.t.,y,1,- 3,y,2,2,y,1,+2,y,2,3,-y,1,-2,y,2,- 3,y,1,y,2,0,Min,y,1,+3,y,2,s.t.,y,1,- 3,y,2,2,y,1,+2,y,2,=,3,y,1,y,2,0,若LP问题的某个变量的值没有非负限制，则在对偶DP问题中与此变量对应的那个约束为等式。,（1）将模型统一为“max，”或“min，” 的形式对于其中的等式约束按下面(2)、(3)中的方法处理；,对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划:,（2）若LP问题的某个约束条件为等式约束，则在对偶DP问题中与此约束对应着一个变量且那个变量取值无非负限制；,（3）若LP问题的某个变量的值没有非负限制，则在对偶DP问题中与此变量对应的那个约束为等式。,例 写出下面线性规划的对偶规划模型,解 先将约束条件变形为“”形式，,再根据非对称形式的对应关系，写出对偶规划,1.对称性,2.弱对偶性,3.最优性准则定理,定理3. 对偶问题的对偶是原问题.,定理3.9.1 若,X,Y,分别为（LP)和（DP）的任意可行解，那么,C,T,X,b,T,Y.,3 对偶定理,证:,A X,b,X,T,A,T,Y,b,T,Y,;,A,T,Y,C,X,T,A,T,Y,X,T,C,那么,C,T,X,b,T,Y.,推论3.9.2 若(LP)和(DP)同时有可行解 那么(LP)和(DP)均有最优解.,4.最优解存在的一个充分条件,5.无界性,推论3.9.1 若,X,(0),Y,(0),分别为（LP)和(DP)的可行解，,且,C,T,X,(0),=,b,T,Y,(0),.,那么,X,(0),Y,(0),分别为(LP)和(DP),的最优解.,证:,C,T,X,b,T,Y,(0),=C,T,X,(0),;,b,T,Y,(0),=,C,T,X,(0),b,T,Y.,定理3. 若原问题的目标无界,则其对偶问题必无可行解,.,证: 若对偶问题有可行解,Y,(0),则,C,T,X,b,T,Y,(0),与原问题的目标无界矛盾.,6.强对偶性,7.原问题与对偶问题的解之间只有以下三种可能的关系,定理3.9.2 若(LP)和(DP)中有一个有最优解,则另一个问题也必存在最优解,且两个问题的最优解的目标函数值必相等,.,(1)两个问题都有可行解,从而都有最优解;,(2)一个问题有,可行解而目标,为无界,另一个问题必无可行解;,(3)两个问题都无可行解,.,Max,z,=,C,T,X,s.t.,AX,b,X,0,证,Max,z,=,C,T,X+C,T,X,s.t.,AX,+,I,X,=,b,X,0,X,0,最优解,X,*,=,X*,0, X*,T ,X,*,B,=,B,-,1,b . X*,0,为原问题变量,j,0,即,j,=,C,B,T,B,-,1,P,j,-,c,j,0. j=1,2,n+1, ,n+m,C,B,T,B,-,1,(,p,1,p,2,p,n,p,n,+1,p,n,+,m,),-,(,c,1,c,2,c,n,c,n,+1,c,n,+,m,),0,原问题变量检验数,C,B,T,B,-,1,(,p,1,p,2,p,n,),-,(,c,1,c,2,c,n,),0,(1),松弛变量的检验数,C,B,T,B,-,1,(,p,n,+1,p,n,+,m,),-,(,c,n,+1,c,n,+,m,),0,(2),由,(1),C,B,T,B,-,1,A,-C,T,0,得,C,B,T,B,-,1,A,C,T,记,Y *,=(,C,B,T,B,-,1,),T,则,A,T,Y*,C,即,Y*,满足对偶问题的约束,又由,(2),知,C,B,T,B,-,1,I,-,(0,0,0,),0,(3),得,C,B,T,B,-,1,0,即,Y *,0,Y*,满足对偶问题的非负条件.,Min,f,=,b,T,Y,s.t.,A,T,Y,C,Y,0,故,Y*,=,(,C,B,T,B,-,1,),T,为对偶问题的可行解.,且有,b,T,Y*,=,(,Y,*,T,b,),T,=(,C,B,T,B,-,1,b,),T,=,X,*,B,T,C,B,=,C,B,T,X,B,*,(4),下证两个问题的目标最优值相等,从而,Y,*为最优解:,将原问题最优值Z*按基变量,X,*,B,与非基变量,X,*,N,表示:,将原问题最优值Z*按最优解,X,*,=,X,0,*, X,*,T,表示:,对偶问题目标函数在可行解,Y*,=(,C,B,B,-,1,),T,的目标值为,f* =,b,T,Y *,再由,(4)(5),有:,Z*=,C,X*,0,= Y*,b=,f*,X*,0,Y *,分别为原问题与对偶问题的可行解且目标值相等,由推论3.9.2,X*,0,Y *,必为各自问题的最优解.,Z*=,C,B,T,X,*,B,+,C,N,T,X,*,N,=,C,B,T,X,*,B,Z*=,C,T,X*,0,+,C,T,X*,=,C,T,X*,0,故,C,B,T,X,*,B,=,C,T,X*,0,(5),由上述证明过程可以得出:,推论1,若线性规划原问题有最优解,最优基为B, 则,Y*,=,(,C,B,T,B,-,1,),T,就是其对偶问题的一个最优解.,推论2,对于对称形式的线性规划原问题,若有最优解,则在其最优单纯形表中,松弛变量的检验数就是对偶问题的一个最优解.,若,X,*,W,*,分别为（LP）和（DP）的最优解，,那么，,C,X,*,= W,*,b,。,根据,f,=,W,*,b,=,b,1,w,1,*,+,b,2,w,2,*,+,+,b,m,w,m,*,可知,f,/,b,i,=,w,i,*,w,i,*,表示,b,i,变化1个单位对目标,f,产生的影响（在不改变原最优基情况下），即若原问题的某个约束的右端项,b,i,每增加一个单位而引起的最优目标函数值的增加量就等于该约束条件相对应的对偶变量的最优解。称,w,i,*,为,b,i,的影子价格。,注意：,B,是最优基，,影子价格 它表示最优目标值随相应资源数量变化的变化率。,对偶解的经济解释,Max,z,=2,x,1,+3,x,2,s.t.,x,1,+2,x,2, 8,4,x,1, 16,4,x,2, 12,x,1,x,2,0,x,1,*,=,4,x,2,*,=,2 z*,=,14,x,1,x,2,O,x,1,+2,x,2,=8,x,1,=4,x,2,=8,2,x,1,+3,x,2,=C,A(4,2),Min,f,= 8,w,1,+ 16,w,2,+ 12,w,3,s.t.,w,1,+4,w,2,2,2,w,1,+4,w,3,3,w,1,w,2,w,3, 0,A,由互补定理,将,x,1,*,x,2,*,代入第三个约束，为严格不等号，故,w*,3,=0；,又,x,1,*,x,2,*,严格大于零故对应的对偶约束为等号,w*,1,+4,w*,2,=,2,2,w*,1,+4,w*,3,=,3,解得,w*,1,= 1.5 ,w*,2,= 0.125 ,w*,3,=0,x,1,x,2,O,B(4,2.5),z=15.5,比原目标增1.5,4,x,1,=17,C,B,x,1,+2,x,2,=8,C(4.25,2.875),z=14.125,比原目标增0.125,x,2,=3,4,x,2,=13,2,x,1,+3,x,2,=C,x,1,+2,x,2,=9,4,x,1,=16,一、对偶单纯形法的基本思想,(,1),基本思想,4.对偶单纯形法,从原问题的一个基本解(不一定是可行解)出发,它对应着一个对偶可行解（检验数非负），也可以说是从一个对偶可行解出发；然后检验原问题的基本解是否可行，即是否有负的分量，如果有负的分量，则求另一个基本解，此基本解对应着另一个对偶可行解（检验数非负）。,如果得到的基本解的分量皆非负，则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性，使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。,(2)离基变量与进基变量的选择,选取负值的基变量出基:,b,r,=min,b,i,0,x,r,为出基变量,1) 若第,r,行所有元素,a,rj,0,则原问题无可行解.,x,r,=,b,r, (,a,r,1,x,1,+,a,rj,x,j,+ ),j,J,N,2),若第,r,行有,a,rk, 0,有利于向可行解转化,但还需考虑保证对偶解的可行性,即新检验数,j,/,0 ,于是取,k,/,a,rk,= max,j,/,a,rj,|,a,rj,0,j,J,N,则,j,/,=,j,(,a,rj,/,a,rk,),k,=,j,(,k,/,a,rk,),a,rj,j,(,j,/,a,rj,),a,rj,=0,此,时,x,r,为出基变量,.,1),建立初始对偶单纯形表,对应一个基本解,所有检验数均非负,转,2；,二、对偶单纯形法求解线性规划问题步骤,2),若,b,0,则得到最优解,停止;否则,若有,b,k,0,由,b,r,=min,b,k,0,基变量,x,r,为出基变量,A,r,为主行.转,3,3),若所有,a,rj,0(,j,= 1,2,n,)，,则原问题无可行,解,停止;否则,若有,a,rj,0 ，,则选,=max,j,/,a,rj,a,rj,0,=,k,/,a,rk,那么,x,k,为进基变量,P,k,为主列, 转,4；,4),以,a,rk,为主元,作矩阵行变换使其变为1,该列其它元变为0,转2.,对偶单纯形法优缺点 ：,优点:,1)原问题的初始解可以是非可行解.当检验数都是非负时,就可以进行基变换,不需要加入人工变量,因此可以简化计算,2)当变量多于约束条件个数,用对偶单纯形法可以减少工作量,3)在灵敏度分析中有时用对偶单纯形法较简单,缺点:,对偶单纯形法要求满足对偶问题有可行性解.该条件不是总能满足,因此这个方法很少单独使用.,例：求解线性规划问题：,解,Max,Z,= - 2,x,1,- 3,x,2,- 4,x,3,s.t,-,x,1,-2,x,2,-,x,3,+,x,4,= -3,-2,x,1,+,x,2,-3,x,3,+,x,5,= -4,x,1,x,2,x,3,x,4,x,5, 0,Min z= 2,x,1,+ 3,x,2,+ 4,x,3,S.t.,x,1,+ 2,x,2,+,x,3, 3,2,x,1,-,x,2,+,x,3, 4,x,1,x,2,x,3, 0,-,最优解:,(11/5,2/5,0,0,0),最优值:,Z,*=,-,28/5,z,*=28/5,-,是,是,是,是,否,否,否,否,所有,所有,得到,最优解,计算,计算,典式对应原规划的基本解是可行的,典式对应原规划的基本解的检验数,所有,所有,计算,计算,以 为主元素进行迭代,以 为主元素进行迭代,停,没有最优解,没有可行解,最优解,单纯形法,对偶单纯形法,单纯形法和对偶单纯形法步骤,