02運(yùn)籌學(xué)-對(duì)偶理論與靈敏度分析

1、第 二 章,線性規(guī)劃的對(duì)偶模型 對(duì)偶性質(zhì) 對(duì)偶問題的經(jīng)濟(jì)解釋－影子價(jià)格 對(duì)偶單純形法 靈敏度分析,本章主要內(nèi)容：,對(duì)偶理論是線性規(guī)劃中最重要的理論之一，是深入了解線性規(guī)劃問題結(jié)構(gòu)的重要理論基礎(chǔ)。同時(shí)，由于問題提出本身所具有的經(jīng)濟(jì)意義，使得它成為對(duì)線性規(guī)劃 問題系統(tǒng)進(jìn)行經(jīng)濟(jì)分析和敏感性分析的重要工具。那么，對(duì)偶問題是怎樣提出的，為什么會(huì)產(chǎn)生這樣一種問題呢？ 且看下面詳解……,§2.1 、線性規(guī)劃

2、的對(duì)偶模型,,對(duì)偶與靈敏度,4,1、對(duì)偶問題的提出引例——倆家具制造商間的對(duì)話：,唉!我想租您的木工和油漆工一用。咋樣？價(jià)格嘛……好說，肯定不會(huì)讓您兄弟吃虧訕。,王老板做家具賺了 大錢，可惜我老李有 高科技產(chǎn)品，卻苦于沒有足夠的木工和油漆工 咋辦？只有租咯。,Hi：王老板，聽說近來家具生意好慘了，也幫幫兄弟我哦!,家具生意還真賺錢，但 是現(xiàn)在的手機(jī)生意這么好， 不如干脆把我的木工和油漆

3、工租給他，又能收租金又可做生意。,價(jià)格嘛……好商量， 好商量。只是…...,王 老 板,李 老 板,在市場競爭的時(shí)代，廠長的最佳決策顯然應(yīng)符合兩條： （1）不吃虧原則。即機(jī)時(shí)定價(jià)所賺利潤不能低于加工甲、乙型產(chǎn)品所獲利潤。由此原則，便構(gòu)成了新規(guī)劃的不等式約束條件。 （2）競爭性原則。即在上述不吃虧原則下，盡量降低機(jī)時(shí)總收費(fèi)，以便爭取更多用戶。,對(duì)偶與靈敏度,6,線性規(guī)劃的對(duì)偶理論 王老板按（D）的

4、解 y1 、y2出租其擁有的木、漆工資源，既保證了自己不吃虧（出租資源的租金收入并不低于自己生產(chǎn)時(shí)的銷售收入），又使得出租價(jià)格對(duì)李老板有極大的吸引力（李老板所付出的總租金W最少）。,按時(shí)下最流行的一個(gè)詞，叫什么來著————,對(duì)偶與靈敏度,7,2、線性規(guī)劃的對(duì)偶理論例2.1某工廠擁有A、B、C三種類型的原料，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中消耗的原料數(shù)量，每件產(chǎn)品的價(jià)格以及三種原料可利用的數(shù)量如下表所示：,對(duì)偶與靈敏度,8,問題：工

5、廠應(yīng)如何安排生產(chǎn)可獲得最大的總收益？解：設(shè)變量xi為第i種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)（i＝1，2）。則有目標(biāo)函數(shù) Max z = 50x1 + 100x2 s.t. x1 + x2 ≤300 2x1 + x2 ≤ 400

6、 x2 ≤ 250 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0,對(duì)偶與靈敏度,9,現(xiàn)在考慮若三種原料都用于轉(zhuǎn)讓，試問：三種原料各如何收費(fèi)才能即保證本廠的利益，有能最有競爭力？ 設(shè) y1 ，y2 ，y3 分別為每設(shè)備工時(shí)（或原料）每單位的收取費(fèi)用，則有,Min f = 300y1+ 400y2 +

7、250y3 s.t.y1+2y2 ≥ 50（不少于甲產(chǎn)品的利潤） y1+ y2+y3 ≥100（不少于乙產(chǎn)品的利潤） y1,y2 ,y3 ≥ 0,對(duì)偶與靈敏度,10,Min f = 300y1+ 400y2 + 250y3 s.t. y1+2y2 ≥ 50 y1+ y2+ y3 ≥100 y

8、1, y2 , y3 ≥ 0,Max z = 50x1 + 100x2 s.t. x1 + x2 ≤300 2x1 + x2 ≤ 400

9、 x2 ≤ 250 x1 , x2 ≥ 0,對(duì)偶問題租賃者模型,原問題管理者模型,一對(duì)互為對(duì)偶的模型,LP,DP,對(duì)偶與靈敏度,11,對(duì)偶問題的定義： （對(duì)稱形式）,（LP ） max Z=c1 x1 + c2 x2 + ... + cn xn s.t. a11x1 + a12 x2 + ... + a1nxn ? b

10、1 . . . . . . am1x1 + am2x2 + ...+ amn xn ? bm x1 , x2 , ... , xn ? 0（DP） min W=b1 y1+ b2 y2+ ... + bm ym s.t. a11y1+ a21 y2+ ... + am1 ym ? c1 . .

11、. . . . a1ny1+ a2n y2+ ... + amnym ? cn y1 , y2 , ... , ym ? 0,對(duì)偶與靈敏度,12,(LP) Max z = cT x (DP) Min f = bT y s.t. Ax ≤ b s.t. AT y ≥

12、c x ≥ 0 y ≥ 0 則（DP）稱為（LP）的對(duì)稱形式對(duì)偶問題,設(shè)：,對(duì)偶與靈敏度,13,線性規(guī)劃的對(duì)偶模型,,,,,,,,,,,,,對(duì)偶與靈敏度,14,線性規(guī)劃的對(duì)偶理論對(duì)稱形式下對(duì)偶問題的一般形式,對(duì)偶與靈敏度,15,例2．2 寫出下面線性規(guī)劃的對(duì)偶規(guī)劃模型,解：按照對(duì)稱形式的對(duì)偶關(guān)系，其對(duì)偶模型為,對(duì)偶與靈敏度,16,對(duì)

13、偶與靈敏度,17,例2.3 寫出線性規(guī)劃問題的對(duì)偶問題,解：首先將原問題變形為對(duì)稱形式,注意：以后不強(qiáng)調(diào)等式右段項(xiàng) b≥0，原因在對(duì)偶單純型表中只保證 而不保證 ，故 b可以是負(fù)數(shù)。,對(duì)偶與靈敏度,18,對(duì)偶與靈敏度,19,3、一般形式的對(duì)偶問題,1. 如何將一般問題轉(zhuǎn)化為對(duì)偶問題,原問題和對(duì)偶問題有很多內(nèi)在聯(lián)系，它們之間存在嚴(yán)格的對(duì)應(yīng)關(guān)系：目標(biāo)函數(shù)類型之間的對(duì)應(yīng)關(guān)系；目標(biāo)函數(shù)系數(shù)與右邊項(xiàng)的對(duì)應(yīng)關(guān)系；

14、約束系數(shù)矩陣之間的對(duì)應(yīng)關(guān)系；約束類型與變量類型之間的對(duì)應(yīng)關(guān)系；,對(duì)偶與靈敏度,20,非對(duì)稱形式的對(duì)偶規(guī)劃 一般稱不具有對(duì)稱形式的一對(duì)線性規(guī)劃為非對(duì)稱形式的對(duì)偶規(guī)劃。 對(duì)于非對(duì)稱形式的規(guī)劃，可以按照下面 的對(duì)應(yīng)關(guān)系直接給出其對(duì)偶規(guī)劃。 （1）將模型統(tǒng)一為“max，≤”或“min，≥” 的形式，對(duì)于其中的等式約束按下面（2）、（3）中的方法處理； （2）若原規(guī)劃的某個(gè)約束條件為等式約束，則在對(duì)偶規(guī)劃中與此約束對(duì)應(yīng)的

15、那個(gè)變量取值沒有非負(fù)限制；,對(duì)偶與靈敏度,21,（3）若原規(guī)劃的某個(gè)變量的值沒有非負(fù)限制，則在對(duì)偶問題中與此變量對(duì)應(yīng)的那個(gè)約束為等式。 下面對(duì)關(guān)系（2）做一說明。對(duì)于關(guān)系（3）可以給出類似的解釋。 設(shè)原規(guī)劃中第1個(gè)約束為等式： a11x1 +a12+…+ a1nxn = b1 那么，這個(gè)等式與下面兩個(gè)不等式等價(jià),對(duì)偶與靈敏度,22,這樣，原規(guī)劃模型可以寫成,對(duì)偶與靈敏度,23,此時(shí)已轉(zhuǎn)化為對(duì)稱

16、形式，直接寫出對(duì)偶規(guī)劃,令 y1 = y1’ - y1’’，于是有,對(duì)偶與靈敏度,24,一般情況，我們總結(jié)如下：,對(duì)偶與靈敏度,25,非對(duì)稱形式下對(duì)偶問題的一般形式 —原始（對(duì)偶）對(duì)偶（原始）關(guān)系表,對(duì)偶與靈敏度,26,習(xí)題2.4寫出下列線性規(guī)劃的對(duì)偶問題：（1）,s.t.,,(LP),若給出的線性規(guī)劃不是對(duì)稱形式，可以先化成對(duì)稱形式再寫對(duì)偶問題。也可直接按表中的對(duì)應(yīng)關(guān)系寫出非對(duì)稱形式的對(duì)偶問題。,對(duì)偶與靈敏度,27,

17、解：原問題求max，現(xiàn)將約束條件變形為“≤”形式，得到,s.t.,,對(duì)偶與靈敏度,28,再根據(jù)非對(duì)稱形式的對(duì)應(yīng)關(guān)系，直接寫出對(duì)偶規(guī)劃：,s.t.,,令,（DP）,對(duì)偶與靈敏度,29,LP,DP,,,對(duì)偶與靈敏度,30,例 2. 4 寫出下列問題的對(duì)偶問題：,對(duì)偶與靈敏度,31,解 ：先將約束條件變形為“≤”形式,對(duì)偶與靈敏度,32,再根據(jù)非對(duì)稱形式的對(duì)應(yīng)關(guān)系，直接寫出對(duì)偶規(guī)劃,對(duì)偶與靈敏度,33,例2. 5 寫出下列線性規(guī)劃

18、問題的對(duì)偶問題.,解：原問題的對(duì)偶問題為,對(duì)偶與靈敏度,34,習(xí)題2.4（3）,,s.t.,對(duì)偶與靈敏度,35,解：由非對(duì)稱形式的對(duì)應(yīng)關(guān)系，得對(duì)偶規(guī)劃,,s.t.,對(duì)偶與靈敏度,36,課堂練習(xí),對(duì)偶與靈敏度,37,對(duì)偶與靈敏度,38,考慮下面一對(duì)對(duì)偶問題：P max z = CT X D min w = bTY s.t. AX ? b s.t. ATY ?

19、 c X ? 0 Y ? 0,A為m×n階矩陣，A的秩為m。引入松弛變量Xs，得到原規(guī)劃（P）的標(biāo)準(zhǔn)型為（P1）,§2.2 、對(duì)偶規(guī)劃的基本性質(zhì),,對(duì)偶與靈敏度,39,其中01和I分別為m維的零向量和m維的單位矩陣。,記,則上面的標(biāo)準(zhǔn)型可記為（P2）,對(duì)偶與靈敏度,40,設(shè)B為一可行基，并記,,得到模型（P2）的另一表示形式,,對(duì)偶與靈敏度

20、,41,性質(zhì)1 對(duì)稱性定理：對(duì)偶問題的對(duì)偶是原問題,min Z’= - CXs.t. - AX≤- bX ≥0,,,max W’ = -Ybs.t. YA≥ C Y ≤ 0,對(duì)偶與靈敏度,42,性質(zhì)2 弱對(duì)偶原理(弱對(duì)偶性)：設(shè) 和 分別是問題(P)和(D)的可行解，則必有,推論1: 原問題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的下界；反之，對(duì)偶問題任意可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)

21、值的上界。,推論2: 在一對(duì)對(duì)偶問題（P）和（D）中，若其中一個(gè)問題可行但目標(biāo)函數(shù)無界，則另一個(gè)問題無可行解；反之不成立。這也是對(duì)偶問題的無界性。,對(duì)偶與靈敏度,43,對(duì)偶與靈敏度,44,性質(zhì)3 最優(yōu)性定理：如果 是原問題的可行解， 是其對(duì)偶問題的可行解，并且:,則 是原問題的最優(yōu)解， 是其對(duì)偶問題的最優(yōu)解。,例如:在一對(duì)對(duì)偶問題（P）和（D）中，可找到 X*=（0.0.4.4）， Y*=（1.2，0.2）,且

22、Z=W28 ，則X*，Y*分別是 P和D 的最優(yōu)解。,對(duì)偶與靈敏度,45,性質(zhì)4 強(qiáng)對(duì)偶性：若原問題及其對(duì)偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。,還可推出另一結(jié)論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個(gè)問題無最優(yōu)解，則另一問題也無最優(yōu)解。,證： 考慮原規(guī)劃（P）的標(biāo)準(zhǔn)型（P2）,設(shè)B為模型（P2）的最優(yōu)基，現(xiàn)在證明對(duì)偶規(guī)劃（D）也有最優(yōu)解。由單純形法可知，此時(shí),對(duì)偶與靈敏度,46,

23、為對(duì)偶規(guī)劃（D）的可行解。另一方面有,因此,對(duì)偶與靈敏度,47,其中,為原規(guī)劃的最優(yōu)解。由定理2.3可知，為對(duì)偶規(guī)劃（D）的最優(yōu)解。,類似地，可以證明，若規(guī)劃（D）有最優(yōu)解，則規(guī)劃（P）也有最優(yōu)解。,可以看到，對(duì)偶規(guī)劃（D）的最優(yōu)解為：,對(duì)偶與靈敏度,48,例2.6 試用對(duì)偶理論判斷下面線性規(guī)劃是否有最優(yōu)解,,解: 此規(guī)劃存在可行解 ，其對(duì)偶規(guī)劃為,,對(duì)偶與靈敏度,49,,顯然，對(duì)偶規(guī)劃沒有可

24、行解，因此，原規(guī)劃沒有最優(yōu)解。,對(duì)偶與靈敏度,50,例2.7 用對(duì)偶理論判斷下面線性規(guī)劃是否存在最優(yōu)解,,解: 此規(guī)劃存在可行解，其對(duì)偶規(guī)劃為,對(duì)偶與靈敏度,51,,,對(duì)偶規(guī)劃也存在可行解,因此原規(guī)劃存在最優(yōu)解。,對(duì)偶與靈敏度,52,例2.8 求解下面線性規(guī)劃問題，并根據(jù)最優(yōu)單純形表中的檢驗(yàn)數(shù)，給出其對(duì)偶問題的最優(yōu)解。,解 引入松弛變量、將模型化為標(biāo)準(zhǔn)型，經(jīng)求解后得到其最優(yōu)單純形表,對(duì)偶與靈敏度,53,對(duì)偶規(guī)劃的最優(yōu)解為 :,即原問題

25、最優(yōu)表中松弛變量檢驗(yàn)數(shù)的相反數(shù),對(duì)偶與靈敏度,54,性質(zhì)5 互補(bǔ)松弛性：設(shè)X0和Y0分別是P問題 和 D問題 的可行解，則它們分別是最優(yōu)解的充要條件是：,其中：Xs、Ys為松弛變量,互補(bǔ)松弛定理(又稱松緊定理)描述了線性規(guī)劃達(dá)到最優(yōu)時(shí)，原問題(或?qū)ε紗栴})變量取值和對(duì)偶問題(或原問題)約束松緊之間的對(duì)應(yīng)關(guān)系。,對(duì)偶與靈敏度,55,性質(zhì)5的應(yīng)用：該性質(zhì)給出了已知一個(gè)問題最優(yōu)解求另一個(gè)問題最優(yōu)解的方法，即已知Y＊求X＊或已知X＊求Y＊

26、,,互補(bǔ)松弛條件,由于松弛變量都非負(fù)，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系：若Y＊≠0，則Xs必為0；若X＊≠0，則Ys必為0利用上述關(guān)系，建立對(duì)偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。,對(duì)偶與靈敏度,56,互補(bǔ)松弛定理證明了最優(yōu)線性規(guī)劃的下列對(duì)應(yīng)關(guān)系： 原問題約束為緊 ? 對(duì)偶變量 ? 0； 原問題約束為松 ? 對(duì)偶變量=0； 對(duì)偶約束為緊 ? 原問題變量 ? 0； 對(duì)偶約束為松

27、 ? 原問題變量=0； 原問題變量>0 ? 對(duì)偶約束為緊約束； 原問題變量=0 ? 對(duì)偶約束可緊可松。,對(duì)偶與靈敏度,57,例2.9 已知線性規(guī)劃 min z = 2x1 + 3x2 + 5x3 + 2x4 + 3x5 s.t. x1 + x2 + 2x3 + x4 + 3x5 ? 4 2x1 - x2 + 3x3 + x4 + x5 ? 3 x1 ,

28、 x2 , x3 , x4 , x5 ? 0其對(duì)偶問題的最優(yōu)解為：y1* = 0.8, y2* = 0.6。試用對(duì)偶理論求出它的原問題的最優(yōu)解,對(duì)偶與靈敏度,58,對(duì)偶問題： Max w= 4y1 + 3y2 s.t. y1 + 2y2 ? 2 y1 - y2 ? 3 2y1+ 3y2 ? 5 y1+ y2 ? 2 3y1+ y2 ? 3

29、 y1 ? 0, y2 ? 0,代入y1*=0.8, y2*=0.6,松約束? x2 = 0,緊約束? x1 ? 0,松約束? x3 = 0,松約束? x4 = 0,緊約束? x5 ? 0,對(duì)偶與靈敏度,59,原問題的約束為緊約束, 故有: x1 + 3x5 = 4 2x1 + x5 = 3解得：x1* = 1， x5* = 1原問題的最優(yōu)解為：X = (1 , 0 , 0 , 0

30、 , 1) , z* = 5,對(duì)偶與靈敏度,60,例2. 10 已知線性規(guī)劃,的最優(yōu)解是X＊=(6,2,0)T,求其對(duì)偶問題的最優(yōu)解Y＊。,解：寫出原問題的對(duì)偶問題，即,,標(biāo)準(zhǔn)化,,對(duì)偶與靈敏度,61,設(shè)對(duì)偶問題最優(yōu)解為Y＊＝(y1，y2),由互補(bǔ)松弛性定理可知，X＊和 Y＊滿足：,即：,因?yàn)閄1=6≠0，X2=2≠0，所以對(duì)偶問題的第一、二個(gè)約束的松弛變量等于零，即y3＝0，y4＝0，帶入方程中：,解此線性方程組得y1=1,y

31、2=1,從而對(duì)偶問題的最優(yōu)解為：Y＊=(1,1)，最優(yōu)值w=26。,,對(duì)偶與靈敏度,62,例2.11 已知線性規(guī)劃,的對(duì)偶問題的最優(yōu)解為Y＊=(0,-2)，求原問題的最優(yōu)解。,解: 對(duì)偶問題是,,標(biāo)準(zhǔn)化,無約束,對(duì)偶與靈敏度,63,設(shè)對(duì)偶問題最優(yōu)解為X＊＝(x1，x2 ，x3)T ,由互補(bǔ)松弛性定理可知，X＊和 Y＊滿足：,將Y＊ =(0,-2)帶入由方程可知，y3＝y(tǒng)5＝0，y4＝1。,∵y2=-2≠0 ∴x5＝0又∵y4=

32、1≠0 ∴x2＝0,將x2，x5分別帶入原問題約束方程中，得：,解方程組得：x1=-5,x3=-1, 所以原問題的最優(yōu)解為,X＊=(-5,0,-1)，最優(yōu)值z(mì)=-12,對(duì)偶與靈敏度,64,線性規(guī)劃的對(duì)偶理論原問題與對(duì)偶問題解的對(duì)應(yīng)關(guān)系表,對(duì)偶與靈敏度,65,線性規(guī)劃的對(duì)偶理論對(duì)偶問題的基本性質(zhì)對(duì)稱性——原始問題與對(duì)偶問題是兩個(gè)互為對(duì)偶的問題。弱對(duì)偶性——兩個(gè)問題的可行解對(duì)應(yīng)的目標(biāo)函數(shù)值互為上下界。最優(yōu)性——兩個(gè)問題最優(yōu)解

33、的目標(biāo)函數(shù)值必相等。強(qiáng)對(duì)偶性——兩個(gè)問題都有可行解時(shí)則兩個(gè)問題必都有最優(yōu)解?；パa(bǔ)松弛性——兩個(gè)問題最優(yōu)解中，一個(gè)問題中某個(gè)變量取值非零，則該變量在對(duì)偶問題中對(duì)應(yīng)的某個(gè)約束條件必為緊約束；反之，如果約束條件為松約束，則其對(duì)應(yīng)的對(duì)偶變量一定取值為零。因此，該定理又稱為松緊定理。,對(duì)偶與靈敏度,66,定義：在一對(duì) P 和 D 中，若 P 的某個(gè)約束條件的右端項(xiàng)常數(shù)bi （第i種資源的擁有量）增加一個(gè)單位時(shí)，所引起目標(biāo)函數(shù)最優(yōu)值z(mì)* 的改變

34、量稱為第 i 種資源的影子價(jià)格，其值等于D問題中對(duì)偶變量yi*。,由對(duì)偶問題得基本性質(zhì)可得：,§2.3 對(duì)偶解的經(jīng)濟(jì)解釋—影子價(jià)格,,對(duì)偶與靈敏度,67,對(duì)偶解的數(shù)學(xué)意義：當(dāng)?shù)玫阶顑?yōu)解后，目標(biāo)函數(shù)值 z =CTX* = bT Y*,z = y1b1+y2b2+….+ymbm 將b1,b2,…bm看作變量，對(duì)右邊項(xiàng)求偏導(dǎo) ?z ? ?bi = yi對(duì)偶解的意義是：當(dāng)取得最優(yōu)解的前提下，右邊資源項(xiàng) bi 的單

35、位改變量（其他參數(shù)不變）所引起目標(biāo)函數(shù) z 的改變量。,對(duì)偶與靈敏度,68,如果把線性規(guī)劃約束看成廣義資源約束，右邊項(xiàng)代表資源的可用量，其經(jīng)濟(jì)含義是資源對(duì)經(jīng)濟(jì)目標(biāo)的邊際貢獻(xiàn)。目標(biāo)函數(shù)值通常用價(jià)值量衡量，對(duì)偶解也具有價(jià)值內(nèi)涵，被稱為影子價(jià)格。影子價(jià)格是對(duì)偶解十分形象的名稱，它既表明對(duì)偶解是對(duì)資源的一種客觀估價(jià)，又表明它是虛擬而不是真實(shí)的價(jià)格。因此，從另一個(gè)角度說，它是一種機(jī)會(huì)成本。,對(duì)偶解的經(jīng)濟(jì)意義：,對(duì)偶與靈敏度,69,影子價(jià)格有以

36、下幾個(gè)特點(diǎn)：（1）系統(tǒng)資源的最優(yōu)估價(jià)影子價(jià)格是綜合考慮系統(tǒng)內(nèi)所有因素和相互之間影響之后對(duì)資源在系統(tǒng)內(nèi)的真實(shí)價(jià)值的估價(jià)。只有系統(tǒng)達(dá)到最優(yōu)狀態(tài)時(shí)才可能賦予該資源這種價(jià)值。因此，也有人稱之為最優(yōu)計(jì)劃價(jià)格。,對(duì)偶與靈敏度,70,（2） 影子價(jià)格與系統(tǒng)價(jià)值取向和狀態(tài)有關(guān) 影子價(jià)格 (y = CBT B-1) 的取值與系統(tǒng)的價(jià)值取向有關(guān) (反映在CB上)； 影子價(jià)格受系統(tǒng)狀態(tài)影響 (反映在B-1 上) ;系統(tǒng)內(nèi)部資源數(shù)量和價(jià)格的任何變化

37、都會(huì)引起影子價(jià)格的變化，從這種意義上講，它是一種動(dòng)態(tài)的價(jià)格體系 。,對(duì)偶與靈敏度,71,（3） 影子價(jià)格是一種邊際值它與經(jīng)濟(jì)學(xué)中邊際成本的概念相同，在管理中有十分重要的應(yīng)有價(jià)值，管理者可以根據(jù)資源在本企業(yè)內(nèi)影子價(jià)格的大小決定企業(yè)的經(jīng)營策略。,對(duì)偶與靈敏度,72,（4）反映資源在系統(tǒng)內(nèi)的稀缺程度如果資源在系統(tǒng)內(nèi)供大于求，其影子價(jià)格為零。增加該資源的供應(yīng)不會(huì)給系統(tǒng)目標(biāo)帶來任何變化。如果是稀缺資源，其影子價(jià)格大于零價(jià)格越高，資源的稀缺

38、程度越高。,對(duì)偶與靈敏度,73,按以下原則考慮經(jīng)營策略： 影子價(jià)格高于市場價(jià)格（或?0）表明資源有獲利能力，購入該資源。 影子價(jià)格低于市場價(jià)格（或?0）表明該資源無獲利能力，出讓該資源。 影子價(jià)格等于市場價(jià)格（或=0）表明該資源處于平衡狀態(tài)，既不用買入, 也不必賣出。,對(duì)偶與靈敏度,74,影子價(jià)格在資源利用中的應(yīng)用根據(jù)對(duì)偶理論的互補(bǔ)松弛性定理:Y*Xs=0 , YsX*=0表明生產(chǎn)過程中：如果某種資源bi未得到充

39、分利用時(shí)（松），該種資源的影子價(jià)格為0（緊）；若當(dāng)資源資源的影子價(jià)格不為0（松）時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完（緊）。,對(duì)偶與靈敏度,75,影子價(jià)格對(duì)單純形表計(jì)算的解釋,單純形表中的檢驗(yàn)數(shù),其中cj表示第j種產(chǎn)品的價(jià)格; 表示生產(chǎn)該種產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和,即產(chǎn)品的隱含成本。,當(dāng)產(chǎn)值大于隱含成本時(shí)，即 ，表明生產(chǎn)該項(xiàng)產(chǎn)品有利，可在計(jì)劃中安排；否則 ，用這些

40、資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。,對(duì)偶與靈敏度,76,單純形方法始終保持原問題的解可行，檢驗(yàn)數(shù)不一定小于等于零（即對(duì)偶解不可行）。一旦檢驗(yàn)數(shù)小于等于零（即對(duì)偶解變?yōu)榭尚薪猓?，則問題達(dá)到最優(yōu)。,對(duì)偶單純形方法的基本思想：從對(duì)偶規(guī)劃的一個(gè)可行基出發(fā)，即保證滿足 = C - CBB-1A ? 0；一旦原問題可行，即：XB = B-1b ? 0，則找到最優(yōu)解。,§2.4 對(duì)偶單純形法,,對(duì)偶與靈敏度,77,對(duì)偶單純

41、形法,找出一個(gè)DP的可行基,LP是否可行（XB ≥0）,保持DP為可行解情況下轉(zhuǎn)移到LP的另一個(gè)基本解,最優(yōu)解,,,,,,,是,否,循環(huán),,結(jié)束,對(duì)偶與靈敏度,78,最優(yōu)檢驗(yàn)存在以下幾種情況： (1)如果B-1b?0，該問題已最優(yōu)，停止； (2) 如果B-1b存在至少一個(gè)負(fù)分量, 且 ?i? 0 , ?i = (?i1, ?i2, ... ?in)，?ij =(B-1pj)i ，由線性規(guī)劃的解出方程： 再由條件(

42、B-1b)i < 0和 ?i ?0，(xB)i 不可能變?yōu)檎虼嗽瓎栴}無可行解。,對(duì)偶與靈敏度,79,(3) 如果B-1b中存在至少一個(gè)負(fù)分量，且每個(gè)負(fù)分量對(duì)應(yīng)的行向量?i存在小于零的元素，此時(shí)原問題解不可行，仍需繼續(xù)迭代。保持對(duì)偶可行的條件可表示為：,對(duì)偶與靈敏度,80,因此可得入基變量的檢驗(yàn)條件為：,對(duì)偶與靈敏度,81,對(duì)偶單純形算法：,1.找初始對(duì)偶可行解；2.最優(yōu)檢驗(yàn)：(B-1b)r=min{(B-1b)i i?

43、JB } 如果(B-1b)r?0，已找到最優(yōu)解，停止。 如果(B-1b)r?0 且 ?r?0, 問題不可行, 停止計(jì)算。 否則選變量 xr 出基，轉(zhuǎn)到3。,對(duì)偶與靈敏度,82,3.確定入基變量，令 j=cj-cBB-1pj, 計(jì)算： 令 xk 入基。 4.以 ?rk 為轉(zhuǎn)軸進(jìn)行旋轉(zhuǎn)迭代得到一個(gè)新的單純形表，轉(zhuǎn)到2。,對(duì)偶與靈敏度,83,原始與對(duì)偶單純形法的對(duì)比,,,對(duì)偶與靈敏度,84,原問題單

44、純形表的檢驗(yàn)數(shù)行 對(duì)應(yīng)其對(duì)偶問題的一個(gè)基解,這里Ys1是對(duì)應(yīng)原問題中基變量XB的剩余變量，Ys2是對(duì)應(yīng)原問題中非基變量XN的剩余變量。,對(duì)偶與靈敏度,85,證：設(shè)B是原問題的一個(gè)可行基，于是A=(B,N);原問題可以改寫為,對(duì)偶與靈敏度,86,相應(yīng)地對(duì)偶問題可表示為,對(duì)偶與靈敏度,87,當(dāng)求得原問題的一個(gè)解基相應(yīng)的檢驗(yàn)數(shù)為現(xiàn)分析這些檢驗(yàn)數(shù)與對(duì)偶解之間的

45、關(guān)系令 ,將它代入（1）、（2）得,原問題單純形表檢驗(yàn)數(shù)行的相反數(shù)對(duì)應(yīng)于對(duì)偶問題的一個(gè)基本解。,對(duì)偶與靈敏度,88,原問題最優(yōu)時(shí)，對(duì)偶基本解為可行解，LP、LD同時(shí)最優(yōu)。最優(yōu)表中（1）對(duì)偶決策變量的值與原問題松弛變量檢驗(yàn)數(shù)對(duì)應(yīng)。（相反）（2）對(duì)偶松弛變量的值與原問題決策變量檢驗(yàn)數(shù)對(duì)應(yīng)。（0，相反）,對(duì)偶與靈敏度,89,例2.12 用對(duì)偶單純形方法求解：,解: （1）引入松弛變量 x3 , x4

46、 , x5 化為標(biāo)準(zhǔn)形，并在約束等式兩側(cè)同乘-1，得到,對(duì)偶與靈敏度,90,取x3 , x4 , x5為基變量，此式即為解出形式，并且檢驗(yàn)數(shù)皆非正，因此可構(gòu)初始對(duì)偶單純形表,對(duì)偶與靈敏度,91,,,,對(duì)偶與靈敏度,92,,,對(duì)偶與靈敏度,93,例2.13 用對(duì)偶單純形法求解下面線性規(guī)劃,解: 構(gòu)造對(duì)偶單純形表進(jìn)行迭代，,對(duì)偶與靈敏度,94,從最后的表可以看到，B-1b列元素中有-2<0，并且，-2所在行各元素皆非負(fù)，因此，原規(guī)劃

47、沒有可行解。,,,對(duì)偶與靈敏度,95,對(duì)偶單純形法適合于解如下形式的線性規(guī)劃問題:,在引入松弛變量化為標(biāo)準(zhǔn)型之后，約束等式兩側(cè)同乘-1，能夠立即得到檢驗(yàn)數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對(duì)偶單純形表進(jìn)行求解，非常方便 。,對(duì)偶與靈敏度,96,使用LP求解管理問題時(shí)，管理者需要了解當(dāng)環(huán)境和數(shù)據(jù)發(fā)生變化時(shí)，線性規(guī)劃得出的結(jié)論還是否有效；資源供應(yīng)發(fā)生變化會(huì)有什么影響?成本變化后利潤會(huì)發(fā)生什么變化?如果模型使用的數(shù)據(jù)不精確會(huì)有什么

48、影響，數(shù)據(jù)允許在什么范圍內(nèi)變化?,§2.5 、靈敏度分析,,對(duì)偶與靈敏度,97,一、 價(jià)值系數(shù)cj的變化分析,例2.14 某企業(yè)利用三種資源生產(chǎn)兩種產(chǎn)品的最優(yōu)計(jì)劃問題歸結(jié)為下列線性規(guī)劃,問題：（1）確定x2的系數(shù)c2的變化范圍，使原最優(yōu)解保持最優(yōu)；（2）若c2=6，求新的最優(yōu)計(jì)劃。,,對(duì)偶與靈敏度,98,最優(yōu)表如下：,對(duì)偶與靈敏度,99,σ4 = c2－5 ≤ 0σ5 = 5－2c2 ≤ 0 5/2 ≤ c2

49、 ≤ 5,最優(yōu)解X*=（35，10，25，0，0）保持不變。,（1）,對(duì)偶與靈敏度,100,（2）,x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，z*=495/2,對(duì)偶與靈敏度,101,二、右端常數(shù)bi的變化分析,XB= B－1b,例2.15 對(duì)于上例中的線性規(guī)劃作下列分析：（1）b3在什么范圍內(nèi)變化，原最優(yōu)基不變？（2）若b3=55，求出新的最優(yōu)解。,對(duì)偶與靈敏度,102,對(duì)偶與靈敏度,103,（1）

50、,XB=B－1b=,解得40≤b3≤50，即當(dāng)b3∈[40，50] 時(shí)，最優(yōu)基B 不變,對(duì)偶與靈敏度,104,（2）當(dāng) b3= 55 時(shí),=,最優(yōu)解：X*=（30，20，0，0，5）,用對(duì)偶單純形法是求解得。,對(duì)偶與靈敏度,105,三、增加一個(gè)變量 的分析,例2.16（續(xù)例2.14）設(shè)企業(yè)研制了一種新產(chǎn)品， 對(duì)三種資源的消耗系數(shù)列向量以P6表示 P6= 。問它的價(jià)值系數(shù)c6符合什么條件才必須安排它的生產(chǎn)？設(shè)c6

51、=3，新的最優(yōu)生產(chǎn)計(jì)劃是什么？,,σ6=c6－CBB－1P6 =c6－（0，5，4） = c6－5/2,對(duì)偶與靈敏度,106,對(duì)偶與靈敏度,107,四、 增加新的約束條件的分析,例2.16 假設(shè)在例2.14中，還要考慮一個(gè)新的資源約束： 4x1+2x2≤150,,標(biāo)準(zhǔn)化,對(duì)偶與靈敏度,108,,,,,對(duì)偶與靈敏度,110,1. cj和bi同時(shí)變化的情況,五、 其它變化情況的分析,例2.17 在例2.14中，假定

52、c2由4上升為6，b3增加到55，試問最優(yōu)解將會(huì)發(fā)生什么變化？,B－1=,B－ = =,代替最優(yōu)表的b列，并把c2改為6,對(duì)偶與靈敏度,111,原問題與對(duì)偶問題均非可行解，表中第一方程是:x3+2x4－5x5=－25，兩邊乘以（-1），得 －x3－2x4 + 5x5= 25，再引入人工變量x6：－x3－2x4+5x5+x6=25以x6為基變量，增添第6列，應(yīng)用大M法

53、繼續(xù)求解。,新的最優(yōu)計(jì)劃產(chǎn)量為x1*=30，x2*=20，z*=270。,－x3－2x4+5x5+x6=25,對(duì)偶與靈敏度,113,2. 技術(shù)系數(shù)aij的變化,例2.17 在例2.14中，第一種產(chǎn)品的消耗系數(shù)改變?yōu)?,價(jià)值系數(shù)不變，求新的最優(yōu)解。,B－1=,對(duì)偶與靈敏度,114,,,,對(duì)偶與靈敏度,116,思考題,判斷下列結(jié)論是否正確，如果不正確，應(yīng)該怎樣改正？,1）任何線性規(guī)劃都存在一

54、個(gè)對(duì)應(yīng)的對(duì)偶線性規(guī)劃.2）原問題第i個(gè)約束是“≤”約束，則對(duì)偶變量yi≥0.3）互為對(duì)偶問題，或者同時(shí)都有最優(yōu)解，或者同時(shí)都無最優(yōu)解.4）對(duì)偶問題有可行解，則原問題也有可行解.5）原問題有多重解，對(duì)偶問題也有多重解.6）對(duì)偶問題有可行解，原問題無可行解，則對(duì)偶問題具有無界解.7）原問題無最優(yōu)解，則對(duì)偶問題無可行解.8）對(duì)偶問題不可行，原問題可能無界解.9）原問題與對(duì)偶問題都可行，則都有最優(yōu)解.10）原問題具有無界解，則

55、對(duì)偶問題不可行.11）對(duì)偶問題具有無界解，則原問題無最優(yōu)解.12）若X*、Y*是原問題與對(duì)偶問題的最優(yōu)解，則X*=Y*.,對(duì)偶與靈敏度,117,本章小結(jié),學(xué)習(xí)要點(diǎn)：1. 線性規(guī)劃解的概念以及3個(gè)基本定理2. 熟練掌握單純形法的解題思路及求解步驟 3. 熟練掌握對(duì)偶問題的轉(zhuǎn)換 4. 掌握對(duì)偶問題的5個(gè)性質(zhì) 5. 熟練掌握對(duì)偶單純形法的解題思路及求解步驟,對(duì)