運(yùn)籌學(xué)第2章

1、Chapter2 對(duì)偶理論 ( Duality Theory ),,單純形法的矩陣描述對(duì)偶問題的提出線性規(guī)劃的對(duì)偶理論對(duì)偶問題的經(jīng)濟(jì)解釋－影子價(jià)格對(duì)偶單純形法靈敏度分析(選講)掌握WinQSB軟件求解對(duì)偶規(guī)劃,本章主要內(nèi)容：,√,√,√,學(xué)習(xí)要點(diǎn)：1. 理解對(duì)偶理論，掌握描述一個(gè)線性規(guī)劃問題 的對(duì)偶問題。 2. 能夠運(yùn)用對(duì)偶單純形法來求解線性規(guī)劃問題。

2、 3. 會(huì)用互補(bǔ)松弛條件來考慮一對(duì)對(duì)偶問題的界。 4. 了解影子價(jià)格、靈敏度分析以及用WinQSB求 解對(duì)偶規(guī)劃問題。,2.1 單純形法的矩陣描述,,,,,每一列的含義？每個(gè)表中的B和B-1的查找？,單純形法的矩陣描述,單純形法的矩陣描述,,單純形法的矩陣描述,單純形法的矩陣描述,單純形法的矩陣描述,2.3 對(duì)偶問題的提出,對(duì)偶

3、理論是線性規(guī)劃中最重要的理論之一，是深入了解線性規(guī)劃問題結(jié)構(gòu)的重要理論基礎(chǔ)。同時(shí)，由于問題提出本身所具有的經(jīng)濟(jì)意義，使得它成為對(duì)線性規(guī)劃問題系統(tǒng)進(jìn)行經(jīng)濟(jì)分析和敏感性分析的重要工具。那么，對(duì)偶問題是怎樣提出的，為什么會(huì)產(chǎn)生這樣一種問題呢？,對(duì)偶問題的提出,倆家具制造商間的對(duì)話：,唉!我想租您的木工和油漆工一用。咋樣？?jī)r(jià)格嘛……好說，肯定不會(huì)讓您兄弟吃虧。,王老板做家具賺了大錢，可惜我老李有高科技產(chǎn)品，卻苦于沒有足夠的木工和油漆工咋辦？只

4、有租咯。,Hi：王老板，聽說近來家具生意好呀，也幫幫兄弟我哦!,家具生意還真賺錢，但是現(xiàn)在的手機(jī)生意這么好，不如干脆把我的木工和油漆工租給他，又能收租金又可做生意。,價(jià)格嘛……好商量， 好商量。只是…...,王 老 板,李 老 板,引例1,對(duì)偶問題的提出,王老板的家具生產(chǎn)模型：x1 、 x2是桌、椅生產(chǎn)量。Z是家具銷售總收入（總利潤(rùn)）。max Z = 50x1 + 30x2s.t. 4x1+3x2 ≤ 120（

5、木工） 2x1+ x2 ≤ 50 （油漆工） x1，x2 ≥ 0原始線性規(guī)劃問題，記為（P）,王老板的資源出租模型：y1、 y2單位木、漆工出租價(jià)格。W是資源出租租金總收入。min W =120y1 + 50y2s.t. 4y1+2y2 ≥ 50 3y1+ y2 ≥ 30 y1，y2 ≥ 0對(duì)偶線性規(guī)劃問題

6、，記為（D）,,,所得不得低于生產(chǎn)的獲利（不吃虧原則）要使對(duì)方能夠接受 （競(jìng)爭(zhēng)性原則）,兩個(gè)原則,對(duì)偶問題的提出,王老板按（D）的解 y1 、y2出租其擁有的木、漆工資源，既保證了自己不吃虧（出租資源的租金收入并不低于自己生產(chǎn)時(shí)的銷售收入），又使得出租價(jià)格對(duì)李老板有極大的吸引力（李老板所付出的總租金W最少）。,按時(shí)下最流行的一個(gè)詞，叫什么來著————,對(duì)偶問題的提出,設(shè)三種資源的使用單價(jià)分別為 y1 , y2 , y3,y

7、1 y2 y3,生產(chǎn)單位產(chǎn)品A的資源消耗所得不少于單位產(chǎn)品A的獲利,生產(chǎn)單位產(chǎn)品B的資源消耗所得不少于單位產(chǎn)品B的獲利,y1 +3 y2 ? 40,2y1 + 2 y2 + 2y3 ? 50,引例2,通過使用所有資源對(duì)外加工所獲得的收益,W = 30y1 + 60 y2 + 24y3,對(duì)偶問題的提出,根據(jù)原則2 ，對(duì)方能夠接受的價(jià)格顯然是越低越好，因此此問題可歸結(jié)為以下數(shù)學(xué)模型：,Min W = 30y1 + 60 y2

8、 + 24y3,y1 + 3y2 ? 402y1 + 2 y2 + 2y3 ? 50y1 , y2 , y3 ? 0,,s.t,目標(biāo)函數(shù),約束條件,原線性規(guī)劃問題稱為原問題，此問題為對(duì)偶問題，y1 , y2 , y3為對(duì)偶變量，也稱為影子價(jià)格,對(duì)偶問題的提出,2.4 線性規(guī)劃的對(duì)偶理論,,,,,,,,,,,,,,,,,,,,,Max Z= 40x1 +50x2,x1 + 2x2 ? 30

9、3x1 + 2x2 ? 60 2x2 ? 24 x1，x2 ? 0,,s.t,原問題（對(duì)偶問題）,對(duì)偶問題（原問題）,一、 原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系,3個(gè)約束2個(gè)變量,2個(gè)約束 3個(gè)變量,線性規(guī)劃的對(duì)偶理論,對(duì)偶問題的形式,定義 設(shè)原線性規(guī)劃問題為 則稱下列線性規(guī)劃問題,為其對(duì)偶問題，其中yi (i=1,2,…,m) 稱為對(duì)偶變量,上述對(duì)偶問題稱為對(duì)稱型對(duì)偶問題,原問題簡(jiǎn)記為(P)，對(duì)偶問

10、題簡(jiǎn)記為(D),稱問題(P)和(D )為一對(duì)對(duì)偶問題,線性規(guī)劃的對(duì)偶理論,對(duì)稱型問題的對(duì)偶規(guī)則,1、給每個(gè)原始約束條件定義一個(gè)非負(fù)對(duì)偶變量yi(i=1,2,…,m)；2、使原問題的目標(biāo)函數(shù)系數(shù) cj 變?yōu)槠鋵?duì)偶問題約束條 件的右端常數(shù)；3、使原問題約束條件的右端常數(shù) bi 變?yōu)槠鋵?duì)偶問題目 標(biāo)函數(shù)的系數(shù)；4、將原問題約束條件的系數(shù)矩陣轉(zhuǎn)置，得到其對(duì)偶問 題約束條件的系數(shù)矩陣；5、改變約束問題不

11、等號(hào)的方向，即將“≤”改為“≥”；6、原問題為“max”型，對(duì)偶問題為“min”型。,線性規(guī)劃的對(duì)偶理論,原始問題Max Z=CXs.t. AX≤bX ≥0,,,,b,A,C,≤,Max,,,,,,,n,m,對(duì)偶問題Min W=Ybs.t.YA≥CY ≥0,,,,≥,Min,C,AT,b,,,,,,,n,m,,,,,,,,,,,,,,,,,,,,,,,,,,線性規(guī)劃的對(duì)偶理論,當(dāng)原問題為求極小值時(shí)，對(duì)偶問題為求

12、極大值。原始問題中目標(biāo)函數(shù)的系數(shù)變成對(duì)偶問題中約束條件的右端；原始問題中約束條件的右端變成對(duì)偶問題中目標(biāo)函數(shù)的系數(shù)。原始問題約束條件系數(shù)矩陣的轉(zhuǎn)置對(duì)應(yīng)對(duì)偶問題中約束條件的系數(shù)矩陣。原始問題的約束條件個(gè)數(shù)決定對(duì)偶問題變量的個(gè)數(shù)；原始問題變量個(gè)數(shù)，決定對(duì)偶問題的約束個(gè)數(shù)。原始問題的約束方程的匹配形式?jīng)Q定對(duì)偶問題變量的符號(hào)；原始問題決策變量的符號(hào)決定所對(duì)應(yīng)對(duì)偶問題的約束方程的匹配形式。,,線性規(guī)劃的對(duì)偶理論,求線性規(guī)劃問題的對(duì)偶規(guī)劃,

13、解：由原問題的結(jié)構(gòu)可知為對(duì)稱型對(duì)偶問題,例1,線性規(guī)劃的對(duì)偶理論,求線性規(guī)劃問題的對(duì)偶規(guī)劃,解：由原問題的結(jié)構(gòu)可知不是對(duì)稱型對(duì)偶問題，可先化為對(duì)稱型，再求其對(duì)偶規(guī)劃。,,例2,線性規(guī)劃的對(duì)偶理論,求線性規(guī)劃問題的對(duì)偶規(guī)劃,解：由原問題的結(jié)構(gòu)可知不是對(duì)稱型對(duì)偶問題，可先化為對(duì)稱型，再求其對(duì)偶規(guī)劃。,,例3,線性規(guī)劃的對(duì)偶理論,上式已為對(duì)稱型對(duì)偶問題，故可寫出它的對(duì)偶規(guī)劃,令,則上式化為,線性規(guī)劃的對(duì)偶理論,對(duì)偶問題的非對(duì)稱形式,min z

14、= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max w=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3-

15、y4 -1 y1 0,y2 ,y3 0,y4 0,≥,≤,=,≤,unr,≥,≤,≥,=,≤,≥,x1≥0,x2≤0,x3: unr,,線性規(guī)劃的對(duì)偶理論,1 原問題為“max”，對(duì)偶問題為“min”；2 原問題中目標(biāo)函數(shù)系數(shù) ci 變?yōu)槠鋵?duì)偶問題約束條件的右端常數(shù)；3 原問題約束條件的右端常數(shù) bi 變?yōu)槠鋵?duì)偶問題目標(biāo)函數(shù)的系數(shù)；4 原問題約束條件的系數(shù)矩陣轉(zhuǎn)置，即為其對(duì)偶

16、問題的系數(shù)矩陣；5 原問題的變量個(gè)數(shù)n等于其對(duì)偶問題的約束條件個(gè)數(shù)n，原問題 約束條件的個(gè)數(shù)m等于其對(duì)偶問題變量的個(gè)數(shù)m；6 在求極大值的原問題中，“≤”，“≥”和“=”的約束條件分別對(duì)應(yīng)其對(duì)偶變量“≥0”，“≤0”和“無符號(hào)限制”；7 在求極大值的原問題中，變量“≥0”，“≤0”和“無符號(hào)限制”分別對(duì)應(yīng)其對(duì)偶約束條件的“≥”，“≤”和“=”約束.,混合型問題的對(duì)偶規(guī)則：,線性規(guī)劃的對(duì)偶理論,線性規(guī)劃的對(duì)偶理論,Max Z=

17、40x1+ 50x2,x1+2x2 ? 303x1+2x2 ? 60 2x2 ? 24 x1 , x2 ?0,s.t,y1y2y3,Min W = 30y1+ 60y2 + 24y3,y1+3y2 + 0y3 ? 402y1+2y2 + 2y3 ? 50 y1 , y2 , y3 ?0,s.t,Max W′= -30y1- 60y2 - 24y3,,y1+3y2 + 0y3 – y4 =

18、402y1+2y2 + 2y3 – y5 = 50 y1 , y2 , y3 , y4 , y5 ?0,s.t,例4,,,二、 對(duì)偶問題的解,線性規(guī)劃的對(duì)偶理論,Max W′= -30y1- 60y2 - 24y3 +0(y4 + y5 )-M (y6 + y7 ),,y1+3y2 + 0y3 – y4 + y6 = 402y1+2y2 + 2y3 – y5 + y7 = 50 y1 , y2 , y3 , y4 , y5

19、 ?0,s.t,線性規(guī)劃的對(duì)偶理論,,線性規(guī)劃的對(duì)偶理論,,線性規(guī)劃的對(duì)偶理論,線性規(guī)劃的對(duì)偶理論,原問題與其對(duì)偶問題的變量與解的對(duì)應(yīng)關(guān)系： 在單純形表中，原問題的松弛變量對(duì)應(yīng)對(duì)偶問題的變量，對(duì)偶問題的剩余變量對(duì)應(yīng)原問題的變量。,線性規(guī)劃的對(duì)偶理論,原問題最優(yōu)表,對(duì)偶問題最優(yōu)表,線性規(guī)劃的對(duì)偶理論,性質(zhì)1 對(duì)稱性定理：對(duì)偶問題的對(duì)偶是原問題,,,三、 對(duì)偶原理,線性規(guī)劃的對(duì)偶理論,,,,對(duì)偶的定義,簡(jiǎn)要證明：,線性規(guī)劃的對(duì)偶理論

20、,性質(zhì)2 弱對(duì)偶原理(弱對(duì)偶性)：設(shè) 和 分別是問題(P)和(D)的可行解，則必有,推論1: 原問題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的下界；反之，對(duì)偶問題任意可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。,證明：,(1) 當(dāng)X和Y為原問題和對(duì)偶問題的一個(gè)可行解,有,原問題目標(biāo)函數(shù)值,對(duì)偶問題目標(biāo)函數(shù)值,線性規(guī)劃的對(duì)偶理論,推論2: 在一對(duì)對(duì)偶問題（P）和（D）中，若其中一個(gè)問題可行但目標(biāo)函數(shù)無界，則另一個(gè)問

21、題無可行解；反之不成立。這也是對(duì)偶問題的無界性。,線性規(guī)劃的對(duì)偶理論,推論3：在一對(duì)對(duì)偶問題（P）和（D）中，若一個(gè)可行（如P），而另一個(gè)不可行（如D），則該可行的問題目標(biāo)函數(shù)值無界。,已知原問題(LP)，,試估計(jì)它的目標(biāo)函數(shù)值的界,并驗(yàn)證弱對(duì)偶定理.,例5,線性規(guī)劃的對(duì)偶理論,解：,問題(LP)的對(duì)偶問題(DP)為,(DP),,線性規(guī)劃的對(duì)偶理論,由觀察可知,分別是原問題和對(duì)偶問題的可行解。,，弱對(duì)偶定理成立。,且由推論1知，對(duì)偶問題

22、目標(biāo)函數(shù)W的下界為10，原問題目標(biāo)函數(shù)Z的上界為40。,且原問題的目標(biāo)函數(shù)值為,對(duì)偶問題的目標(biāo)函數(shù)值為,故,,,線性規(guī)劃的對(duì)偶理論,例：利用對(duì)偶性質(zhì)判斷下面問題有無最優(yōu)解,例6,解：此問題的對(duì)偶問題為,不能成立，因此對(duì)偶問題不可行。故由推論3知原問題無界。,,,,線性規(guī)劃的對(duì)偶理論,性質(zhì)3 最優(yōu)性定理：如果 是原問題的可行解， 是其對(duì)偶問題的可行解，并且:,則 是原問題的最優(yōu)解， 是其對(duì)偶問題的最優(yōu)解。,線性規(guī)

23、劃的對(duì)偶理論,性質(zhì)4 強(qiáng)(主)對(duì)偶性：若原問題及其對(duì)偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。,還可推出另一結(jié)論：若一對(duì)對(duì)偶問題中的任意一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等；若一個(gè)問題無最優(yōu)解，則另一問題也無最優(yōu)解。,一對(duì)對(duì)偶問題的關(guān)系，有且僅有下列三種：都有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等；兩個(gè)都無可行解；一個(gè)問題無界，則另一問題無可行解。,線性規(guī)劃的對(duì)偶理論,證明：當(dāng)X*為原問題的

24、一個(gè)最優(yōu)解，B為相應(yīng)的最優(yōu)基，通過引入松弛變量Xs，將問題(P)轉(zhuǎn)化為標(biāo)準(zhǔn)型,,,,,,,說明Y*可行,,,線性規(guī)劃的對(duì)偶理論,問題:（1）由性質(zhì)4可知，對(duì)偶問題最優(yōu)解的表達(dá)式 Y*=?,（2）求 Y*是否有必要重新求解(D)?,—不必?？梢詮脑瓎栴}（P）的單純形終表獲得。,,線性規(guī)劃的對(duì)偶理論,性質(zhì)5 互補(bǔ)松弛性：設(shè)X0和Y0分別是P問題 和 D問題 的可行解，則它們分別是最優(yōu)解的充要條件是：,其中：Xs、Ys為松弛變量。,在線性規(guī)

25、劃問題的最優(yōu)解中，若對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；另一方面，如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的變量一定為零。,緊約束與松約束,線性規(guī)劃的對(duì)偶理論,一個(gè)約束稱為緊約束，如果該約束在所有最優(yōu)解上的值使左右取等號(hào)。 即我們把嚴(yán)格等式約束稱為緊約束（或起作用約束）.,不是緊約束的約束稱為松約束。 即把某一最優(yōu)解處取嚴(yán)格不等式的約束稱為松約束（或不起作用約束）。,對(duì)于最優(yōu)解X*和Y*而言，松約束

26、的對(duì)偶約束是緊約束.,以上關(guān)系稱為對(duì)偶問題的互補(bǔ)松弛關(guān)系或松緊關(guān)系。在計(jì)算上，若已知一個(gè)問題的最優(yōu)解，則可利用互補(bǔ)松弛條件求另一個(gè)問題的最優(yōu)解.,緊約束與松約束,松緊關(guān)系,非常重要,線性規(guī)劃的對(duì)偶理論,證: (必要性）,,,線性規(guī)劃的對(duì)偶理論,Max Z=CXs.t.AX+XS=bX, XS ≥0,Min W=Ybs.t. YA-YS=CW, WS ≥0,XTYS=0YTXS=0,,,,,,,,,,,,m,n,

27、=,Y,YS,AT,-I,C,,,n,,,,,,,,,,,=,A,XS,I,b,,,,n,m,m,X,原始問題和對(duì)偶問題變量、松弛變量的維數(shù),線性規(guī)劃的對(duì)偶理論,,,,,,,,,x1 xj xn xn+1 xn+i xn+m,對(duì)偶問題的變量 對(duì)偶問題的松弛變量,原始問題的變量 原始問題的松弛變量,xjym+j=0

28、yixn+i=0(i=1,2,…,m; j=1,2,…,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0,線性規(guī)劃的對(duì)偶理論,性質(zhì)5的應(yīng)用：該性質(zhì)給出了已知一個(gè)問題最優(yōu)解求另一個(gè)問題最優(yōu)解的方法，即已知Y＊求X＊或已知X＊求Y＊,互補(bǔ)松弛條件,由于變量都非負(fù)，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系： 若Y＊≠0，則Xs必為0；若X＊≠0，則Ys必為0利用上述關(guān)系，建立對(duì)偶問題（或原問題）的

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

30、問題的最優(yōu)解為：Y＊=(1,1)，最優(yōu)值w=26。,線性規(guī)劃的對(duì)偶理論,已知線性規(guī)劃,的對(duì)偶問題的最優(yōu)解為Y＊=(0,-2)，求原問題的最優(yōu)解。,解: 對(duì)偶問題是,例8,線性規(guī)劃的對(duì)偶理論,設(shè)原問題最優(yōu)解為X＊＝(x1，x2 ，x3)T ,由互補(bǔ)松弛性定理知，X＊和 Y＊滿足：,將Y＊帶入由方程可知，y3＝y(tǒng)5＝0，y4＝1。,∵y2=-2≠0 ∴x5＝0又∵y4=1≠0 ∴x2＝0,將x2，x5分別帶入原問題約束方程

31、中，得：,解方程組得：x1=-5,x3=-1, 所以原問題的最優(yōu)解為,X＊=(-5,0,-1)，最優(yōu)值z(mì)=-12,線性規(guī)劃的對(duì)偶理論,試用對(duì)偶原理求解線性規(guī)劃問題,已知其對(duì)偶規(guī)劃的最優(yōu)解為,練習(xí),線性規(guī)劃的對(duì)偶理論,,解：,該問題的對(duì)偶規(guī)劃為,線性規(guī)劃的對(duì)偶理論,利用松緊關(guān)系，,代入對(duì)偶規(guī)劃的約束條件得下列約束是松約束，,,將最優(yōu)解,松約束,緊約束,其對(duì)偶約束是緊約束,線性規(guī)劃的對(duì)偶理論,設(shè)原問題的最優(yōu)解為,緊約束,線性規(guī)劃的對(duì)偶理論

32、,對(duì)偶規(guī)劃可以用線性規(guī)劃的單純形法求解。由對(duì)偶原理可見，原問題與對(duì)偶問題之間有緊密聯(lián)系，因此我們能夠通過求解原問題來找出對(duì)偶問題的解，反之依然?；パa(bǔ)松弛條件就可以解決由原問題的最優(yōu)解直接求出對(duì)偶問題的最優(yōu)解。,對(duì)偶問題解的求法,線性規(guī)劃的對(duì)偶理論,原問題與對(duì)偶問題解的對(duì)應(yīng)關(guān)系小結(jié),線性規(guī)劃的對(duì)偶理論,思考題,判斷下列結(jié)論是否正確，如果不正確，應(yīng)該怎樣改正？,1）任何線性規(guī)劃都存在一個(gè)對(duì)應(yīng)的對(duì)偶線性規(guī)劃.2）原問題第i個(gè)約束是“≤”

33、約束，則對(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）原問題具有無界解，則對(duì)偶問題不可行.11）對(duì)偶問題具有無界解，則原問題

34、無最優(yōu)解.12）若X*、Y*是原問題與對(duì)偶問題的最優(yōu)解，則X*=Y*.,線性規(guī)劃的對(duì)偶理論,2.5 影子價(jià)格,,單位產(chǎn)品消耗的資源(噸/件)),原始問題是利潤(rùn)最大化的生產(chǎn)計(jì)劃問題,總利潤(rùn)(元),產(chǎn)品產(chǎn)量(件),單位產(chǎn)品的利潤(rùn)(元/件),消耗的資源(噸),剩余的資源(噸),資源限量(噸),,,,,,,影子價(jià)格,對(duì)偶問題——資源定價(jià)問題,,,,對(duì)偶問題是資源定價(jià)問題，對(duì)偶問題的最優(yōu)解y1、y2、...、ym稱為m種資源的影子價(jià)格（S

35、hadow Price）,原始和對(duì)偶問題都取得最優(yōu)解時(shí)，最大利潤(rùn) Max z=Min w,總利潤(rùn)(元),資源限量(噸),資源價(jià)格(元/噸),影子價(jià)格,在一對(duì) P 和 D 中，若 P 的某個(gè)約束條件的右端項(xiàng)常數(shù) bi （第 i 種資源的擁有量）增加一個(gè)單位時(shí)，所引起目標(biāo)函數(shù)最優(yōu)值z(mì)* 的改變量稱為第 i 種資源的影子價(jià)格，其值等于D問題中對(duì)偶變量 yi*。,由對(duì)偶問題得基本性質(zhì)可得：,1. 影子價(jià)格的數(shù)學(xué)分析：,影子價(jià)格,2. 影子價(jià)

36、格的經(jīng)濟(jì)意義1）影子價(jià)格是一種邊際價(jià)格在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。即對(duì)偶變量yi 就是第 i 種資源的影子價(jià)格。即：,影子價(jià)格,資源影子價(jià)格的性質(zhì),影子價(jià)格越大，說明這種資源越是相對(duì)緊缺影子價(jià)格越小，說明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0,影子價(jià)格,,,0,,,,X2,X1,X= (15,7.5) Z=975,,X= (15.5,7.25

37、) Z=982.5,,,X= (14.5,8.25) Z=992.5,,,,,,0,,,,X2,X1,X= (15,7.5) Z=975,,,,0,,,,X2,X1,X= (15,7.5) Z=975,,,X= (14.5,8.25) Z=992.5,,,,0,,,,X2,X1,X= (15,7.5) Z=975,,X= (15.5,7.25) Z=982.5,,,,,0,,,,X2,X1,X= (15,7.5) Z=975,,,,,0

38、,,,,X2,X1,X= (15,7.5) Z=975,,X= (15.5,7.25) Z=982.5,,,X= (14.5,8.25) Z=992.5,,2）影子價(jià)格是一種機(jī)會(huì)成本影子價(jià)格是在資源最優(yōu)利用條件下對(duì)單位資源的估價(jià)，這種估價(jià)不是資源實(shí)際的市場(chǎng)價(jià)格。因此，從另一個(gè)角度說，它是一種機(jī)會(huì)成本。,若第i 種資源的單位市場(chǎng)價(jià)格為mi ，則有當(dāng)yi* > mi 時(shí)，企業(yè)愿意購進(jìn)這種資源，單位純利為yi*－mi ，則有利可圖

39、；當(dāng)yi* < mi 時(shí)，企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利mi－yi * ，否則，企業(yè)無利可圖，甚至虧損。,結(jié)論：若yi* > mi 則購進(jìn)資源 i，可獲單位純利yi*－mi ； 若yi* < mi則轉(zhuǎn)讓資源 i ，可獲單位純利mi－yi 。,影子價(jià)格,,y1y2ym,產(chǎn)品的機(jī)會(huì)成本,機(jī)會(huì)成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤(rùn),增加單位資源可以增加的利潤(rùn),減少一件產(chǎn)品可以節(jié)省的資源,影子價(jià)

40、格,,,,機(jī)會(huì)成本,利潤(rùn),差額成本,產(chǎn)品的差額成本（Reduced Cost）,,差額成本=機(jī)會(huì)成本 - 利潤(rùn),影子價(jià)格,,3）影子價(jià)格在資源利用中的應(yīng)用 根據(jù)對(duì)偶理論的互補(bǔ)松弛性定理: Y*Xs=0 , YsX*=0表明生產(chǎn)過程中如果某種資源 bi 未得到充分利用時(shí)，該種資源的影子價(jià)格為0；若當(dāng)資源資源的影子價(jià)格不為0時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完。,影子價(jià)格,yixn+i=0,如果yi >0，則xn

41、+i =0,如果xn+i >0，則yi =0,影子價(jià)格大于0的資源，在最優(yōu)生產(chǎn)計(jì)劃條件下沒有剩余,ym+jxj=0,如果ym+j >0，則xj =0,如果xj >0，則ym+j =0,最優(yōu)生產(chǎn)計(jì)劃條件下有剩余的資源，其影子價(jià)格等于0,差額成本大于0（機(jī)會(huì)成本大于利潤(rùn)）的產(chǎn)品，不安排生產(chǎn),安排生產(chǎn)的產(chǎn)品，差額成本等于0（機(jī)會(huì)成本等于利潤(rùn)）,互補(bǔ)松弛關(guān)系經(jīng)濟(jì)解釋,影子價(jià)格,4）影子價(jià)格對(duì)單純形表計(jì)算的解釋,單純形表中的檢驗(yàn)

42、數(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ì)劃中安排；否則 ，用這些資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。,影子價(jià)格,2.6 對(duì)偶單純形法,對(duì)偶單純形法是求解線性規(guī)劃的另一個(gè)基本方法。它是根據(jù)對(duì)偶原理和單純形法原理而設(shè)計(jì)出來的，因此稱為對(duì)偶

43、單純形法。不要簡(jiǎn)單理解為是求解對(duì)偶問題的單純形法。,對(duì)偶單純形法原理,對(duì)偶單純形法基本思路：,找出一個(gè)對(duì)偶問題的可行基，保持對(duì)偶問題為可行解的條件下，判斷XB是否可行（XB為非負(fù)），若否，通過變換基解，直到找到原問題基可行解（即XB為非負(fù)），這時(shí)原問題與對(duì)偶問題同時(shí)達(dá)到可行解，由定理4可得最優(yōu)解。,對(duì)偶單純形法,找出一個(gè)DP的可行基,LP是否可行（XB ≥0）,保持DP為可行解情況下轉(zhuǎn)移到LP的另一個(gè)基本解,最優(yōu)解,,,,,,,是,否

44、,循環(huán),,結(jié)束,對(duì)偶單純形法,先回顧一下單純形算法：它是從線性規(guī)劃的一個(gè)基可行解迭代到另一個(gè)基可行解的過程，在迭代過程中，保持基解的可行性，逐步消除基解的檢驗(yàn)數(shù)的非負(fù)性，即,,為了求解線性規(guī)劃，我們也可以從線性規(guī)劃的一個(gè)基解迭代到另一個(gè)基解，在迭代過程中，保持基解的檢驗(yàn)數(shù)的非正性，逐步消除基解的不可行性，即,,對(duì)偶單純形法,如果原問題(P)的一個(gè)基本解X與對(duì)偶問題(D)的基可 行解Y對(duì)應(yīng)的檢驗(yàn)數(shù)向

45、量滿足條件 則稱X為原問題(P)的一個(gè)正則解。,求解原問題(P)時(shí)，可以從(P)的一個(gè)正則解開始，迭代到另一個(gè)正則解，使目標(biāo)函數(shù)值增加，當(dāng)?shù)秸齽t解滿足原始可行性條件(即xi≥0)時(shí)，就找到了原問題(P)的最優(yōu)解。 這一方法稱為對(duì)偶單純形法,對(duì)偶單純形法,定義,對(duì)偶單純形法,,,原問題解空間,對(duì)偶問題解空間,,,,,,,,可行解,可行解,基本解,基本解,正則解,正則解,基可

46、行解,基可行解,,,最優(yōu)解,,,,對(duì)偶單純形法,對(duì)偶單純法的迭代步驟：,（1）找一個(gè)正則基B和初始正則解X(0)，將問題（P）化為關(guān)于基B的典式，列初始對(duì)偶單純形表.,設(shè)正則解,的典式為：,對(duì)偶單純形法,將上面的典式轉(zhuǎn)換成前面所學(xué)習(xí)過的單純形表：,,,對(duì)偶單純形法,,,,,,對(duì)偶單純形法,,,,,,,,,,,,對(duì)偶單純形法,用對(duì)偶單純形法計(jì)算,例9,對(duì)偶單純形法,由于初始正則解有負(fù)分量，于是取min{-3,-4}=-4x5為換出變量，

47、取,x1為換入變量，得新基{x4,x1} ，?51= -2為主元,,,,對(duì)偶單純形法,基變換的過程：,主元變?yōu)?，即用-2去除單純形表中基變量x5所在的行；主元所在列的其它元變?yōu)?，消去非基變量x1所在的列的其余元-1，-2；得新基{x4,x1}的單純形表,,,,對(duì)偶單純形法,,基變換的過程：,,,,,,對(duì)偶單純形法,,可見正則解的有負(fù)分量，由于x4=1 , 所以取x4為換出變量，取,x2為換入變量，得新基{x2,x1} ，?42

48、=-5/2為主元,,,,對(duì)偶單純形法,此時(shí)正則解是可行解，也是最優(yōu)解。 X*=(11/5，2/5，0，0，0)；z*=-28/5,,進(jìn)行基變換，得新正則解的單純形表：,對(duì)偶單純形法,,,例10,,例11,,例12,對(duì)偶單純形法的迭代步驟中,如何找一個(gè)初始正則解？,初始正則解的確定,標(biāo)準(zhǔn)形線性規(guī)劃問題,選定的基B，不妨設(shè),對(duì)偶單純形法,可行基B的典式為,右端常數(shù)中有負(fù)數(shù)，而檢驗(yàn)數(shù)全非正，則基B為正則基，相應(yīng)的

49、 解為初始正則解，就可用對(duì)偶單純形法求解。,否則，若出現(xiàn)正檢驗(yàn)數(shù)，X(0)就不是正則解。,為此，求初始正則基和初始正則解，可增加一個(gè)約束條件：,原問題(P)的典式擴(kuò)充為下列問題:,擴(kuò)充問題：,對(duì)偶單純形法,擴(kuò)充問題的一個(gè)正則基和正則解是不難得到的。,對(duì)偶單純形法,擴(kuò)充問題的兩種可能結(jié)果：,（1）若擴(kuò)充問題無可行解，則原問題(P)也無可行解。,則把 x

50、0 作為換出變量，xk 作為換入變量，經(jīng)過一次迭代，就可得到一個(gè)正則解：,具體計(jì)算可以在單純形表上實(shí)現(xiàn).,,,證明:,則 一定是擴(kuò)充問題的可行解，與假設(shè)矛盾。,令,對(duì)偶單純形法,（1）若擴(kuò)充問題無可行解，則原問題(P)也無可行解。事實(shí)上，若原問題如果有可行解：,由于,所以,則 是擴(kuò)充問題的可行解，又因擴(kuò)充問題與原問題的目標(biāo)函數(shù)相同，且都與 無關(guān),所以必有,這與 是擴(kuò)充問題的最優(yōu)解矛盾。,

51、對(duì)偶單純形法,（2）若擴(kuò)充問題有最優(yōu)解,且目標(biāo)函數(shù)最優(yōu)值與 M 無關(guān),則有,必為原問題(P)的最優(yōu)解。事實(shí)上，如果原問題有可行解,對(duì)偶單純形法的理論解釋,對(duì)偶單純形法所使用的表格與原單純形法一樣，可將典式中的數(shù)據(jù)放在原單純形表上，即得到對(duì)偶單純形表，所不同的是這里保證在整個(gè)過程中,,不保證,,即右端常數(shù)中可以出現(xiàn)負(fù)數(shù)。,對(duì)偶單純形法,先定換出變量，再定換入變量。,設(shè)正則基

52、的典式為：,對(duì)偶單純形法,對(duì)偶單純形表,對(duì)偶單純形法的迭代方式與原單純形法基本一致.所不同的是：先定換出變量，再定換入變量，決定主元并作基變換得到一個(gè)新的正則解X(1),從而完成一次迭代.算法的后半部分與原單純形法完全一致.,對(duì)偶單純形法,,,(2)再選進(jìn)基變量:假定xk為進(jìn)基變量, 我們分析一下xk 應(yīng)滿足什么條件,才能使迭代后得到的解仍為問題(P)的正則解.,(1)先選出基變量:若 則取與 相對(duì)應(yīng)的基變量 xr 為出基變量.

53、,因?yàn)?,而換基運(yùn)算的第一步是用主元 去除第r 行中的各元素,為了使變換后 為正數(shù),所以主元 必須從第r 行的負(fù)元素中選取,即 .,,設(shè)主元處在第 k 列,于是換基運(yùn)算后,各檢驗(yàn)數(shù)變?yōu)?因?yàn)橐蟮蟮玫降慕馊詾檎齽t解,于是,又因?yàn)?于是當(dāng) 時(shí),不等式(1)自然成立;,由此,則取與之相對(duì)應(yīng)的非基變量 為換入變量。,

54、否則,當(dāng) 時(shí),要使不等式(1)成立,必須,又因?yàn)?于是當(dāng) 時(shí),不等式(1)自然成立;,對(duì)偶單純形法,,最后證明對(duì)應(yīng)于新的正則解X(1),對(duì)偶問題(D)的目標(biāo)函數(shù)值將得到改善.,這樣,上述求極大值問題(P)的迭代過程,實(shí)質(zhì)上是在對(duì)對(duì)偶問題(D)求極小值,所以目標(biāo)函數(shù)越小就越接近最優(yōu)解.直到得到對(duì)偶問題(D)的最小值,相應(yīng)地也就求出了原問題(P)的最大值.,出基變量 與進(jìn)

55、基變量 xk 確定以后,以 為主元進(jìn)行換基運(yùn)算(方法與原單純形法相同)即可得新的正則解X(1) .,這是因?yàn)?,故,,和原始單純形法一樣,若對(duì)偶問題是非退化的(即對(duì)偶問題的每一個(gè)基可行解都是非退化的,或者說,對(duì)于原問題的每一個(gè)正則解，都有 ,

56、則每迭代一次,目標(biāo)函數(shù)都將嚴(yán)格減小,從而一定能在有限次迭代后得到原問題的最優(yōu)解,或者判定它無解.,容易證明:若 ,且所有的 ,則原問題(P)無解(自己證明).,用對(duì)偶單純形法求解線性規(guī)劃問題時(shí)，當(dāng)約束條件為“＞”時(shí)，不必引進(jìn)人工變量，使計(jì)算簡(jiǎn)化。當(dāng)線性規(guī)劃問題中變量多于約束條件時(shí)，用對(duì)偶單純形法計(jì)算可以減少工作量。對(duì)偶單純形法應(yīng)用于主