运筹学概论第章线性规划的对偶理论.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章 线性规划的对偶实际,线性规划的对偶问题,对偶问题的根本性质,影子价钱,第一节 线性规划的对偶问题,窗含西岭千秋雪，门泊东吴万里船,对偶是一种普遍景象,例1 美佳公司方案制造甲、乙两种家电产品，知制造一件甲需占用B设备5小时，调试工序1小时；制造一件乙需占用A设备6小时，B设备2小时，调试工序1小时；A设备每天可用15小时，B设备可用24小时，调试工序每天可用5小时。知售出一件甲获利2元，售出一件乙获利1元，问该公司每天应制造两种家电各多少件，使获取的利润最大？,例2 假设某个公司想把美佳公司的资源购买过来，他至少应付多大的代价，才干使美佳公司情愿放弃消费活动，出让本人的资源。,对偶问题,原问题,一、对偶问题的提出,二、对称方式下对偶问题的普通方式,用矩阵方式表示：,任何线性规划问题都有其对偶问题,对偶问题有其明显的经济含义,例 3,假设有商人要向厂方购买资源A和B，问他们谈判原料价钱的模型是怎样的？,设A、B资源的出卖价钱分别为 y1 和 y2,显然商人希望总的收买价越小越好(目的),工厂希望出卖资源后所得不应比消费产品所得少约束,原问题,对偶问题,A,约束系数矩阵,其约束系数矩阵的转置,b,约束条件的右端项,目的函数中的价值系数向量,C,目的函数中的价值系数向量,约束条件的右端项向量,目的函数,Max z=CX,Min w=Yb,约束条件,AXb,AYC,决策变量,X 0,Y 0,那么xj*(j=1,n)是原问题的最优解，yi*(i=1,m)是其对偶问题的最优解。,B-1 N B-1,y1 y2 y3,资源的市场价钱是知数，相对比较稳定，而它的影子价钱那么有赖于资源的利用情况，是未知数。,0 1/4 1/2,假设原问题和对偶问题都有可行解，那么它们都有最优解，且它们的最优解的目的函数值相等。,2初始单纯形表中基变量Xs=b，迭代后的表中 XB=B-1 b,0 0,假设xj*(j=1,2n)是原问题(max)的可行解，yi*(i=1,2m)是对偶问题(min)的可行解，那么恒有,y4 y5,显然商人希望总的收买价越小越好(目的),资源的影子价钱实践上是一种时机本钱。,x3 x4 x5,0 1/4 3/2,0 -1/4 -1/2,知售出一件甲获利2元，售出一件乙获利1元，问该公司每天应制造两种家电各多少件，使获取的利润最大？,对偶问题的对偶即原问题。同样，可以将对偶问题当作原问题，写出其对偶问题。,课堂练习：,三、非对称方式的原-对偶问题关系,转换为对偶问题的思绪是：先将其转化成对称方式，再按对应关系来写。因例中目的函数为max，故约束条件应换为“号，一切的变量均应“0，,-3x1+x2-6x3-1,x1+x2+x34,-x1-x2-x3-4,x2=-x2；x3=x3-x3,y2=-y2；y3=y3-y3；3式 两端乘“-1，4、5合并。,解：设对偶变量为y1,y2,y3,对偶问题模型为：,Max w=5y1+4y2+6y3,y1+2y2,y1 +y3,-3y1+2y2+y3,y1-y2 +y3,2,3,-5,=1,y10,y20,y3无约束,2,课堂练习：,第二章 线性规划的对偶实际,线性规划的对偶问题,对偶问题的根本性质,影子价钱,第二节 对偶问题的根本性质,为了便于讨论，下面无妨总是假设：,原线性规划问题的矩阵表达式加上松弛变量后为：,一、单纯形法的矩阵描画,上式中Xs为松弛变量，I为mm单位矩阵。,Cj,c1,c2,cn,0,0,0,CB,XB,b,x1,x2,xn,xn+1,xn+2,xn+m,0,xn+1,b1,a11,a12,a1n,1,0,0,0,xn+2,b2,a21,a22,a2n,0,1,0,0,xn+m,bm,am1,am2,amn,0,0,1,cj-zj,c1,c2,cn,0,0,0,非基变量,基变量,XB XN,XS,0 XS b,B N,I,Cj-zj,CB CN,0,单纯形法计算时，总选取I为初始基，对应基变量为Xs。设迭代假设干步后，基变量为XB，在初始单纯形表中的系数矩阵为B。B将在初始单纯形表中单独列出，而A中去掉假设干列后剩下的列组成矩阵N，这样初始单纯形表可列成如下方式。,非基变量,基变量,XB XN,XS,0 XS b,B N,I,Cj-zj,CB CN,0,当迭代假设干步后，基变量为XB时，那么该步的单纯形表中由XB系数组成的矩阵为I。又因单纯形法的迭代是对约束增广矩阵进展的行的初等变换，对应XS的系数矩阵在新表中应为B-1。故当基变量为XB时，新的单纯形表具有如下方式。,基变量,非基变量,XB,XN XS,CB XB B-1 b,I,B-1 N B-1,Cj-zj,0,CN-CB B-1 N -CB B-1,当迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为B，那么有：,1对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1,2初始单纯形表中基变量Xs=b，迭代后的表中 XB=B-1 b,3初始单纯形表中约束系数矩阵为 ，迭代后的表中约束系数矩阵为(B-1 左乘):,非基变量,基变量,XB XN,XS,0 XS b,B N,I,Cj-zj,CB CN,0,基变量,非基变量,XB,XN XS,CB XB B-1 b,I,B-1 N B-1,Cj-zj,0,CN-CB B-1 N -CB B-1,4假设初始矩阵中变量Xj的系数向量为Pj，迭代后为 ，那么有:,5当B为最优基时，应有:,这时从检验数行看出，假设取其相反数恰好是其对偶问题的一个可行解。,将这个解代入对偶问题的目的函数值，有：,因XB的检验数可写为:,那么有,称为单纯形乘子，假设令,基变量,非基变量,XB,XN XS,CB XB B-1 b,I,B-1 N B-1,Cj-zj,0,CN-CB B-1 N -CB B-1,XN的检验数,XS的检验数,XB的检验数,所以,XA的检验数,例1 两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为：,二、原规划与对偶规划问题的变量及解之间的对应关系,两个问题的最终单纯形表见下页：,原问题变量,松弛变量,x1 x2,x3 x4 x5,x3 15/2,0 0,1 5/4 15/2,x1 7/2,1 0,0 1/4 1/2,x2 3/2,0 1,0 1/4 3/2,0 0,0 -1/4 -1/2,对偶问题的剩余变量,对偶问题变量,y4 y5,y1 y2 y3,对偶问题变量,对偶问题的剩余变量,y1 y2 y3,y4 y5,y2 1/4,5/4 1 0,1/4 1/4,y3 1/2,15/2 0 1,1/2 3/2,-15/2 0 0,-7/2 -3/2,原问题松弛变量,x3 x4 x5,原问题变量,x1 x2,二、原规划与对偶规划问题的变量及解之间的对应关系,对偶(min型)变量的最优解等于原问题松弛变量检验数的绝对值,对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值,更普通地讲，不论原问题能否规范，在最优解的单纯形表中，都有原问题虚变量(松弛或剩余)的检验数对应其对偶问题实变量(对偶变量)的最优解，原问题实变量(决策变量)的检验数对应其对偶问题虚变量(松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。,三、线性规划的对偶定理,假设xj*(j=1,2n)是原问题(max)的可行解，yi*(i=1,2m)是对偶问题(min)的可行解，那么恒有,1.弱对偶定理,证明：,弱对偶定理推论:,max问题的任何可行解目的函数值是其对偶min问标题的函数值的下限；min问题的任何可行解目的函数值是其对偶max问标题的函数值的上限。,假设原问题对偶问题为无界解，那么其对偶问题原问题无可行解。,假设原问题对偶问题有可行解，其对偶问题原问题无可行解，那么原问题对偶问题为无界解。,留意：假设原问题对偶问题无可行解，对偶问题原问题或具有无界解或无可行解。,2.最优性最优解判别定理,假设xj*(j=1,n)是原问题的可行解，yi*(i=1,m)是其对偶问题的可行解，且有：,那么xj*(j=1,n)是原问题的最优解，yi*(i=1,m)是其对偶问题的最优解。,3.强对偶性对偶定理,假设原问题和对偶问题都有可行解，那么它们都有最优解，且它们的最优解的目的函数值相等。,例1 两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为：,假设原问题对偶问题为无界解，那么其对偶问题原问题无可行解。,y4 y5,又因单纯形法的迭代是对约束增广矩阵进展的行的初等变换，对应XS的系数矩阵在新表中应为B-1。,min问题的任何可行解目的函数值是其对偶max问标题的函数值的上限。,x1 x2,0 0,0 1/4 3/2,最优性最优解判别定理,资源的市场价钱是知数，相对比较稳定，而它的影子价钱那么有赖于资源的利用情况，是未知数。,1/4 1/4,2初始单纯形表中基变量Xs=b，迭代后的表中 XB=B-1 b,0 1/4 1/2,x3 x4 x5,工厂希望出卖资源后所得不应比消费产品所得少约束,4.互补松弛性互补松弛定理,在线性规划问题的最优解中，假设对应某一约束条件的对偶变量值为非零的，那么该约束条件取严厉等式；反之假设约束条件取严厉不等式，那么其对应的对偶变量一定为0。也即,第二章 线性规划的对偶实际,线性规划的对偶问题,对偶问题的根本性质,影子价钱,例1 美佳公司方案制造甲、乙两种家电产品，知制造一件甲需占用B设备5小时，调试工序1小时；制造一件乙需占用A设备6小时，B设备2小时，调试工序1小时；A设备每天可用15小时，B设备可用24小时，调试工序每天可用5小时。知售出一件甲获利2元，售出一件乙获利1元，问该公司每天应制造两种家电各多少件，使获取的利润最大？,例2 假设某个公司想把美佳公司的资源购买过来，他至少应付多大的代价，才干使美佳公司情愿放弃消费活动，出让本人的资源。,yi*表示资源最优利用条件下对第i种资源的估价,第三节 影子价钱,三种资源的拥有量,对偶问题的经济解释 影子价钱,bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi*的意义是在资源最优利用条件下对单位第i种资源的估价。这种估价不是资源的市场价钱，而是根据资源在消费中作出的奉献而作的估价，为区别起见，称为影子价钱(shadow price)。,资源的市场价钱是知数，相对比较稳定，而它的影子价钱那么有赖于资源的利用情况，是未知数。由于企业消费义务、产品构造等情况发生变化，资源的影子价钱也随之改动。,资源的影子价钱实践上是一种时机本钱。在纯市场经济条件下，当资源市场价钱低于影子价钱时，可以买进这种资源，反之，那么卖出这种资源。,