原问题、对偶问题、一对对偶问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 线性规划的对偶理论,线性规划问题具有对偶性，即任何一个求极大值的线性规划问题，都有一个求极小值的线性规划问题与之对应，反之亦然,原问题、对偶问题、一对对偶问题,对偶理论（,Duality Theory,）,dju(:),liti,研究对偶问题之间的关系及其解的性质,根据对偶理论，在解原问题的同时，也可以得到对偶问题的解，并且还可以提供影子价格等有价值的信息，在经济管理中有着广泛的应用,为什么研究对偶理论？,对偶问题可能比原问题容易求解,对偶问题还有很多理论和实际应用的意义,1,对偶问题的一般概念,2,对偶问题的基本性质,3,对偶问题的解,4,对偶问题的经济解释,影子价格,5,对偶单纯形法,6,原始,对偶单纯形法,1,对偶问题的一般概念,对偶问题的提出,对偶问题的形式,1.1,对偶问题的提出,资源的合理利用问题，即充分利用资源生产两种产品,大规模定制生产时代，充分利用资源生成所需的产品,对外提供加工服务，收取加工费,存在一个矛盾,自己要赚钱，定价越高越好,定价太高，别人不找你,折中,保证不亏的前提下，对方的支出最少,例1,甲,乙,限额,材料,2,3,32,工时,4,5,23,利润（元,/,件）,10,20,问题,假设不是安排生产，而是出售材料，出租工时，问如何定价，可使工厂获利不低于安排生产所获得的利益，且又能使这些定价具有竞争力,解决,设,出售材料的定价为每单位,y,1,元,出租工时的定价为每工时,y,2,元,1.2,对偶问题的形式,对称型对偶问题,非对称型对偶问题,混合型对偶问题,1.,对称型对偶问题,定义,1,矩阵形式,原,问题,对偶问题,增加内容,对偶规则,给每个原始约束条件定义一个非负对偶变量,y,i,(,i,=1,2,m,);,使原问题的目标函数系数,c,j,变为其对偶问题约束条件的右端常数；,使原问题约束条件的右端常数,b,i,变为其对偶问题目标函数的系数；,将原问题约束条件的系数矩阵转置，得到其对偶问题约束条件的系数矩阵；,改变约束条件不等号的方向，即将“,=”,；,原问题“,max”,型，对偶问题为“,min”,型,例3,2.,非对称型对偶问题,例,4,对偶规则,原问题第,k,个约束为等式，对偶问题第,k,个变量是自由变量。,原问题第,k,个变量是自由变量，则对偶问题第,k,个约束为等式约束。,3.,混合型对偶问题,对偶约束,另外，我们把约束条件分为行约束（变量的线性组合的等式或不等式约束）和变量的符号约束两部分，而以原问题的行约束与对偶问题的变量一一对应，原问题的变量与对偶问题的行约束一一对应，并且将对应的一对约束称为一对对偶约束,例5,例3,用矩阵理论讨论对偶问题,设原问题：,可用另一形式：,X,B,X,N,X,S,X,B,X,N,X,S,表示线性规划问题已得到最优解,.,令,则由,(4),有,由,(2),和,(3),有,故有,因为,而,Y,的上限无限大,所以只存在最小值,.,由上讨论,可得另一个线性规划问题,:,称为原线性规划问题 的对偶规划问题。,原问题,Prime Problem,对偶问题,Dual Problem,原问题与对偶问题的对应关系,原问题求极小,-,原问题约束方程有“,”-,两边同乘（,-1,），“,”,原问题约束方程有“,=”-,对偶问题？,2,对偶问题的基本性质,对称性,弱对偶性,无界性,最优性,强对偶性,互补松弛性,解的对应性,产品,A,，,B,产量,X,1,，,X,2,，,Z,为利润,例,1,、,3X,1,+X,2,+X,3,=48,3X,1,+4X,2,+X,4,=120,X,1,X,4,0,maxZ,=,5X,1,+6X,2,3X,1,+X,2,48,3X,1,+4X,2,120,X,1,X,2,0,机器台时,劳动工时,X=(8,24),T,Z=184,5 6 0 0,X,1,X,2,X,3,X,4,X,B,0 5 6 0 0,0 X,3,48 3 1 1 0,0 X,4,120 3 (4)0 1,180 1/2 0 0 -3/2,0 X,3,18 (9/4)0 1 -1/4,6 X,2,30 3/4 1 0 1/4,184 0 0 -2/9 -13/9,5 X,1,8,1 0 4/9 -1/9,6 X,2,24 0 1 -1/3 1/3,3y,1,+3y,2,5,y,1,+4y,2,6,minW,=48y,1,+120y,2,3y,1,+3y,2,-y,3,+y,5,=5,y,1,+4y,2,-y,4,+y,6,=,6,minW,=48y,1,+120y,2,+My,5,+My,6,48 120 0 0,M,M,y,1,y,2,y,3,y,4,y,5,y,6,y,B,11,M,48-4,M 120-7M,M,M,0 0,M,y,5,5 3 3 -1 0 1 0,M,y,6,6 1,4 0 -1 0 1,y,B,180+1/2,M,18-9/4,M,0,M,30-3/4,M,0 -30+7/4,M,M y,5,1/2 9/4 0 -1 3/4 1 -3/4,120,y,2,3/2,1/4,1,0 -1/4 0,1/4,y,B,184 0 0 8 24,M,-8,M-24,48,y,1,2/9 1,0 -4/9 1/3 4/9 -1/3,120 y,2,13/9 0 1 1/9 -1/3 -1/9 1/3,y=(2/9,13/9),Z=184,观察结论,:,一对对偶问题都有最优解，且目标函数值相等。,最优表中有两个问题的最优解。,对称性,定理,1,（对称性定理）,对偶问题的对偶是原问题。,弱,对偶性,定理,2,（弱对偶性）,证明,推论,1,最大化问题的任一个可行解的目标函数值都是其对偶最小化问题目标函数的下界；,最小化问题的任一个可行解的目标函数值都是其对偶最大化问题目标函数的上界。,无界性,推论,2,若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。,逆命题不成立。,在一对对偶问题,P,和,D,中，当其中一个问题无可行解时，则另一个问题或者目标函数无界，或者无可行解。,推论,3,在,一对对偶问题,P,和,D,中，若一个可行，而另一个不可行，则该可行的问题无界。,例1,例2,例3,最优性,定理,3,（最优性判别定理）,证明,定理,1,对称性定理,定理,2,弱对偶性定理,定理,3,最优性判别定理,定理,4,主对偶定理,定理,5,互补松弛定理,强对偶性,定理,4,（主对偶理论）,若一对对偶问题都有可行解，则它们都有最优解，且目标函数的最优值必相等。,证明,根据弱对偶性定理，有,所以，,P,有最优解,所以，,D,有最优解,根据最优性判别定理，,Y*,也是最优解,推论,4,原问题有最优解，那末对偶问题也有最优解，且目标函数值相等。,一对对偶问题的关系,两个问题都有可行解，从而都有最优解,一个问题为无界解，另一个问题必无可行解,两个问题都无可行解,互补松弛性,定理,5,（互补松弛定理）,设,X,*,和,Y,*,分别是,P,和,D,的,可行解，则它们分别是最优解的充要条件是,互补松弛条件,互补松弛条件,互补松弛关系（松紧关系）,若原,问题最优解第,i,个约束方程为严格的不等式，则对偶问题最优解中第,i,个对偶变量取值必为,0,松,约束与紧约束,把某一可行点处的严格不等式约束（包括对变量的非负约束）称为松约束,不起作用约束,把严格等式约束称为紧约束,起作用约束,结论,即对于最优解,X,*,和,Y,*,而言，松约束的对偶约束是紧约束,注意：是先松后紧！,推论,5,设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束,松紧关系的实际意义,在计算上，若已知一个问题的最优解，则可利用互补松弛条件求另一个问题的最优解,w,1,w,i,w,m,w,m+1,w,m+j,w,n+m,x,1,x,j,x,n,x,n+1,x,n+i,x,n+m,对偶问题的变量 对偶问题的松弛变量,原始问题的变量 原始问题的松弛变量,x,j,w,m+j,=0,w,i,x,n+i,=0(i=1,2,m;j=1,2,n),在一对变量中，其中一个大于,0,，另一个一定等于,0,max z=3x,1,+4x,2,-x,3,s.t.4x,1,+2x,2,+5x,3,38,-x,1,+3x,2,-x,3,18,2x,1,-x,2,+3x,3,26,3x,1,+x,2,-2x,3,10,x,1,x,2,x,3,0,min y=38w,1,+18w,2,+26w,3,+10w,4,s.t.4w,1,-w,2,+2w,3,+3w,4,3,2w,1,+3w,2,-w,3,+w,4,4,5w,1,-w,2,+3w,3,-2w,4,-1,w,1,0,w,2,0,w,3,0,w,4,0,|,变量,|,松弛变量,|,(,x,1,x,2,x,3,x,4,x,5,x,6,x,7,),(,0,19,0,0,39,45,9,),(,2,0,0,0,5,0,11,),(,w,1,w,2,w,3,w,4,w,5,w,6,w,7,),|,变量,|,松弛变量,|,互补松弛关系,+x,4,=38,-x,5,=18,+x,6,=26,-x,7,=10,x,4,x,5,x,6,x,7,0,-w,5,=3,-w,6,=4,-w,7,=-1,w,5,w,6,w,7,0,原始问题,对偶问题,原始问题的每一个变量和对偶问题相应的松弛变量组成互补松弛对，每一对变量中至少有一个等于,0,。,对偶问题的每一个变量和原始问题相应的松弛变量组成互补松弛对，每一对变量中至少有一个等于,0,。,例4,先松后紧！,非,对称对偶问题的互补松弛条件,设,X,*,和,Y,*,分别是一对非对称对偶问题的可行解，则它们分别是最优解的充要条件是下式成立,Why?,对于非对称形式的对偶问题，因为此时,Y*,无正负限制，所以只有一个成立,混合型对偶问题,定理,1,5,成立,例5,结论,如果,D,易求，可以通过求,D,来讨论,P,若,D,无界，则,P,无解,若求得,D,的最优解,Y,*,，,最优值为,W,*,，,则利用互补松弛条件可求得,P,的最优解,X,*,，,并且,P,的,最优值为,Z,*,=,Y,*,b,解的,对应性,推论,对于对称形式的原问题，若有最优解，则在其最优单纯形表中，松弛变量,的检验数,的负值即为对偶问题的一个最优解,非,基变量,基变量,X,B,X,N,X,S,C,B,X,B,B,-1,b,B,N,I,j,C,B,C,N,O,基变量,非基变量,X,B,X,N,X,S,C,B,X,B,B,-1,b,I,B,-1,N,B,-1,j,O,C,N,-C,B,B,-1,N,-C,B,B,-1,非,基变量,基变量,X,B,X,N,X,S,C,B,X,B,B,-1,b,B,N,I,j,C,B,C,N,O,单纯形乘子定理,若,P,有最优解，最优基为,B,，则,Y,=,C,B,B,-1,就是其对偶问题,D,的一个最优解。,3,对偶问题的解,能否通过求解原问题来找出对偶问题的解，或者相反,互补松弛条件就可以由原问题的最优解可以直接求出其对偶问题的最优解,求,P,的,X*,PDD,的解,Y*P,的解,X*,利用原问题的最优单纯形表求对偶最优解,例,1,为了求得对偶最优解,Y,*,只需将初始基变量（包括人工变量）在原问题的目标函数中相应的系数,(,如果是人工变量，则系数为,M,）,减去对应的检验数,j,即可,例2,2.,利用改进单纯形表求对偶最优解,所谓单纯形乘子就是现在所说的对偶最优解,因此，通过改进单纯形法的计算过程，就可以找到对偶最优解,特别是在用改进单纯形表进行计算时，单纯形乘子已经记录下来,.,当迭代到最后，就可从最终改进单纯形表上查到对偶最优解,例,3,结论,究竟是解它的原问题还是解它的对偶问题比较省事,一般说来，求解一个线性规划问题的计算量，是同这个问题所含约束条件的个数有密切关系的若约束条件的个数愈多，则基可行解中基变量的个数也随之增多，相应地确定主元和迭代变换的计算量也愈大根据经验，单纯形法的选代次数大约是约束条件的,l,1,5,倍,因此，当,m=0,时，即正则解,满足原始可行性条件,时，就找到了原问题,P,的,最优解,对偶单纯形法的定义,是,基于对偶问题的对称性,所设计的,求解原问题,的一种方法。,对偶单纯形法的,基本思想,是在,保持对偶问题的可行性,的基础上，逐步迭代，,当原问题也达到可行时,，同样表示也达到了,最优,。,在,单纯形表中,进行迭代时，在,b,列得到的是,原问题的基可行解,，而在检验数行列得到的是,对偶问题的基解,，通过逐步迭代，当在检验数行得到,对偶问题的解也是基可行解时,，已得最优解。,根据对称性，若,保持对偶问题的解是基可行解,，而原问题在,非基可行解,的基础上，通过逐步迭代达到,基可行解,，这也得到了,最优解,。,对偶单纯形法的,优点,是,求解,原问题的初始解,不一定是基可行解,，在对偶可行的前提下，可以,非基可行解开始迭代,。因此，对有些问题使用起来比较方便（,灵敏度分析,）。这时,不需要加入人工变量,，因此可以简化计算。,原始单纯形法,保持解的可行性,不变,由,不小于等于,0,到小于等于,0,对偶问题的解由不可行到可行,对偶单纯形法,始终,保持对偶问题解的可行性,原问题的解,由不可行到可行,一旦可行，即最优,对偶单纯形法的,优点,当,变量多于约束条件,时，对这样的,LP,问题，,用对偶单纯形法,可以减少计算工作量，因此对变量较少而约束条件很多的,LP,问题，可以先将它变换成对偶问题，然后用对偶单纯形法求解。,在,灵敏度分析,中，有时需要用对偶单纯形法，这样可使问题的处理简化。,对偶单纯形法的,局限性,对,大多数,LP,问题，,很难找到一个初始可行基,。因而这样方法在求解,LP,问题时，,很少单独使用,。,但,要求初始解满足正则性（对偶可行性）,构造一个扩充问题,对偶单纯形法的,基本措施,对偶单纯形法所使用的表格与原单纯形法一样，,不同之处,：,保证,j,=0,迭代也基本一致,不同之处,：,先选,出,基变量,后选,进,基变量,选出基变量,选,进基变量,定理,5.2,对偶单纯形法的迭代步骤,5.2,对偶单纯形法的迭代步骤,5.2,对偶单纯形法的迭代步骤,例1,5.3,初始正则解的求法,对偶单纯形法初始基的确定,检验数中有正数,出现，,X(0),不是正则解,则,增加一个约束,例2,Why,？,