对偶线性规划精选PPT.ppt

《对偶线性规划精选PPT.ppt》由会员分享，可在线阅读，更多相关《对偶线性规划精选PPT.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、对偶线性规划第1页，此课件共35页哦一、对偶的定义原始问题min z=CTXs.t.AXbX 0对偶问题max y=bTWs.t.ATWCW 0minbACTCATbTmaxmnmn第2页，此课件共35页哦二、对偶问题的性质1、对偶的对偶就是原始问题max z=-CTXs.t.-AX-bX 0min y=-bTWs.t.-ATW-CW 0max y=bTWs.t.ATWCW 0min z=CTXs.t.AXb X 0对偶的定义对偶的定义第3页，此课件共35页哦min z=CTXs.t.AXbX 0max y=bTWs.t.ATWC W 02、其他形式问题的对偶min z=CTXs.t.AXbX

2、 0max y=bTWs.t.ATWC W 0min z=CTXs.t.AX=bX 0max y=bTWs.t.ATWC W：unr第4页，此课件共35页哦三、原始对偶关系1、可行解的目标函数值之间的关系 设XF、WF分别是原始问题和对偶问题的可行解z=CTXF WTAXF WTb=y2、最优解的目标函数值之间的关系 设Xo、Wo分别是原始问题和对偶问题的最优解 z=CTXo=WoTAXo=WoTb=y第5页，此课件共35页哦3、原始问题和对偶问题最优解之间的互补松弛关系min z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW+WS=C W,WS0min z=CTX

3、s.t.AXb X 0max y=bTWs.t.ATWC W0对偶引进松弛变量引进松弛变量XTWS=0 WTXS=0互补松弛关系X，XsW，Ws第6页，此课件共35页哦min z=CTXs.t.AX-XS=bX,XS 0max y=bTWs.t.ATW+WS=CW,WS 0XTWS=0WTXS=0mn=WWSATICn=AXS-IbnmmX原始问题和对偶问题变量、松弛变量的维数第7页，此课件共35页哦w1 wi wm wm+1 wm+j wn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量xjwm+j=0wixn+i=

4、0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0第8页，此课件共35页哦Kuhn-Tucher 条件3、原始问题和对偶问题最优解的充分必要条件 (1)原始可行条件（PFC）AX-XS=bX,XS 0(2)对偶可行条件（DFC）ATW+WS=CW,WS 0(3)互补松弛条件（CSC）XTWS=0WTXS=0第9页，此课件共35页哦四、对偶单纯形法1、用单纯形表求解原始问题的四种形式min z=CTXs.t.AXb X 0min z=CTXs.t.AX b X 0max z=CTXs.t.AX b X 0max z=CTXs.t.AX b X 0（2）（3）（4）

5、（1）第10页，此课件共35页哦单纯形表和对偶(1)min z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW+WS=C W,WS0min z=CTXs.t.AXb X 0max y=bTWs.t.ATWC W0对偶问题原始问题引进松弛变量引进松弛变量第11页，此课件共35页哦min z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW+WS=C W,WS0WT=CBTB-1WST=CT-WTA第12页，此课件共35页哦min z=CTXs.t.AX+XS=b X,XS0max y=bTWs.t.ATW+WS=C W 0,WS0min z=CT

6、Xs.t.AX b X 0max y=bTWs.t.ATWC W 0单纯形表和对偶(2)对偶问题原始问题引进松弛变量引进松弛变量第13页，此课件共35页哦min z=CTXs.t.AX+XS=b X,XS0max y=bTWs.t.ATW+WS=C W 0,WS0WT=CBTB-1WST=CT-WTA第14页，此课件共35页哦max z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW-WS=C W 0,WS0max z=CTXs.t.AX b X 0min y=bTWs.t.ATW C W 0单纯形表和对偶(3)对偶问题原始问题引进松弛变量引进松弛变量第15页，此课件

7、共35页哦max z=CTXs.t.AX-XS=b X,XS0min y=bTWs.t.ATW-WS=C W 0,WS0WT=CBTB-1WST=WTA-CT第16页，此课件共35页哦max z=CTXs.t.AX+XS=b X,XS0max y=bTWs.t.ATW-WS=C W,WS0max z=CTXs.t.AX b X 0min y=bTWs.t.ATW C W 0单纯形表和对偶(4)对偶问题原始问题引进松弛变量引进松弛变量第17页，此课件共35页哦max z=CTXs.t.AX+XS=b X,XS0min y=bTWs.t.ATW-WS=C W,WS0WT=CBTB-1WST=WTA

8、-CT第18页，此课件共35页哦2、对偶单纯形法（初始解原始不可行的问题）第19页，此课件共35页哦第20页，此课件共35页哦第21页，此课件共35页哦已获得最优解：（x1,x2,x3,x4,x5,x6）=（5,7,6,0,0,0）min z=35对偶问题的最优解为：（w1,w2,w3,w4,w5,w6）=（-1,5,7,0,0,0）max y=35第22页，此课件共35页哦3、初始解原始、对偶都不可行的问题第23页，此课件共35页哦解法1：先解决原始可行性第24页，此课件共35页哦第25页，此课件共35页哦在得到原始可行解时同时得到对偶可行解，已获得最优解：（x1,x2,x3,x4,x5,x

9、6）=（5,7,6,0,0,0）min z=17对偶问题的最优解为：（w1,w2,w3,w4,w5,w6）=（-7,5,10,0,0,0）max y=17第26页，此课件共35页哦解法2：先解决对偶可行性已得到对偶可行解，再用对偶单纯形法求解第27页，此课件共35页哦第28页，此课件共35页哦得到原始可行解，已获得最优解：（x1,x2,x3,x4,x5,x6）=（5,7,6,0,0,0）min z=17对偶问题的最优解为：（w1,w2,w3,w4,w5,w6）=（-7,5,10,0,0,0）max y=17第29页，此课件共35页哦五、对偶的经济解释1、原始问题是利润最大化的生产计划问题单位产

10、品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）第30页，此课件共35页哦2、对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min y第31页，此课件共35页哦3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0第32页，此课件共35页哦w1w2wm4、产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源第33页，此课件共35页哦机会成本利润差额成本5、产品的差额成本（Reduced Cost）差额成本=机会成本-利润第34页，此课件共35页哦5、互补松弛关系的经济解释在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产第35页，此课件共35页哦