對(duì)偶問(wèn)題和運(yùn)輸問(wèn)題(已修改)
2025-01-03 20:41 本頁(yè)面
【正文】 原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系 原問(wèn)題 (或?qū)ε紗?wèn)題 ) 對(duì)偶問(wèn)題 (或原問(wèn)題 ) 目標(biāo)函數(shù) max z n 個(gè) 變 =0 量 =0 無(wú)約束 目標(biāo)函數(shù) min w n 個(gè) 約 = 束 = 條 = 件 約 m個(gè) 束 = 條 = 約束條件右端項(xiàng) 目標(biāo)函數(shù)變量的系數(shù) m 個(gè) =0 變 =0 量 目標(biāo)函數(shù)變量的系數(shù) 約束條件右端項(xiàng) 例 3 寫(xiě)對(duì)偶問(wèn)題 Min z=2x1+3x25x3+x4 x1+x23x3+x4=5 2x1 +2x3x4=4 x2+x3+x4 =6 x1=0,x2,x3=0 x4無(wú)約束 Max z’ =5y1+4y2+6y3 y1+2y2 =0 y1 +y3=0 3y1+2y2+y3=5 y1 y2 +y3 =1 y1=0,y2=0, y3無(wú)約束 (原問(wèn)題與對(duì)偶問(wèn)題解的關(guān)系） 考慮（ LP）和（ DP） 定理 31 (弱對(duì)偶定理） 若 x, y 分別為（ LP) 和（ DP）的可行解，那么 cTx ≤ bTy。 推論 若（ LP）可行，那么（ LP） 無(wú)有限最優(yōu)解的充分必要條件是（ LD） 無(wú)可行解。 定理 32 (最優(yōu)性準(zhǔn)則定理 ) 若 x,y分別 (LP),(DP)的可行解 ,且 cTx=bTy ，那么 x,y分別為 (LP)和 (DP) 的最優(yōu)解。 定理 33 (主對(duì)偶定理 ) 若 (LP)和 (DP)均可行 那么 (LP)和 (DP)均有最優(yōu)解 ,且最優(yōu)值相等。 以上定理、推論對(duì)任意形式的相 應(yīng)性規(guī)劃的對(duì)偶均有效 原始問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解之間的互補(bǔ)松弛關(guān)系 min z=CTX . AXXS=b X, XS≥0 max y=bTW . ATW+WS=C W, WS≥0 min z=CTX . AX≥b X ≥0 max y=bTW . ATW≤C W≥0 對(duì)偶 引進(jìn)松弛變量 引進(jìn)松弛變量 XTWS=0 WTXS=0 互補(bǔ)松弛關(guān)系 X， Xs W， Ws 五、對(duì)偶的經(jīng)濟(jì)解釋 原始問(wèn)題是利潤(rùn)最大化的生產(chǎn)計(jì)劃問(wèn)題 0xxxxxxbxxaxaxabxxaxaxaxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111222211??????????????????????????????????單位產(chǎn)品的利潤(rùn)（元 /件） 產(chǎn)品產(chǎn)量（件） 總利潤(rùn)（元） 資源限量（噸） 單位產(chǎn)品消耗的資源（噸 /件） 剩余的資源（ 噸） 消耗的資源（噸） 對(duì)偶問(wèn)題 0cwwawawacwwawawawbwbwbyminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211??????????????????????????????????資源限量（噸） 資源價(jià)格（元 /噸） 總利潤(rùn)（元） 對(duì)偶問(wèn)題是資源定價(jià)問(wèn)題，對(duì)偶問(wèn)題的最優(yōu)解 w w ...、wm稱(chēng)為 m種資源的影子價(jià)格（ Shadow Price） 原始和對(duì)偶問(wèn)題都取得最優(yōu)解時(shí)， 最大利潤(rùn) max z=min y 資源影子價(jià)格的性質(zhì) ■ 影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺 ■ 影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺 ■ 如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于 0 種資源的邊際利潤(rùn)第種資源的增量第最大利潤(rùn)的增量 iibzwiooi ?????mmii2211 wbwbwbwbyz ??????? ?? mmiii2211 wbw)bb(wbwbzz ?????????? ??ii wbz ??? 影子價(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è)備 ， 否則不宜出租 。 第二 ， 是否將投資用于購(gòu)買(mǎi)設(shè)備 ， 以擴(kuò)大生產(chǎn)能力 ， 若市價(jià)低于某設(shè)備的影子價(jià)格 ，可考慮買(mǎi)進(jìn)該設(shè)備 ， 否則不宜買(mǎi)進(jìn) 。 需要指出 ， 影子價(jià)格不是固定不變的 ， 當(dāng)約束條件 、 產(chǎn)品利潤(rùn)等發(fā)生變化時(shí) ， 有可能使影子價(jià)格發(fā)生變化 。 另外 ，影子價(jià)格的經(jīng)濟(jì)含義 （ 2） ， 是指資源在一定范圍內(nèi)增加時(shí)的情況 ， 當(dāng)某種資源的增加超過(guò)了這個(gè) “ 一定的范圍 ” 時(shí) ，總利潤(rùn)的增加量則不是按照影子價(jià)格給出的數(shù)值線性地增加 。 這個(gè)問(wèn)題還將在靈敏度分析一節(jié)中討論 。 優(yōu)解 標(biāo)準(zhǔn)形式： Max z = 50 x1 + 100 x2 . x1 + x2 + x3 = 300 2x1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0 max z=CTX . AX+XS=b X, XS≥0 max y=bTW . ATWWS=C W, WS≥0 max z=CTX . AX ≤ b X ≥0 min y=bTW . ATW ≥ C W ≥ 0 單純形表和對(duì)偶 對(duì)偶問(wèn)題 原始問(wèn)題 引進(jìn)松弛變量 引進(jìn)松弛變量 z X X S RH S1 W STWTC BTB1b0 B1A B1B1bz X X S RH S1 CT0T00 A I bmax z=CTX . AX+XS=b X, XS≥0 min y=bTW . ATWWS=C W, WS≥0 z X X S R H S 1 C BTB 1A CT C BTB 1 C BTB 1b 0 B 1A B 1 B 1b WT=CBTB1 WST=WTA CT 50 100 0 0 0CBXBx1x2x3x4x5θi0 x3300 1 1 1 0 0 3000 x4400 2 1 0 1 0 4000 x5250 0 ( 1) 0 0 1 250z 0 50 100* 0 0 00 x350 ( 1) 0 1 0 1 500 x4150 2 0 0 1 1 75100 x2250 0 1 0 0 1z 25000 50* 0 0 0 10050 x150 1 0 1 0 10 x450 0 0 2 1 1100 x2250 0 1 0 0 1z 27500 0 0 50 0 50cBTB1 I B=(p1, p4,p2 ) oT B1 最優(yōu)解 x1 = 50 x2 = 250 x4 = 50 影子價(jià)格 y1 = 50 y2 = 0 y3 = 50 , B1對(duì)應(yīng)的檢驗(yàn)數(shù) ?T = cBTB1 。 例 ： 求解線性規(guī)劃問(wèn)題： 標(biāo)準(zhǔn)化： Max z = 2x1 3x2 4x3 . x12x2x3+x4= 3 2x1+x23x3+x5= 4 x1,x2,x3,x4,x5 ≥ 0 Min f = 2x1 + 3x2 + 4x3 . x1 + 2x2 + x3 ≥ 3 2
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1