對(duì)偶問題和運(yùn)輸問題.ppt

《對(duì)偶問題和運(yùn)輸問題.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、原問題與對(duì)偶問題的關(guān)系原問題(或?qū)ε紗栴})對(duì)偶問題(或原問題)目標(biāo)函數(shù)maxzn個(gè)變>=0量<=0無約束目標(biāo)函數(shù)minwn個(gè)約>=束<=條=件約m個(gè)束<=條>=約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)m個(gè)>=0變<=0量目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)例3寫對(duì)偶問題Minz=2x1+3x2-5x3+x4x1+x2-3x3+x4>=52x1+2x3-x4<=4x2+x3+x4=6x1<=0,x2,x3>=0x4無約束Maxz’=5y1+4y2+6y3y1+2y2>=0y1+y3<=0-3y1+2y2+y3<=-5y1-y2+y3=1y1>=0,y2<=0,y3無約束3

2、.對(duì)偶定理(原問題與對(duì)偶問題解的關(guān)系）考慮（LP）和（DP）定理3-1(弱對(duì)偶定理）若x,y分別為（LP)和（DP）的可行解，那么cTx≤bTy。推論若（LP）可行，那么（LP）無有限最優(yōu)解的充分必要條件是（LD）無可行解。1.線性規(guī)劃對(duì)偶問題定理3-2(最優(yōu)性準(zhǔn)則定理)若x,y分別(LP),(DP)的可行解,且cTx=bTy，那么x,y分別為(LP)和(DP)的最優(yōu)解。定理3-3(主對(duì)偶定理)若(LP)和(DP)均可行那么(LP)和(DP)均有最優(yōu)解,且最優(yōu)值相等。以上定理、推論對(duì)任意形式的相應(yīng)性規(guī)劃的對(duì)偶均有效1.線性規(guī)劃對(duì)偶問題4、原始問題和對(duì)偶問題最

3、優(yōu)解之間的互補(bǔ)松弛關(guān)系minz=CTXs.t.AX-XS=bX,XS≥0maxy=bTWs.t.ATW+WS=CW,WS≥0minz=CTXs.t.AX≥bX≥0maxy=bTWs.t.ATW≤CW≥0對(duì)偶引進(jìn)松弛變量引進(jìn)松弛變量XTWS=0WTXS=0互補(bǔ)松弛關(guān)系X，XsW，Ws五、對(duì)偶的經(jīng)濟(jì)解釋1、原始問題是利潤最大化的生產(chǎn)計(jì)劃問題單位產(chǎn)品的利潤（元/件）產(chǎn)品產(chǎn)量（件）總利潤（元）資源限量（噸）單位產(chǎn)品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）2、對(duì)偶問題資源限量（噸）資源價(jià)格（元/噸）總利潤（元）對(duì)偶問題是資源定價(jià)問題，對(duì)偶問題的最優(yōu)解w1、

4、w2、...、wm稱為m種資源的影子價(jià)格（ShadowPrice）原始和對(duì)偶問題都取得最優(yōu)解時(shí)，最大利潤maxz=miny3、資源影子價(jià)格的性質(zhì)影子價(jià)格越大，說明這種資源越是相對(duì)緊缺影子價(jià)格越小，說明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0影子價(jià)格的經(jīng)濟(jì)含義(1)影子價(jià)格是對(duì)現(xiàn)有資源實(shí)現(xiàn)最大效益時(shí)的一種估價(jià)企業(yè)可以根據(jù)現(xiàn)有資源的影子價(jià)格，對(duì)資源的使用有兩種考慮：第一，是否將設(shè)備用于外加工或出租，若租費(fèi)高于某設(shè)備的影子價(jià)格，可考慮出租該設(shè)備，否則不宜出租。第二，是否將投資用于購買設(shè)備，以擴(kuò)大生產(chǎn)能力，若市價(jià)低于某設(shè)備的影

5、子價(jià)格，可考慮買進(jìn)該設(shè)備，否則不宜買進(jìn)。1.線性規(guī)劃對(duì)偶問題需要指出，影子價(jià)格不是固定不變的，當(dāng)約束條件、產(chǎn)品利潤等發(fā)生變化時(shí)，有可能使影子價(jià)格發(fā)生變化。另外，影子價(jià)格的經(jīng)濟(jì)含義（2），是指資源在一定范圍內(nèi)增加時(shí)的情況，當(dāng)某種資源的增加超過了這個(gè)“一定的范圍”時(shí)，總利潤的增加量則不是按照影子價(jià)格給出的數(shù)值線性地增加。這個(gè)問題還將在靈敏度分析一節(jié)中討論。1.線性規(guī)劃對(duì)偶問題5.由最優(yōu)單純形表求對(duì)偶問題最優(yōu)解標(biāo)準(zhǔn)形式：Maxz=50x1+100x2s.t.x1+x2+x3=3002x1+x2+x4=400x2+x5=250x1,x2,x3,x4,x5≥01.線性

6、規(guī)劃對(duì)偶問題maxz=CTXs.t.AX+XS=bX,XS≥0maxy=bTWs.t.ATW-WS=CW,WS≥0maxz=CTXs.t.AX≤bX≥0miny=bTWs.t.ATW≥CW≥0單純形表和對(duì)偶對(duì)偶問題原始問題引進(jìn)松弛變量引進(jìn)松弛變量maxz=CTXs.t.AX+XS=bX,XS≥0miny=bTWs.t.ATW-WS=CW,WS≥0WT=CBTB-1WST=WTA-CT-cBTB-1IB=(p1,p4,p2)oTB-1最優(yōu)解x1=50x2=250x4=50影子價(jià)格y1=50y2=0y3=50,B-1對(duì)應(yīng)的檢驗(yàn)數(shù)?T=cBTB-1。1.線性規(guī)劃對(duì)

7、偶問題例3.2：求解線性規(guī)劃問題：標(biāo)準(zhǔn)化：Maxz=-2x1-3x2-4x3s.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥0Minf=2x1+3x2+4x3S.t.x1+2x2+x3≥32x1-x2+x3≥4x1,x2,x3≥02.對(duì)偶單純形法對(duì)偶單純形法的基本思想對(duì)偶單純形法的基本思想是：從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行，但它對(duì)應(yīng)著一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正），所以也可以說是從一個(gè)對(duì)偶可行解出發(fā)；然后檢驗(yàn)原規(guī)劃的基本解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)基

8、本解，此基本解對(duì)應(yīng)著另一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正）。