《修正对偶》PPT课件.ppt

《《修正对偶》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《修正对偶》PPT课件.ppt（47页珍藏版）》请在三一办公上搜索。

1、3.9 线性规划的对偶问题,第三章 线性规划,1 对偶问题的提出,4 对偶单纯形法,2 对偶规划的形式,3.8 修正单纯形法,3 对偶定理,Max Z=C X s.t.AX=b X 0,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）形成变换矩阵：,

2、Ers,（6）计算：以 代，以 代，转（1）,例 Max Z=x1 2x2-x3 S.t.x1 x2+x3 4-x1+2x2-2x3 6 2x1+x2 5 x1,x2,x30,解 Max Z=x1 2x2-x3 S.t.x1 x2+x3+x4 4-x1+2x2-2x3+x5 6 2x1+x2+x6 5 x1,x2,x3 x4,x5,x6 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),第三次

3、迭代,（1）,（2）,例:某工厂要安排生产甲、乙两种产品.生产单位产品所需设备台时及A,B两种原材料的消耗量，每件产品可以获得的利润以及设备可利用的时数,可用的原材料如下表所示：,1、对偶问题的提出：,3.9 线性规划的对偶问题,若有一公司有一订单要生产甲、乙两种产品,需要向工厂租用设备.公司决策者就要考虑给每种设备如何定价,才最有竞争力？,Max z=2x1+3x2 s.t.x1+2x2 8 4x1 16 4x2 12 x1,x2 0,A(4,2),Min f=8y1+16y2+12y3,设 y1，y2，y3 分别为出租单位设备台时和出让原材料 A、B 的费用。,Max z=2x1+3x2

4、s.t.x1+2x2 8 4x1 16 4x2 12 原问题 x1,x2 0,s.t.y1+4y2 2（不少于甲产品的利润）,2y1+4y3 3（不少于乙产品的利润）,y1,y2,y3 0 对偶问题,Max z=c1 x1+c2 x2+cn xn s.t.a11 x1+a12 x 2+a1n xn b1 a21 x1+a22 x2+a2n xn b2 am1 x1+am2 x2+amn xn bm x1，x2，xn 0,2、对偶规划的形式(1)对称形式的对偶关系(规范型的线性规划),Min f=b1y1+b2 y2+bn ym s.t.a11 y1+a21 y2+am1 ym c1 a12 y

5、1+a22 y2+am2 ym c2 a1n y1+a2n y2+amn ym cn y1，y2，ym 0,一对对称形式的对偶规划之间具有下面的对应关系。原问题记为LP,对偶问题记为DP,LP问题为目标最大化，DP问题为最小化;,LP问题的约束为“”,DP问题的约束为“”;,LP的价值系数ci,在DP问题中恰好为约束右端项;,LP的约束右端项bi,在DP问题中恰好为价值系数;,LP中的每个约束条件对应着DP问题中的一个变量,而LP中的每个决策变量对应着DP问题中的一个约束;,Max z=c1 x1+c2 x2+cn xn s.t.a11 x1+a12 x 2+a1n xn b1 a21 x1+

6、a22 x2+a2n xn b2 am1 x1+am2 x2+amn xn bm x1，x2，xn 0,Min f=b1y1+b2 y2+bn ym s.t.a11 y1+a21 y2+am1 ym c1 a12 y1+a22 y2+am2 ym c2 a1n y1+a2n y2+amn ym cn y1，y2，ym 0,1)2)3)4)5),(LP)Max z=CTX s.t.AX b X 0,Max z=c1 x1+c2 x2+cn xn s.t.a11 x1+a12 x 2+a1n xn b1 a21 x1+a22 x2+a2n xn b2 am1 x1+am2 x2+amn xn bm

7、 x1，x2，xn 0,Max f=b1y1+b2 y2+bm ym s.t.a11 y1+a21 y2+am1 ym c1 a12 y1+a22 y2+am2 ym c2 a1n y1+a2n y2+amn ym cm y1，y2，ym 0,LP与DP的矩阵的形式,(DP)Min f=bT y s.t.AT y C y 0,(2)非对称形式的对偶关系,Max z=2x1+4 x2 s.t.x1+x 2=1-3x1+2 x2 3 x1,x 2 0,Max z=2x1+4 x2 s.t.x1+x 2 1-x1-x2 1-3x1+2 x2 3,Min y1-y2+3y3 s.t.y1-y2-3y3

8、 2 y1-y2+2y3 4 y1,y2,y3,0,令 y1-y2=y4,Min y4+3y3 s.t.y4-3y3 2 y4+2y3 4 y3 0,若LP问题的某个约束条件为等式约束，则在对偶DP问题中与此约束对应着一个变量且那个变量取值无非负限制；,Min y1+3y2 s.t.y1-3y2 2 y1+2y2 4 y2 0,Max z=2x1+4 x2 s.t.x1+x 2=1-3x1+2 x2 3 x1,x 2 0,Max z=2x1+3 x2 s.t.x1+x 2 1-3x1+2 x2 3 x1 0,令 x/2 x/2=x2,Max z=2x1+3 x/2 3x/2 s.t.x1+x/

9、2 x/2 1-3x1+2 x/2 2x/2 3 x1,x/2,x/2 0,Min y1+3y2 s.t.y1-3y2 2 y1+2y2 3-y1-2y2-3 y1 y2 0,Min y1+3y2 s.t.y1-3y2 2 y1+2y2=3 y1 y2 0,若LP问题的某个变量的值没有非负限制，则在对偶DP问题中与此变量对应的那个约束为等式。,（1）将模型统一为“max，”或“min，”的形式对于其中的等式约束按下面(2)、(3)中的方法处理；,对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划:,（2）若LP问题的某个约束条件为等式约束，则在对偶DP问题中与此约束对应着一个变量且

10、那个变量取值无非负限制；（3）若LP问题的某个变量的值没有非负限制，则在对偶DP问题中与此变量对应的那个约束为等式。,例 写出下面线性规划的对偶规划模型,解 先将约束条件变形为“”形式，再根据非对称形式的对应关系，写出对偶规划,1.对称性2.弱对偶性3.最优性准则定理,定理3.对偶问题的对偶是原问题.,定理3.9.1 若 X,Y 分别为（LP)和（DP）的任意可行解，那么CTX bTY.,3 对偶定理,证:A X b,X TATY bT Y;ATYC,XTATYXTC,那么CTX bTY.,推论3.9.2 若(LP)和(DP)同时有可行解 那么(LP)和(DP)均有最优解.,4.最优解存在的一

11、个充分条件5.无界性,推论3.9.1 若 X(0),Y(0)分别为（LP)和(DP)的可行解，且CTX(0)=bTY(0).那么X(0),Y(0)分别为(LP)和(DP)的最优解.,证:CTX bTY(0)=CTX(0);bTY(0)=CTX(0)bTY.,定理3.若原问题的目标无界,则其对偶问题必无可行解.,证:若对偶问题有可行解Y(0),则CTX bTY(0)与原问题的目标无界矛盾.,6.强对偶性7.原问题与对偶问题的解之间只有以下三种可能的关系,定理3.9.2 若(LP)和(DP)中有一个有最优解,则另一个问题也必存在最优解,且两个问题的最优解的目标函数值必相等.,(1)两个问题都有可行

12、解,从而都有最优解;(2)一个问题有可行解而目标为无界,另一个问题必无可行解;(3)两个问题都无可行解.,Max z=CT X s.t.AX b X 0,证,Max z=C TX+CTX s.t.AX+I X=b X 0,X 0,最优解 X*=X*0,X*T,X*B=B-1b.X*0 为原问题变量,j 0,即j=CBTB-1Pj-cj 0.j=1,2,n+1,n+m,CBT B-1(p1,p2,pn pn+1,pn+m)-(c1,c2,cn cn+1,cn+m)0,原问题变量检验数 CBT B-1(p1,p2,pn)-(c1,c2,cn)0(1),松弛变量的检验数CBT B-1(pn+1,pn

13、+m)-(cn+1,cn+m)0(2),由(1)CBTB-1A-CT0,得CBTB-1A CT,记Y*=(CBTB-1)T,则A TY*C 即Y*满足对偶问题的约束,又由(2)知 CBT B-1 I-(0,0,0)0(3)得CBT B-1 0,即Y*0,Y*满足对偶问题的非负条件.,Min f=bTY s.t.ATY C Y 0,故Y*=(CBTB-1)T 为对偶问题的可行解.且有,b TY*=(Y*Tb)T=(CBTB-1 b)T=X*BT CB=CBT XB*(4)下证两个问题的目标最优值相等,从而Y*为最优解:,将原问题最优值Z*按基变量X*B与非基变量X*N表示:将原问题最优值Z*按最

14、优解 X*=X0*,X*T表示:,对偶问题目标函数在可行解Y*=(CB B-1)T的目标值为 f*=bTY*,再由(4)(5)有:,Z*=C X*0=Y*b=f*,X*0,Y*分别为原问题与对偶问题的可行解且目标值相等,由推论3.9.2,X*0,Y*必为各自问题的最优解.,Z*=CBT X*B+CNT X*N=CBT X*B,Z*=CT X*0+CTX*=CT X*0,故 CBT X*B=CT X*0(5),由上述证明过程可以得出:,推论1 若线性规划原问题有最优解,最优基为B,则Y*=(CBT B-1)T就是其对偶问题的一个最优解.,推论2 对于对称形式的线性规划原问题,若有最优解,则在其最

15、优单纯形表中,松弛变量的检验数就是对偶问题的一个最优解.,若X*,W*分别为（LP）和（DP）的最优解，那么，C X*=W*b。根据 f=W*b=b1w1*+b2w2*+bmwm*可知 f/bi=wi*wi*表示 bi 变化1个单位对目标 f 产生的影响（在不改变原最优基情况下），即若原问题的某个约束的右端项bi每增加一个单位而引起的最优目标函数值的增加量就等于该约束条件相对应的对偶变量的最优解。称wi*为 bi的影子价格。注意：B 是最优基，影子价格 它表示最优目标值随相应资源数量变化的变化率。,对偶解的经济解释,Max z=2x1+3x2 s.t.x1+2x2 8 4x1 16 4x2 1

16、2 x1,x2 0 x1*=4,x2*=2 z*=14,Min f=8w1+16w2+12w3 s.t.w1+4w2 2 2w1+4w3 3 w1,w2,w3 0,由互补定理,将 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.对偶单纯形法,从原问题的一个基本解(不一定是可行解

17、)出发,它对应着一个对偶可行解（检验数非负），也可以说是从一个对偶可行解出发；然后检验原问题的基本解是否可行，即是否有负的分量，如果有负的分量，则求另一个基本解，此基本解对应着另一个对偶可行解（检验数非负）。如果得到的基本解的分量皆非负，则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性，使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。,(2)离基变量与进基变量的选择,选取负值的基变量出基:br=minbi0,xr为出基变量,1)若第r 行所有元素arj 0 则原问题无可行解.xr=br(ar1 x1+arj xj+)

18、,jJN,2)若第r行有ark 0,有利于向可行解转化,但还需考虑保证对偶解的可行性,即新检验数 j/0,于是取 k/ark=maxj/arj|arj 0,jJN 则 j/=j(arj/ark)k=j(k/ark)arj j(j/arj)arj=0 此时xr为出基变量.,1)建立初始对偶单纯形表,对应一个基本解,所有检验数均非负,转2；,二、对偶单纯形法求解线性规划问题步骤,2)若b0,则得到最优解,停止;否则,若有bk0,由br=minbk 0,基变量xr 为出基变量,Ar 为主行.转3,3)若所有arj0(j=1,2,n)，则原问题无可行 解,停止;否则,若有arj0，则选=maxj/ar

19、jarj0=k/ark 那么 xk为进基变量,Pk为主列,转4；,4)以ark为主元,作矩阵行变换使其变为1,该列其它元变为0,转2.,对偶单纯形法优缺点：,优点:1)原问题的初始解可以是非可行解.当检验数都是非负时,就可以进行基变换,不需要加入人工变量,因此可以简化计算 2)当变量多于约束条件个数,用对偶单纯形法可以减少工作量 3)在灵敏度分析中有时用对偶单纯形法较简单缺点:对偶单纯形法要求满足对偶问题有可行性解.该条件不是总能满足,因此这个方法很少单独使用.,例：求解线性规划问题：,-,-,是,是,是,是,否,否,否,否,所有,所有,得到最优解,计算,计算,典式对应原规划的基本解是可行的,典式对应原规划的基本解的检验数,所有,所有,计算,计算,以 为主元素进行迭代,以 为主元素进行迭代,停,没有最优解,没有可行解,最优解,单纯形法,对偶单纯形法,单纯形法和对偶单纯形法步骤,