对偶线性规划优秀PPT.ppt
对偶线性规划你现在浏览的是第一页，共35页一、对偶的定义原始问题min z=CTXs.t.AXbX 0对偶问题max y=bTWs.t.ATWCW 0minbACTCATbTmaxmnmn你现在浏览的是第二页，共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对偶的定义对偶的定义你现在浏览的是第三页，共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你现在浏览的是第四页，共35页三、原始对偶关系1、可行解的目标函数值之间的关系 设XF、WF分别是原始问题和对偶问题的可行解z=CTXF WTAXF WTb=y2、最优解的目标函数值之间的关系 设Xo、Wo分别是原始问题和对偶问题的最优解 z=CTXo=WoTAXo=WoTb=y你现在浏览的是第五页，共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你现在浏览的是第六页，共35页min z=CTXs.t.AX-XS=bX,XS 0max y=bTWs.t.ATW+WS=CW,WS 0XTWS=0WTXS=0mn=WWSATICn=AXS-IbnmmX原始问题和对偶问题变量、松弛变量的维数你现在浏览的是第七页，共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你现在浏览的是第八页，共35页Kuhn-Tucher 条件3、原始问题和对偶问题最优解的充分必要条件 (1)原始可行条件（PFC）AX-XS=bX,XS 0(2)对偶可行条件（DFC）ATW+WS=CW,WS 0(3)互补松弛条件（CSC）XTWS=0WTXS=0你现在浏览的是第九页，共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）你现在浏览的是第十页，共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对偶问题原始问题引进松弛变量引进松弛变量你现在浏览的是第十一页，共35页min z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW+WS=C W,WS0WT=CBTB-1WST=CT-WTA你现在浏览的是第十二页，共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)对偶问题原始问题引进松弛变量引进松弛变量你现在浏览的是第十三页，共35页min z=CTXs.t.AX+XS=b X,XS0max y=bTWs.t.ATW+WS=C W 0,WS0WT=CBTB-1WST=CT-WTA你现在浏览的是第十四页，共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)对偶问题原始问题引进松弛变量引进松弛变量你现在浏览的是第十五页，共35页max z=CTXs.t.AX-XS=b X,XS0min y=bTWs.t.ATW-WS=C W 0,WS0WT=CBTB-1WST=WTA-CT你现在浏览的是第十六页，共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)对偶问题原始问题引进松弛变量引进松弛变量你现在浏览的是第十七页，共35页max z=CTXs.t.AX+XS=b X,XS0min y=bTWs.t.ATW-WS=C W,WS0WT=CBTB-1WST=WTA-CT你现在浏览的是第十八页，共35页2、对偶单纯形法（初始解原始不可行的问题）你现在浏览的是第十九页，共35页你现在浏览的是第二十页，共35页你现在浏览的是第二十一页，共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你现在浏览的是第二十二页，共35页3、初始解原始、对偶都不可行的问题你现在浏览的是第二十三页，共35页解法1：先解决原始可行性你现在浏览的是第二十四页，共35页你现在浏览的是第二十五页，共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你现在浏览的是第二十六页，共35页解法2：先解决对偶可行性已得到对偶可行解，再用对偶单纯形法求解你现在浏览的是第二十七页，共35页你现在浏览的是第二十八页，共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你现在浏览的是第二十九页，共35页五、对偶的经济解释1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）你现在浏览的是第三十页，共35页2、对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min y你现在浏览的是第三十一页，共35页3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0你现在浏览的是第三十二页，共35页w1w2wm4、产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源你现在浏览的是第三十三页，共35页机会成本利润差额成本5、产品的差额成本（Reduced Cost）差额成本=机会成本-利润你现在浏览的是第三十四页，共35页5、互补松弛关系的经济解释在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产你现在浏览的是第三十五页，共35页
