运筹学2.3对偶理论.ppt

《运筹学2.3对偶理论.ppt》由会员分享，可在线阅读，更多相关《运筹学2.3对偶理论.ppt（38页珍藏版）》请在第壹文秘上搜索。

1、 2.3 对偶理论OR第二章 线性规划Exp.:考虑第一章考虑第一章(引言引言)中所讲的奶制品加工的例子中所讲的奶制品加工的例子.不考虑生产者自己生产不考虑生产者自己生产,而是将各种资源而是将各种资源(牛奶牛奶,工人工人,设备设备)承包给别人承包给别人.试问试问:生产者应该如何给资源定价生产者应该如何给资源定价?分析分析:设设分别表示分别表示每桶牛奶每桶牛奶每小时加工时间每小时加工时间设备甲每小时加工能力设备甲每小时加工能力三种资源的承包价格三种资源的承包价格123yyyNote:由于设备乙加工能力过剩由于设备乙加工能力过剩,在承包时不考虑其收费在承包时不考虑其收费.OR第二章 线性规划考虑承

2、包后获得的利润不得小于直接生产获得的利润考虑承包后获得的利润不得小于直接生产获得的利润:1桶牛奶桶牛奶&12h加工时间加工时间&设备甲设备甲3千克加工能力生产千克加工能力生产A1可获得利润可获得利润 72元元12312372yyy 1桶牛奶桶牛奶&8h加工时间加工时间&生产生产A2可获得利润可获得利润 64元元12864yy当上述条件满足时当上述条件满足时,承包获得的收入不低于直接生产的收入承包获得的收入不低于直接生产的收入 再考虑原来的生产者如何能将生产资源承包出去再考虑原来的生产者如何能将生产资源承包出去,即要考虑即要考虑 对方容易接受的问题对方容易接受的问题,对方的支出为对方的支出为:1

3、2350490100yyyOR第二章 线性规划 从原来的生产者考虑从原来的生产者考虑,越大越好越大越好.但从市场竞争的角度但从市场竞争的角度而言而言,定价越低越有利于竞争定价越低越有利于竞争.于是得该问题的数学模型于是得该问题的数学模型:12312312123min50490100s.t.12372864,0yyyyyyyyyyy 这也是一个这也是一个 LP问题问题,我们称其为原我们称其为原Exp1中问题的中问题的对偶对偶问题问题.相应的相应的,原来的规划称为原来的规划称为原始线性规划原始线性规划.原问题与对偶问题是同一组数据参数原问题与对偶问题是同一组数据参数,只是位置有所不同只是位置有所不

4、同.两者实际上是从两种角度描述同一个问题两者实际上是从两种角度描述同一个问题.且且:maxmin00 价值系数价值系数 右端向量右端向量形式上完全对称形式上完全对称OR第二章 线性规划 其实其实,对几乎任一个实际问题对几乎任一个实际问题,都可从不同角度给出类似上都可从不同角度给出类似上述的相互对称的述的相互对称的LP描述描述.考虑一般形式的考虑一般形式的LP问题问题:需将需将(1)变为标准形式的变为标准形式的LP问题问题 为约束为约束矩阵矩阵 的第的第i个行向量个行向量Tnii1in,aaaRm nAR右端向量右端向量T1m,bbb(1)TTiiTiijjmins.t.,1,1,0,1,0,1

5、,c xa xbipa xbipmxjqxjqnOR第二章 线性规划对每个不等式约束对每个不等式约束 :1,ipm 减去一个非负的剩余变量减去一个非负的剩余变量six对每个自由变量对每个自由变量 :j,1,xjqn jjjjj;,0 xxxxxA中相应的列中相应的列 用列用列 和和()替换替换jjjAAAT mins.t.0c xAxbx0ITss1qq+1q+1nn1m-pT1qq+1q+1nnT1qq+1q+1nn,0,0,xxxxxxxxxccc ccccAAA AAAA q+2 n-qm-pR()pmp()()mpmp mq+2 n-qm-pR(2)OR第二章 线性规划令令单纯形乘子单

6、纯形乘子T1TB0c B AcT则则 满足线性约束满足线性约束TTAcTm1m,R依照上述对依照上述对 的列集合的划分的列集合的划分,将该不等式约束划分为三组将该不等式约束划分为三组:A 由单纯形法和最优性准则由单纯形法和最优性准则,若问题若问题(2)有最优基本可行有最优基本可行解解 ,则问题则问题(2)存在一个相应于存在一个相应于 的可行基的可行基 ,使得检验数使得检验数向量向量B0 x0 xOR第二章 线性规划 对应于非负变量对应于非负变量Tjjj,1,:,1,xjqAcjq 对应于自由变量对应于自由变量j,1,:xjqn TjjTjjAcAc Tjj,1,Acjqn 对应于对应于 的不等

7、式约束的不等式约束(剩余变量剩余变量 ):1,ipm sixi0i0,1,ipm LP问题的约束条问题的约束条件件可用来定义一个新可用来定义一个新的的&若再加上一个目标函数若再加上一个目标函数 ,则得到如下新的则得到如下新的LP:TmaxbTTjjTjjimaxs.t.,1,10,1bAcjqAcjqnipm当当 时时,它不仅是该问题的可行解它不仅是该问题的可行解,而且还是最优解而且还是最优解TT1B cBOR第二章 线性规划Def.给定任一一般形式的给定任一一般形式的LP问题问题,称它为称它为原始原始LP问题问题,则它的则它的对偶问题对偶问题定义如下定义如下:原始原始(P)对偶对偶(D)Ti

8、iTjjTjjmaxs.t.00bAcAcTTiiTiijjmins.t.,1,1,0,1,0,1,c xa xbipa xbipmxjqxjqnOR第二章 线性规划两者之间的关系两者之间的关系:原始问题原始问题(P)对偶问题对偶问题(D)min max 自由变量自由变量 等式约束等式约束价值向量价值向量 右端向量右端向量 右端向量右端向量 价值向量价值向量两个问题的约束系数矩阵互为转置两个问题的约束系数矩阵互为转置不等式约束不等式约束 不等式约束不等式约束等式约束等式约束 自由变量自由变量0不等式约束不等式约束 非负变量非负变量0非负变量非负变量 不等式约束不等式约束OR第二章 线性规划规范

9、形式规范形式:对偶问题对偶问题标准形式标准形式:又如又如:(P)(D)TTmaxs.t.0bAcTTmaxs.t.0bAcTmin.0c xstAxbxTmin.0c xstAxbxTLPmaxs.t.0zc xAxbxLPT1mmins.t.(,)0ubuAcuuuOR第二章 线性规划Th.:对偶定理对偶定理 对偶对偶LP问题的对偶即为原始的问题的对偶即为原始的LP问题问题.不失一般性不失一般性,考虑上述互为对偶的两个考虑上述互为对偶的两个LP(P)与与(D)类似前一节类似前一节,可定义对偶问题可定义对偶问题(D)的基本解、基本可行解的基本解、基本可行解,并分别称为并分别称为对偶基本解对偶基

10、本解、对偶基本可行解对偶基本可行解.相对应地相对应地,称原始问题称原始问题(P)的可行解、最优解为的可行解、最优解为原始原始可行解、原始最优解可行解、原始最优解.对偶最优解对偶最优解:称使称使 达到最小值达到最小值 的对偶可行解为对偶的对偶可行解为对偶 最优解最优解.LPubDef.对偶可行解对偶可行解:称满足条件称满足条件 的的 为为(D)的的对偶对偶 可行解可行解.TTmuAcuROR第二章 线性规划Th.:弱对偶定理弱对偶定理:两个互为对偶的两个互为对偶的LP问题问题,任一个问题的可行解将产生任一个问题的可行解将产生另一问题最优目标函数值的一个界另一问题最优目标函数值的一个界.对任何原始

11、可行解对任何原始可行解 与对偶可行解与对偶可行解 ,必有必有xuTLPLPc xzu bProof:由由 的原始可行性的原始可行性xAxbu Axu b因因 对偶可行对偶可行uTT&0u Acxu Axc x对于对于(P)的所有可行解的所有可行解x,必有必有TLPc x而对于而对于(D)的所有可行解的所有可行解u,必有必有LPzubTu bu Axc xLPLPzOR第二章 线性规划推论推论:若原始问题若原始问题(P)有无界最优值有无界最优值,则问题则问题(D)不可行不可行.Proof:由由B是最优基知是最优基知,必有必有T1TB0cB Ac是一个对偶可行解是一个对偶可行解T1BucB设设 为

12、对应于为对应于B的基本最优解的基本最优解,则有关系则有关系:xTT1Bc xcB bu b由前一定理知由前一定理知 为一个对偶最优解为一个对偶最优解.uTh.:若若B为问题为问题(P)的最优基的最优基,则则 为问题为问题(D)的最优解的最优解.T1BucBOR第二章 线性规划Th.:强对对偶定理:如果问题如果问题(P)和和(D)同时存在可行解同时存在可行解,则必同时有基本则必同时有基本 最优解最优解,进而进而LPLPzProof:两个问题均可行两个问题均可行(P)和和(D)必都有最优解必都有最优解.应用单纯形法应用单纯形法,必可求得必可求得(P)的一个最优基的一个最优基.由前一由前一个定理即得

13、证个定理即得证.有上界有上界,有下界有下界 Tc xub其实其实,还可进一步证明还可进一步证明:(P)和和(D)同时有最优解同时有最优解它们同时有可行解它们同时有可行解OR第二章 线性规划若设若设 分别为分别为 的可行解的可行解,则它们分别为则它们分别为 的最优解的最优解 xPuD PDTc xu b对于互为对偶的问题对于互为对偶的问题(P)和和(D),只能有下列四种可能性只能有下列四种可能性:b)(P)和和(D)均均 不可行不可行.a)和和 有限且相等有限且相等.LPLPzb),而而(D)不可行不可行.LPz c),而而(P)不可行不可行.LP OR第二章 线性规划由前述三个定理易知由前述三

14、个定理易知:是原始最优解和对偶最优解的充要条件为是原始最优解和对偶最优解的充要条件为,uxTh.:原始可行解原始可行解 和对偶可行解和对偶可行解 是原始最优解和对偶是原始最优解和对偶 最优解最优解uxT()0u AcxProof:Tc xu bu AxT0u Acx由于由于 ,故该定理中的充要条件等价于故该定理中的充要条件等价于T0,0 xu Acjjj0,1,2,u Acxjn这里这里 为为 的第的第j列列.jAAOR第二章 线性规划 以上条件以上条件 称为称为互补松弛性条件互补松弛性条件.jjj0,1,2,u Acxjn含义含义:此时称第此时称第j 个约束对问题个约束对问题(D)是是松的松

15、的此时称第此时称第j 个非负约束对问题个非负约束对问题(P)是是紧的紧的a)若有某对偶最优解若有某对偶最优解 ,使得对某下标使得对某下标j 有有ujju Ac对一切原始最优解对一切原始最优解 ,必使必使xj0 xb)反之反之,若有某最优解若有某最优解 ,使得对某下标使得对某下标j,满足满足xj0 x对一切对偶最优解对一切对偶最优解 ,必有必有 ujju AcOR第二章 线性规划 若实际中若实际中LP问题的形式与以上所述不同问题的形式与以上所述不同,则亦可类似地则亦可类似地定义其对偶问题定义其对偶问题.并易证上述所有有关对偶结论均成立并易证上述所有有关对偶结论均成立.例如例如:假如原假如原LP问

16、题呈如下形式问题呈如下形式:则其对偶规划应写为则其对偶规划应写为进而进而,可行解分别是他们的最优解的充要条件是可行解分别是他们的最优解的充要条件是:原始互补性条件原始互补性条件对偶互补性条件对偶互补性条件Tmax,0c x Axb xTmin,0ub uAcuT0u Acx0uAxbOR第二章 线性规划应用应用:Farkas 引理引理:要么要么 ,要么存在一个要么存在一个 使得使得 且且 ,但这两者不可能同时成立但这两者不可能同时成立.nxRAxb TmvR00vAvbProof:考虑考虑LP与其对偶问题与其对偶问题:因该对偶问题有一显然的可行解因该对偶问题有一显然的可行解 v=0=0,由由LP的对偶理论的对偶理论知只可能有下列两种情形之一知只可能有下列两种情形之一:nLPmax 0,zx Axb xRTmLPmin0,vb vAvR1 LPLP0,z2 LPLP,z 因此因此 ,且对任意且对任意使得使得vA0 的的 ,有有vb 0.n:xRAxb TmvR那么那么n:xRAxb 且同时存在某一且同时存在某一 ,使得使得vA0和和vb 0.TmvROR第二章 线性规划Farkas 引理