對偶理論與影子價格

1第六節(jié)

對偶理論與影子價格

對偶問題的提出對偶問題的形式對偶問題的基本性質(zhì)影子價格對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第1頁!2對偶問題的提出對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第2頁!例1：某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示：問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤？

產(chǎn)品甲產(chǎn)品乙設(shè)備能力設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤15002500現(xiàn)在從另一個角度來討論該問題：

如果工廠考慮不安排生產(chǎn)，而準(zhǔn)備把所有設(shè)備出租（或用于外協(xié)加工），工廠收取租金（或加工費）。試問：設(shè)備A、B、C每工時各如何收費（租金或加工費）才最有競爭力？工廠為了獲得最大利潤，在為設(shè)備定價時，應(yīng)保證生產(chǎn)某產(chǎn)品的設(shè)備工時所收取的費用不低于生產(chǎn)該產(chǎn)品的利潤；同時，為了提高競爭力，應(yīng)該使定價盡可能低。目標(biāo)函數(shù)

設(shè)x1，x2分別為生產(chǎn)甲乙兩種產(chǎn)品的件數(shù)約束條件

設(shè)y1，y2，y3分別為每工時設(shè)備A、B、C的收費。目標(biāo)函數(shù)

約束條件對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第3頁!4

解：可以建立如下的線性規(guī)劃模型：

目標(biāo)函數(shù)

約束條件

化為標(biāo)準(zhǔn)型，利用單純形法進(jìn)行求解。最優(yōu)解X=(5,25,0,5,0)，最優(yōu)值（利潤）為70000。

對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第4頁!5原問題對偶問題對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第5頁!線性規(guī)劃有一個有趣的特性，就是對于任何一個求極大的線性規(guī)劃問題都存在一個與其匹配的求極小的線性規(guī)劃問題，并且這一對線性規(guī)劃問題的解之間還存在著密切的關(guān)系。線性規(guī)劃的這個特性稱為對偶性。

對這兩個線性規(guī)劃問題，一般稱前者為原問題，后者是前者的對偶問題

6對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第6頁!

一對對稱形式的對偶規(guī)劃之間具有下面的對應(yīng)關(guān)系：

1.若一個模型為目標(biāo)求“極大”，約束為“小于等于”的不等式，則它的對偶模型為目標(biāo)求“極小”，約束是“大于等于”的不等式。即“max，≤”和“min，≥”相對應(yīng)。

2.從約束系數(shù)矩陣看：一個模型中為Ａ，則另一個模型中為AT。一個模型是m個約束，n個變量，則它的對偶模型為n個約束，m個變量

3.從數(shù)據(jù)b、C的位置看：在兩個規(guī)劃模型中，b和C的位置對換

4.兩個規(guī)劃模型中的變量皆非負(fù)

7對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第7頁!一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形式的對偶規(guī)劃。

對于非對稱形式的規(guī)劃，可以按照下面的對應(yīng)關(guān)系進(jìn)行處理并給出其對偶規(guī)劃：

1.將模型統(tǒng)一為“max，≤”或“min，≥”的形式，對于其中的等式約束按下面的方法處理；

2.若原規(guī)劃的某個約束條件為等式約束，則在對偶規(guī)劃中與此約束對應(yīng)的那個變量取值沒有非負(fù)限制；

3.若原規(guī)劃的某個變量的值沒有非負(fù)限制，則在對偶問題中與此變量對應(yīng)的那個約束為等式。

也可以直接給出其對偶規(guī)劃。

8對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第8頁!解：先化為對稱形式（Max—≤）

“≥”的約束兩端同乘以“–1”

“=”的約束等價轉(zhuǎn)換為“≤”和“≥”的兩個約束，再變換

變量≤0，用變量替換，如

變量無非負(fù)限制，用變量替換，如

9對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第9頁!變量替換，令

10對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第10頁!

由此得到非對稱形式的線性規(guī)劃原問題和對偶問題的對應(yīng)關(guān)系（對稱形式也適用）

11原問題對偶問題A約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置b約束條件右端項目標(biāo)函數(shù)中的系數(shù)C目標(biāo)函數(shù)中的系數(shù)約束條件右端項目標(biāo)函數(shù)Maxz=ΣcjxjMinz=Σbiyi變量n個

xj≥0(≤0，無限制)約束條件n個Σaijyj≥(≤，=)cj約束條件m個Σaijxj≤(≥，=)bi變量m個

yi≥0(≤0，無限制)對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第11頁!1．對稱性。即對偶問題的對偶是原問題。12對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第12頁!弱對偶定理的推論：

1.（P）任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下界；（D）任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。

2.若（P）可行，那么（P）無有限最優(yōu)解的充分必要條件是（D）無可行解。

3.若（D）可行，那么（D）無有限最優(yōu)解的充分必要條件是（P）無可行解。

4.若（P）、（D）可行，那么（P）、（D）都有最優(yōu)解。

13對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第13頁!

4.（主對偶定理）若(P)和(D)均可行，那么(P)和(D)均有最優(yōu)解，且最優(yōu)值相等。

證明：若(P)和(D)均可行，則由弱對偶定理的推論知(P)和(D)均有最優(yōu)解。

設(shè)(P)的最優(yōu)基為B，令YT=CBB-1，由σ=C-CBB-1A≤0，對于松弛變量部分，目標(biāo)函數(shù)系數(shù)為0，系數(shù)矩陣為單位陣，檢驗數(shù)為σ=-CBB-1≤0，故Y≥0，且YTA≥C，ATY≥CT，因此Y為(D)的可行解。

目標(biāo)YTb=CBB-1b=CX（原問題最優(yōu)值），由最優(yōu)性準(zhǔn)則定理知Y為(D)的最優(yōu)解

注：(P)松弛變量的檢驗數(shù)的絕對值是(D)的基可行解

推論：(P)有最優(yōu)解的充分必要條件是(D)有最優(yōu)解

14對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第14頁!證明：由弱對偶定理（CX≤YTb）得由主對偶定理可知最優(yōu)值相等，上述不等式取“=”，15對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第15頁!影子價格影子價格(ShadowPrice)的概念：若X*，Y*分別為（P）和（D）的最優(yōu)解，則

z=CX*=Y*Tb=f根據(jù)z=b1y1*+b2y2*+???+bmym*可知z/bi

=

yi*

其中bi表示第i種資源的擁有量，yi*表示bi

變化1個單位對目標(biāo)z產(chǎn)生的影響，也是在資源最優(yōu)利用條件下對該資源的估價，稱為該資源的影子價格例如，在例1中yi*是對設(shè)備租金的估價注意：若B是最優(yōu)基，y*T=CBB-116對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第16頁!由互補(bǔ)松弛定理，可知如果某種資源未得到充分利用時（松弛變量不為0），則其影子價格為0（對應(yīng)變量為0）；當(dāng)資源的影子價格不為0，表明該資源在生產(chǎn)中已耗費完畢。

從影子價格的含義上來考察檢驗數(shù)j=cj-∑aijyi，其中cj

表示產(chǎn)品的價值，∑aijyi是生產(chǎn)該產(chǎn)品所消耗的各項資源的影子價格的總和，即產(chǎn)品的隱含成本。當(dāng)產(chǎn)品的價值大于隱含成本時，表明生產(chǎn)該產(chǎn)品有利；否則就不安排生產(chǎn)。這就是檢驗數(shù)的經(jīng)濟(jì)含義。

影子價格反映了不同的局部或個體的增量可以獲得不同的整體經(jīng)濟(jì)效益。如果為了擴(kuò)大生產(chǎn)能力，考慮增加設(shè)備，就應(yīng)該從影子價格高的設(shè)備入手，以較少的局部努力，獲得較大的整體效益。

17對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第17頁!影子價格的應(yīng)用舉例：

例5：某外貿(mào)公司準(zhǔn)備購進(jìn)兩種產(chǎn)品A1，A2。購進(jìn)產(chǎn)品A1每件需要10元，占用5平方米的空間，賣出1件可獲純利潤3元；購進(jìn)產(chǎn)品A2每件需要15元，占用3平方米的空間，賣出1件可獲純利潤4元。公司現(xiàn)有資金1400元，有430平方米的倉庫空間存放產(chǎn)品。根據(jù)這些條件可以建立求最大利潤的線性規(guī)劃模型：

Maxz=3x1+4x2

s.t.10x1+15x2≤1400

5x1+3x2≤430

x1,x2≥0

18對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第18頁!假設(shè)公司現(xiàn)在另有一筆資金585元，準(zhǔn)備用于投資。當(dāng)然，這筆資金用于購買產(chǎn)品或者增加倉庫空間都可以使公司獲得更多的利潤。問題是應(yīng)該如何合理安排投資，使公司能夠獲得更多的利潤。已知增加1平方米的倉庫空間需要0.8元，因此如果資金用于增加倉庫空間，每投資0.8元可以多獲利1/9元，即每增加1元投資可多獲利5/36=0.14元；而每增加1元用于購買產(chǎn)品，可以多獲利11/45=0.24元。因此應(yīng)該把資金用于購買產(chǎn)品，這樣可以獲得更多的利潤將這585元也用于購買產(chǎn)品，可以增加利潤

585×y1=585×11/45=143元19對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第19頁!20

解：設(shè)y1，y2，y3分別為每工時設(shè)備A、B、C的收費。可以建立以下線性規(guī)劃模型：

化為標(biāo)準(zhǔn)型，利用單純形法進(jìn)行求解。最優(yōu)解Y=(500,0,500,0,0)最優(yōu)值（收費）為70000。

對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第20頁!21原問題對偶問題目標(biāo)函數(shù)

Max

Min

約束條件 ≤ ≥系數(shù)矩陣A AT資源常數(shù) b c目標(biāo)系數(shù) cb2個變量 2個約束

3個約束

3個變量解 檢驗數(shù)檢驗數(shù)解可以看到，這兩個問題關(guān)系密切，用同樣的原始數(shù)據(jù)：對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第21頁!對偶問題的形式22如果線性規(guī)劃問題的變量均具有非負(fù)約束，其約束條件當(dāng)目標(biāo)函數(shù)求極大值時均取“≤”，當(dāng)目標(biāo)函數(shù)求極小值時均取“≥”，則稱具有對稱形式。對稱形式下原問題和對偶問題的形式：（LP）“Max——≤”s.t.（DP）“Min——≥”s.t.對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第22頁!23MaxzMinfx1x2…xnxi≥0y1a11a12…a1n≤b1y2a21a22…a2n≤b2……………≤…ymam1am2…amn≤bmyi≥0c1c2…cn≥≥≥≥對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第23頁!例2：寫出下面線性規(guī)劃的對偶規(guī)劃模

24對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第24頁!寫出對偶問題：

25對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第25頁!把對偶問題和原問題進(jìn)行比較26Maxz=x1+4x2+3x3s.t.2x1+3x2–5x3≤

2原問題3x1–x2+6x3≥1

x1+x2+x3=4x1≥

0，x2≤0，x3沒有非負(fù)限制Minf=2y1+y2

+4y3s.t.2y1+3y2

+y3

≥

1對偶問題3y1–y2

+y3≤4–5y1+6y2+y3=3y1≥0

，y2

≤

0，y3無非負(fù)限制對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第26頁!對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)對對稱形式和非對稱形式都是同樣適用的，但為了方便，在說明或證明時以對稱形式為例（非對稱形式可以化為對稱形式）對稱形式下原(Primal)問題和對偶(Dual)問題如下：

(P)Maxz=CX(D)Minf=YTbs.t.AX≤bs.t.ATY≥CTX≥0Y≥0“Max--≤”“Min--≥”27對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第27頁!

2.（弱對偶定理）若X，Y分別為（P)和（D）的可行解，那么CX≤YTb。

證明：由變量的非負(fù)性限制，可以得到

28對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第28頁!

3.（最優(yōu)性準(zhǔn)則定理）若X’，Y’分別為(P)，(D)的可行解，且CTX’=Y’Tb，則X’，Y’分別為(P)和(D)的最優(yōu)解。

證明：設(shè)X為(P)的可行解，由弱對偶定理可得

CTX≤Y’Tb=CTX’

因此X’為(P)的最優(yōu)解。

設(shè)Y為(D)的可行解，由弱對偶定理可得

YTb≥CTX’=Y’Tb

因此Y’為(D)的最優(yōu)解。

29對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第29頁!對稱形式下原問題和對偶問題的標(biāo)準(zhǔn)形式如下5.（互補(bǔ)松弛定理）若X和Y分別是(P)和(D)的最優(yōu)解（對稱形式的標(biāo)準(zhǔn)型下），則有即約束取等式或?qū)?yīng)的變量為030對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第30頁!對偶問題基本性質(zhì)的應(yīng)用：利用單純形法，求得對偶問題最優(yōu)解X=(1,0,0,2,0)T，最優(yōu)值z*=9。由互補(bǔ)松弛定理，得x1y3=0，x2y4=0，x3y5=0，x4y1=0，x5y2=0，因此有y1=0，y3=0，代入第1個約束得到y(tǒng)2=9，代入其余約束得y4=4，y5=64。對于變量數(shù)量少、約束多的問題，可以利用基本性質(zhì)簡化求解31例4：Minf=5y1+y2s.t.3y1+y2≥9

y1+y2≥5

y1+8y2≥

8y1，y2≥

0Maxz=9x1+5x2

+8x3s.t.3x1+x2

+x3≤

5

x1+x2

+8x3≤

1x1，x2，x3≥0

對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第31頁!影子價格的經(jīng)濟(jì)含義及應(yīng)用：

資源的市場價格是已知的，且相對比較穩(wěn)定，而影子價格有賴于資源的利用情況，是未知數(shù)，隨著企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況的變化而發(fā)生變化。

影子價格是一種邊際價格，說明在資源得到最優(yōu)利用的條件下，增加單位資源量可以增加的收益。

影子價格是對現(xiàn)有資源實現(xiàn)最大效益時的一種估價，實際上是一種機(jī)會成本。企業(yè)可以根據(jù)現(xiàn)有資源的影子價格，考慮經(jīng)營策略：如果影子價格高于市場價格，可考慮買進(jìn)設(shè)備，以擴(kuò)大生產(chǎn)能力，否則不宜買進(jìn)；若某設(shè)備的租費高于影子價格，可考慮出租該設(shè)備，否則不宜出租

32對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第32頁!一般來說，對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當(dāng)估價。這種估價涉及到資源的最有效利用，如在一個大公司內(nèi)部，可借助資源的影子價格確定內(nèi)部結(jié)算價格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。

需要指出的是，影子價格不是固定不變的，當(dāng)約束條件、產(chǎn)品利潤等發(fā)生變化時，有可能使影子價格發(fā)生變化。另外，影子價格說明增加單位資源量可以增加的收益，是指資源在一定范圍內(nèi)增加時的情況，當(dāng)某種資源的增加超過了一定的范圍，總利潤的增加量就不是按照影子價格給出的數(shù)值線性地增加。這將在靈敏度分析中討論

33對偶理論與影子價格共35頁，您現(xiàn)在瀏覽的是第33頁!求解后得到最優(yōu)單純形表如下所示：因此，最優(yōu)方案是分別購進(jìn)兩