IE10_OR06 CH2 线性规划的对偶理论与灵敏度分析1

第,*,页,西南科技大学制造科学与工程学院工业工程与设计系 石宇强,运筹学,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,*,页,西南科技大学制造科学与工程学院工业工程与设计系 石宇强,运筹学,第,*,页,西南科技大学制造科学与工程学院工业工程与设计系 石宇强,运筹学,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,*,页,西南科技大学制造科学与工程学院工业工程与设计系 石宇强,运筹学,第,*,页,西南科技大学制造科学与工程学院工业工程与设计系 石宇强,运筹学,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,6,讲 目 录,第一章 软件运用补充、总结、习题讲解,CH2,线性规划的对偶理论与灵敏度分析,2.1,线性规划的对偶问题,2.2,对偶问题的基本性质,2.3,影子价格,2.4,对偶单纯形法,2.5,灵敏度分析,2.6,参数线性规划,软件运用补充,用软件求解线性规划问题,(,演示,),Lindo,Excel Solver,北理工软件,第,1,章 线性规划与单纯形法 （小结）,1.,线性规划的概念,（,1,）线性规划模型的构成,决策变量,目标函数,：,max(min)Z(,是决策变量的线性函数）,约束条件,：,s.t.,（满足于含决策变量的线性等式或不等式）,（,2,）一般形式：,max=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,j,0;j=1,2,n,b,i,0;i=,1,2,m,(3),标准形式,线性规划的标准形式有如下四个特点：,目标最大化；,约束为线性等式；,决策变量均非负；,右端项非负。,(4),剩余变量、松驰变量及意义,2.,有关线性规划解的概念,(1),概念：凸集、可行解、可行域、最优解、最优值、基、基变量、基解、基可行解、可行基、最优基。,(2),可行域、基解、基可行解、最优基的关系。,3.,图解法,图解法的步骤：,(1),建立直角坐标系,(2),图示约束条件、找出可行解,(3),图示代表目标函数的直线及目标函数值增加（或减小）的方向,(4),找出最优解,4.,单纯形法,(1),理论基础,定理,若,LP,问题可行域存在，则可行域是凸集合,定理,LP,问题的基可行解与可行域顶点一一对应,定理,若,LP,问题存在最优解，则一定存在一个基可行解是最优解,(2),单纯形法计算步骤,线性规划求解流程图,5.,大,M,法与二阶段法,(1),大,M,法,人工变量在目标函数中的系数确定：若目标函数为,maxZ,，则系数为,-M,；否则为,M,计算方法：单纯形法,(2),二阶段法,第一阶段,：求解一个目标函数仅含人工变量，且为极小化的线性规划问题，其最优表有两种情况：,目标函数最优值为,0,则去掉人工变量转为第二阶段,目标函数最优值不为,0,则原问题无可行解，停止计算,第二阶段,：去掉第一阶段中的人工变量，将第一阶段得到的最优解作为初始基可行解，利用单纯形法继续进行迭代，直至求出原问题最优解,习题,1.7,(2),(4),2.1,线性规划的对偶问题,一、问题的提出,例,1,某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：,试拟订使总收入最大的生产方案。,资源单耗 产品,资源,甲 乙,资源限量,煤,电,油,9 4,4 5,3 10,360,200,300,单位产品价格,7 12,资源单耗 产品,资源,甲 乙,资源限量,煤,电,油,9 4,4 5,3 10,360,200,300,单位产品价格,7 12,例,2,这时有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少。试建立购买者的线性规划模型。,例,2,称为例,1,的,对偶问题,，记为（,D,），例,1,称为例,2,的,原问题,记为（,P,）。,资源单耗 产品,资源,甲 乙,资源限量,煤,电,油,9 4,4 5,3 10,360,200,300,单位产品价格,7 12,例,2,称为例,1,的,对偶问题,，记为（,D,），例,1,称为例,2,的,原问题,记为（,P,）。,LP OPTIMUM FOUND AT STEP 1,OBJECTIVE FUNCTION VALUE,1)428.0000,VARIABLE VALUE REDUCED COST,X1 20.000000 0.000000,X2 24.000000 0.000000,ROW SLACK OR SURPLUS DUAL PRICES,2)84.000000 0.000000,3)0.000000 1.360000,4)0.000000 0.520000,NO.ITERATIONS=1,LP OPTIMUM FOUND AT STEP 1,OBJECTIVE FUNCTION VALUE,1)428.0000,VARIABLE VALUE REDUCED COST,Y1 0.000000 84.000000,Y2 1.360000 0.000000,Y3 0.520000 0.000000,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 -20.000000,3)0.000000 -24.000000,NO.ITERATIONS=1,2.1,线性规划的对偶问题,二、对称形式下对偶问题的一般形式,（,P,）,（,D,）,这是最常见的对偶模型形式，称为,对称式对偶模型,。二者间具有十分对称的对应关系：,原问题（,P,）,对偶问题（,D,）,目标,max,型,目标,min,型,有,n,个变量（非负）,有,n,个约束（大于等于）,有,m,个约束（小于等于）有,m,个变量（非负）,价格系数,资源向量,资源向量 价格系数,技术系数矩阵 技术系数矩阵的转置,对称形式：互为对偶,(LP)Max,z,=,c,T,x,(DP)Min,f,=,b,T,y,s.t.,Ax,b,s.t.,A,T,y,c,T,x,0,y,0,“,Max-,”,“,Min-,”,min,b,A,C,T,C,A,T,b,T,max,m,n,m,n,2.1,线性规划的对偶问题,三、非对称形式下的原,-,对偶问题关系,原问题（,P,）对偶问题（,D,）,第,i,个约束为等式约束 第,i,个变量为自由变量,第,j,个变量为自由变量 第,j,个约束为等式约束,参考,P52,表,2-2,原问题,Max,（对偶问题）,对偶问题,Min,（原问题）,约束条件数,=m,变量个数,=m,第,i,个约束条件为“”,第,i,个约束条件为“”,第,i,个约束条件为“,=”,第,i,个变量,0,第,i,个变量,0,第,i,个变量无限制,变量个数,=n,约束条件个数,=n,第,i,个变量,0,第,i,个变量,0,第,i,个变量无限制,第,i,个约束条件为“”,第,i,个约束条件为“”,第,i,个约束条件为“,=”,第,i,个约束条件的右端项,目标函第,i,个变量的系数,目标函数第,i,个变量的系数,第,i,个约束条件的右端顶,归纳对称形式与非对称形式的对偶,原问题与对偶问题之间的关系如下表所示,例,3,：写出下面线性规划的对偶规划模型：,例,4,写出下面线性规划的对偶规划模型,再根据非对称形式的对应关系，直接写出对偶规划,解 先将约束条件变形为,“,”,形式,2.2,对偶问题的基本性质,一、单纯形法的矩阵描述,max=CX,s.t.AX=b,X0,A=B,N,C=(C,B,C,N,),X=,则有,:,max=C,B,X,B,+C,N,X,N,x.t.BX,B,+NX,N,=b,X,B,X,N,0,X,B,=B,-1,b-B,-1,NX,N,=C,B,(B,-1,b-B,-1,NX,N,)+C,N,X,N,=C,B,B,-1,b+(C,N,-C,B,B,-1,N)X,N,X,B,X,N,单纯形表,Z X,B,X,N,0 I B,-1,N B,-1,b,1 0 C,N,-C,B,B,-1,N -C,B,B,-1,b,补充：矩阵形式的单纯形表,加入松驰变量化为标准形,设,C=,（,C,B,C,N,),A=(B,N),代入,(2),得,:,(2),将基变量从目标函数中消除,建立对应于基,B,的矩阵形式的单纯形表,T,（,B,）：,C,C,B,C,N,C,S,b,X,B,X,N,X,S,X,B,B,-1,b,I,B,-1,N,B,-1,Z,-C,B,B,-1,b,0,C,N,-C,B,B,-1,N,C,B,B,-1,B,-1,A,C-C,B,B,-1,A,b,X,X,B,B,-1,b,B,-1,A,Z,-C,B,B,-1,b,C-C,B,B,-1,A,化简为如下简单的表格形式,:,2.2,对偶问题的基本性质,1.,对称性,（,P,）与（,D,）互为对偶。,对偶问题的对偶问题是原问题,（,P,）,（,D,）,二、对偶问题的基本性质,2,弱,对偶定理,对偶问题,(min),的任何可行解,Y,0,，,其目标函数值总是不小于原问题,(max),任何可行解,X,0,的目标函数值,几何意义：,CX,Yb,弱,对偶定理推论,max,问题的任何可行解目标函数值是其对偶,min,问题目标函数值的下限；,min,问题的任何可行解目标函数值是其对偶,max,问题目标函数值的上限,如果原,max(min),问题为无界解，则其对偶,min(max),问题无可行解,如果原,max(min),问题有可行解，其对偶,min(max),问题无可行解，则原问题为无界解,3,最优解判别,定理,若原问题的某个可行解,X,0,的目标函数值与对偶问题某个可行解,Y,0,的目标函数值相等，则,X,0,Y,0,分别是相应问题的最优解,.,证：由弱对偶定理推论,1,，结论是显然的。,即,CX,0,=,Y,0,b,CX,Y,0,b,=,CX,0,Yb,。,证毕。,4,主对偶,定理,如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。,5.,对偶定理 若（,P,）,有最优解，则（,D,）,也有最优解，且最优值相同。,证：对（,P,）增加松弛变量,Xs,，化为,设其最优基为,B,，终表为,其检验数为,问题：,(1),由性质,5,可知，对偶问题最优解的表达式,Y*,=,？,(2),求,Y*,是否有必要重新求解（,D,）？,C,B,B,-1,不必。可以从原问题（,P,）,的单纯形终表获得。,例如，已知,的终表为,请指出其对偶问题的最优解和最优值。,6.,互补松驰性,(,松紧定理,),：若,X,，,分别是,(P),(D),问题的可行解，那么,X,为最优解的充要条件是：,X,S,=0,Y,S,X=0,(,即若,A,i,X,i,=0,A,i,X=b,i,0,P,j,=C,j,0,P,j,C,j,=X,j,=0),例 已知线性规划问题,已知其对偶问题的最优解为 用对偶理论求原问题的最优解。,解 先写出它的对偶问题,min,将 代入对偶问题的约束条件，得第,2,3,4,个约束条件为严格不等式，第,1,、,5,个约束条件为严格等式，由互补松驰性得 ；又因 ，原问题的两个约束条件应取等式，故有,max,求解后得 ；故原问题的最优解为,7.,原问题单纯形表的检验数行对应其对偶问题的一个基解,.,其对应关系见表：,X,B,X,N,X,S,0 C,N,-C,B,B,-1,N -C,B,B,-1,Y,S1,Y,S2,-Y,Y,S1,为对应原问题中基变量,X,B,的剩余变量，,Y,S2,是对应原问题中非基变量,X,N,的剩余变量,设,B,是原问题的一个基本可行基，则,A=(B,N),max=C,B,X,B,+C,N,X,N,BX,B,+NX,N,+X,S,=b,X,B,X,N,X,S,0,相应地对偶