《运筹学线性规划对偶问题ppt课件》由会员分享，可在线阅读，更多相关《运筹学线性规划对偶问题ppt课件（18页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章 线性规划的对偶实际与灵敏度分析线性规划的对偶实际与灵敏度分析 n线性规划的对偶问题线性规划的对偶问题 n对偶问题的根本性质对偶问题的根本性质n影子价钱影子价钱n对偶单纯形法对偶单纯形法n灵敏度分析灵敏度分析第二节第二节 对偶问题的根本性质对偶问题的根本性质为了便于讨论，下面无妨总是假设：为了便于讨论，下面无妨总是假设：原线性规划问题的矩阵表达式加上松弛变量后为：原线性规划问题的矩阵表达式加上松弛变量后为： 一、单纯形法的矩阵描画一、单纯形法的矩阵描画上式中上式中XsXs为松弛松弛变量，量， ，I I为mmmm单位矩位矩阵。 Cjc1c2cn000CBXBbx1x2xnxn+1xn
2、+2xn+m0xn+1b1a11a12a1n1000xn+2b2a21a22a2n0100xn+mbmam1am2amn001cj-zjc1c2cn000非基变量非基变量基变量基变量XB XNXS0 XS bB NICj-zjCB CN0 单纯形形法法计算算时，总选取取I I为初初始始基基，对应基基变量量为XsXs。设迭迭代代假假设干干步步后后，基基变量量为XBXB，在在初初始始单纯形形表表中中的的系系数数矩矩阵为B B。B B将将在在初初始始单纯形形表表中中单独独列列出出，而而A A中中去去掉掉假假设干干列列后后剩剩下下的的列列组成成矩矩阵N N，这样初初始始单纯形形表表可可列成如下方式。列
3、成如下方式。 非基变量非基变量基变量基变量XB XNXS0 XS bB NICj-zjCB CN0 当迭代假当迭代假设干步后，基干步后，基变量量为XBXB时，那么，那么该步的步的单纯形表中由形表中由XBXB系数系数组成的矩成的矩阵为I I。又因。又因单纯形法的迭代是形法的迭代是对约束增广矩束增广矩阵进展的行的初等展的行的初等变换，对应XSXS的系数矩的系数矩阵在新表中在新表中应为B-1B-1。故当基。故当基变量量为XBXB时，新的，新的单纯形表具形表具有如下方式。有如下方式。 基变量基变量非基变量非基变量XBXN XSCB XB B-1 bIB-1 N B-1 B-1 N B-1 Cj-zj0
4、CN -CB B-1 N -CB B-1 当迭代后基变量为当迭代后基变量为XBXB时，其在初始单纯形表中的系数矩阵为时，其在初始单纯形表中的系数矩阵为B B，那么有：，那么有：1 1对应初始单纯形表中的单位矩阵对应初始单纯形表中的单位矩阵I I，迭代后的单纯形表中为，迭代后的单纯形表中为B-1 B-1 2 2初始单纯形表中基变量初始单纯形表中基变量Xs=bXs=b，迭代后的表中，迭代后的表中 XB= B-1 b XB= B-1 b3 3初始单纯形表中约束系数矩阵为初始单纯形表中约束系数矩阵为 ，迭，迭代后的表中约束系数矩阵为代后的表中约束系数矩阵为(B-1 (B-1 左乘左乘) :) :非基变
5、量非基变量基变量基变量XB XNXS0 XS bB NICj-zjCB CN0基变量基变量非基变量非基变量XBXN XSCB XB B-1 bIB-1 N B-1 B-1 N B-1 Cj-zj0CN -CB B-1 N -CB B-1 4假设初始矩阵中变量假设初始矩阵中变量Xj的系数向量为的系数向量为Pj ，迭代后为，迭代后为 ，那么有，那么有: 5 当当B为为最最优优基基时时，应应有有: 这时从从检验数行看出，假数行看出，假设取其相反数恰好是其取其相反数恰好是其对偶偶问题的一个可行解。的一个可行解。将将这个解代入个解代入对偶偶问题的目的函数的目的函数值，有：，有： 因因XBXB的的检验数可
6、写数可写为: : 那么那么有有称为单纯形乘子，假设称为单纯形乘子，假设令令基变量基变量非基变量非基变量XBXN XSCB XB B-1 bIB-1 N B-1 B-1 N B-1 Cj-zj0CN -CB B-1 N -CB B-1 XN的的检验检验数数 XS的的检验检验数数 XB的检验数的检验数 所以所以XA的检验数的检验数 例例1 1 两个互为对偶的线性规划问题，两者分别加上两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为：松弛和剩余变量后为： 二、原规划与对偶规划问题的变量及解之间的对应关系二、原规划与对偶规划问题的变量及解之间的对应关系两个问题的最终单纯形表见下页：两个问题的
7、最终单纯形表见下页： 原问题变量原问题变量松弛变量松弛变量x1x2x3x4x5x315/20015/415/2x17/21001/41/2x23/20101/43/2000-1/4-1/2对偶问题的剩余变量对偶问题的剩余变量对偶问题变量对偶问题变量y4y5y1y2y3对偶问题变量对偶问题变量对偶问题的剩余变量对偶问题的剩余变量y1y2y3y4y5y21/4 5/4 1 0 1/4 1/4y31/215/2011/23/215/2007/23/2原问题松弛变量原问题松弛变量 x3 x4 x5原问题变量原问题变量x1 x2二、原规划与对偶规划问题的变量及解之间的对应关系二、原规划与对偶规划问题的变
8、量及解之间的对应关系对偶偶(min(min型型) )变量的最量的最优解等于原解等于原问题松弛松弛变量量检验数的数的绝对值对偶偶问题最最优解的剩余解的剩余变量解量解值等于原等于原问题对应变量的量的检验数的数的绝对值由于原由于原问题和和对偶偶问题是相互是相互对偶的，因此偶的，因此对偶偶问题的的检验数与原数与原问题的解也有的解也有类似上述关系。似上述关系。更普通地更普通地讲，不，不论原原问题能否能否规范，在最范，在最优解的解的单纯型表型表中，都有原中，都有原问题虚虚变量量( (松弛或剩余松弛或剩余) ) 的的检验数数对应其其对偶偶问题实变量量 ( (对偶偶变量量) )的最的最优解，原解，原问题实变量
9、量( (决策决策变量量) ) 的的检验数数对应其其对偶偶问题虚虚变量量 ( (松弛或剩余松弛或剩余变量量) )的最的最优解。因此，原解。因此，原问题或或对偶偶问题只需求解其中之一就可以只需求解其中之一就可以了。了。三、线性规划的对偶定理三、线性规划的对偶定理1.弱对偶性弱对偶定理弱对偶性弱对偶定理证明：证明：弱对偶定理推论弱对偶定理推论:max问题问题的任何可行解目的函数的任何可行解目的函数值值是其是其对对偶偶min问标题问标题的函的函数数值值的下限；的下限； min问题问题的任何可行解目的函数的任何可行解目的函数值值是其是其对对偶偶max问标题问标题的函数的函数值值的上限。的上限。假假设设原
10、原问题问题 对对偶偶问题问题 为为无界解，那么其无界解，那么其对对偶偶问题问题 原原问题问题 无可行解。无可行解。假假设设原原问题问题 对对偶偶问题问题 有可行解，其有可行解，其对对偶偶问题问题 原原问题问题 无可无可行解，那么原行解，那么原问题问题 对对偶偶问题问题 为为无界解。无界解。留意：假留意：假设设原原问题问题 对对偶偶问题问题 无可行解，无可行解，对对偶偶问题问题 原原问题问题 具有无界解或无可行解。具有无界解或无可行解。2. 2. 最优性最优解判别定理最优性最优解判别定理证明：设xj*是原问题的最优解， yi*是对偶问题的最优解3.强对偶性对偶定理强对偶性对偶定理定理定理 假假设
11、原原问题和和对偶偶问题都有可行解，那么它都有可行解，那么它们都有最都有最优解，且它解，且它们的最的最优解的目的函数解的目的函数值相等。相等。证：第一步，：第一步，证明都有最明都有最优解。原解。原问题和和对偶偶问题都有可行都有可行解，由弱解，由弱对偶定理推偶定理推论1可知，原可知，原问标题的函数有上界，的函数有上界，对偶偶问题的目的函数有下界，故一定存在最的目的函数有下界，故一定存在最优解。解。 第二步，第二步，证明最明最优解的目的函数解的目的函数值相等。根据相等。根据单纯形法形法的矩的矩阵描画，原描画，原问题有最有最优解，解，对偶偶问题为可行解，且二者可行解，且二者的目的函数的目的函数值相等，根据最相等，根据最优性定理，二者的解均性定理，二者的解均为最最优解。解。4. 互补松弛性互补松弛定理互补松弛性互补松弛定理 在线性规划问题的最优解中，假设对应某一约束条件的对偶在线性规划问题的最优解中，假设对应某一约束条件的对偶变量值为非零的，那么该约束条件取严厉等式；反之假设约束条变量值为非零的，那么该约束条件取严厉等式；反之假设约束条件取严厉不等式，那么其对应的对偶变量一定为件取严厉不等式，那么其对应的对偶变量一定为0。也即。也即
