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

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

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

3、t. 4x1+3x2 120（木工） 2x1+ x2 50 （油漆工） x1，x2 0 原始線性規(guī)劃問題，記為（P）,王老板的資源出租模型： y1、 y2單位木、漆工出租價(jià)格。 W是資源出租租金總收入。 min w =120y1 + 50y2 s.t. 4y1+2y2 50 3y1+ y2 30 y1，y2 0 對(duì)偶線性規(guī)劃問題，記為（D）,6,線性規(guī)劃 Linear Programming（LP）,王老板按（D）的解 y1 、y2出租其擁有的木、漆工資源，既保證了自己不吃虧（出租資源的租金收入并不低于自己生產(chǎn)時(shí)的銷售收入），又使得出租價(jià)格對(duì)李老板有極大的吸引力（李老板所付出的總租金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）,下面我們從另一角度提出一個(gè)新的問題。這時(shí)有另一家廠商提出要購(gòu)買其煤、電、油全部資源，并希望花費(fèi)盡量少。試建立購(gòu)買者的線性規(guī)劃模型。,（D） min w = 360y1 + 200y2 + 300y3 s.t. 9y1+4y2 + 3y3 7 4y1

5、+ 5y2 + 10y3 12 y1， y2， y3 0,這個(gè)問題我們將其稱為原始問題的對(duì)偶問題，記為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,特點(diǎn)： （1）P為max型，D為min型 （2）P的變量個(gè)數(shù)=D的約束個(gè)數(shù) （3）P的約束個(gè)數(shù)=D的變量個(gè)數(shù) （4）P的目標(biāo)函數(shù)系數(shù)=D的資源約束向量 （5）P的資源約束向量=D的目標(biāo)函數(shù)系數(shù) （6）P技術(shù)系數(shù)矩陣=D技術(shù)系數(shù)矩陣轉(zhuǎn)置,這是最常見的對(duì)偶模型形式，稱為對(duì)稱式對(duì)偶模型。二者間具有十分對(duì)稱的對(duì)應(yīng)關(guān)系。,10

6、,線性規(guī)劃 Linear Programming（LP）,對(duì)稱形式下對(duì)偶問題的一般形式：,11,注：若P的某個(gè)約束為“=”型，則D的相應(yīng)變量為自由；若P的某個(gè)變量為自由，則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模型的對(duì)偶問題：,（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）,非對(duì)稱形式下對(duì)偶問題的一般形式 原始（對(duì)偶）對(duì)偶（原始）關(guān)系表,14,線性規(guī)劃 Linear Programming（LP）,例2 寫出下面線性規(guī)劃問題的對(duì)偶規(guī)劃模型：,max z = 2X1 + 3X2 s.t. X1+ 2X2 3 2X1 -X2 5 -X1 + 3X2 =1 X1 0,設(shè)對(duì)偶變量為y1,y2,y3，對(duì)偶目標(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ī)劃問題的對(duì)偶規(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ī)劃的對(duì)偶理論 1 對(duì)稱性原始問題與對(duì)偶問題是兩個(gè)互為對(duì)偶的問題。 即（P）和（D）互為對(duì)偶。 2 弱對(duì)偶性兩個(gè)問題的可行解對(duì)應(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 對(duì)偶性若（P）有最優(yōu)解，則（D）也有最優(yōu)解，且二者最優(yōu)值相等。,18,5 互補(bǔ)松緊定理 設(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,原始問題的變量,原始問題的松弛變量,對(duì)偶問題的變量,對(duì)偶問題的松弛變量,XjYm+j=0， Yj Xn+j=0, 在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0.

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

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

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

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

14、統(tǒng)內(nèi)的影子價(jià)格卻為零，而影子價(jià)格越高，資源在系統(tǒng)內(nèi)越稀缺。 特點(diǎn)4、影子價(jià)格是一種邊際價(jià)值，其與經(jīng)濟(jì)學(xué)中的邊際成本的概念相同。因而，在經(jīng)濟(jì)管理中十分重要的應(yīng)用價(jià)值。企業(yè)管理者可以根據(jù)資源在企業(yè)內(nèi)部的影子價(jià)格的大小決定企業(yè)的經(jīng)營(yíng)策略。 特點(diǎn)5、對(duì)偶解準(zhǔn)確的經(jīng)濟(jì)意義與線性規(guī)劃模型的構(gòu)造方法有關(guān)，模型構(gòu)造方法的不同有時(shí)會(huì)導(dǎo)致對(duì)偶解的不同經(jīng)濟(jì)解釋。,29,線性規(guī)劃 Linear Programming（LP）,對(duì)偶約束的經(jīng)濟(jì)解釋-機(jī)會(huì)成本,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,機(jī)會(huì)成本a1j y1+ amj ym 表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤(rùn).,30,線性規(guī)劃 Linear Programming（LP）,對(duì)偶松弛變量的經(jīng)濟(jì)解釋-產(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 差額成本=機(jī)會(huì)成本-產(chǎn)品價(jià)格,31,線性規(guī)劃 Linear Programming（LP）,互

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

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

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