对偶线性规划.ppt

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

1、第二章 对偶线性规划对偶的定义对偶问题的性质原始对偶关系 目标函数值之间的关系 最优解之间的关系互补松弛关系 最优解的Kuhn-Tucher条件对偶可行基对偶单纯形法对偶的经济解释DUAL一、对偶的定义原始问题min z=CTXs.t.AXbX 0对偶问题max y=bTWs.t.ATWCW 0minbACTCATbTmaxmnmn二、对偶问题的性质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对偶的定义对偶的定义min z=CTXs.t.AXb

2、X 0max y=bTWs.t.ATWC W 02、其他形式问题的对偶min z=CTXs.t.AXbX 0max y=bTWs.t.ATWC W 0min z=CTXs.t.AX=bX 0max y=bTWs.t.ATWC W：unr三、原始对偶关系1、可行解的目标函数值之间的关系 设XF、WF分别是原始问题和对偶问题的可行解z=CTXF WTAXF WTb=y2、最优解的目标函数值之间的关系 设Xo、Wo分别是原始问题和对偶问题的最优解 z=CTXo=WoTAXo=WoTb=y3、原始问题和对偶问题最优解之间的互补松弛关系min z=CTXs.t.AX-XS=b X,XS0max y=bT

3、Ws.t.ATW+WS=C W,WS0min z=CTXs.t.AXb X 0max y=bTWs.t.ATWC W0对偶引进松弛变量引进松弛变量XTWS=0 WTXS=0互补松弛关系X，XsW，Wsmin z=CTXs.t.AX-XS=bX,XS 0max y=bTWs.t.ATW+WS=CW,WS 0XTWS=0WTXS=0mn=WWSATICn=AXS-IbnmmX原始问题和对偶问题变量、松弛变量的维数w1 wi wm wm+1 wm+j wn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量xjwm+j=0wix

4、n+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0Kuhn-Tucher 条件3、原始问题和对偶问题最优解的充分必要条件 (1)原始可行条件（PFC）AX-XS=bX,XS 0(2)对偶可行条件（DFC）ATW+WS=CW,WS 0(3)互补松弛条件（CSC）XTWS=0WTXS=0四、对偶单纯形法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）（1）单纯形表和对偶(1)min z=C

5、TXs.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对偶问题原始问题引进松弛变量引进松弛变量min z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW+WS=C W,WS0WT=CBTB-1WST=CT-WTAmin z=CTXs.t.AX+XS=b X,XS0max y=bTWs.t.ATW+WS=C W 0,WS0min z=CTXs.t.AX b X 0max y=bTWs.t.ATWC W 0单纯形表和对偶(2)对偶问题原始问题引进松弛变量引

6、进松弛变量min z=CTXs.t.AX+XS=b X,XS0max y=bTWs.t.ATW+WS=C W 0,WS0WT=CBTB-1WST=CT-WTAmax 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)对偶问题原始问题引进松弛变量引进松弛变量max z=CTXs.t.AX-XS=b X,XS0min y=bTWs.t.ATW-WS=C W 0,WS0WT=CBTB-1WST=WTA-CTmax z=CTXs.t.AX+XS=

7、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)对偶问题原始问题引进松弛变量引进松弛变量max z=CTXs.t.AX+XS=b X,XS0min y=bTWs.t.ATW-WS=C W,WS0WT=CBTB-1WST=WTA-CT2、对偶单纯形法（初始解原始不可行的问题）已获得最优解：（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

8、3、初始解原始、对偶都不可行的问题解法1：先解决原始可行性在得到原始可行解时同时得到对偶可行解，已获得最优解：（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解法2：先解决对偶可行性已得到对偶可行解，再用对偶单纯形法求解得到原始可行解，已获得最优解：（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五、对偶的经济解释1、

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