【文章內(nèi)容簡介】 練習 線性規(guī)劃的對偶理論 62 China University of Mining and Technology 運 籌 學 ? 對偶規(guī)劃可以用線性規(guī)劃的單純形法求解。 ?由對偶原理可見，原問題與對偶問題之間有緊密聯(lián)系，因此我們能夠通過求解原問題來找出對偶問題的解，反之依然。 ?互補松弛條件就可以解決由原問題的最優(yōu)解直接求出對偶問題的最優(yōu)解。 對偶問題解的求法 線性規(guī)劃的對偶理論 63 China University of Mining and Technology 運 籌 學 ? 原問題與對偶問題解的對應關系小結(jié) 對應關系 原問題 最優(yōu)解 無界解 無可行解 對偶問題 最優(yōu)解 (Y,Y) (N,N) —— —— 無界解 —— —— (Y,Y) 無可行解 —— (Y,Y) 無法判斷 線性規(guī)劃的對偶理論 65 China University of Mining and Technology 運 籌 學 影子價格 66 China University of Mining and Technology 運 籌 學 單位產(chǎn)品消耗的資源 (噸 /件 )) 原始問題是利潤最大化的生產(chǎn)計劃問題 總利潤 (元 ) 產(chǎn)品產(chǎn)量 (件 ) 單位產(chǎn)品的利潤 (元 /件 ) 消耗的資源 (噸 ) 剩余的資源 (噸 ) 資源限量 (噸 ) ????????????????????????????0bbbx,x,x,x,xx00xaxa0x0xaxa00xxaxaxcxczM axm21mn2n1nnmnnnmm2nnn21nnnnn?????????????????111121111111影子價格 67 China University of Mining and Technology 運 籌 學 對偶問題 —— 資源定價問題 對偶問題是資源定價問題，對偶問題的最優(yōu)解 y y ...、 ym稱為 m種資源的 影子價格 （ Shadow Price） 原始和對偶問題都取得最優(yōu)解時， 最大利潤 Max z=Min w 總利潤 (元 ) 資源限量 (噸 ) 資源價格 (元 /噸 ) ???????????????????????????0cccy,y,y,y,yy00yaya0y0yaya00yyayaybybwinMn21nm2m1mmnmmnm1n2mmm211mmmmm?????????????????111211111影子價格 68 China University of Mining and Technology 運 籌 學 在一對 P 和 D 中 ， 若 P 的某個約束條件的右端項常數(shù) bi （ 第 i 種資源的擁有量 ） 增加一個單位時 ， 所引起目標函數(shù)最優(yōu)值z* 的改變量稱為第 i 種資源的影子價格 ， 其值等于 D 問題中對偶變量 yi*。 由對偶問題得基本性質(zhì)可得： 1. 影子價格的數(shù)學分析： ????????????0 D 0 m i nm a x YCYAXbAXPYbW C X Z???????miiinjjj ybxcz11影子價格 69 China University of Mining and Technology 運 籌 學 2. 影子價格的經(jīng)濟意義 1）影子價格是一種邊際價格 在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標函數(shù)最優(yōu)值的變化。即對偶變量 yi 就是第 i 種資源的影子價格。即： )2,1(** miybZ ii?????影子價格 影子價格是針對某一具體約束條件而言 ,因此影子價格可理解為目標函數(shù)最優(yōu)值對資源的一階偏導數(shù) 70 China University of Mining and Technology 運 籌 學 資源影子價格的性質(zhì) ■ 影子價格越大，說明這種資源越是相對緊缺 ■ 影子價格越小，說明這種資源相對不緊缺 ■ 如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影子價格一定等于 0 種資源的邊際利潤第種資源的增量第最大利潤的增量 iibΔ zΔyiooi ???mmii ybybybybwz ??????? ??2211mmiii yby)bb(ybybzz ?????????? ??2211ii ybz ???影子價格 72 China University of Mining and Technology 運 籌 學 0 X2 X1 X= (15,) Z=975 602x3x 21 ??302xx 21 ??242x 2 ?ii ybz ???Max Z=40X1+ 50X2 X1+2X2 ? 30 3X1+2X2 ? 60 2X2 ? 24 X1 , X2 ?0 73 China University of Mining and Technology 運 籌 學 0 X2 X1 X= (15,) Z=975 602x3x 21 ??302xx 21 ??242x 2 ?312xx 21 ??X= (,) Z= ii ybz ???Max Z=40X1+ 50X2 X1+2X2 ? 30 3X1+2X2 ? 60 2X2 ? 24 X1 , X2 ?0 74 China University of Mining and Technology 運 籌 學 0 X2 X1 X= (15,) Z=975 602x3x 21 ??302xx 21 ??242x 2 ?612x3x 21 ??X= (,) Z= ii ybz ???Max Z=40X1+ 50X2 X1+2X2 ? 30 3X1+2X2 ? 60 2X2 ? 24 X1 , X2 ?0 75 China University of Mining and Technology 運 籌 學 0 X2 X1 X= (15,) Z=975 602x3x 21 ??302xx 21 ??242x 2 ?252x 2 ?ii ybz ???Max Z=40X1+ 50X2 X1+2X2 ? 30 3X1+2X2 ? 60 2X2 ? 24 X1 , X2 ?0 76 China University of Mining and Technology 運 籌 學 0 X2 X1 X= (15,) Z=975 602x3x 21 ??302xx 21 ??242x 2 ?612x3x 21 ??X= (,) Z= 312xx 21 ??X= (,) Z= 252x 2 ???????? 0215235*yii ybz ???Max Z=40X1+ 50X2 X1+2X2 ? 30 3X1+2X2 ? 60 2X2 ? 24 X1 , X2 ?0 77 China University of Mining and Technology 運 籌 學 2）影子價格是一種機會成本 影子價格是在資源最優(yōu)利用條件下對單位資源的估價，這種估價不是資源實際的市場價格。因此，從另一個角度說，它是一種機會成本。 若第 i 種資源的單位市場價格為 mi ，則有 當 yi* mi 時，企業(yè)愿意購進這種資源，單位純利為 yi*－ mi ，則有利可圖； 當 yi* mi 時，企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利 mi－ yi * ，否則，企業(yè)無利可圖，甚至虧損。 結(jié)論：若 yi* mi 則購進資源 i，可獲單位純利 yi*－ mi ； 若 yi* mi則轉(zhuǎn)讓資源 i ，可獲單位純利 mi－ yi 。 影子價格 78 China University of Mining and Technology 運 籌 學 y1 y2 ym 產(chǎn)品的機會成本 機會成本 表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤 mmjiijjj yayayaya ????? ??2211增加單位資源可以增加的利潤 減少一件產(chǎn)品可以節(jié)省的資源 0xxxxbxaxaxaxabxaxaxaxabxaxaxaxas .t .xcxcxcxczm axnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211??????????????????????????????????影子價格 79 China University of Mining and Technology 運 籌 學 機會成本 利潤 差額成本 0..212122112222221121112211112211??????????????????????nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayatsybybybWM i n????????????產(chǎn)品的差額成本（ Reduced Cost） 差額成本 =機會成本 利潤 jjTjmjmj22j11jm cayc)ayayay(y ???????? ?影子價格 80 China University of Mining and Technology 運 籌 學 3）影子價格在資源利用中的應用 根據(jù)對偶理論的互補松弛性定理 : Y*Xs=0 , YsX*=0 表明生產(chǎn)過程中如果某種資源 bi 未得到充分利用時，該種資源的影子價格為 0； 若當資源資源的影子價格不為 0時，表明該種資源在生產(chǎn)中已耗費完。 影子價格 81 China University of Mining and Technology 運 籌 學 yixn+i=0 如果 yi 0，則 xn+i =0 如果 x