02運籌學-對偶理論與靈敏度分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、值的上界。,推論2: 在一對對偶問題（P）和（D）中，若其中一個問題可行但目標函數無界，則另一個問題無可行解；反之不成立。這也是對偶問題的無界性。,對偶與靈敏度,43,對偶與靈敏度,44,性質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,性質4 強對偶性：若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標函數值相等。,還可推出另一結論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。,證： 考慮原規(guī)劃（P）的標準型（P2）,設B為模型（P2）的最優(yōu)基，現在證明對偶規(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ī)劃問題，并根據最優(yōu)單純形表中的檢驗數，給出其對偶問題的最優(yōu)解。,解 引入松弛變量、將模型化為標準型，經求解后得到其最優(yōu)單純形表,對偶與靈敏度,53,對偶規(guī)劃的最優(yōu)解為 :,即原問題

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

26、,,互補松弛條件,由于松弛變量都非負，要使求和式等于零，則必定每一分量為零，因而有下列關系：若Y＊≠0，則Xs必為0；若X＊≠0，則Ys必為0利用上述關系，建立對偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。,對偶與靈敏度,56,互補松弛定理證明了最優(yōu)線性規(guī)劃的下列對應關系： 原問題約束為緊 ? 對偶變量 ? 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＊。,解：寫出原問題的對偶問題，即,,標準化,,對偶與靈敏度,61,設對偶問題最優(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)解。,解: 對偶問題是,,標準化,無約束,對偶與靈敏度,63,設對偶問題最優(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ī)劃的對偶理論原問題與對偶問題解的對應關系表,對偶與靈敏度,65,線性規(guī)劃的對偶理論對偶問題的基本性質對稱性——原始問題與對偶問題是兩個互為對偶的問題。弱對偶性——兩個問題的可行解對應的目標函數值互為上下界。最優(yōu)性——兩個問題最優(yōu)解

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

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

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

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

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

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

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

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

41、形法,找出一個DP的可行基,LP是否可行（XB ≥0）,保持DP為可行解情況下轉移到LP的另一個基本解,最優(yōu)解,,,,,,,是,否,循環(huán),,結束,對偶與靈敏度,78,最優(yōu)檢驗存在以下幾種情況： (1)如果B-1b?0，該問題已最優(yōu)，停止； (2) 如果B-1b存在至少一個負分量, 且 ?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中存在至少一個負分量，且每個負分量對應的行向量?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 出基，轉到3。,對偶與靈敏度,82,3.確定入基變量，令 j=cj-cBB-1pj, 計算： 令 xk 入基。 4.以 ?rk 為轉軸進行旋轉迭代得到一個新的單純形表，轉到2。,對偶與靈敏度,83,原始與對偶單純形法的對比,,,對偶與靈敏度,84,原問題單

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

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

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

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

48、影響，數據允許在什么范圍內變化?,§2.5 、靈敏度分析,,對偶與靈敏度,97,一、 價值系數cj的變化分析,例2.14 某企業(yè)利用三種資源生產兩種產品的最優(yōu)計劃問題歸結為下列線性規(guī)劃,問題：（1）確定x2的系數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,二、右端常數bi的變化分析,XB= B－1b,例2.15 對于上例中的線性規(guī)劃作下列分析：（1）b3在什么范圍內變化，原最優(yōu)基不變？（2）若b3=55，求出新的最優(yōu)解。,對偶與靈敏度,102,對偶與靈敏度,103,（1）

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

51、=3，新的最優(yōu)生產計劃是什么？,,σ6=c6－CBB－1P6 =c6－（0，5，4） = c6－5/2,對偶與靈敏度,106,對偶與靈敏度,107,四、 增加新的約束條件的分析,例2.16 假設在例2.14中，還要考慮一個新的資源約束： 4x1+2x2≤150,,標準化,對偶與靈敏度,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列，應用大M法

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

54、個對應的對偶線性規(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,本章小結,學習要點：1. 線性規(guī)劃解的概念以及3個基本定理2. 熟練掌握單純形法的解題思路及求解步驟 3. 熟練掌握對偶問題的轉換 4. 掌握對偶問題的5個性質 5. 熟練掌握對偶單純形法的解題思路及求解步驟,對