2.運籌學(xué)-對偶理論敏感分析課件

1、1,線性規(guī)劃 Linear Programming（LP）,第二章 線性規(guī)劃的對偶理論與靈敏度分析,2,線性規(guī)劃 Linear Programming（LP）,線性規(guī)劃對偶理論,3,線性規(guī)劃 Linear Programming（LP）,對偶問題？.,線性規(guī)劃的對偶理論 對偶理論是線性規(guī)劃中最重要的理論之一，是深入了解線性規(guī)劃問題結(jié)構(gòu)的重要理論基礎(chǔ)。同時，由于問題提出本身所具有的經(jīng)濟意義，使得它成為對線性規(guī)劃問題系統(tǒng)進行經(jīng)濟分析和敏感性分析的重要工具。那么，對偶問題是怎樣提出的，為什么會產(chǎn)生這樣一種問題呢？,4,線性規(guī)劃 Linear Programming（LP）,引例倆家具制造商間的對話：

2、,唉!我想租您的木工和油漆工一 用。咋樣？價格嘛好說， 肯定不會讓您兄弟吃虧訕。,王老板做家具賺了 大錢，可惜我老李有 高科技產(chǎn)品，卻苦于沒有 足夠的木工和油漆工 咋辦？只有租咯。,Hi：王老板，聽說 近來家具生意好慘了， 也幫幫兄弟我哦!,家具生意還真賺錢，但 是現(xiàn)在的生意這么好， 不如干脆把我的木工和油漆 工租給他，又能 收租金又可做生意。,價格嘛好商量， 好商量。只是.,王 老 板,李 老 板,5,線性規(guī)劃 Linear Programming（LP）,王老板的家具生產(chǎn)模型： x1 、 x2是桌、椅生產(chǎn)量。 Z是家具銷售總收入（總利潤）。 max z = 50 x1 + 30 x2 s.

3、t. 4x1+3x2 120（木工） 2x1+ x2 50 （油漆工） x1，x2 0 原始線性規(guī)劃問題，記為（P）,王老板的資源出租模型： y1、 y2單位木、漆工出租價格。 W是資源出租租金總收入。 min w =120y1 + 50y2 s.t. 4y1+2y2 50 3y1+ y2 30 y1，y2 0 對偶線性規(guī)劃問題，記為（D）,6,線性規(guī)劃 Linear Programming（LP）,王老板按（D）的解 y1 、y2出租其擁有的木、漆工資源，既保證了自己不吃虧（出租資源的租金收入并不低于自己生產(chǎn)時的銷售收入），又使得出租價格對李老板有極大的吸引力（李老板所付出的總租金W最少）。

4、,7,線性規(guī)劃 Linear Programming（LP）,例1 第一章例1煤電油，其線性規(guī)劃問題為 將其稱為原始問題，記為P,（P） max z = 7X1 + 12X2 s.t. 9X1+ 4X2 360 4X1 + 5X2 200 3X1 + 10X2 300 X1 ， X2 0,8,線性規(guī)劃 Linear Programming（LP）,下面我們從另一角度提出一個新的問題。這時有另一家廠商提出要購買其煤、電、油全部資源，并希望花費盡量少。試建立購買者的線性規(guī)劃模型。,（D） min w = 360y1 + 200y2 + 300y3 s.t. 9y1+4y2 + 3y3 7 4y1

5、+ 5y2 + 10y3 12 y1， y2， y3 0,這個問題我們將其稱為原始問題的對偶問題，記為D,9,線性規(guī)劃 Linear Programming（LP）,（P） max z = CX s.t. AX b X 0,（D） min w = Yb s.t. YA C Y 0,特點： （1）P為max型，D為min型 （2）P的變量個數(shù)=D的約束個數(shù) （3）P的約束個數(shù)=D的變量個數(shù) （4）P的目標(biāo)函數(shù)系數(shù)=D的資源約束向量 （5）P的資源約束向量=D的目標(biāo)函數(shù)系數(shù) （6）P技術(shù)系數(shù)矩陣=D技術(shù)系數(shù)矩陣轉(zhuǎn)置,這是最常見的對偶模型形式，稱為對稱式對偶模型。二者間具有十分對稱的對應(yīng)關(guān)系。,10

6、,線性規(guī)劃 Linear Programming（LP）,對稱形式下對偶問題的一般形式：,11,注：若P的某個約束為“=”型，則D的相應(yīng)變量為自由；若P的某個變量為自由，則D的相應(yīng)約束為“=”型。 見示例：,（P） max z = 7X1 + 12X2 s.t. 9X1+ 4X2 360 4X1 + 5X2 200 3X1 + 10X2 = 300 X1 ， X2 0,12,線性規(guī)劃 Linear Programming（LP）,如何寫出LP模型的對偶問題：,（1）若LP為Max型，則盡量化成(P)形式。(等式、自由變量除外),（2）若LP為Min型，則盡量化成(D)形式。(等式、自由變量除外

7、),（P） max z = CX s.t. AX b X 0,（D） min w = Yb s.t. YA C Y 0,13,線性規(guī)劃 Linear Programming（LP）,非對稱形式下對偶問題的一般形式 原始（對偶）對偶（原始）關(guān)系表,14,線性規(guī)劃 Linear Programming（LP）,例2 寫出下面線性規(guī)劃問題的對偶規(guī)劃模型：,max z = 2X1 + 3X2 s.t. X1+ 2X2 3 2X1 -X2 5 -X1 + 3X2 =1 X1 0,設(shè)對偶變量為y1,y2,y3，對偶目標(biāo)為w，則,min z = 3y1+5y2+y3 s.t. y1+ 2y2-y3 2 2y

8、1 y2+3y2 =3 y1 , y2 0,15,線性規(guī)劃 Linear Programming（LP）,練習(xí)：寫出下面線性規(guī)劃問題的對偶規(guī)劃模型,min z = 2X1 + 3X2-5X3 +4X4 s.t. X1+ X2 -3X3+X4 5 2X1 +2X3-X4 4 X2 + X3 +X4 =6 X1 0 , X2 ，X3 0，X4無約束,16,線性規(guī)劃 Linear Programming（LP）,線性規(guī)劃的對偶理論 1 對稱性原始問題與對偶問題是兩個互為對偶的問題。 即（P）和（D）互為對偶。 2 弱對偶性兩個問題的可行解對應(yīng)的目標(biāo)函數(shù)值互為上下界。設(shè)X、Y 分別為（P）、（D）的任

9、一可行解，則CX YB,17,3 解的最優(yōu)性設(shè)X， Y分別為（P）和（D）的可行解，且CX =YB，則X=X*， Y=Y*。 4 對偶性若（P）有最優(yōu)解，則（D）也有最優(yōu)解，且二者最優(yōu)值相等。,18,5 互補松緊定理 設(shè)X， Y分別為（P）和（D）的可行解，則X， Y是最優(yōu)解 Y Xs = Ys X =0 ，其中Xs 、 Ys 為最優(yōu)解中松弛變量部分。,19,Xn+1，- Xn+j，-，Xn+m,Ym+1，- Ym+j，-，Ym+n,原始問題的變量,原始問題的松弛變量,對偶問題的變量,對偶問題的松弛變量,XjYm+j=0， Yj Xn+j=0, 在一對變量中，其中一個大于0，另一個一定等于0.

10、,20,在線性規(guī)劃問題的最優(yōu)解中，若對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴(yán)格等式，另一方面，如果約束條件取嚴(yán)格不等式，則其對應(yīng)的變量一定為零. 具體見p-70.,21,線性規(guī)劃 Linear Programming（LP）,對偶最優(yōu)解的經(jīng)濟解釋 我們已經(jīng)明白原始線性規(guī)劃與對偶線性規(guī)劃之間形式上的對偶以及他們的解之間的關(guān)系，那么對偶問題的解除了前面引例中提到的租金這種經(jīng)濟含義外其深刻的經(jīng)濟含義是什么呢？,22,對偶最優(yōu)解的經(jīng)濟解釋：資源的影子價格(shadow price) CBB-1 ：對偶問題的最優(yōu)解-買主的最低出價； 原問題資源的影子價格-當(dāng)該資源增加1單位時引起的總收入的增

11、量賣主的內(nèi)控價格。,23,線性規(guī)劃 Linear Programming（LP）,對偶問題解的經(jīng)濟含義分析： 從單純形法的矩陣描述中，目標(biāo)函數(shù)取值 Z = CBB-1 b ，和檢驗數(shù) CN - CBB-1N 中都有乘子 Y = CBB-1。 設(shè)B 是 max Z = CX | AX b，X 0 的最優(yōu)基矩陣，由強對偶定理知 Z* =CX*= CBB-1b=Y*b=W* 由此, Z* b, Z* bi,（ Y*b） bi,= CBB-1= Y* 或,=,= yi*,24,例：（煤電油例）的單純形終表如下,請指出資源煤電油的影子價格，并解釋其經(jīng)濟意義。,25,線性規(guī)劃 Linear Program

12、ming（LP）,由上面分析對偶問題解中變量 yi* 的經(jīng)濟含義是在其他條件不變的情況下，單位第 i 種“資源”變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。所以， yi* 描述了原始線性規(guī)劃問題達到最優(yōu)時（各種“資源”都處于最優(yōu)的配置時），第 i 種“資源”的某種“價值”，故稱其為第 i 種“資源”的影子價格。這正是經(jīng)濟學(xué)中機會價值的含義。,26,影子價格在管理決策中的作用： （1）影子價格市場價格。若影子價格市場價格，則應(yīng)買進該資源；若影子價格市場價格，則應(yīng)賣出該資源。 （2）影子價格反映了資源的稀缺性，影子價格越高，則越稀缺。,27,線性規(guī)劃 Linear Programming（LP）,影子價格的

13、特點： 影子價格是對偶解的一個十分形象的名稱，它既表明對偶解是對系統(tǒng)內(nèi)部資源在當(dāng)前的最優(yōu)利用配置下的一種客觀估價，又表明它是一種虛擬的價格（或價值的影象）而不是真實的價格。 特點1、影子價格是對系統(tǒng)資源的一種內(nèi)部最優(yōu)估價，只有當(dāng)系統(tǒng)達到最優(yōu)狀態(tài)時才可能賦予資源這種價值。 特點2、系統(tǒng)資源的一種動態(tài)價格體系，影子價格的大小與系統(tǒng)的價值取向有關(guān)，并受系統(tǒng)狀態(tài)變化的影響。系統(tǒng)環(huán)境的任何變化都可能會引起影子價格的變化。,28,線性規(guī)劃 Linear Programming（LP）,特點3、影子價格的大小客觀地反映資源在系統(tǒng)內(nèi)的稀缺程度。如果某種資源在系統(tǒng)內(nèi)供大于求，盡管它有實實在在的市場價格，但它在系

14、統(tǒng)內(nèi)的影子價格卻為零，而影子價格越高，資源在系統(tǒng)內(nèi)越稀缺。 特點4、影子價格是一種邊際價值，其與經(jīng)濟學(xué)中的邊際成本的概念相同。因而，在經(jīng)濟管理中十分重要的應(yīng)用價值。企業(yè)管理者可以根據(jù)資源在企業(yè)內(nèi)部的影子價格的大小決定企業(yè)的經(jīng)營策略。 特點5、對偶解準(zhǔn)確的經(jīng)濟意義與線性規(guī)劃模型的構(gòu)造方法有關(guān)，模型構(gòu)造方法的不同有時會導(dǎo)致對偶解的不同經(jīng)濟解釋。,29,線性規(guī)劃 Linear Programming（LP）,對偶約束的經(jīng)濟解釋-機會成本,s.t. a11x1 + +a1j xj+ + a1n xn b1 am1x1 + +amj xj + + amn xn bm x1 , , xn 0,Max z=

15、 c1x1 + + cn xn,y1 ym,機會成本a1j y1+ amj ym 表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤.,30,線性規(guī)劃 Linear Programming（LP）,對偶松弛變量的經(jīng)濟解釋-產(chǎn)品的差額成本,s.t. a11y1 + +aj1 yj+ + an1 ym ym+1 = c1 a1nx1 + +ajn xj + + anm xn ym+n= cn x1 , , xn 0,Min w= b1y1 + + bn yn,ym +j =(a1j y1+ amj ym)-cj 差額成本=機會成本-產(chǎn)品價格,31,線性規(guī)劃 Linear Programming（LP）,互

16、補松緊關(guān)系的經(jīng)濟解釋,Yj Xn+j=0, XjYm+j=0， 在一對變量中，其中一個大于0，另一個一定等于0. 在利潤最大化的生產(chǎn)計劃中： （1）影子價格大于0的資源沒有剩余； （2）有剩余的資源影子價格等于0； （3）安排生產(chǎn)的產(chǎn)品機會成本等于產(chǎn)品價格； （4）機會成本大于產(chǎn)品價格的產(chǎn)品不安排生產(chǎn)。,32,線性規(guī)劃 Linear Programming（LP）,靈敏度分析 任務(wù)：討論模型的系數(shù)或變量發(fā)生小的變化時對解的影響（如它們在何范圍內(nèi)變化時可使原最優(yōu)解或最優(yōu)基不變？） 我們主要討論C、b和變量結(jié)構(gòu)變化時對解的影響。 對解的影響： 可行性：B-1b0 最優(yōu)性： cj CB B-1 Pj

17、 0,33,1、b變化時的分析（只影響解的可行性）設(shè)第r 種資源brbr+（bb） 問題：b在何范圍變化時，不影響最優(yōu)基？ 方法：B-1b0（保證可行性）即B-1（b1, ，br+, ， bm)T 0解出即可.,34,2、C變化時的分析（只影響解的最優(yōu)性,但分兩種情況討論）： （1）Cj是非基變量xj的價格系數(shù) 因只影響自己的檢驗數(shù)，為=cj + cj CB B-1 Pj ，故只要 0即可。 （2）Cj是基變量xj的價格系數(shù) 這時要影響所有的檢驗數(shù)，為=cj-（c1, ， cj+ cj, , cm） B-1 Pj ，應(yīng)由所有的i 0解的公共的 cj。,35,3、增加新變量時的分析 主要討論增加

18、新變量xn+1是否有利。經(jīng)濟意義是第n+1種新產(chǎn)品是否應(yīng)當(dāng)投產(chǎn)，數(shù)學(xué)意義是xn+1是否應(yīng)進基。 方法：計算xn+1的檢驗數(shù)n+1 =cn+1 CB B-1 Pn+1。 若n+10，則增加xn+1，即投產(chǎn)有利； 若n+1 0，則不增加xn+1，即投產(chǎn)無利。 經(jīng)濟意義： cn+1 CB B-1 Pn+1，即市場價格-機會成本,36,例：（煤電油例）的單純形終表如下,（1）電的影子價格是多少？使最優(yōu)基仍適用的電的變化范圍為何？（2）若有人愿以每度1元的價格向該廠供應(yīng)25度電，是否值得接受？（3）甲產(chǎn)品的價格在何范圍內(nèi)變化時，現(xiàn)最優(yōu)解不變？（4）若現(xiàn)又考慮一新產(chǎn)品丙，其資源單耗為10，2，5，售價為6.5，問該產(chǎn)品是否可投產(chǎn)？,37,例：（煤電油例）的單純形終表如下,（1）電的影子價格是多少？使最優(yōu)基仍適用的電的變化范圍為何？ 答：電的影子價格