運(yùn)籌學(xué)第2章(講課比賽)

Chapter2對(duì)偶理論

(DualityTheory)單純形法的矩陣描述對(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ī)劃問題。

3.會(huì)用互補(bǔ)松弛條件來考慮一對(duì)對(duì)偶問題的界。

4.了解影子價(jià)格、靈敏度分析以及用WinQSB求解對(duì)偶規(guī)劃問題。2.1

單純形法的矩陣描述0.16-0.120102412x2-0.20.4001207x11.16-3.12100840x3-1.20003.41000.10010,33012x220-0.51002.5500x430.8-0.40107.82400x3000127301001033000x540010542000x490001493600x3?x5x4x3x2x1B-1bCBXB每一列的含義？每個(gè)表中的B和B-1的查找？單純形法的矩陣描述單純形法的矩陣描述單純形法的矩陣描述CBCNbXBXNbBNCBCNbXBXNB-1bIB-1N-CBB-1b0CN-CBB-1N單純形法的矩陣描述CBCNCS(0)bXBXNXSbBNI0CBCN0CBCNCS(0)bXBXNXSB-1bIB-1NB-1-CBB-1b0CN-CBB-1N-CBB-1

單純形法的矩陣描述2.3對(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)生這樣一種問題呢？對(duì)偶問題的提出倆家具制造商間的對(duì)話：唉!我想租您的木工和油漆工一用。咋樣？?jī)r(jià)格嘛……好說，肯定不會(huì)讓您兄弟吃虧。王老板做家具賺了大錢，可惜我老李有高科技產(chǎn)品，卻苦于沒有足夠的木工和油漆工咋辦？只有租咯。Hi：王老板，聽說近來家具生意好呀，也幫幫兄弟我哦!家具生意還真賺錢，但是現(xiàn)在的手機(jī)生意這么好，不如干脆把我的木工和油漆工租給他，又能收租金又可做生意。價(jià)格嘛……好商量，好商量。只是…...

王老板李老板引例1對(duì)偶問題的提出王老板的家具生產(chǎn)模型：x1、

x2是桌、椅生產(chǎn)量。Z是家具銷售總收入（總利潤(rùn)）。maxZ=50x1+30x2s.t.4x1+3x2

≤120（木工）

2x1+x2

≤50（油漆工）

x1，x2

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

≥503y1+y2

≥30y1，y2

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

Z=

40x1+50x2

x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目標(biāo)函數(shù)約束條件設(shè)三種資源的使用單價(jià)分別為y1,y2,y3y1y2y3生產(chǎn)單位產(chǎn)品A的資源消耗所得不少于單位產(chǎn)品A的獲利生產(chǎn)單位產(chǎn)品B的資源消耗所得不少于單位產(chǎn)品B的獲利y1+3y240

2y1+2y2+2y350甲乙資源量A1230B3260C0224單位獲利4050引例2通過使用所有資源對(duì)外加工所獲得的收益W=30y1+60y2+24y3對(duì)偶問題的提出根據(jù)原則2，對(duì)方能夠接受的價(jià)格顯然是越低越好，因此此問題可歸結(jié)為以下數(shù)學(xué)模型：Min

W=30y1+60y2+24y3

y1+3y2402y1+2y2+2y350y1,y2,y3

0s.t目標(biāo)函數(shù)約束條件原線性規(guī)劃問題稱為原問題，此問題為對(duì)偶問題，y1,y2,y3為對(duì)偶變量，也稱為影子價(jià)格對(duì)偶問題的提出2.4線性規(guī)劃的對(duì)偶理論Max

Z=

40x1+50x2

x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t原問題（對(duì)偶問題）對(duì)偶問題（原問題）一、原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系Min

W=30y1+60y2+24y3

y1+3y2402y1+2y2+2y350y1,y2,y3

0s.t（y1）

（y2）（y3）

（x1）

13040（x2）22250306024

minωmaxz

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ì)偶問題簡(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、改變約束問題不等號(hào)的方向，即將“≤”改為“≥”；6、原問題為“max”型，對(duì)偶問題為“min”型。線性規(guī)劃的對(duì)偶理論原始問題MaxZ=CXs.t.AX≤b

X

≥0bAC≤Maxnm對(duì)偶問題MinW=Ybs.t. YA≥C Y≥0≥MinCATbnmY為行向量線性規(guī)劃的對(duì)偶理論當(dāng)原問題為求極小值時(shí)，對(duì)偶問題為求極大值。原始問題中目標(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ī)劃解：由原問題的結(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ì)稱形式minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40≥≤=≤unr≥≤≥=≤≥x1≥0x2≤0x3:unr原始問題變量的個(gè)數(shù)(3)等于對(duì)偶問題約束條件的個(gè)數(shù)(3)；原始問題約束條件的個(gè)數(shù)(4)等于對(duì)偶問題變量的個(gè)數(shù)(4)。原始問題變量的性質(zhì)影響對(duì)偶問題約束條件的性質(zhì)，用

表示原始問題約束條件的性質(zhì)影響對(duì)偶問題變量的性質(zhì)，用表示線性規(guī)劃的對(duì)偶理論原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)目標(biāo)函數(shù)max目標(biāo)函數(shù)min約束條件m個(gè)m個(gè)變量≤≥0≥≤0=無約束變量n個(gè)n個(gè)約束條件≥0≥≤0≤無約束=線性規(guī)劃的對(duì)偶理論MaxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20s.ty1y2y3MinW=30y1+60y2+24y3

y1+3y2+0y3

402y1+2y2+2y3

50

y1,y2,y30s.tMaxW′=-30y1-60y2-24y3

y1+3y2+0y3–y4

=402y1+2y2+2y3

–y5

=50y1,y2,y3,y4,y50s.t例4二、對(duì)偶問題的解線性規(guī)劃的對(duì)偶理論MaxW′=-30y1-60y2-24y3+0(y4+

y5)-M(y6+

y7)

y1+3y2+0y3–y4+

y6

=402y1+2y2+2y3

–y5

+

y7

=50y1,y2,y3,y4,y50s.tcj-30-60-2400-M-MB-1bθcByBy1y2y3y4y5y6y7-My6130-10104040/3-My72220-1015050/2σj3M-305M-602M-24-M-M00-90M線性規(guī)劃的對(duì)偶理論cj-30-60-2400-M-MB-1bθcByBy1y2y3y4y5y6y7-60y21/310-1/301/3040/3-My74/3022/3-1-2/3170/335/3σj4M/3-1002M-242M/3+20-M-5M/3+200800-70M/3-60y21/310-1/301/3040/340-24y32/3011/3-1/2-1/31/235/335/2σj600-12-12-M+12-M+12-1080-60y201-1/2-1/21/41/2-1/415/2-30y1103/21/2-3/4-1/23/435/2σj00-9-15-15/2-M+30-M-15/2-975線性規(guī)劃的對(duì)偶理論cj4050000B-1bcBxBx1x2x3x4x540x1101/2-1/20150x5003/2-1/21950x201-3/41/4015/2σj00-35/2-15/20975MaxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20s.t

x1+2x2+x3=303x1+2x2+x4=602x2+x5=24

x1–x50s.t線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論原問題與其對(duì)偶問題的變量與解的對(duì)應(yīng)關(guān)系： 在單純形表中，原問題的松弛變量對(duì)應(yīng)對(duì)偶問題的變量，對(duì)偶問題的剩余變量對(duì)應(yīng)原問題的變量。線性規(guī)劃的對(duì)偶理論XBb原問題的變量原問題的松弛變量x1x2x3x4x5x115101/2-1/20x59003/2-1/21x215/2013/4-1/4000-35/2-15/20YBb對(duì)偶問題的變量對(duì)偶問題的剩余變量y1y2y3y4y5y215/201-1/2-1/21/4y135/2103/21/2-3/400-9-15-15/2原問題最優(yōu)表對(duì)偶問題最優(yōu)表MaxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20s.tMinW=30y1+60y2+24y3

y1+3y2+0y3

402y1+2y2+2y3

50

y1,y2,y30s.t線性規(guī)劃的對(duì)偶理論性質(zhì)1對(duì)稱性定理：對(duì)偶問題的對(duì)偶是原問題

minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≤bX≥0三、對(duì)偶原理線性規(guī)劃的對(duì)偶理論minz′=-

CXs.t.-AX≥-b X≥0maxw′=-Ybs.t.-YA≤-C

Y≥0minw=Ybs.t.YA≥C

Y≥0maxz=CXs.t.AX≤bX≥0對(duì)偶的定義對(duì)偶的定義簡(jiǎn)要證明：線性規(guī)劃的對(duì)偶理論性質(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è)問題無可行解；反之不成立。這也是對(duì)偶問題的無界性。若（P）為無界解，則（D）無可行解；若（D）為無界解，則（P）無可行解。線性規(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ì)偶理論解：?jiǎn)栴}(LP)的對(duì)偶問題(DP)為(DP)線性規(guī)劃的對(duì)偶理論由觀察可知分別是原問題和對(duì)偶問題的可行解。，弱對(duì)偶定理成立。且由推論1知，對(duì)偶問題目標(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ī)劃的對(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*為原問題的一個(gè)最優(yōu)解，B為相應(yīng)的最優(yōu)基，通過引入松弛變量Xs，將問題(P)轉(zhuǎn)化為標(biāo)準(zhǔn)型令CCBCN0解基系數(shù)基變量XBXNXsCBXBIB-1NB-1B-1bσ0CN-CBB-1N

-CBB-1CBB-1bCXAC-CBB-1A說明Y*可行線性規(guī)劃的對(duì)偶理論問題:（1）由性質(zhì)4可知，對(duì)偶問題最優(yōu)解的表達(dá)式Y(jié)*=?（2）求Y*是否有必要重新求解(D)?—不必?？梢詮脑瓎栴}（P）的單純形終表獲得。CCBCN0解基系數(shù)基變量XBXNXsCBXBIB-1NB-1B-1bσ0CN-CBB-1N

-CBB-1CBB-1b線性規(guī)劃的對(duì)偶理論性質(zhì)5

互補(bǔ)松弛性：設(shè)X0和Y0分別是P問題和D問題的可行解，則它們分別是最優(yōu)解的充要條件是：其中：Xs、Ys為松弛變量。在線性規(guī)劃問題的最優(yōu)解中，若對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；另一方面，如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的變量一定為零。緊約束與松約束線性規(guī)劃的對(duì)偶理論證:(必要性）原問題對(duì)偶問題線性規(guī)劃的對(duì)偶理論MaxZ=CXs.t. AX+XS=b X,XS≥0MinW=Ybs.t.YA-YS=C W,WS≥0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始問題和對(duì)偶問題變量、松弛變量的維數(shù)線性規(guī)劃的對(duì)偶理論

y1

yi

ymym+1

ym+j

yn+m

x1

xj

xnxn+1

xn+i

xn+m

對(duì)偶問題的變量對(duì)偶問題的松弛變量原始問題的變量原始問題的松弛變量xjym+j=0

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ì)偶問題（或原問題）的約束線性方程組，方程組的解即為最優(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ì)偶問題的最優(yōu)解為：Y＊=(1,1)，最優(yōu)值w=26。線性規(guī)劃的對(duì)偶理論已知線性規(guī)劃的對(duì)偶問題的最優(yōu)解為Y＊=(0,-2)，求原問題的最優(yōu)解。解:對(duì)偶問題是標(biāo)準(zhǔn)化例8線性規(guī)劃的對(duì)偶理論設(shè)原問題最優(yōu)解為X＊＝(x1，x2，x3)T,由互補(bǔ)松弛性定理知，X＊和Y＊滿足：將Y＊帶入由方程可知，y3＝y(tǒng)5＝0，y4＝1?！遹2=-2≠0∴x5＝0又∵y4=1≠0∴x2＝0將x2，x5分別帶入原問題約束方程中，得：解方程組得：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ì)偶理論對(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é)對(duì)應(yīng)關(guān)系原問題最優(yōu)解無界解無可行解對(duì)偶問題最優(yōu)解(Y,Y)(N,N)————無界解————(Y,Y)無可行解——(Y,Y)無法判斷線性規(guī)劃的對(duì)偶理論思考題判斷下列結(jié)論是否正確，如果不正確，應(yīng)該怎樣改正？1）任何線性規(guī)劃都存在一個(gè)對(duì)應(yīng)的對(duì)偶線性規(guī)劃.2）原問題第i個(gè)約束是“≤”約束，則對(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ì)偶問題具有無界解，則原問題無最優(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à)格（ShadowPrice）原始和對(duì)偶問題都取得最優(yōu)解時(shí)，最大利潤(rùn)Maxz=Minw總利潤(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à)格的經(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à)格0X2X1X=(15,7.5)Z=975MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975X=(14.5,8.25)

Z=992.5MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975X=(15.5,7.25)

Z=982.5MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975X=(15.5,7.25)

Z=982.5X=(14.5,8.25)

Z=992.5MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t2）影子價(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è)愿意購(gòu)進(jìn)這種資源，單位純利為yi*－mi

，則有利可圖；當(dāng)yi*<mi

時(shí)，企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利mi－yi

*

，否則，企業(yè)無利可圖，甚至虧損。結(jié)論：若yi*>mi

則購(gòu)進(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à)格機(jī)會(huì)成本利潤(rùn)差額成本產(chǎn)品的差額成本（ReducedCost）差額成本=機(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+i=0如果xn+i>0，則yi=0邊際利潤(rùn)大于0的資源，在最優(yōu)生產(chǎn)計(jì)劃條件下沒有剩余ym+jxj=0如果ym+j>0，則xj=0如果xj>0，則ym+j=0最優(yōu)生產(chǎn)計(jì)劃條件下有剩余的資源，其邊際利潤(rùn)等于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)數(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ì)偶單純形