三1矩陣表示對偶問題理論影子價格

1、 對偶理論與靈敏度分析對偶理論與靈敏度分析 (Dual Theories and Sensitivity Analysis) 單純形法的矩陣描述單純形法的矩陣描述 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì) 對偶問題的經(jīng)濟(jì)解釋對偶問題的經(jīng)濟(jì)解釋 -影子價格影子價格 對偶單純形法對偶單純形法 靈敏度分析靈敏度分析 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 單純形表中約束方程的右端項單純形表中約束方程的右端項： B-1b 單純形表中目標(biāo)函數(shù)值單純形表中目標(biāo)函數(shù)值： CBB-1b單純形表中變量單純形表中變量 xj 的檢驗數(shù)的檢驗數(shù) ： Cj - CBB-1aj 單純形法的矩陣描述單純形法的矩陣描述選定主元，做完初等變換以后（相當(dāng)于對增廣矩陣選定主元，做完初等變換以后（相當(dāng)于對增廣矩陣/線性線性方程組兩邊同時左乘了基的逆矩陣方程組兩邊同時左乘了基的逆矩陣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ī)劃問題的對偶問題線性規(guī)劃問題的對偶問題 (Dual Problems)1. 對偶問題的提出對偶問題的提出 (Dual Problem)例例1 1 某工廠用兩臺機(jī)器生產(chǎn)三種產(chǎn)品某工廠用兩臺機(jī)器生產(chǎn)三種產(chǎn)品, ,有關(guān)數(shù)據(jù)如下表有關(guān)數(shù)據(jù)如下表: : 如何組織生產(chǎn)，使總利潤最大？如何組織生產(chǎ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利潤利潤 2 3 11/3

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

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

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

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

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

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

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

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

18、s.t.32max21212121xxxxxxxxz對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)解解: 由已知得由已知得 CB=(2 0 3),.08/15 .015 .0204/101 B因此，由對偶定理可得所求問題的對偶問題的最優(yōu)解為：因此，由對偶定理可得所求問題的對偶問題的最優(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=?對偶問題

19、的基本性質(zhì)對偶問題的基本性質(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.試用對偶問題的性質(zhì)求其對偶問試用對偶問題的性質(zhì)求其對偶問題的最優(yōu)解。題的最優(yōu)解。對偶問題的基本性質(zhì)對偶問題的基本性質(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ī)劃問題的約束條件中，可知第一個約束代入原線性規(guī)劃問題的約束條件中，可知第一個約束條件為嚴(yán)格不等式，則由互補松弛性得條件為嚴(yán)格不等式，則由互補松弛性得 y y* *1 1=0. =0. 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì) 又因又因 x x* *1 1 x x* *3 300，所以對偶問題的第一個約束條件以及第三個約束條件所以對偶問題的第一個約束條件以及第三個約束條件 均應(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. 因此，對偶問題的最優(yōu)解為因此，對偶問題的最優(yōu)解為 y*1=0 , y*2=10, y*3=10. 0,85 . 05 . 12205 . 12 448 6 8s.t.203060max321321321321321xxxxxxxxxxxxxxxz線性規(guī)劃對偶問題的經(jīng)濟(jì)解釋線性規(guī)劃對偶問題的經(jīng)濟(jì)解釋 - -影子價格影子價格 (Shadow Prices)設(shè)設(shè) 與與 分別是原問分別是原問題與對偶問題的最優(yōu)解，則由對偶問題的基本性質(zhì)有題與對偶問題的最優(yōu)解

22、，則由對偶問題的基本性質(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 影子價格的解釋影子價格的解釋 變量變量 的值代表對第的值代表對第 i 種資源的估價。這種估價不是資種資源的估價。這種估價不是資 源源 i 的市場價格，而是具體工廠根據(jù)資源在生產(chǎn)中做出的貢的市場價格，而是具體工廠根據(jù)資源在

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