第二章线性规划的对偶理论

第,*,页,广西工学院财政经济系 冯金丽,第二章 对偶理论与灵敏度分析,2.1,线性规划的对偶问题,2.2,对偶问题的基本性质,2.3,影子价格,2.4,对偶单纯形法,2.5,灵敏度分析,DUAL,本章学习要求,掌握对偶理论及其性质,掌握影子价格的应用,掌握对偶单纯形法,熟悉灵敏度分析的概念和内容,掌握右侧常数，价值系数的变换对原最优解的影响,掌握增加新变量和增加新约束条件对原最优解的影响，并求出相应因素的灵敏度范围,2.1,线性规划的对偶问题,问题的提出,对称形式下对偶问题的一般形式,非对称形式下的原问题与对偶问题的关系,一、对偶问题的提出,每一个,LP,问题，都伴随着另一个,LP,，而且二者有密切关系，互为对偶，另其中一个问题为原问题，另一个问题为对偶问题，只要得到了其中一个问题的解（目标值），也得到另一问题的解，因此通常只求解一个问题就可以了。,例,1,：（美佳公司）,美佳公司应如何生产安排，使已有资源利润最大化。,某公司至少该出多大代价，使美佳公司愿意放弃自己的资源，,产品,资源,资源约束,A,0,5,15,B,6,2,24,调试工序,1,1,5,单位产品利润,2,1,产品,资源,A,B,调试,工序,单位资源利润,0,6,1,2,5,2,1,1,资源量,15,24,5,数学模型,Z*=8.5,W*=8.5,一般认为变量均为非负约束的情况下，约束条件在目标函数取,Max,时均取“,”,号；当目标函数求,Min,值时均取“,“,号。则称这些线性规划问题具有对称性。,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,1n,x,n,b,1,a,21,x,1,+a,22,x,2,+a,2n,x,n,b,2,a,m1,x,1,+a,m2,x,2,+,a,mn,x,n,b,m,x,1,x,2,x,n,0,min w=b,1,y,1,+b,2,y,2,+,b,m,y,m,s.t.a,11,y,1,+a,21,y,2,+a,m1,y,m,c,1,a,12,y,1,+a,22,y,2,+a,m2,y,m,c,2,a,1n,y,1,+a,2n,y,2,+,a,mn,y,m,c,n,y,1,y,2,y,m,0,Max Z=CX,s.t,.,AXb,X0,Minw,=,Yb,s.t,.AYC,Y0,二、对偶问题的一般形式,原问题,max z=CX,s.t.,AX,b,X 0,对偶问题,min w=,Yb,s.t.AY,C,Y,0,max,b,C,C,A,T,b,min,m,n,m,n,A,举例：,maxZ,=3x,1,+2x,2,s.t,.-x,1,+2x,2,4,3x,1,+2x,2,14,x,1,-x,2,3,x,1,x,2,0,minw,=4y,1,+14y,2,+y,3,s.t,.-y,1,+3y,2,+y,3,3,2y,1,+2x,2,-y,3,2,y,1,y,2,y,3,0,y,1,y,2,y,3,第一种资源,第二种资源,第三种资源,第一种产品,第二种产品,x,1,x,2,原始问题为,min z=2x,1,+3x,2,-x,3,s.t.x,1,+2x,2,+x,3,6,2x,1,-3x,2,+2x,3,9,x,1,x,2,x,3,0,根据定义，对偶问题为,max y=6y,1,+9y,2,s.t.y,1,+2y,2,2,2y,1,-3y,2,3,y,1,+2y,2,-1,y,1,y,2,0,原始问题是极小化问题,原始问题的约束全为,原始问题有,3,个变量，,2,个约束,原始问题的变量全部为非负,对偶问题是极大化问题,对偶问题的约束全为,对偶问题有,2,个变量，,3,个约束,原始问题的变量全部为非负,对偶问题的对偶,max z=6x,1,+9x,2,s.t.x,1,+2x,2,2,2x,1,-3x,2,3,x,1,+2x,2,-1,x,1,x,2,0,minw,=2y,1,+3y,2,-y,3,s.t.y,1,+2y,2,+y,3,6,2y,1,-3y,2,+2y,3,9,y,1,y,2,y,3,0,对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题。另一个就是它的对偶问题。,根据定义写出对偶问题,根据定义写出对偶问题,max u=6w,1,+9w,2,s.t.w,1,+2w,2,2,2w,1,-3w,2,3,w,1,+2w,2,-1,w,1,w,2,0,对偶问题的性质总结,对偶的对偶就是原始问题,max z=CX,s.t.,AX,b,X 0,min w=,Yb,s.t.A,T,Y,C,Y0,对偶的定义,max u=CW,s.t.AW,C,W,0,maxZ,=x,1,+4x,2,+2x,3,s.t,.5x,1,-x,2,+2x,3,8,x,1,+3x,2,-3x,3,5,x,1,x,2,x,3,0,minw,=8y,1,+5y,2,s.t,.5y,1,+y,2,1,-y,1,+3y,2,4,2y,1,-3y,2,2,y,1,y,2,0,三、非对称形式的原,对偶问题,minz,=2x,1,+3x,2,-5x,3,+x,4,s.t,.x,1,+x,2,-3x,3,+x,4,5,2x,1,+2x,3,-x,4,4,x,2,+x,3,+x,4,=6,x,1,0,x,2,x,3,0,minz,=-2x,1,+3x,2,-5x,3,+(x,4,-x,4,”),s.t.-x,1,+x,2,-3x,3,+(x,4,-x,4,”)5,2x,1,-2x,3,+(x,4,-x,4,”)-4,x,2,+x,3,+(x,4,-x,4,”)6,-x,2,-x,3,-(x,4,-x,4,”)-6,x,1,x,2,x,3,x,4,x,4,”,0,变为对称形式,y,1,y,2,y,3,y,3,”,maxw,=5y,1,-4y,2,+6(y,3,-y,3,”),s.t.-y,1,+2y,2,-,2,y,1,+(y,3,-y,3,”),3,-3y,1,-2y,2,+(y,3,-y,3,”),-5,y,1,+y,2,+(y,3,-y,3,”),1,-,y,1,-y,2,-(y,3,-y,3,”)-1,y,1,y,2,y,3,y,3,”0,写出对偶问题,maxw,=5y,1,+4y,2,+6y,3,s.t,.y,1,+2y,2,2,y,1,+y,3,3,-3y,1,+2y,2,+y,3,-5,y,1,-y,2,+y,3,=1,y,1,0,y,2,0,y,3,无约束,结论,LP(LD),Max,X0,X0,X,无约束,St,st,St=,LD(LP),Min,st,St,St=,Y0,Y0,Y,无约束,min z=2x,1,+4x,2,-x,3,s.t.3x,1,-x,2,+2x,3,6,-x,1,+2x,2,-3x,3,12,2x,1,+x,2,+2x,3,8,x,1,+3x,2,-x,3,15,max w=6y,1,+12y,2,+8y,3,+15y,4,s.t.3y,1,-y,2,+2y,3,+y,4,2,-y,1,+2y,2,+y,3,+3y,4,4,2y,1,-3y,2,+2y,3,-y,4,-1,y,1,0,y,2,y,3,0,y,4,0,=,Free,=,x,1,0,x,2,0,x,3,:Free,原始问题变量的个数,(3),等于对偶问题约束条件的个数,(3),；,原始问题约束条件的个数,(4),等于对偶问题变量的个数,(4),。,原始问题变量的性质影响对偶问题约束条件的性质。,原始问题约束条件的性质影响对偶问题变量的性质。,写对偶问题的练习（,1,）,写对偶问题的练习（,2,）,原始问题,max z=2x,1,-x,2,+3x,3,-2x,4,s.t,.x,1,+3x,2,-2x,3,+x,4,12,-2x,1,+x,2,-3x,4,8,3x,1,-4x,2,+5x,3,-x,4,=15,x,1,0,x,2,:Free,x,3,0,x,4,0,min w=12y,1,+8y,2,+15y,3,s.t,.y,1,2y,2,+3y,3,2,3y,1,+y,2,4y,3,=-1,-2y,1,+5y,3,3,y,1,3y,2,-y,3,-2,y,1,0,y,2,0,y,3,:Free,对偶问题,maxZ,=x,1,-2x,2,+3x,3,s.t,.2x,1,+4x,2,+3x,3,100,3x,1,-2x,2,+6x,3,200,5x,1,+3x,2,+4x,3,=150,x,1,x,3,0,练习,minw,=100y,1,+200y,2,+150y,3,s.t,.2y,1,+3y,2,+5y,3,1,4y,1,-2y,2,+3y,3,=-2,3y,1,+6y,2,+4y,3,3,y,1,0,y,2,0,minZ,=2x,1,+2x,2,+4x,3,s.t,.x,1,+3x,2,+4x,3,2,2x,1,+x,2,+3x,3,3,x,1,+4x,2,+3x,3,=5,x,1,0,x,2,0,maxw,=2y,1,+3y,2,+5y,3,s.t,.y,1,+2y,2,+y,3,2,3y,1,+y,2,+4y,3,2,4y,1,+3y,2,+3y,3,4,y,1,0,y,2,0,课后作业,P64 2.1(a),2.2,对偶问题的基本性质,原始问题,max z=CX,s.t.,AX,b,X 0,对偶问题,min w=,Yb,s.t.A,Y,C,Y,0,1.,弱对偶性,若,X,0,为原问题的可行解，,Y,0,为对偶问题的可行解，则恒有,CX,0,Y,0,b,1.LP,任一可行解的目标函数是其,LD,目标函数值的下界，,反之,LD,任一可行解的目标函数是其,LP,目标函数的上界。,Z=,CXMaxZ,=,MinW,Yb,2.,如,LP,有可行解且目标函数值,无界,，则其,LD,无可行解,；,反之,LD,有可行解且目标函数,无界,，则,LP,无可行解,。,(,对偶问题无可行解时，其原问题无界解或无可行解。,),Z=CX+,Yb,W=,Yb,-CX,3.,若,LP,有可行解而其,LD,无可行解时，,LP,目标函数,无界,反之，若,LD,有可行解而其,LP,无可行解时，,LD,目标函数,无界,。,推论,:(LP-Max LD-Min),2.,最优性,若,X,0,为,LP,的可行解，,Y,0,为,LD,的可行解，且,CX,0,Y,0,b,则,X,0,，,Y,0,分别为,LP,和,LD,的最优解。,3.,强对偶性,若原问题和对偶问题均具有可行解，则两者均具有最优解，且他们的最优解的目标值相等。,4.,互补松弛定理,在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零。,5.,互补的基解,原问题和对偶问题总存在一对互补的基解，且这对互补的基解的目标值相等。,数学模型,Cj,2,1,0,0,0,CB,XB,b,x1,x2,x3,x4,x5,0,x3,15/2,0,0,1,5/4,-15/2,2,x1,7/2,1,0,0,1/4,-1/2,1,x2,3/2,0,1,0,-1/4,3/2,j,0,0,0,-1/4,-1/2,cj,-15,-24,-5,0,0,-M,CB,YB,b,y1,y2,y3,y4,y5,y6,-M,y6,2,0,6,1,-1,0,1,1/3,-15,y1,1/5,1,2/5,1/5,0,-1/5,0,5/2,j,0,6M-18,M-2,-M,-3,0,-24,y2,1/3,0,1,1/6,-1/6,0,1/6,2,-15,y1,1/5,1,0,2/15,1/15,-1/5,-1/15,1/2,j,0,0,1,-3,-3,-M+8,-24,y2,1/4,-5/4,1,0,-1/4,1/4,1/2,-5,y3,1/2,15/2,0,1,1/2,-3/2,-3,j,-15/2,0,0,-7/2,-3/2,-M-3,Z*=8.5,W*=8.5,课后作业,P64 2.4,2.3,影子价格,阐