第六節(jié)影子價(jià)格和對(duì)偶單純形法

1、chapter 2 duality theory and sensitivity analysis第第2章章 對(duì)偶理論與靈敏度分析對(duì)偶理論與靈敏度分析對(duì)偶問(wèn)題的基本性質(zhì)對(duì)偶問(wèn)題的基本性質(zhì)1.對(duì)稱性2.弱對(duì)偶性3.無(wú)界性4.最優(yōu)解性質(zhì)5.對(duì)偶定理6.互補(bǔ)松馳性7.原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系xbxnxs0cb-cbb-1n-cbb-1ys1-ys2-y0.xbaxtscxzmax0.ycyatsybzmin例題123451234512345min235232342330,1,.,5jxxxxxxxxxxxxxxxxj*124/5,3/5,5yyz練習(xí)練習(xí)第三章第三章 對(duì)偶理論與靈敏度分析對(duì)偶理論與靈敏

2、度分析第五節(jié)第五節(jié) 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格影子價(jià)格0.xbaxtscxzmax11bbzc b b y bzc bybxbxnxs0cb-cbb-1n-cbb-1ys1-ys2-y0.ycyatsybzmin第五節(jié)第五節(jié) 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格影子價(jià)格xbxnxs0cb-cbb-1n-cbb-1ys1-ys2-y影子價(jià)格影子價(jià)格（shadow price)不同于一般意義上的市場(chǎng)不同于一般意義上的市場(chǎng)價(jià)格，按照資源最優(yōu)分配理論價(jià)格，按照資源最優(yōu)分配理論, , 可定義為可定義為“機(jī)會(huì)成本機(jī)會(huì)成本的貨幣表現(xiàn)的貨幣表現(xiàn)”，是指某種資源或勞務(wù)被用于一種用，是指

3、某種資源或勞務(wù)被用于一種用途途, , 而放棄另一種用途時(shí)的價(jià)值。而放棄另一種用途時(shí)的價(jià)值。 這正是資源利用這正是資源利用問(wèn)題的數(shù)學(xué)規(guī)劃中對(duì)偶模型的最優(yōu)解問(wèn)題的數(shù)學(xué)規(guī)劃中對(duì)偶模型的最優(yōu)解。這是著名的。這是著名的前蘇聯(lián)數(shù)學(xué)家線性規(guī)劃創(chuàng)始人、諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)獲前蘇聯(lián)數(shù)學(xué)家線性規(guī)劃創(chuàng)始人、諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)獲得者康特羅維奇發(fā)現(xiàn)的。得者康特羅維奇發(fā)現(xiàn)的。檢驗(yàn)檢驗(yàn)線性規(guī)劃的圖解法例線性規(guī)劃的圖解法例2-1graphical solution of linear programming (4) 0,) 3 ( 8 ) 2( 5025 ) 1 ( 182 45212212121xxxxxxxxxmaxza（8，5）

4、第五節(jié)第五節(jié) 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)影子價(jià)格格1921822121xxxx)625. 5 ,75. 7(25.61625. 5475. 75maxz第五節(jié)第五節(jié) 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格影子價(jià)格512550252121xxxx).8754 ,25. 8(75.60875. 4425. 85maxz2289xx605485maxz第三章第三章 對(duì)偶理論與靈敏度分析對(duì)偶理論與靈敏度分析32185018yyyminz0,4225 5 32132121yyyyyyyy寫(xiě)出下面問(wèn)題的對(duì)偶問(wèn)題，然后用單純形法求解。寫(xiě)出下面問(wèn)題的對(duì)偶問(wèn)題，然后用單純形法求解。1212

5、1221254 218 5250 8 ,0 maxzxxxxxxxx x第三章第三章 對(duì)偶理論與靈敏度分析對(duì)偶理論與靈敏度分析32185018yyyminz0,4225 5 32132121yyyyyyyy6543210085018myyyyyyminz6 , 2 , 1 04 225 5 53216421jyyyyyyyyyj1850800mcbybby1y2y3y4 y5y6my65150-10118y342210-1025m+32zjm+165m+168m8m zj -cjm-25m340m-8050y211/510-1/501/558y328/5012/5-1-2/55/466zj22

6、.8508-6.8-86.8zj -cj4.800-6.8-86.8-m50y23/401-1/8-1/41/81/418y15/4105/81/4-5/8-1/460zj18505-8-58zj -cj00-3-8-58-m?第三章第三章 對(duì)偶理論與靈敏度分析對(duì)偶理論與靈敏度分析第六節(jié)第六節(jié) 對(duì)偶單純形法對(duì)偶單純形法一、對(duì)偶單純形法的基本原理一、對(duì)偶單純形法的基本原理 由原問(wèn)題與對(duì)偶問(wèn)題之間的關(guān)系知道，在單純由原問(wèn)題與對(duì)偶問(wèn)題之間的關(guān)系知道，在單純形表中進(jìn)行迭代時(shí)，在形表中進(jìn)行迭代時(shí)，在 b 列得到的是列得到的是原問(wèn)題的基可原問(wèn)題的基可行解行解，而在檢驗(yàn)數(shù)行得到的是，而在檢驗(yàn)數(shù)行得到的是對(duì)偶

7、問(wèn)題的基解對(duì)偶問(wèn)題的基解。經(jīng)。經(jīng)過(guò)迭代計(jì)算，當(dāng)檢驗(yàn)數(shù)行得到的對(duì)偶問(wèn)題的解也是過(guò)迭代計(jì)算，當(dāng)檢驗(yàn)數(shù)行得到的對(duì)偶問(wèn)題的解也是基可行解時(shí)，則得到最優(yōu)解?；尚薪鈺r(shí)，則得到最優(yōu)解。第六節(jié)第六節(jié) 對(duì)偶單純形法對(duì)偶單純形法32185018yyyminz0,4225 5 32132121yyyyyyyy二、對(duì)偶問(wèn)題的計(jì)算步驟二、對(duì)偶問(wèn)題的計(jì)算步驟1.列出初始單純形表；列出初始單純形表；2.若若b-1b0，j=cj zj 0，則問(wèn)題得到最優(yōu)解，否則問(wèn)題得到最優(yōu)解，否則進(jìn)入下一步；則進(jìn)入下一步；3.取取 對(duì)應(yīng)的基變量對(duì)應(yīng)的基變量xi*為換為換出變量；出變量；4.由由 確定換確定換入變量入變量xj*，當(dāng)所有的，當(dāng)

8、所有的ai*j 0時(shí)時(shí),問(wèn)題無(wú)可行解；問(wèn)題無(wú)可行解；*111)(0|iibbbbbbmin*0|jijjjijijjjazcaazcmin5. 以以ai*j*為主元素，按原單純形法進(jìn)行迭代，得到為主元素，按原單純形法進(jìn)行迭代，得到新的計(jì)算表；新的計(jì)算表；6. 重復(fù)重復(fù)25步。步。例：用對(duì)偶單純形法求例例：用對(duì)偶單純形法求例3-43-4的解的解32185018yyyminz0,4225 5 32132121yyyyyyyy543210085018)(yyyyyzmax0,4 225 5 543215321421yyyyyyyyyyyy第三章第三章 對(duì)偶理論與靈敏度分析對(duì)偶理論與靈敏度分析 -18

9、-50-800cbybby y1 1y y2 2y y3 3y y4 4 y y5 50y4-5-1-50100y5-4-2-2-101-z=0 cj -zj-18-50-800-50y23/401-1/8-1/41/8-18y15/4105/81/4-5/8-z=60cj -zj00-3-8-5-50y211/510-1/500y5-2-8/50-1-2/51-z=50cj -zj-80-8-100課堂討論課堂討論 比較單純形算法與對(duì)偶單純形比較單純形算法與對(duì)偶單純形算法的異同算法的異同 對(duì)偶單純形法例子123123123123min23423234,0 xxxxxxxxxxxx123671

10、234612357max234 2 32 3 40,1,.,7jxxxmxmxxxxxxxxxxxxj 1231234123512345max234 2 32 3 4,0 xxxxxxxxxxxx x x x x -2-3-40000-3-4-1-2-21-1-31001-2-3-400bxbcb1x2x3x4x5xjjcz5x4xjc 是是是是否否否否所有所有得到得到最優(yōu)解最優(yōu)解計(jì)算計(jì)算原規(guī)劃的基本解原規(guī)劃的基本解是可行的是可行的原規(guī)劃的基本解的原規(guī)劃的基本解的檢驗(yàn)數(shù)檢驗(yàn)數(shù)0所有所有計(jì)算計(jì)算以以aek為主元素進(jìn)行迭代為主元素進(jìn)行迭代以以aek為主元素進(jìn)行迭代為主元素進(jìn)行迭代停無(wú)界解無(wú)可行解單純形法單純形法對(duì)偶單純形法對(duì)偶單純形法0j0ib0maxjjk0miniiebbb0ika0ejaekeikikiabaab0minekkejejjaaa0minnjxmibxacxcfjnjijijnjjjj, 2 , 1, 0, 2 , 10min11 在引入松弛變量化為標(biāo)準(zhǔn)型之后，約束等式兩側(cè)同乘-1，能夠立即得到檢驗(yàn)數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對(duì)偶單純形表進(jìn)行求解，非常方便。 對(duì)于有些線性規(guī)劃模型，如果在開(kāi)始求解時(shí)不能很快使所有檢驗(yàn)數(shù)