三節(jié)對(duì)偶與靈敏度分析ppt課件

1、 對(duì)偶問(wèn)題與靈敏度分析一、對(duì)偶問(wèn)題及其模型問(wèn)題的提出0,3001032005436049. .21212121xxxxxxxxts21127xxMaxz乙甲油電煤 這時(shí)有另一家廠商提出要購(gòu)買其煤、電、油全部資源，并希望破費(fèi)盡量少。試建立購(gòu)買者的線性規(guī)劃模型。則總花費(fèi)為分別為的價(jià)格解：設(shè)其購(gòu)買三種資源,321wyyy0,5449.21212133312107 3yyyyyyyyyts321300200360yyyMinw油電煤 乙甲原問(wèn)題原問(wèn)題, ,記為記為P P對(duì)偶問(wèn)題對(duì)偶問(wèn)題, ,記為記為D D對(duì)偶模型的普通式對(duì)偶模型的普通式則對(duì)偶問(wèn)題為，記),(321yyyY以例1為例，原問(wèn)題為0.XbA

2、XtsCXzmaxP0. .minYCYAt sYbwD這是最常見的對(duì)偶模型方式，稱為對(duì)稱式對(duì)偶模型。二者間具有非常對(duì)稱的對(duì)應(yīng)關(guān)系： 原問(wèn)題P 對(duì)偶問(wèn)題 D 目的max型 目的min型 有n個(gè)變量非負(fù) 有n個(gè)約束大于等于 有m個(gè)約束 小于等于 有m個(gè)變量非負(fù) 價(jià)錢系數(shù) 資源向量 資源向量 價(jià)錢系數(shù) 技術(shù)系數(shù)矩陣 技術(shù)系數(shù)矩陣的轉(zhuǎn)置此外，還有一種情形此外，還有一種情形 原問(wèn)題P 對(duì)偶問(wèn)題 D 第j個(gè)變量為自在變量 第j個(gè)約束為等式約束 第i個(gè)約束為等式約束 第i個(gè)變量為自在變量例：寫出下面線性規(guī)劃的對(duì)偶規(guī)劃模型：0135232. .32max121212121xxxxxxxtsxxz則對(duì)偶目標(biāo)為

3、解：設(shè)對(duì)偶變量為,321wyyy0,322.5321321321321yyyyyyyytsyyyw32min寫出下面線性規(guī)劃的對(duì)偶規(guī)劃模型：4321432maxxxxxz0,2023220322432143214321xxxxxxxxxxxx321635maxxxxz無(wú)約束321321322321,0,101632182xxxxxxxxxxxx32122minxxxz無(wú)約束321321321, 0, 064xxxxxxxxx0,64321321321xxxxxxxxx32122minxxxz練習(xí)：寫出下面LP的對(duì)偶43214532minxxxxz無(wú)約束43214324314321, 0, 06

4、42253. .xxxxxxxxxxxxxxts其對(duì)偶模型為：321645maxyyyw無(wú)約束3213213213121,0,4523322.yyyyyyyyyyyyyts二、對(duì)偶的性質(zhì)0.XbAXtsCXzmaxP0.YCYAtsYbzminD思索1 .1 .對(duì)稱性對(duì)稱性 P P與與D D互為對(duì)偶?；閷?duì)偶。證：X,Y分別為(P)、(D)的可行解，由約束條件可得幾何意義：CXYb2. 2.弱對(duì)偶性弱對(duì)偶性 YbCXDP的可行解，則，分別是，設(shè)YXbAX CYA YbYAX CXYAX YbYAXCXYbCX 由此可以推出：由此可以推出：假設(shè)假設(shè)(P)(P)為無(wú)界解，那么為無(wú)界解，那么(D)(

5、D)無(wú)可行解無(wú)可行解假設(shè)假設(shè)(D)(D)為無(wú)界解，那么為無(wú)界解，那么(P)(P)無(wú)可行解無(wú)可行解例 設(shè)線性規(guī)劃問(wèn)題1 ， 是其對(duì)偶問(wèn)題的最優(yōu)解；CXz 1maxY0.XbAXts又設(shè)線性規(guī)劃問(wèn)題2 ，其中k是知的常向量；CXz2max0.XkbAXts求證：kYzz*12maxmax0. 0. 2121YCYAtsYCYAtsYkYbMinwYbMinw）（）（的對(duì)偶問(wèn)題分別是與問(wèn)題證：?jiǎn)栴}由(I)和(II)的約束一樣，故(I)的最優(yōu)解 為(II)的可行解。Y由弱對(duì)偶性， ，由解的最優(yōu)性 ，得證kYbYz*2max1max zbY3. 3. 解的最優(yōu)性解的最優(yōu)性., ,)D(P)(YYXXbY

6、XCYX則的可行解，且與分別是與若.XCbYCXX，由弱對(duì)偶性，證：對(duì)任可行解.YYXX同理，故4. 4. 對(duì)偶定理對(duì)偶定理 假設(shè)假設(shè)(P)(P)有最優(yōu)解，那么有最優(yōu)解，那么(D)(D)也有最優(yōu)解，且二也有最優(yōu)解，且二者最優(yōu)值相等者最優(yōu)值相等證：對(duì)P添加松弛變量Xs，化為0,. .ssXXbIXAXtsCXMaxz設(shè)其最優(yōu)基為B，終表為sXXC 0 IBAB11 1bBCBIBCABCCBB110 00011IBCABCCBsB其檢驗(yàn)數(shù)為滿足則取YBCYB,10YCAYzbBCbYYB1D）的可行解，且是（即.3YY，由性質(zhì)問(wèn)題：(1) 由性質(zhì)4可知，對(duì)偶問(wèn)題最優(yōu)解的表達(dá)式 Y* =？ (2)

7、 求Y*能否有必要重新求解 D？ CBB-1 不用?？梢詮脑瓎?wèn)題P的單純形終表獲得。0,25.2121 21xxxxxxts105153212.5xxMaxz例如，在前面的練習(xí)中知的終表為51 0 52 153- 1 519 02913xx2.50 0.5- 0 0 0TX)09,0,2,(5z請(qǐng)指出其對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值。5)5 . 0 , 0(wY5. 5.互補(bǔ)松弛定理互補(bǔ)松弛定理。最優(yōu)解的充要條件是、是和的可行解，則、分別是與若0)()()D()P( XYXYDPYXYXss自證。故只需而即是最優(yōu)解，所以、由于 0 , 0,),()( , XYXYXYXYXIXAYXIYAYbYXC

8、YXssssss的約束化為等式：、證：將,)D()P(CIYYAbIXAXssy1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1xn+ixn+m 對(duì)偶問(wèn)題的變量 對(duì)偶問(wèn)題的松弛變量 原始問(wèn)題的變量 原始問(wèn)題的松弛變量xjym+j=0 yixn+i=0(i=1,2,m; j=1,2,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0直觀上直觀上 在線性規(guī)劃問(wèn)題的最優(yōu)解中，在線性規(guī)劃問(wèn)題的最優(yōu)解中，假設(shè)對(duì)應(yīng)某一約束條件的對(duì)偶變量假設(shè)對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，那么該約束條件取嚴(yán)厲值為非零，那么該約束條件取嚴(yán)厲等式，另一方面，假設(shè)約束條件取等式，另一方面，假設(shè)約束條件

9、取嚴(yán)厲不等式，那么其對(duì)應(yīng)的變量一嚴(yán)厲不等式，那么其對(duì)應(yīng)的變量一定為零。定為零。例：知線性規(guī)劃問(wèn)題5432132532minxxxxxw5,.,2 , 1, 0332432. .5432154321jxxxxxxxxxxxtsj知其對(duì)偶問(wèn)題的最優(yōu)解為：5,53,54*2*1zyy試用對(duì)偶實(shí)際找出原問(wèn)題的最優(yōu)解 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋1對(duì)偶最優(yōu)解的經(jīng)濟(jì)解釋資源的影子價(jià)錢Shadow PriceCBB-1 對(duì)偶問(wèn)題的最優(yōu)解 買主的最低出價(jià)； 原問(wèn)題資源的影子價(jià)錢 當(dāng)該資源添加1單 位時(shí)引起的總收入的增量賣主的內(nèi)控價(jià)錢。 簡(jiǎn)單推導(dǎo)：簡(jiǎn)單推導(dǎo)：設(shè)D其最優(yōu)值為 (注：與3最優(yōu)值一樣，那么根據(jù)zmmbybyby

10、bYz*2*21*1*.*/iiybz例：例1煤電油例的單純形終表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z1請(qǐng)指出資源煤、電、油的影子價(jià)錢，并解釋其經(jīng)濟(jì)意義。2由單純形終表還可得到哪些有用的信息？解：1煤、電、油的影子價(jià)錢分別是0、1.36、0.52； 其經(jīng)濟(jì)意義是當(dāng)煤、電、油分別添加1單位時(shí)可使總 收入分別添加0 、1.36、0.52。2由單純形終表還可得到：原問(wèn)題的最優(yōu)消費(fèi)方案、最大收入、資源剩余，對(duì)偶問(wèn)題的最低購(gòu)買價(jià)錢、最少的購(gòu)買費(fèi)用等。 影子價(jià)錢在管理決

11、策中的作用：影子價(jià)錢在管理決策中的作用：1 1影子價(jià)錢影子價(jià)錢市場(chǎng)價(jià)錢市場(chǎng)價(jià)錢 假設(shè)影子價(jià)錢市場(chǎng)價(jià)錢，那么應(yīng)買進(jìn)假設(shè)影子價(jià)錢市場(chǎng)價(jià)錢，那么應(yīng)買進(jìn)該資源該資源 影子價(jià)錢市場(chǎng)價(jià)錢，那么應(yīng)賣出該影子價(jià)錢市場(chǎng)價(jià)錢，那么應(yīng)賣出該資源資源2 2影子價(jià)錢反映了資源的稀缺性，影影子價(jià)錢反映了資源的稀缺性，影子價(jià)錢越高，那么越稀缺。子價(jià)錢越高，那么越稀缺。y1y2ym2對(duì)偶約束的經(jīng)濟(jì)解釋產(chǎn)品的時(shí)機(jī)本錢 (Opportunity Cost)時(shí)機(jī)本錢時(shí)機(jī)本錢表示減少一件產(chǎn)品所節(jié)省的資源可以添加的利潤(rùn)表示減少一件產(chǎn)品所節(jié)省的資源可以添加的利潤(rùn)mmjiijjjyayayaya2211添加單位資源可以添加的利潤(rùn)減少一件產(chǎn)

12、品可以節(jié)省的資源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211時(shí)機(jī)本錢利潤(rùn)差額本錢3對(duì)偶松弛變量的經(jīng)濟(jì)解釋產(chǎn)品的差額本錢Reduced Cost差額本錢差額本錢=時(shí)機(jī)本錢時(shí)機(jī)本錢 利潤(rùn)利潤(rùn)jjTjmjmjjjmcaYcayayayy)(22110. .min212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayatsybybybw0000

13、000000jjmjmjjmjiininiinixyyxyxyxxyxy 在利潤(rùn)最大化的消費(fèi)方案中 1影子價(jià)錢大于0的資源沒(méi)有剩余； 2有剩余的資源影子價(jià)錢等于0； 3安排消費(fèi)的產(chǎn)品時(shí)機(jī)本錢等于利潤(rùn)； 4時(shí)機(jī)本錢大于利潤(rùn)的產(chǎn)品不安排消費(fèi)。4互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋三、靈敏度分析三、靈敏度分析 討論模型的系數(shù)或變量發(fā)生小的變化討論模型的系數(shù)或變量發(fā)生小的變化時(shí)對(duì)解的影響時(shí)對(duì)解的影響如它們?cè)诤畏秶鷥?nèi)變化時(shí)可使原最優(yōu)解或如它們?cè)诤畏秶鷥?nèi)變化時(shí)可使原最優(yōu)解或最優(yōu)基不變？最優(yōu)基不變？我們主要討論C、b和變量構(gòu)造變化時(shí)對(duì)解的影響。對(duì)解怎樣影響？- 最優(yōu)性 - 可行性001bB1. b變化時(shí)的分析變化時(shí)的分析

14、 只影響解的可行性只影響解的可行性不變。則原最優(yōu)基使得故只要變化后的因?yàn)樗挥绊懣尚行?，變?yōu)榉N資源設(shè)第BbBbbbbrrrr0,1 的范圍即可。解出只要由rmrrbbbbbBbB01112. C變化時(shí)的分析變化時(shí)的分析但要分兩種情況討論。只影響最優(yōu)性時(shí)變?yōu)閮r(jià)格,jjjccc的范圍。解得只需由jjc 0即可。故只需，為因只影響本人的檢驗(yàn)數(shù)0, 1jjBjjjPBCcc的價(jià)錢系數(shù)是非基變量(1)jjxc 的價(jià)錢系數(shù)是基變量jjxc (2)。解得公共的應(yīng)由一切的數(shù)這時(shí)要影響一切的檢驗(yàn)jiimiiiicPBccccc0,)( 113.添加新變量時(shí)的分析添加新變量時(shí)的分析 主要討論添加新變量主要討論添加

15、新變量xn+1能否有利。經(jīng)濟(jì)意能否有利。經(jīng)濟(jì)意義是第義是第n+1種新產(chǎn)品能否該當(dāng)投產(chǎn)，數(shù)學(xué)意義是種新產(chǎn)品能否該當(dāng)投產(chǎn)，數(shù)學(xué)意義是xn+1能否應(yīng)進(jìn)基。能否應(yīng)進(jìn)基。，即投產(chǎn)無(wú)利。，則不增加若，即投產(chǎn)有利；，則增加若的檢驗(yàn)數(shù)方法：計(jì)算1111111110 0 ,nnnnnBnnnxx3BCcx1111nBnn3BCc經(jīng)濟(jì)意義：市場(chǎng)價(jià)影子價(jià)例：在例1煤電油例中，其單純形終表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z1電的影子價(jià)錢是多少？使最優(yōu)基仍適用的電的變 化范圍為何？

16、2假設(shè)有人愿以每度1元的價(jià)錢向該廠供應(yīng)25度電，是 否值得接受？3甲產(chǎn)品的價(jià)錢在何范圍內(nèi)變化時(shí)，現(xiàn)最優(yōu)解不變？4假設(shè)現(xiàn)又思索一新產(chǎn)品丙，其資源單耗為10，2，5， 售價(jià)為6.5，問(wèn)該產(chǎn)品能否可投產(chǎn)？例：在例1煤電油例中，其單純形終表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z1電的影子價(jià)錢是多少？使最優(yōu)基仍適用的電的變 化范圍為何？解：1電的影子價(jià)錢是1.36。解得由 00.120.43.12242084300200360221bbB仍適用的范圍。，即使原最優(yōu)基Bb

17、26.92502例：在例1煤電油例中，其單純形終表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z2假設(shè)有人愿以每度1元的價(jià)錢向該廠供應(yīng)25度電，是 否值得接受？解：2值得。 因25在B的適用范圍內(nèi)即影子價(jià)錢適用，且 1.36-1.000。0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z3甲產(chǎn)品的價(jià)錢在何范圍內(nèi)變化時(shí)，現(xiàn)最優(yōu)解不變？解：甲產(chǎn)品的價(jià)錢c1是基變量的價(jià)錢系數(shù)。044. 14 . 08 . 2