对偶线性规划精.ppt
对偶线性规划第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 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=CTXs.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=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）（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=CTXs.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页，本讲稿共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-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,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第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、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）第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页
