第三章-对偶单纯形法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运 筹 帷 幄 之 中,决 胜 千 里 之 外,对偶理论与灵敏度分析,第二章 对偶理论与灵敏度分析,第一节对偶问题的提出,第二节线性规划的对偶理论,第三节对偶问题的经济解释,第四节对偶单纯形法,【,例,2-1】,某家电厂利用现有资源生产两种产品，有关数据如下表：,设备,A,设备,B,调试工序,利润（元）,0,6,1,2,5,2,1,1,15,时,24,时,5,时,产品,产品,D,第一节 对偶问题的提出,如何安排生产，,使获利最多,？,厂,家,设,产量,产量,设：设备,A,元时,设备,B,元时,调试工序,元时,承租,付出的代价最小，,且对方能接受。,出让代价应不低于,用同等数量的资源,自己生产的利润。,设备,A,设备,B,调试工序,利润（元）,0,6,1,2,5,2,1,1,15,时,24,时,5,时,D,厂家能接受的条件：,出让代价应不低于,用同等数量的资源,自己生产的利润。,收购方的意愿：,厂,家,对,偶,问,题,原,问,题,承,租,厂,家,一对对偶问题,第二节 线性规划的对偶理论,一,原问题与对偶问题的关系,二,对偶问题的基本性质,一,原问题与对偶问题的关系,1,对称式的对偶,“”,不等式约束条件的原问题与“”不等式约束条件的对偶问题，称为,对称式,的一对对偶问题。,原问题：,max,z,=,c,1,x,1,+,c,2,x,2,+,c,n,x,n,a,11,a,12,a,1n,a,m1,a,m2,a,mn,x,1,x,n,b,1,b,m,x,1,，,x,2,，,，,x,n,0,对偶问题：,min,=,b,1,y,1,+,b,2,y,2,+,b,m,y,m,a,11,a,12,a,1,n,a,m,1,a,m,2,a,mn,y,1,，,y,2,，,，,y,m,0,(,y,1,y,2,y,m,),(,c,1,c,2,c,n,),max,z,=,CX,AX,b,X,0,min,=,Yb,YA,C,Y,0,n,个变量，,m,个约束条件,m,个变量，,n,个约束条件,2,约束条件全部为“,=”,的对偶,max,z,=,CX,AX,b,X,0,原问题：,max,z,=,CX,AX,b,X,0,AX,b,等价,max,z,=,CX,AX,b,X,0,AX,b,max,z,=,CX,X,0,A,A,X,b,b,min,=(,Y,1,Y,2,),Y,1,Y,2,0,A,A,C,b,b,(,Y,1,Y,2,),其中,Y,1,=(,y,1,y,2,y,m,),，,Y,2,=(,y,m,+1,y,m,+2,y,2,m,),等价,等价,min,=,Yb,Y,为无约束,YA,C,min,=(,Y,1,Y,2,),b,Y,1,Y,2,0,(,Y,1,Y,2,),A,C,令,Y,=(,Y,1,Y,2,),对偶问题,对偶问题,3,约束条件为“”的对偶,max,z,=,CX,AX,b,X,0,原问题：,max,z,=,CX,AX,b,X,0,min,=,Y,1,(,b,),Y,1,(,A,),C,Y,1,0,min,=,Yb,YA,C,Y,0,等价,对偶问题,令,Y,=,Y,1,对偶问题,4,变量,0,的对偶,max,z,=,CX,AX,b,X,0,原问题：,令,X,=,X,1,max,z,=,C,(,X,1,),A,(,X,1,),b,X,1,0,max,z,=(,C,),X,1,(,A,),X,1,b,X,1,0,等价,min,=,Y b,Y,(,A,),C,Y,0,min,=,Y b,Y,A,C,Y,0,对偶问题,对偶问题,等价,5,变量无约束的对偶,max,z,=,CX,AX,b,X,无约束,原问题：,令,X,=,X,1,X,2,X,1,，,X,2,0,max,z,=,CX,1,CX,2,X,1,X,2,0,AX,1,AX,2,b,max,z,=(,C,C,),X,1,X,2,0,b,X,1,X,2,(,A,A,),X,1,X,2,等价,min,=,Yb,Y,0,Y,(,A,A,)(,C,C,),对偶,min,=,Yb,YA,C,Y,0,YA,C,min,=,Yb,YA,C,Y,0,min,=,Yb,YA,C,Y,0,YA,C,等价,等价,等价,对偶问题,6,原问题与对偶问题的关系表,原问题（或对偶问题）,对偶问题（或原问题）,目标函数,max,z,n,个变量,变量,0,变量,0,变量无约束,目标函数,min,n,个约束条件,约束,约束,约束,=,m,个约束条件,约束,约束,约束,=,约束条件右端项,目标函数变量系数,m,个变量,变量,0,变量,0,变量无约束,目标函数变量系数,约束条件右端项,【,例,2-2】,试求下述线性规划问题的对偶问题,（,P,）与,(D),的关系对应表：,原,(,对偶,),问题,对偶,(,原,),问题,目标函数,max,目标函数,min,目标函数系数,约束方程常数列,约束方程常数列,目标函数系数,变量个数,n,约束方程个数,n,约束方程个数,m,变量个数,m,约束方程,变量,0,0,=,无符号约束,变量,0,约束方程,0,无符号约束,=,系数矩阵,A,解：,（,P,）与,(D),的关系对应表：,原,(,对偶,),问题,对偶,(,原,),问题,目标函数,max,目标函数,min,目标函数系数,约束方程常数列,约束方程常数列,目标函数系数,变量个数,n,约束方程个数,n,约束方程个数,m,变量个数,m,约束方程,变量,0,0,=,无符号约束,变量,0,约束方程,0,无符号约束,=,系数矩阵,A,【,例,2-3】,试求下述线性规划原问题的对偶问题,解：原问题的对偶问题,【,课堂练习,】,（,P,）与,(D),的关系对应表：,原问题,对偶问题,目标函数,max,目标函数,min,目标函数系数,约束方程常数列,约束方程常数列,目标函数系数,变量个数,n,约束方程个数,n,约束方程个数,m,变量个数,m,约束方程,变量,0,0,=,无符号约束,变量,0,约束方程,0,无符号约束,=,系数矩阵,A,构建对偶问题的规则,原始问题的 目标,对偶问题,目标,约束类型,变量符号,最大化,极小化,=,无限制,最小化,极大化,=,无限制,要求：,1,、将所有约束转换成等式；,2,、将所有决策变量转换成大于等于。,回顾：原问题与对偶问题的关系表,原问题（或对偶问题）,对偶问题（或原问题）,目标函数,max,z,n,个变量,变量,0,变量,0,变量无约束,目标函数,min,n,个约束条件,约束,约束,约束,=,m,个约束条件,约束,约束,约束,=,约束条件右端项,目标函数变量系数,m,个变量,变量,0,变量,0,变量无约束,目标函数变量系数,约束条件右端项,二,对偶问题的基本性质,1,对称性：,对偶问题的对偶问题是原问题。,2,弱对偶性：,若,X,(0),是原问题的可行解，,Y,(0),是对偶问题的可行解，则存在,CX,(0),Y,(0),b,。,3,无界性：,若原问题无界解，则其对偶问题无可行解。,4,最优性：,若,X,(0),是原问题的可行解，,Y,(0),是对偶问题的可行解，且,C X,(0),=Y,(0),b,，则,X,(0),，,Y,(0),是最优解。,5,对偶定理：,若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。,6,互补松弛性：,若,X,(0),是原问题的可行解，,Y,(0),是对偶问题的可行解，则,YsX,(0),=0,和,Y,(0),Xs=0,当且仅当,X,(0),，,Y,(0),是最优解。,其中,X,s,和,Y,s,分别为原问题和对偶问题的松弛变量的可行解,.,【,例,2-4】,已知线性规划问题,min,w,=2x,1,+3x,2,+5x,3,+2x,4,+3x,5,x,1,+x,2,+2x,3,+x,4,+3x,5,4,2x,1,-x,2,+3x,3,+x,4,+x,5,3,x,j,0,，,j=1,，,2,，,，,5,已知其对偶问题的最优解为,y,1,*,=4/5,，,y,2,*,=3/5,；,z=5,。,试用对偶理论找出原问题的最优解。,【,例,2-4】,已知线性规划问题,解：先写出它的对偶问题,max z=4y,1,+3y,2,y,1,+2y,2,2 ,y,1,-y,2,3 ,2y,1,+3y,2,5 ,y,1,+y,2,2 ,3y,1,+y,2,3 ,y,1,，,y,2,0,【,例,2-4】,已知线性规划问题,将,y,1,*,=4/5,y,2,*,=3/5,的值代入约束条件，,得,=1/53,，,=17/55,，,=7/52,它们为严格不等式；由互补松弛性得,x,2,*,=x,3,*,=x,4,*,=0,。,因,y,1,，,y,2,0,；,原问题的两个约束条件应取等式，故有,x,1,*,+3x,5,*,=4,，,2x,1,*,+x,5,*,=3,求解后得到,x,1,*,=1,x,5,*,=1,；,故原问题的最优解为,X,*,=(1,，,0,，,0,，,0,，,1),T,；,w,*,=5,1,、,原始问题是利润最大化的生产计划问题,单位产品的利润（元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（吨,/,件）,剩余的资源（吨）,消耗的资源（吨）,第三节 对偶问题的经济解释,2,、,对偶问题,资源限量（吨）,资源价格（元,/,吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解,y,1,、,y,2,、.、,y,m,称为m种资源的,影子价格,（,Shadow Price,）,原始和对偶问题都取得最优解时，最大利润 max z=min w,3,、,资源影子价格的性质,从对偶定理可知,，当达到最优解时，原问题和对偶问题的目标函数值相等，即,z=CX,(0),=Y,(0),b=C,B,B,-1,b.,也即,z=CX,(0),=Y,(0),b=C,B,B,-1,b=y,1,(0),b,1,+y,2,(0),b,2,+y,m,(0),b,m,其中,X,(0),Y,(0),分别是原问题和对偶问题的最优解。,现在考虑在最优解处,，常数项,b,i,的微小变动对目标函数值的影响,(,不改变原来的最优基,).,求,z,对,b,i,的偏导数，可得：,y,1,(0),z,b,1,y,2,(0),z,b,2,y,m,(0),z,b,m,这说明,，若原问题的某一约束条件的右端常数项,b,i,增加一个单位，则由此引起的最优目标函值的增加量，就等于该约束条件相对应的对偶变量的最优值。,最优变量,y,i,(0),的值,，就相当于对单位第,I,种资源在实现最大利润时的一种估价。这种估价是针对具体企业具体产品而存在的一种特殊价格，称它为“,影子价格,”。,【,例,1-3】,求下列问题的最优解。,影价格及其经济解释,第四节 对偶单纯形法,6,(LP),的检验数的相反数对应于,(DP),的一个基解,，其中第,j,个决策变量,x,j,的检验数的相反数对应于,(DP),中第,j,个松弛变量,y,sj,的解，第,i,个松弛变量,x,si,的检验数的相反数对应于第,i,个对偶变量,y,i,的解。,s,0,Y,s1,C,N1,C,B,B,-1,N,1,Y,s2,C,B,B,-1,Y,二,对偶问题的基本性质,【,例,2-4】,线性规划,（,1,）用单纯形方法求最优解；,（,2,）求每步迭代对应对偶问题的基本解。,c,j,6,-2,1,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,0,x,4,x,5,2,4,2,1,1,0,2,4,1,0,0,1,j,6,-2,1,0,0,6,0,x,1,x,5,1,3,1,0,1/2,1/2,1,3,1/2,-1/2,0,1,j,0,1,-5,-3,0,6,-2,x,1,x,2,4,6,1,0,0,1,4,6,0,-1,1,2,j,0,0,-11,-2,-2,1,2,3,解：,原问题与对偶问题解之间的对应关系指出：,在单纯形表中进行迭代时，在,b,列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。,通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，已得到最优解。即原问题与对偶问题都是最优解。,根据对偶问题的对称性，可以这样考虑：若保持对偶问题的解是基可行解，即,c,j,C,B,B,-1,P,j,0,，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。,设原问题为,max,z,=,CX,AX,=,b,X,0,又设,B,是一个基。不失一般性，令,B,=(,P,1,，,P,2,，,，,P,m,),，它对应的变量为,X,B,=(,x,1,，,x,2,，,x,m,),。当非基变量都为零时，可以得到,X,B,=,B,-1,b,。若在,B,-1,b,中至少有一个负分量，设,(,B,-1,b,),i,0,，并且在,单纯形表的检验数行中的检验数都为非正,，即对偶问题保持可行解。,每次迭代是将基变量中的负分量,x,l,取出，去替换非基变量中的,x,k,，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。,2,对偶单纯形法的计算步骤,列出初始单纯形表,最优性检验,根据线性规划问题，确定一个,对偶可行的基解,，列出初始单纯形表。,检查,b,列的数，若都为非负，则已得到最优解。停止计算。若,b,列的数中，还有分量为负数，则进行下一步计算。,确定换出变量,按,min(B,-1,b),i,|(B,-1,b),i,0,，则无可行解，停止计算。,如果 有,a,lj,0(,j=1,2,n),则计算,c,k,z,k,min,c,j,z,j,a,lj,|,a,lj,a,lk,确定,x,k,为换入 变量，且保持得到的对偶问题的解是基可行解。,迭代运算,以,a,lk,为主元素，对单纯形表进行迭代运算，得到新单纯表。,重复,【,例,2-5】,用对偶单纯形法求解,x,1,+2x,2,+x,3,3,2 x,1,x,2,+3x,3,4,min,=,2 x,1,+3x,2,+4x,3,x,1,x,2,x,3,0,x,1,2x,2,x,3,+,x,4,=3,2 x,1,+x,2,3x,3,+x,5,=4,max,z=,2 x,1,3x,2,4x,3,x,1,x,2,x,3,x,4,x,5,0,解：,c,j,2,3,4,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,0,x,4,x,5,3,4,1,2,2,1,1,3,1,0,0,1,j,2,3,4,0,0,1,4/3,其中,x,4,x,5,为松弛变量,c,j,2,3,4,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,2,x,4,x,1,1,2,0,1,5/2,1/2,1/2,3/2,1,0,1/2,1/2,j,0,4,1,0,1,8/5,2,c,j,2,3,4,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,3,2,x,2,x,1,2/5,11/5,0,1,1,0,1/5,7/5,2/5,1/5,1/5,2/5,j,0,0,9/5,8/5,1/5,原最优,X,*,=(11/5,2/5,0,0,0),T,，对偶最优,Y,*,=(8/5,1/5),从以上求解过程可以看到对偶单纯形法有以下优点：,(1),初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。,(2),当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。,(3),在灵敏度分析及,求解整数规划的割平面法中,，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，,很难找到一个对偶问题初始可行基,，因而这种方法在求解线性规划问题时很少单独应用。,对偶单纯形法的计算步骤,（,min,）,列出初始单纯形表,最优性检验,根据线性规划问题，确定一个对偶可行的基解，列出初始单纯形表。,检查,b,列的数，若都为非负，则已得到最优解。停止计算。若,b,列的数中，还有分量为负数，则进行下一步计算。,确定换出变量,按,min(B,-1,b),i,|(B,-1,b),i,0,，则无可行解，停止计算。,如果 有,a,lj,0(,j=1,2,n),则计算,c,k,z,k,max,c,j,z,j,a,lj,|,a,lj,a,lk,确定,x,k,为换入 变量，且保持得到的对偶问题的解是基可行解。,迭代运算,以,a,lk,为主元素，对单纯形表进行迭代运算，得到新单纯表。,重复,【,例,2-6】,用对偶单纯行法求解,初始单纯形表,1600,2500,400,0,0,0,0,-4,-3,-2,-2,-5,-2.5,-1,0,1,0,0,1,0,1600,2500,400,0,0,-,800,-,500,-,400,第一次迭代,1600,2500,400,0,0,400,0,4,-3,2,-2,5,-2.5,1,0,-1,0,0,1,1600,800,500,0,400,0,-,400,-,200,第二次迭代,1600,2500,400,0,0,400,2500,-2,1.2,-2,0.8,0,1,1,0,-1,0,2,-0.4,2200,400,0,0,400,200,-,200,-,400,第三次迭代,1600,2500,400,0,0,1600,2500,1,0.4,1,0,0,1,-0.5,0.4,0.5,-0.4,-1,0.4,2600,0,0,200,200,600,原问题最优解,由互补松弛定理，容易识别原问题的最优解,。,作业,p75 2.8 (1),结 束,