第2章 对偶理论与灵敏度分析

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 对偶理论与灵敏度分析,讲授：郝海,日期：,2006-10,目 录,1,线性规划的对偶问题,2,对偶问题的基本性质,3,影子价格,4,对偶单纯形法,5,灵敏度分析,6,对偶的经济解释,线性规划的对偶问题,一、相关概念,二、对偶问题的提出,三、对偶问题的定义,四、对偶关系对应表,相 关 概 念,转置矩阵：,将一个,m,n,矩阵,A,的行换成同序数的列而得到的新矩阵，称为矩阵,A,的转置矩阵，记为,A,T,。,逆矩阵：,设有,n,阶方阵,A,，,如果存在,n,阶,方阵,B,，,满足,AB=BA=E,，,则称,A,阵是可逆的，,B,是,A,的逆矩阵，记做,B=A,-1,。,相 关 概 念,相 关 概 念,矩阵的运算：,矩阵的加法，矩阵的减法，,矩阵的乘法,对偶问题的提出,美佳公司利用该公司资源生产两种家电产品。,I,II,每天可用 能力,设备,A,（,h,）,设备,B,（,h,）,调试工序（,h,）,0,6,1,5,2,1,15,24,5,利润（元）,2,1,设：,y,1,表示单位时间（,h,）,设备,A,的出让代价；,y,2,表示单位时间（,h,）,设备,B,的出让代价,;,y,3,表示调试工序的出让代价。,已知：美佳公司用,6,小时设备,A,和,l,小时调试可生 产一件家电,I,，,盈利,2,元；用,5,小时设备,A,，,2,小时设备,B,及,14,小时调试可生产一件家电,II,，,盈利,1,元。,由此,y,1,，,y,2,，,y,3,的取值应满足,:,该公司希望用最小代价把美佳公司的全部资源收买过来。,因此，线性规划模型为：,LP2,原问题,对偶问题,LP2,(2 1),x,1,x,2,0 5,2,1 1,15,24,5,x,1,x,2,0 6 1,5 2 1,2,1,y,1,y,2,y,3,(15 24 5),y,1,y,2,y,3,LP2,对偶问题的定义,原始问题,max z=CX,s.t.AX b,X 0,对偶问题,min W=,b,T,Y,s.t. A,T,Y,C,T,Y 0,C,T,A,T,b,T,min,m,n,max,b,A,C,m,n,对偶理论的基本思想,每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题的解的时候，也同时给出了另一个问题的解。,对偶单纯形法,基本原理,决策变量的检验数可写成：,C,B,B,-1,称为单纯形乘子,非基变量,基,变量,X,B,X,N,X,S,0 X,S,b,B N,I,c,j,z,j,C,B,C,N,0,基变量,非基变量,X,B,X,N,X,S,C,B,X,B,B,-1,b,I,B,-1,N B,-1,C,j,z,j,0,C,N,-C,B,B,-1,N -C,B,B,-1,C -C,B,B,1,A0,-C,B,B,1,0,A,y,C,y,0,若令,y,= C,B,B,-1,则,显然,y,= C,B,B,-1,是其对偶问题的可行解,，即,原问题检验数的相反数恰好是其对偶问题的一个可行解！,代入,对偶问题,min W=,b,T,y,s.t. A,y,C,y,0,得：,C -C,B,B,1,A0,-C,B,B,1,0,y,A,C,y,0,也就是说,：当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值，对偶问题的解也为最优解,.,将这个解代入对偶问题的目标函数值，有：,原问题的松弛变量对应着其对偶问题的决策变量！,基变量,非基变量,X,B,X,N,X,S,C,B,X,B,B,-1,b,I,B,-1,N B,-1,c,j,z,j,0,C,N,-C,B,B,-1,N -C,B,B,-1,互为对偶问题变量的对应关系,原,问题变量,松弛变量,x,1,x,2,x,3,x,4,x,5,x,3,15/2,x,1,7/2,x,2,3/2,0 0,1 0,0 1,1 5/4 -15/2,0 1/4 -1/2,0 -1/4 3/2,c,j,-z,j,0 0,0 -1/4 -1/2,对偶问题变量,对偶问题剩余变量,y,1,y,2,y,3,y,4,y,5,y,2,1/4,y,3,1/2,5/4 1 0,15/2 0 1,-1/4 1/4,1 /2 -3/2,c,j,-z,j,-15/2 0 0,-7/2 -3/2,对偶问题的剩余变量,y,4,y,5,对偶问题变量,y,1,y,2,y,3,原问题的松弛变量,x,3,x,4,x,5,原问题变量,x,1,x,2,原问题最终表,对偶问题最终表,若存在对偶问题的一个可行基,B,，,只要令,X,B,B,-1,b 0,则原问题也有可行解,且,同为最优解,。,互为对偶问题变量的对应关系可以看出：,只需要求出原问题（对偶问题）的最优解，从最优解的单纯形表中就可以同时得到其对偶问题（原问题）的最优解。,对偶单纯形法的基本原理,例1,1 2,加工能力,(,小时,/,天,),A 2 2 12,B 1 2 8,C 4 0 16,D 0 4 12,2 3,销售收入,产品,设备,写出原问题与对偶问题,设,x,1,，,x,2,为产品,1,，,2,的产量,2x,1,+2x,2,12,x,1,+2x,2,8,4x,1,16,4x,2,12,x,1,x,2,0,maxZ,=,2x,1,+3x,2,(2 3),C,x,1,x,2,X,2 2,1 2,4 0,0 4,A,x,1,x,2,X,12,8,16,12,b,设 ：,y,1,y,2,y,3,y,4,分别为单位时间内出让,A, B, C, D,设备的单价,y,1,y,2,y,3,y,4,2y,1,+y,2,+4y,3, 2,2y,1,+2y,2,+y,4, 3,y,1, y,4,0,minW,=12y,1,+8y,2,+16y,3,+12y,4,minW,=,b,T,y,y,1,y,2,y,3,y,4,(12 8 16 12 ),b,T,A,T,y,C,T,2 1 4 0,2 2 0 4,A,T,2,3,C,T,maxZ,=,2x,1,+3x,2,2x,1,+2x,2,12,x,1,+2x,2,8,4x,1,16,4x,2,12,x,1,x,2,0,2x,1,+2x,2,12,x,1,+2x,2,8,4x,1,16,4x,2,12,x,1,x,2,0,maxZ,=,2x,1,+3x,2,2y,1,+y,2,+4y,3, 2,2y,1,+2y,2,+y,4, 3,y,1, y,4,0,minW,=12y,1,+8y,2,+16y,3,+12y,4,原问题,对偶问题,写出下面问题的对偶规划,例2,maxZ,=,5x,1,+6x,2,3x,1,2x,2,=7,4x,1,+x,2,9,x,1, x,2,0,3x,1,2x,2,=7,3x,1,2x,2,7,3x,1,2x,2,7,-3x,1,+2x,2,-7,3x,1,2x,2,7,-3x,1,+2x,2,-7,4x,1,+x,2,9,x,1, x,2,0,y,1,y,1,y,2,对偶问题,令,y,1,=,y,1,-y,1,minW,=7y,1,-7y,1,+9y,2,3y,1,-3y,1,+4y,2,5,-2y,1,+2y,1,+y,2,6,y,1, y,1, y,2,0,minW,=7y,1,+9y,2,3y,1,+4y,2,5,-2y,1,+y,2,6,y,1,自由, y,2,0,3y,1,-2y,1,7y,1,对偶关系对应表,原,(,对偶,),问题 对偶,(,原,),问题,目标函数类型,max min,目标函数系数 目标函数系数 右边项系数,与右边项的对应关系 右边项系数 目标函数系数,变量数与约束数 变量数,n,约束数,n,的对应关系 约束数,m,变量数,m,原问题,变量,类型与 变量,0,约束,对偶问题,约束,类型 变量,0,约束,的对应关系 变量无限制 约束,原问题,约束,类型与 约束,变量,0,对偶问题,变量,类型 约束,变量,0,的对应关系 约束,变量,无限制,minW,=7y,1,+9y,2,3y,1,+4y,2,5,-2y,1,+y,2,6,y,1,无限制, y,2,0,maxZ,=,5x,1,+6x,2,3x,1,2x,2,=7,4x,1,+x,2,9,x,1, x,2,0,原问题,对偶问题,请,写出以下问题的对偶问题,maxZ,=180y,1,+60y,2,+240y,3,S.t. y,1,+2y,2,+5y,3,3,2y,1,-3y,2,+3y,3,9,3y,1,+y,2,=4,y,1,无约束,y,2,0,y,3,0,若,x,是原问题的可行解，,y,是对偶问题的可行解。则有,cx,y,b,二,.,弱对偶性：,对偶问题的基本性质,一,.,对称性 ：,对偶问题的对偶是原问题,推论,(1),： 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,推论,(2),： 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。注 ： 其逆不成立。,推论,(3),：,若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界，反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,弱对偶性的三个推论,A,Z=W,B,设,x,是原问题的可行解，,y,是对偶问题的可行解。,当,cx,=,y,b,时,x,y,是最优解。,三,.,最优性,若原问题及其对偶问题均具有可行解，则两者均具有最优解且它们最优解的目标函数值相等。,四,.,强对偶性（对偶定理）,五,.,互补松弛性（松紧定理）,在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也即：,五,.,互补松弛性（松紧定理）,在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也即：,推论,(3),：,若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界，反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,证明：,1.,证明原问题有可行解,2.,写出其对偶问题：,-1,y,1,-1,y,2,0,1,）说明原问题和对偶问题都有最优解,.,2,）求原问题和对偶问题的最优目标函数值的一个上界和下界,.,四,.,强对偶性（对偶定理）,若原问题及其对偶问题均具有可行解，则两者均具有最优解且它们最优解的目标函数值相等。,推论,(1),： 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,1.,证明原问题有可行解,解：,1,）说明原问题和对偶问题都有最优解,.,2.,对偶问题有可行解：,2,）求原问题和对偶问题的最优目标函数值的一个上界和下界,.,用,互补松弛定理计算对偶问题的最优解,互补松弛定理,:,在线性规划问题的最优解中，,已知原问题,影子价格,式中,b,i,是线性规划原问题约束条件的右端项，它代表第,i,种资源的拥有量；对偶变量,y,i,*,的意义代表在资源最优利用条件下对单位第,i,种,资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格,(shadow price),。,几点,说明：,1,资源的影子价格是未知数，有赖于企业资源状况。,2,影子价格是一种边际价格,相当于在资源得到最优利用的生产条件下，每增加一个单位时目标函数,z,的增量。,3,资源的影子价格实际上又是一种机会成本。,4,生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。,5,对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定资源的恰当估价。,对偶单纯形法,基本思路,：在迭代过程中保持原问题的检验数为非正，逐步替换负基变量，从而得到最优解。,即保持对偶问题有可行解,使,原问题具有可行解,检验数为非正,替换负基变量,对偶单纯形法计算步骤,1.,列出初始单纯形表，且,检验数非正,。,2. b,值有否为负，无，计算结束。有，转,3,5.,以,a,rs,为主元素，进行迭代变换。,6 .,返,3,，直到,b 0,为止。,用对偶单纯形法求解下述线性规划问题,例,化标准型：,整理得：,解：,Cj,15,24,5,0,0,C,B,y,B,b,y,1,y,2,y,3,y,4,y,5,0,y,4,2,0,-6,-1,1,0,0,y,5,1,-5,-2,-1,0,1,j,=,c,j,-z,j,24,y,2,1/3,0,1,1/6,-1/6,0,0,y,5,-1/3,-5,0,-2/3,-1/3,1,j,=,c,j,-z,j,-15,-24,-5,0,0,-15,0,-1,-4,0,24,y,2,1/4,-5/4,1,0,-1/4,1/4,-5,y,3,1/2,15/2,0,1,1/2,-3/2,j,=,c,j,-z,j,-15/2,0,0,-7/2,-3/2,在得到原始可行解时同时得到对偶可行解，已获得最优解：,（,y,1, y,2, y,3, y,4, y,5,）,=,（,0,1/4, 1/2,0,0,）,max w=17/2,对偶问题的最优解为：,（,x,1, x,2, x,3,）,=,（,7/2, 3/2, 15/2,）,min z=17/2,例,:(,初始解原始、对偶都不可行的问题,),C,j,3,2,2,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,4,1,1,1,1,0,0,0,x,5,5,2,3,1,0,1,0,0,x,6,2,2,2,1,0,0,1,j,=,c,j,-z,j,3,2,2,0,0,0,先解决对偶可行性,0,x,3,4,1,1,1,1,0,0,0,x,5,9,1,2,0,-1,1,0,0,x,6,2,1,1,0,1,0,1,j,=,c,j,-z,j,5,0,0,-2,0,0,已得到对偶可行解，再用对偶单纯形法求解,C,j,3,2,2,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,2,x,3,17/2,1/2,0,1,3/2,-1/2,0,-2,x,2,9/2,-1/2,1,0,1/2,-1/2,0,0,x,6,5/2,1/2,0,0,1/2,1/2,1,j,=,c,j,-z,j,5,0,0,-2,0,0,0,x,3,6,0,0,1,2,0,1,0,x,2,7,0,1,0,0,1,1,0,x,1,5,0,1,0,0,1,1,j,=,c,j,-z,j,0,0,0,-7,5,10,在得到原始可行解时同时得到对偶可行解，已获得最优解：,（,x,1, x,2, x,3, x,4, x,5, x,6,）,=,（,5, 7, 6, 0, 0, 0,）,minz,=17,对偶问题的最优解为： （,y,1, y,2, y,3,）,=,（,7,5, 10,）,即（,y,1, y,2, y,3,）,=,（,7,5, 10,）,maxw,=17,对偶单纯形法中出现的一些情况,2.,对偶单纯形法与原始单纯形法的比较：,1.,对于对偶问题有可行解，而原问题无可行解的判断。,项目,原始单纯形法,对偶单纯形法,选,主元素,按列选主元,按行选主元,确定主元素,a,rj,0,a,rj,1,时，表中为,-1/4+1/4,0,，,x,4,入基，,x,3,出基。,b.,当, ,0,，,x,5,入基，,x,2,出基。,2+ 1+2 0 0 0,0,2+,1+2,0 0 0 -1/4+1/4 -1/2-5/2,x,4,6,2,3,4/5,-1/5,1/5,1,0,0,-6,1,0,0 0 1/5-1/5 0 -2-,显然，当,1,时，,当前表检验数均取负值，即当前解为最优解，且,z,7,8,。,2+ 1+2 0 0 0,0,2+,0,0 0 0 -1/4+1/4 -1/2-5/2,15,4,1,x,5,5,1/3,2/3,0,1/6,1/6,0,0,1,0 1/3,5/3 0 -1/3-1/6 0,2+ 1+2 0 0 0,0,2+,0,0 0 0 -1/4+1/4 -1/2-5/2,15,4,1,x,5,5,1/3,2/3,0,1/6,1/6,0,0,1,0 1/3,5/3 0 -1/3-1/6 0,当,1/3+5/3,0,，,-1/3-1/6,0,当前解为最优解，即：,当,2,1,/5,时，表中为最优解，且,z,8,4 ,当,0,则，,x,4,入基，,x,1,出基,2+ 1+2 0 0 0,0,0,0,0 0 0 -1/4+1/4 -1/2-5/2,15,24,5,x,5,5,2,1,0,1,0,0,0,1,2, 1,2 0 0 0,0,6,1,显然，当,-2,时，,当前表检验数均取负值，且,z,0,。,Z,（,）随,值变化的情况图,作 业,P61,：,2.7,2.9,