02運籌學(xué)-對偶理論與靈敏度分析

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

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

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

4、解 y1 、y2出租其擁有的木、漆工資源，既保證了自己不吃虧（出租資源的租金收入并不低于自己生產(chǎn)時的銷售收入），又使得出租價格對李老板有極大的吸引力（李老板所付出的總租金W最少）。,按時下最流行的一個詞，叫什么來著————,對偶與靈敏度,7,2、線性規(guī)劃的對偶理論例2.1某工廠擁有A、B、C三種類型的原料，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中消耗的原料數(shù)量，每件產(chǎn)品的價格以及三種原料可利用的數(shù)量如下表所示：,對偶與靈敏度,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,對偶與靈敏度,9,現(xiàn)在考慮若三種原料都用于轉(zhuǎn)讓，試問：三種原料各如何收費才能即保證本廠的利益，有能最有競爭力？ 設(shè) y1 ，y2 ，y3 分別為每設(shè)備工時（或原料）每單位的收取費用，則有,Min f = 300y1+ 400y2 +

7、250y3 s.t.y1+2y2 ≥ 50（不少于甲產(chǎn)品的利潤） y1+ y2+y3 ≥100（不少于乙產(chǎn)品的利潤） y1,y2 ,y3 ≥ 0,對偶與靈敏度,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,對偶問題租賃者模型,原問題管理者模型,一對互為對偶的模型,LP,DP,對偶與靈敏度,11,對偶問題的定義： （對稱形式）,（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,對偶與靈敏度,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）的對稱形式對偶問題,設(shè)：,對偶與靈敏度,13,線性規(guī)劃的對偶模型,,,,,,,,,,,,,對偶與靈敏度,14,線性規(guī)劃的對偶理論對稱形式下對偶問題的一般形式,對偶與靈敏度,15,例2．2 寫出下面線性規(guī)劃的對偶規(guī)劃模型,解：按照對稱形式的對偶關(guān)系，其對偶模型為,對偶與靈敏度,16,對

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

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

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

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

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

18、問題的對偶問題.,解：原問題的對偶問題為,對偶與靈敏度,34,習(xí)題2.4（3）,,s.t.,對偶與靈敏度,35,解：由非對稱形式的對應(yīng)關(guān)系，得對偶規(guī)劃,,s.t.,對偶與靈敏度,36,課堂練習(xí),對偶與靈敏度,37,對偶與靈敏度,38,考慮下面一對對偶問題：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 、對偶規(guī)劃的基本性質(zhì),,對偶與靈敏度,39,其中01和I分別為m維的零向量和m維的單位矩陣。,記,則上面的標(biāo)準(zhǔn)型可記為（P2）,對偶與靈敏度,40,設(shè)B為一可行基，并記,,得到模型（P2）的另一表示形式,,對偶與靈敏度

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

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

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

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

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

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

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

27、 ? 原問題變量=0； 原問題變量>0 ? 對偶約束為緊約束； 原問題變量=0 ? 對偶約束可緊可松。,對偶與靈敏度,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其對偶問題的最優(yōu)解為：y1* = 0.8, y2* = 0.6。試用對偶理論求出它的原問題的最優(yōu)解,對偶與靈敏度,58,對偶問題： 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,對偶與靈敏度,59,原問題的約束為緊約束, 故有: x1 + 3x5 = 4 2x1 + x5 = 3解得：x1* = 1， x5* = 1原問題的最優(yōu)解為：X = (1 , 0 , 0 , 0

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

31、2=1,從而對偶問題的最優(yōu)解為：Y＊=(1,1)，最優(yōu)值w=26。,,對偶與靈敏度,62,例2.11 已知線性規(guī)劃,的對偶問題的最優(yōu)解為Y＊=(0,-2)，求原問題的最優(yōu)解。,解: 對偶問題是,,標(biāo)準(zhǔn)化,無約束,對偶與靈敏度,63,設(shè)對偶問題最優(yōu)解為X＊＝(x1，x2 ，x3)T ,由互補松弛性定理可知，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=-12,對偶與靈敏度,64,線性規(guī)劃的對偶理論原問題與對偶問題解的對應(yīng)關(guān)系表,對偶與靈敏度,65,線性規(guī)劃的對偶理論對偶問題的基本性質(zhì)對稱性——原始問題與對偶問題是兩個互為對偶的問題。弱對偶性——兩個問題的可行解對應(yīng)的目標(biāo)函數(shù)值互為上下界。最優(yōu)性——兩個問題最優(yōu)解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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