(简介)线性、对偶规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹与优化,第一章 线性规划与单纯形法,福州大学体育馆,第一章,线性规划与单纯形法,线性规划模型,线性规划的图解,可行域的性质,线性规划的基本概念,线性规划的几何意义,单纯形法,人工变量法,单纯形法的矩阵表示,线性规划的一般模式,LP,的特征,:,一组有待决策的变量，一个线性的,目标函数，一组线性的约束条件。,目标函数：,max(min)Z=c,1,x,1,+c,2,x,2,+c,3,x,3,+,c,n,x,n,约束条件：,a,11,x,1,+a,12,x,2,+a,13,x,3,+a,1n,x,n,(=)b,1,a,21,x,1,+a,22,x,2,+a,23,x,3,+a,2n,x,n,(=)b,2,a,m1,x,1,+a,m2,x,2,+a,m3,x,3,+,a,mn,x,n,(=),b,m,非负性约束,：,x,1,0,x,2,0,x,n,0,可行域是凸集。可行域有有限个顶点,最优值在可行域的某个顶点上达到,无穷多解的情形、无界解情形、无解情形,凸集,凸集,不是凸集,顶点,概 念,可行解：满足所有约束条件的解。,可行域：满足所有约束条件的解的集合，,称为可行域。即可行解的集合。,最优解：使目标函数达到最优值的可行解,.,图解法：例,1,图示,等值线,z=70,x,1,+120,x,2,沿其法向量,n=70,120,移至其极限,位置点,H.,Maxz,=z(20,24),=4280,90 80 60 40 20,0 20 40 60 80 100,x,1,x,2,9x,1,+4x,2,360,4x,1,+5x,2,200,3x,1,+10 x,2,300,A,B,C,D,E,F,G,H,I,Z=70 x,1,+120 x,2,线性规划的标准型,和式：,向量式,:,矩阵,式,:,标准型的特征,目标函数极大化,约束条件为等式,决策变量非负,其中：,价值向量,决策向量,资源向量,系数矩阵,非标准型转化为标准型,目标函数极小化转为极大化：,min,z,=,max(,Z),（,一个数的极小化等价于其相反数的极大化）,不等式约束的转化：,a,ij,x,j,b,i,加入松弛变量,a,ij,x,j,b,i,减去剩余变量,非正变量：即,x,k,0,则令,x,k,=,x,k,自由变量：即,x,k,无约束，令,x,k,=,x,k,x”,k,有界变量,:,即,x,k,(,),v,k,则令,x,k,=(,x,k,v,k,)(,),非标准型转化举例,minZ,=x,1,+2x,2,-3x,3,maxZ,=x,1,2x,2,+3(x,3,x”,3,),x,1,+x,2,+x,3,9,x,1,+x,2,+x,3,x”,3,+,x,4,=9,-x,1,-2x,2,+x,3,2 x,1,2x,2,+x,3,x”,3,x,5,=2,3x,1,+x,2,-3x,3,=5,3x,1,+x,2,3(x,3,x”,3,)=5,x,1,0 x,2,0 x,3,无约束,x,1,0 x,2,0 x,3,0,x”,3,0 x,4,0 x,5,0,基矩阵,基的概念,：,如前所述,LP,标准型,和式：,maxZ,=,c,j,x,j,a,ij,x,j,=,b,j,x,j,0,j=1 n,矩阵式：,maxZ,=CX,s.t.AX=b,X,0.,约束方程的系数矩阵,A,的秩为,m,，且,m,n,.,设,A=(B,N),，,B,是,A,中,m,m,阶非奇异子矩阵，,则称,B,是,LP,的一个基，即,B,是,A,中,m,个线性,无关向量组,。,n,j=1,n,j=1,基解、基可行解,不失一般性,设,B,是,A,的前,m,列，即,B=(p,1,p,2,p,m,）,其相对应的变量,X,B,=(x,1,x,2,x,m,),T,，,称为基变量；其,余变量,X,N,=(x,m+1,x,n,),T,称为非基变量。,B,中,P,j,称为基向量。令所有非基变量等于零,则,X=,（,x,1,x,2,x,m,0,0,),T,称为基解。,基可行解：,满足所有约束条件的基解称为基可行解。,退化的基可行解,：若某个基变量取值为零，则称之为,退化的基可行解。,基最优解：使目标函数达到最优值的基可行解。,基解的数目：最多,=n!/m!(n-m)!,基本定理,定理,1.,（,LP,）,的可行域 是凸集,.,引理,1.,为基可行解 的,正分量所对应的系数列向量线性无关,.,定理,2.x,为（,LP,）,的基可行解 为,S,的顶点,.,引理,2.,若,K,是有界凸集，则 都可表示为,K,的顶点的凸组合,.,定理,3.,若,S,有界，则,（,LP,）,一定在,S,的顶点取到最优,值,.,若,LP,在多个顶点处达到最优,则,(LP),必有,无穷多,最优,解,.,定理,4.,若,(LP),有,可行解,则一定存在基可行解,.,3.4,单纯形表,初始单纯形表：,c,j,c,1,c,2,c,n,i,C,B,X,B,b0,x,1,x,2,.,x,n,b,1,b,2,b,m,a,11,a,12,a,1n,a,21,a,22,a,2n,a,m1,a,m2,a,mn,1,2,m,-,z=-C,B,*b,1,2,n,单纯形表,单纯形表的格式：,C,B,X,B,b,x,B,1,x,B,m,x,j,x,n,x,B,1,x,B,2,x,B,m,b,1,b,2,b,m,1,0 a,1 j,a,1 n,0 0 a,2 j,a,2 n,0 1 a,m j,a,m n,1,2,m,-z=-C,B,*b,0,0,j,n,最优性,判别定理,1.,若 为一基可行解,且对,j=1,2,n,检验数,则 为最优解,.,2.,若 为一基可行,解,且对,j=1,2,n,有,又存在某非基变量的检验数,则,(LP),有无穷多最优解,.,3.,若 为一基可行,解,又存在某检验数 且有,则,(LP),具有无界解,.,4.,若存在某,b,r,0,而,P,k,0,，则,(LP),无界，结束。,否则转下步,4.,根据,max,j,0,=,k,原则,确定,X,k,为,进基变量；根据,规则：,=min,b,i,/a,ik,a,ik,0,=,b,lk,/,a,lk,确定 为出基变量。,5.,以,a,lk,为主元素进行迭代，回到第,2,步。,例,1.,用单纯形法求解,(L):,maxZ,=4X,1,+6X,2,s.t.X,1,5,2X,2,8,2X,1,+3X,2,16,X,1,0,X,2,0,解,:,单纯形表如下,:,c,j,4 6 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,j,0,0,0,X,3,X,4,X,5,5,8,16,1 0 1 0 0,0 2 0 1 0,2 3 0 0 1,_,4,16/3,c,j,4 6 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,j,0,0,0,X,3,X,4,X,5,5,8,16,1 0 1 0 0,0 2 0 1 0,2 3 0 0 1,_,4,16/3,j,0,4 6 0 0 0,0,6,0,X,3,X,2,X,5,5,4,4,1 0 1 0 0,0 1 0 1/2 0,2 0 0 -3/2 1,5,_,2,j,-24,4 0 0 -3 0,0,6,4,X,3,X,2,X,1,3,4,2,0 0 1 3/4 -1/2,0 1 0 1/2 0,1 0 0 -3/4 1/2,j,-32,0 0 0 0 -2,单纯形法的进一步探讨,极小化问题直接求解：所有检验数,j,=,c,j,-,z,j,0,(,或,j,=,z,j,-,c,j,0,),时则为最优,.,无穷多最优解情形：存在最优解且有某个非基变量,的检验数,j,=0.,退化解的情形：有两个以上,值相等,.,人工变量法,1.,大,M,法,:,目标函数中人工变量的价值系数,为,M.,2.,两阶段法：构造目标函数；分阶段求,解,.,线性规划的矩阵表示,.,例,2.,下表是,例,1,的最优表,试求另一个最优解,.,解,:,另一张最优表如下,x,1,x,2,x,3,x,4,x,5,RHS,x,3,x,2,x,1,0,0,1,0,1,0,1,0,0,3/4,1/2,-3/4,-1/2,0,1/2,3,4,2,c,j,-,z,j,0,0,0,0,-2,-32,x,1,x,2,x,3,x,4,x,5,RHS,x,4,x,2,x,1,0,0,1,0,1,0,4/3,-2/3,1,1,0,0,-2/3,1/3,0,4,2,5,c,j,-,z,j,0,0,0,0,-2,-32,单纯形法的矩阵表示,c,j,-,z,j,=c,j,-C,B,B,-1,P,j,称为非基变量的检验数（,Reduced Cost,）：,y,j,=B,-1,P,j,=B,-1,b,z=C,B,B,-1,b.,注,:,初始单纯形表中单位矩阵所在的位置,在每次迭代后的单纯形表中总存放现行基,的逆矩阵,;,松弛变量的检验数为,-C,B,B,-1,.,事实上,(y,s1,y,s2,y,sm,)=B,-1,(P,s1,P,s2,P,sm,)=B,-1,I,m,=B,-1,0-C,B,(y,s1,y,s2,y,sm,)=-C,B,B,-1,最优单纯形表,B,-1,-C,B,B,-1,I,O,运筹与优化,第二章,对偶问题与灵敏度分析,福州大学体育馆,第二章 对偶问题与灵敏度分 析,对偶问题,原问题与对偶问题的关系,对偶问题的基本性质,对偶单纯形法,对偶问题的经济解释,灵敏度分析,DUAL,对偶规则,原问题一般模型：对偶问题一般模型：,maxz,=CX min,=,Yb,(L)AX,b (2.1);(DL)YA C (2.2),X 0 Y 0,maxz,=CX min,=,Yb,(L)AX,=b (2.3);(DL)YA C (2.4),X 0 Y,无符号约束,(2.1),与,(2.2),为对称形式的对偶,.,(2.3),与,(2.4),为非对称形式的对偶,.,对偶规则,原问题,有,m,个约束条件，对偶问题有,m,个变量,.,原问题有,n,个变量，对偶问题,有,n,个约束条件,.,原问题的价值系数对应对偶问题的右端项,.,原问题的右端项对应对偶问题的价值系数,.,原问题的技术系数矩阵转置后为对偶问题的系数矩阵,.,极大化问题的约束型与极小化问题的变量符号方向相反,.,原问题与对偶问题优化方向相反,.,对偶规则,原问题,对偶问题,目标函数,max,min,目标函数,约束条件,=,变量符号,无约束,变量符号,无约束,约束条件,=,例题,1,minz,=3x,1,+2x,2,-6x,3,+x,5,2x,1,+x,2,-4x,3,+x,4,+3x,5,7,x,1,+2x,3,x,4,4,-x,1,+3x,2,x,4,+x,5,=-2,x,1,，,x,2,，,x,3,0;,x,4,0,x,5,无限制,.,max,=7y,1,+4y,2,-2y,3,s.t.2y,1,+y,2,y,3,3,y,1,+3y,3,2,-4y,1,+2y,2,-6,y,1,y,2,y,3,0,3y,1,+y,3,=1,y,1,0 ,y,2,0,y,3,无约束,.,对偶问题的基本性质,1.,对称性：对偶问题的对偶问题是原问题,.,注：,任何线性规划问题都具有唯一的对偶问题,.,2.,弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行的目标函数值,即,C X,Yb,.,3.,无界性：若原问题为无界解,则对偶问题无可行解,.,若,(L),可行,则,(L),有无界解的充要条件是,(DL),无可行解,.,注：,原问题无可行解时,其对偶问题或具有无界解,或无可行解,.,4.,最优性准则：若,X,Y,分别为,(L),和,(DL),的可行解,且,C X=,Yb,，,则,X,Y,分别为,(L),和,(DL),的最优解,.,5.,对偶定理：若一个问题有最优解，则另一问题也,有最优解，且目标函数值相等,.,若原问题最优基为,B,，,则其对偶问题最优解,Y*=C,B,B,-1,.,6.,互补松弛,:,(L),和,(DL),的可行解,X,Y,为最优解的充要,条件是,YXs,=0,YsX,=0.,7.(2.1),的检验数的反数是,(2,2),的一个基解,其对应关系,见下表,:,6.,设,x,、,y,分别是,(2.1),和,(2.2),的可行解,那么,x,、,Y,都是,最优解的充分必要条件是,对所有,i,和,j,下列关系成立,:,(1).,若,则,;(,其中,P,j,是,A,的第,j,列,),(2).,若,则,;,(3).,若,则,;(,其中,A,i,是,A,的第,i,行,),(4).,若,则,.,例,2.,已知线性规划,(L):,其,(DL),的最优解,为,(4/5,3/5),，,试求,(L),的最优解,.(,书,P,59,)(1,0,0,0,1),T,1,、原始问题是利润最大化的生产计划问题,对偶问题的,经济解释,2,、对偶问题,原始和对偶问题都取得最优解时，,最大利润,max z=min y,对偶问题是资源定价问题，对偶问题的最优解,w,1,、,w,2,、,.,、,w,m,称为,m,种资源的,影子价格,3,、资源影子价格的性质,影子价格,:,（边际利润）,影子价格越大，说明这种资源越是相对紧缺,影子价格越小，说明这种资源相对不紧缺,如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于,0,;,若资源的影子价格,0,表明该资源已耗尽,.,4,、产品的机会成本,机会成本,表示减少一件产品所节省的资源可以增加的利润,5,、产品的差额成本,差额成本,=,机会成本,-,利润,6,、互补松弛关系的经济解释,在利润最大化的生产计划中,（,1,）边际利润大于,0,的资源没有剩余,（,2,）有剩余的资源,其边际利润等于,0,（,3,）安排生产的产品，其机会成本等于利润,（,4,）机会成本大于利润的产品不安排生产,对偶单纯形法在什么情况下使用：,应用前提：有一个基，其对应的基本解满足,单纯形表的检验,数,全部非正（对偶可行）,;,变量取值可,以,有负数（非可行解）。,*注：,通过矩阵行变换运算，使所有相应,变量取值均为非负数即得到最优单纯性表。,对偶单纯形法,对偶单纯形法计算步骤,1,、建立初始对偶单纯形表，对应一个基本解，所有检验数均非正，转,2,；,2,、若,b,0,，,则得到最优解，停止；否则，若有,b,r,0,则选,r,行的基变量,x,Br,为出基变量,转,3,；,3,、若所有,a,rj,0(j=1,2,n),，,则原问题无可行解，停止；否则，若有,a,rj,0,则选,=,min,j,/,a,rj,a,rj,0,b,r,Min-b,i,/,ir,ir,0,=,Max-6/1,-(13/3)/(1/3)=-6,Min-b,i,/,i3,i3,0,则,将原最优表中,1,用,1,取代，得下,表,:,继续单纯形法的计算,.,得下,表,:,2).,x,2,x,B,时最优解不变,.,最优解,x=(x,1,x,2,x,3,)=(0,6,0),w=C,B,B,-1,=(c,2,0),最优值,z=,C,B,B,-1,b=12+6(c,2,-2)=6c,2,。,3),c,2,=0,1,由,2),知,B,非最优基,将原,最优表中第,r=1,行的,-,c,2,=-(0-2),倍加到检验行,并取,2,=,0,继续单纯形,法计算,.,得,:,最优解,x=(,x,1,x,2,x,3,)=(0,0,6),w=(,w,1,w,2,)=(1,0),最优值,maxz,=min=6,技术矩阵,A,中元素发生变化：,假设,p,j,变为,P,j,（只讨论,N,中某一列变化情况）,则计算,P*,j,=B,-1,P,j,j,=,c,j,-,C,B,B,-1,P,j,填入最优单纯形表，若,j,0,则最优解不变；,否则，进一步用单纯形法求解。,增加一个新约束,增加一个新约束后，应把原最优解代入新的约束，,若满足则最优解不变，否则填入最优单纯形表作为新的,一行，引入,1,个新的非负变量,若约束为“”型的，则两,边乘,(-1),，并通过矩阵行变换把对应基变量的元素列变,为单位列，再用单纯形法或对偶单纯形法求解。,如例,1,，增加,-3x,1,+x,2,+6x,3,17,，原最优解,x=,（,1/3,，,0,，,13/3,）,不满足这个约束。,于是将约束方程,-3x,1,+x,2,+6x,3,+x,7,=17,的系数置于原最优,表，求解过程如下：,由上表知,新问题的最优解,x,*,=(5/3,0,11/3),最优值,minf,=-13,