三1矩陣表示對(duì)偶問題理論影子價(jià)格

1、 對(duì)偶理論與靈敏度分析對(duì)偶理論與靈敏度分析 (Dual Theories and Sensitivity Analysis) 單純形法的矩陣描述單純形法的矩陣描述 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì) 對(duì)偶問題的經(jīng)濟(jì)解釋對(duì)偶問題的經(jīng)濟(jì)解釋 -影子價(jià)格影子價(jià)格 對(duì)偶單純形法對(duì)偶單純形法 靈敏度分析靈敏度分析 0,12 4 16 482 s.t.32max21212121xxxxxxxxz 0,12 4 16 48 2 s.t.32 max54321524132121xxxxxxxxxxxxxxz 100400100400121A例例 12168b0 0 0

2、3 2 C 54321xxxxxX 單純形法的矩陣描述單純形法的矩陣描述 (Matrices Description) 251xxxXB 43xxXNXB x1 x2 x3 x4 x5 bx1 1 0 0 1/4 0 4x5 0 0 -2 0.5 1 4x2 0 1 0.5 -1/8 0 2-z 0 0 -3/2 -1/8 0 -14CB=2 0 3 CN=0 0 410004201B 001001N 單純形法的矩陣描述單純形法的矩陣描述 0,12 4 16 48 2 s.t.32 max54321524132121xxxxxxxxxxxxxxz.00,000 12168001001 4100

3、04201 s.t. 0 0 3 0 2 max432514325143251 xxxxxxxxxxxxxxxzBCBXBCNXNNb 單純形法的矩陣描述單純形法的矩陣描述 08/15 . 015 . 0204/101B 12168100001 41000420143251xxxxx 1216808/15 . 015 . 0204/1010000108/15 . 015 . 0204/10 43251xxxxx 2448/15 . 05 . 024/10 43251xxxxx 單純形法的矩陣描述單純形法的矩陣描述B-1 NB-1 b 單純形法的矩陣描述單純形法的矩陣描述考慮線性規(guī)劃問題的標(biāo)準(zhǔn)型

4、考慮線性規(guī)劃問題的標(biāo)準(zhǔn)型(LP) 0 s.t.max XbAXCXz A Cm n, R(A)=m .可行基可行基相應(yīng)于非基變量的系數(shù)矩陣相應(yīng)于非基變量的系數(shù)矩陣令令 A=(B N)X=(XB XN)TC=(CB CN) 0, s.t. max NBNBNNBBXXbNXBXXCXCz 0, s.t. )( max 1111NBNBNBNBXXbBNXBXXNBCCbBCz 單純形法的矩陣描述單純形法的矩陣描述 矩陣形式的單純形表矩陣形式的單純形表 XB XB XN b XB I B-1N B-1b - z 0 CN - CB B-1N - CB B-1b單純形表中變量單純形表中變量 xj 的

5、系數(shù)列向量的系數(shù)列向量 ： B-1aj 單純形表中約束方程的右端項(xiàng)單純形表中約束方程的右端項(xiàng)： B-1b 單純形表中目標(biāo)函數(shù)值單純形表中目標(biāo)函數(shù)值： CBB-1b單純形表中變量單純形表中變量 xj 的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) ： Cj - CBB-1aj 單純形法的矩陣描述單純形法的矩陣描述選定主元，做完初等變換以后（相當(dāng)于對(duì)增廣矩陣選定主元，做完初等變換以后（相當(dāng)于對(duì)增廣矩陣/線性線性方程組兩邊同時(shí)左乘了基的逆矩陣方程組兩邊同時(shí)左乘了基的逆矩陣B-1） 單純形法的矩陣描述單純形法的矩陣描述 5 . 020001 08/ 15 . 015 . 0204/ 1031aB?41 aB繼續(xù)討論上例繼續(xù)討論上例

6、?51 aBXB x1 x2 x3 x4 x5 bx1 1 0 0 1/4 0 4x5 0 0 -2 0.5 1 4x2 0 1 0.5 -1/8 0 2-z 0 0 -3/2 -1/8 0 -1408/15 . 015 . 0204/101B1412168 0 8/1 5 . 1 1bBCBCB=2 0 3 CBB -1=1.5 1/8 0 5 . 1001 0 8/1 5 . 1 03133aBCcB?4單純形法的矩陣描述單純形法的矩陣描述?1例例 用單純形法求解下述線性規(guī)劃問題用單純形法求解下述線性規(guī)劃問題. 0,12 4 16 482 s.t.32max21212121xxxxxxxx

7、z解解: 把原問題化為標(biāo)準(zhǔn)型把原問題化為標(biāo)準(zhǔn)型 0,12 4 16 48 2 s.t.32max54321524132121xxxxxxxxxxxxxxz 單純形法的矩陣描述單純形法的矩陣描述用單純形法求解如下用單純形法求解如下: 迭代迭代XB x1 x2 x3 x4 x5 b R x3 1 2 1 0 0 8 4x4 4 0 0 1 0 16 -x5 0 4 0 0 1 12 3-z 2 3 0 0 0 0XB x1 x2 x3 x4 x5 b R x3 1 0 1 0 -0.5 2 2x4 4 0 0 1 0 16 4x2 0 1 0 0 1/4 3 -z 2 0 0 0 -3/4 -9

8、1000100010B 4000102011B 單純形法的矩陣描述單純形法的矩陣描述 迭代迭代 迭代迭代 X*=(4, 2)T z*=14 XB x1 x2 x3 x4 x5 b Rx1 1 0 1 0 -0.5 2 - x4 0 0 -4 1 2 8 4 x2 0 1 0 0 1/4 3 12 -z 0 0 -2 0 1/4 -13XB x1 x2 x3 x4 x5 b R x1 1 0 0 1/4 0 4x5 0 0 -2 0.5 1 4x2 0 1 0.5 -1/8 0 2-z 0 0 -3/2 -1/8 0 -14 4000142012B 4100042013B 單純形法的矩陣描述單純

9、形法的矩陣描述線性規(guī)劃問題的對(duì)偶問題線性規(guī)劃問題的對(duì)偶問題 (Dual Problems)1. 對(duì)偶問題的提出對(duì)偶問題的提出 (Dual Problem)例例1 1 某工廠用兩臺(tái)機(jī)器生產(chǎn)三種產(chǎn)品某工廠用兩臺(tái)機(jī)器生產(chǎn)三種產(chǎn)品, ,有關(guān)數(shù)據(jù)如下表有關(guān)數(shù)據(jù)如下表: : 如何組織生產(chǎn)，使總利潤(rùn)最大？如何組織生產(chǎn)，使總利潤(rùn)最大？ . 0, 40574 135 s.t.3/1132max321321321321 xxxxxxxxxxxxZ 甲甲(m) (m) 乙乙(m) (m) 丙丙(m) (m) 限制條件限制條件機(jī)器機(jī)器 I 1 1 1 135機(jī)器機(jī)器 II 1 4 7 405利潤(rùn)利潤(rùn) 2 3 11/3

10、 x1 , x2 , x3 -分別生產(chǎn)甲、分別生產(chǎn)甲、乙、丙產(chǎn)品的數(shù)量乙、丙產(chǎn)品的數(shù)量例例2 2 若另一工廠想要租賃這兩臺(tái)機(jī)器用于生產(chǎn)產(chǎn)品，那么該若另一工廠想要租賃這兩臺(tái)機(jī)器用于生產(chǎn)產(chǎn)品，那么該 工廠應(yīng)該如何確定合理的租金呢？工廠應(yīng)該如何確定合理的租金呢？線性規(guī)劃問題的對(duì)偶問題線性規(guī)劃問題的對(duì)偶問題21405135minyyZ .0, 3/117 34 2 s.t.21212121 yyyyyyyy y1 , y2 - - - - 機(jī) 器機(jī) 器 I 與 機(jī) 器與 機(jī) 器 I I 的每臺(tái)時(shí)的租金的每臺(tái)時(shí)的租金例例1 1與例與例2 2是一個(gè)問題的兩個(gè)方面是一個(gè)問題的兩個(gè)方面兩個(gè)線性規(guī)劃模型是一對(duì)對(duì)

11、偶問題兩個(gè)線性規(guī)劃模型是一對(duì)對(duì)偶問題線性規(guī)劃問題的對(duì)偶問題線性規(guī)劃問題的對(duì)偶問題2. 原問題與對(duì)偶問題的關(guān)系原問題與對(duì)偶問題的關(guān)系 對(duì)稱性形式對(duì)稱性形式 OXbAXCXzs.t. max OYCYAbYwTTTs.t. min例例 3 3 求下列問題的對(duì)偶問題求下列問題的對(duì)偶問題 0,85 . 05 . 12205 . 12 448 6 8s.t.203060max321321321321321xxxxxxxxxxxxxxxz 0,205 .05 .1305 .12 6602 4 8s.t.82048min321321321321321yyyyyyyyyyyyyyyw 對(duì)稱性形式的對(duì)偶關(guān)系對(duì)稱

12、性形式的對(duì)偶關(guān)系 c c c y 0)( y 0)( 0)( 0) ( 0)( 0) ( min max n2121222221221112111 1n21n 21 mmnmmmmnnbaaaybaaaybaaayy xxxxxxwz線性規(guī)劃問題的對(duì)偶問題線性規(guī)劃問題的對(duì)偶問題非對(duì)稱性形式非對(duì)稱性形式 OXbAXCXzs.t. maxTTTCYAbYw s.t. min 0,74 max432142132121,253s.t.8+6xxxxxxxxxxxxz 練習(xí)：練習(xí)：線性規(guī)劃問題的對(duì)偶問題線性規(guī)劃問題的對(duì)偶問題 原原 (對(duì)偶對(duì)偶) 問題問題目標(biāo)函數(shù)目標(biāo)函數(shù) max z=CX 0n 個(gè)變量個(gè)

13、變量 0 自由變量自由變量 m 個(gè)約束個(gè)約束 AX b = 對(duì)偶對(duì)偶 (原原) 問題問題目標(biāo)函數(shù)目標(biāo)函數(shù) min w=YTb n 個(gè)約束個(gè)約束 ATY CT = 0m 個(gè)變量個(gè)變量 0 自由變量自由變量原問題與對(duì)偶問題對(duì)偶關(guān)系對(duì)照表原問題與對(duì)偶問題對(duì)偶關(guān)系對(duì)照表線性規(guī)劃問題的對(duì)偶問題線性規(guī)劃問題的對(duì)偶問題例例 4 4 求下列問題的對(duì)偶問題求下列問題的對(duì)偶問題 自自由由變變量量2121212121, 01322s.t.2maxxxxxxxxxxxz 00,122s.t.32 min321321321321yyyyyyyyyyyyw自自由由變變量量線性規(guī)劃問題的對(duì)偶問題線性規(guī)劃問題的對(duì)偶問題例例

14、5 5 求下列問題的對(duì)偶問題求下列問題的對(duì)偶問題 0,3 21 1 22 s.t.642min321213231321321yyyyyyyyyyyyyyyw自由變量自由變量 0 , , 0 ,6 4 222 s.t.32max43213214314214321xxxxxxxxxxxxxxxxxz自由變量自由變量線性規(guī)劃問題的對(duì)偶問題線性規(guī)劃問題的對(duì)偶問題考慮對(duì)稱性關(guān)系的對(duì)偶：考慮對(duì)稱性關(guān)系的對(duì)偶： 0s.t. max XbAXCXZ原原問問題題 0 s.t. min YCYAbYwTTT對(duì)對(duì)偶偶問問題題對(duì)稱性對(duì)稱性對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì)(Basic Properties)對(duì)偶問題

15、的對(duì)偶是原問題。對(duì)偶問題的對(duì)偶是原問題。弱對(duì)偶性弱對(duì)偶性wbYXczYX . 則則有有解解是是對(duì)對(duì)偶偶問問題題的的任任意意可可行行，是是原原問問題題的的任任意意可可行行解解若若若原若原(對(duì)偶對(duì)偶)問題有無界解，則對(duì)偶問題有無界解，則對(duì)偶(原原)問題無可行解問題無可行解.無界性無界性對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì)0, 1 1 . .max21212121xxxxxxtsxxz0, 1 1 . .min21212121yyyyyytsyyw原原對(duì)偶對(duì)偶0, 2 323 . .max21212121xxxxxxtsxxz0, 12 13 . .23min21212121yyyyyytsyyw原

16、原對(duì)偶對(duì)偶不可行不可行不可行不可行無界無界不可行不可行可行解是最優(yōu)解時(shí)的性質(zhì)可行解是最優(yōu)解時(shí)的性質(zhì)是是對(duì)對(duì)偶偶問問題題的的最最優(yōu)優(yōu)解解。是是原原問問題題的的最最優(yōu)優(yōu)解解，則則如如果果是是對(duì)對(duì)偶偶問問題題的的可可行行解解是是原原問問題題的的可可行行解解，設(shè)設(shè)Y X b,YXC .YXT 對(duì)偶定理對(duì)偶定理若原問題有最優(yōu)解，相應(yīng)的最優(yōu)基為若原問題有最優(yōu)解，相應(yīng)的最優(yōu)基為 B, 則對(duì)偶問題也有最優(yōu)解，且最則對(duì)偶問題也有最優(yōu)解，且最優(yōu)解為優(yōu)解為 (CBB -1)T ；并且目標(biāo)函數(shù)值相等，均為；并且目標(biāo)函數(shù)值相等，均為 CBB-1b . 對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì)互補(bǔ)松弛性互補(bǔ)松弛性令令 原問題

17、的可行解，原問題的可行解， 是對(duì)偶問題的可行解，則它們分別是原問題是對(duì)偶問題的可行解，則它們分別是原問題與對(duì)偶問題的最優(yōu)解的充要條件是與對(duì)偶問題的最優(yōu)解的充要條件是:XY 00TTTTCYAXXAbY原問題和對(duì)偶問題的基解的對(duì)應(yīng)關(guān)系原問題和對(duì)偶問題的基解的對(duì)應(yīng)關(guān)系對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì)基變量基變量XB非基變量非基變量XN檢驗(yàn)數(shù)（原問題）0CN-CBB-1N對(duì)偶問題的基解-YN-YB例例6 已知用單純形法求解下述線性規(guī)劃問題所得最終表如下，試確已知用單純形法求解下述線性規(guī)劃問題所得最終表如下，試確 定該問題的對(duì)偶問題的最優(yōu)解定該問題的對(duì)偶問題的最優(yōu)解. 0,12 4 16 482

18、s.t.32max21212121xxxxxxxxz對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì)解解: 由已知得由已知得 CB=(2 0 3),.08/15 .015 .0204/101 B因此，由對(duì)偶定理可得所求問題的對(duì)偶問題的最優(yōu)解為：因此，由對(duì)偶定理可得所求問題的對(duì)偶問題的最優(yōu)解為：TTBBCY)0 8/1 2/3()(1* XB x1 x2 x3 x4 x5 b R x1 1 0 0 1/4 0 4x5 0 0 -2 0.5 1 4x2 0 1 0.5 -1/8 0 2-z 0 0 -3/2 -1/8 0 -14其中其中 x3, x4, x5 為為 松弛變量。松弛變量。(Y*)Tb=?對(duì)偶問題

19、的基本性質(zhì)對(duì)偶問題的基本性質(zhì)例例 7 已知線性規(guī)劃問題已知線性規(guī)劃問題 0,85 . 05 . 12205 . 12 448 6 8s.t.203060max321321321321321xxxxxxxxxxxxxxxz且其最優(yōu)解為且其最優(yōu)解為x*1=2, x*2=0, x*3=8.試用對(duì)偶問題的性質(zhì)求其對(duì)偶問試用對(duì)偶問題的性質(zhì)求其對(duì)偶問題的最優(yōu)解。題的最優(yōu)解。對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì)解解: 0,205.05.1305.12 6602 4 8s.t.82048min321321321321321yyyyyyyyyyyyyyyw 將將 x x* *1 1=2, =2, x x* *2

20、 2=0, =0, x x* *3 3=8 =8 代入原線性規(guī)劃問題的約束條件中，可知第一個(gè)約束代入原線性規(guī)劃問題的約束條件中，可知第一個(gè)約束條件為嚴(yán)格不等式，則由互補(bǔ)松弛性得條件為嚴(yán)格不等式，則由互補(bǔ)松弛性得 y y* *1 1=0. =0. 對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì) 又因又因 x x* *1 1 x x* *3 300，所以對(duì)偶問題的第一個(gè)約束條件以及第三個(gè)約束條件所以對(duì)偶問題的第一個(gè)約束條件以及第三個(gè)約束條件 均應(yīng)取等式，即均應(yīng)取等式，即 8 8y y* *1 1+4+4 y y* *2 2+2+2y y* *3 3=60=60， y y* *1 1+1.5+1.5y y*

21、*2 2+0.5+0.5y y* *3 3=20. =20. 解之得解之得 y y* *2 2=10,=10, y y* *3 3=10.=10. 因此，對(duì)偶問題的最優(yōu)解為因此，對(duì)偶問題的最優(yōu)解為 y*1=0 , y*2=10, y*3=10. 0,85 . 05 . 12205 . 12 448 6 8s.t.203060max321321321321321xxxxxxxxxxxxxxxz線性規(guī)劃對(duì)偶問題的經(jīng)濟(jì)解釋線性規(guī)劃對(duì)偶問題的經(jīng)濟(jì)解釋 - -影子價(jià)格影子價(jià)格 (Shadow Prices)設(shè)設(shè) 與與 分別是原問分別是原問題與對(duì)偶問題的最優(yōu)解，則由對(duì)偶問題的基本性質(zhì)有題與對(duì)偶問題的最優(yōu)解

22、，則由對(duì)偶問題的基本性質(zhì)有TmxxxX),(*2*1* TnyyyY),(*2*1* *1*1*wbyxczmiiiniii 由此，由此，) ,.,2 , 1( *miybzii 變量變量 的的經(jīng)濟(jì)意義經(jīng)濟(jì)意義是：是：在其他條件不變的情況下，在其他條件不變的情況下， 第第 i種資源的單位改變量所引起的目標(biāo)函數(shù)值的增加量種資源的單位改變量所引起的目標(biāo)函數(shù)值的增加量。*iy1 1 影子價(jià)格的解釋影子價(jià)格的解釋 變量變量 的值代表對(duì)第的值代表對(duì)第 i 種資源的估價(jià)。這種估價(jià)不是資種資源的估價(jià)。這種估價(jià)不是資 源源 i 的市場(chǎng)價(jià)格，而是具體工廠根據(jù)資源在生產(chǎn)中做出的貢的市場(chǎng)價(jià)格，而是具體工廠根據(jù)資源在

23、生產(chǎn)中做出的貢 獻(xiàn)而作的估價(jià)，稱它為獻(xiàn)而作的估價(jià)，稱它為 “影子價(jià)格影子價(jià)格 ”。*iy 影子價(jià)格是對(duì)偶解的一個(gè)十分形象的名稱，它既表明了對(duì)偶影子價(jià)格是對(duì)偶解的一個(gè)十分形象的名稱，它既表明了對(duì)偶 解是對(duì)系統(tǒng)內(nèi)部資源的一種客觀估價(jià)，又表明它是一種虛解是對(duì)系統(tǒng)內(nèi)部資源的一種客觀估價(jià)，又表明它是一種虛 擬的價(jià)格，而不是真實(shí)的價(jià)格。擬的價(jià)格，而不是真實(shí)的價(jià)格。線性規(guī)劃對(duì)偶問題的經(jīng)濟(jì)解釋線性規(guī)劃對(duì)偶問題的經(jīng)濟(jì)解釋- -影子價(jià)影子價(jià)格格例例 某工廠用三臺(tái)機(jī)器生產(chǎn)兩種產(chǎn)品某工廠用三臺(tái)機(jī)器生產(chǎn)兩種產(chǎn)品, ,有關(guān)數(shù)據(jù)如下表有關(guān)數(shù)據(jù)如下表: : 如何組織生產(chǎn)，使總利潤(rùn)最大？如何組織生產(chǎn)，使總利潤(rùn)最大？ 甲甲(m) (m) 乙乙(m) (m) 可供資源可供資源( (臺(tái)時(shí)臺(tái)時(shí)) ) 機(jī)器機(jī)器 I 1 2 8 機(jī)器機(jī)器 II 4 0 16 機(jī)器機(jī)器 III 0 4 12 利潤(rùn)利潤(rùn) 2 3 x1 , x2 -分別生產(chǎn)甲、分別生產(chǎn)甲、乙產(chǎn)品的數(shù)量乙產(chǎn)品的數(shù)量 0,12 4 16 482 s.t.32max21212121xxxxxxxxz X*=(4, 2)T z*=14 線性規(guī)劃對(duì)偶問題的經(jīng)濟(jì)解釋線性規(guī)劃對(duì)偶問題的經(jīng)