對偶理論與影子價格

對偶理論與影子價格第1頁，課件共35頁，創(chuàng)作于2023年2月2對偶問題的提出第2頁，課件共35頁，創(chuàng)作于2023年2月例1：某工廠擁有A、B、C三種類型的設備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設備機時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設備可利用的時數(shù)如下表所示：問題：工廠應如何安排生產(chǎn)可獲得最大的總利潤？

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

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

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

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

約束條件第3頁，課件共35頁，創(chuàng)作于2023年2月4

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

目標函數(shù)

約束條件

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

第4頁，課件共35頁，創(chuàng)作于2023年2月5

解：設y1，y2，y3分別為每工時設備A、B、C的收費?？梢越⒁韵戮€性規(guī)劃模型：

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

第5頁，課件共35頁，創(chuàng)作于2023年2月6原問題對偶問題第6頁，課件共35頁，創(chuàng)作于2023年2月7原問題對偶問題目標函數(shù)

Max

Min

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

3個約束

3個變量解 檢驗數(shù)檢驗數(shù)解可以看到，這兩個問題關系密切，用同樣的原始數(shù)據(jù)：第7頁，課件共35頁，創(chuàng)作于2023年2月線性規(guī)劃有一個有趣的特性，就是對于任何一個求極大的線性規(guī)劃問題都存在一個與其匹配的求極小的線性規(guī)劃問題，并且這一對線性規(guī)劃問題的解之間還存在著密切的關系。線性規(guī)劃的這個特性稱為對偶性。

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

8第8頁，課件共35頁，創(chuàng)作于2023年2月對偶問題的形式9如果線性規(guī)劃問題的變量均具有非負約束，其約束條件當目標函數(shù)求極大值時均取“≤”，當目標函數(shù)求極小值時均取“≥”，則稱具有對稱形式。對稱形式下原問題和對偶問題的形式：（LP）“Max——≤”s.t.（DP）“Min——≥”s.t.第9頁，課件共35頁，創(chuàng)作于2023年2月

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

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

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

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

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

10第10頁，課件共35頁，創(chuàng)作于2023年2月11MaxzMinfx1x2…xnxi≥0y1a11a12…a1n≤b1y2a21a22…a2n≤b2……………≤…ymam1am2…amn≤bmyi≥0c1c2…cn≥≥≥≥第11頁，課件共35頁，創(chuàng)作于2023年2月一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形式的對偶規(guī)劃。

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

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

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

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

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

12第12頁，課件共35頁，創(chuàng)作于2023年2月例2：寫出下面線性規(guī)劃的對偶規(guī)劃模

13第13頁，課件共35頁，創(chuàng)作于2023年2月解：先化為對稱形式（Max—≤）

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

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

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

變量無非負限制，用變量替換，如

14第14頁，課件共35頁，創(chuàng)作于2023年2月寫出對偶問題：

15第15頁，課件共35頁，創(chuàng)作于2023年2月變量替換，令

16第16頁，課件共35頁，創(chuàng)作于2023年2月把對偶問題和原問題進行比較17Maxz=x1+4x2+3x3s.t.2x1+3x2–5x3≤

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

x1+x2+x3=4x1≥

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

+4y3s.t.2y1+3y2

+y3

≥

1對偶問題3y1–y2

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

，y2

≤

0，y3無非負限制第17頁，課件共35頁，創(chuàng)作于2023年2月

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

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

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

yi≥0(≤0，無限制)第18頁，課件共35頁，創(chuàng)作于2023年2月對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)對對稱形式和非對稱形式都是同樣適用的，但為了方便，在說明或證明時以對稱形式為例（非對稱形式可以化為對稱形式）對稱形式下原(Primal)問題和對偶(Dual)問題如下：

(P)Maxz=CX(D)Minf=YTbs.t.AX≤bs.t.ATY≥CTX≥0Y≥0“Max--≤”“Min--≥”19第19頁，課件共35頁，創(chuàng)作于2023年2月1．對稱性。即對偶問題的對偶是原問題。20第20頁，課件共35頁，創(chuàng)作于2023年2月

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

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

21第21頁，課件共35頁，創(chuàng)作于2023年2月弱對偶定理的推論：

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

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

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

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

22第22頁，課件共35頁，創(chuàng)作于2023年2月

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

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

CTX≤Y’Tb=CTX’

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

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

YTb≥CTX’=Y’Tb

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

23第23頁，課件共35頁，創(chuàng)作于2023年2月

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

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

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

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

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

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

24第24頁，課件共35頁，創(chuàng)作于2023年2月對稱形式下原問題和對偶問題的標準形式如下5.（互補松弛定理）若X和Y分別是(P)和(D)的最優(yōu)解（對稱形式的標準型下），則有即約束取等式或?qū)淖兞繛?25第25頁，課件共35頁，創(chuàng)作于2023年2月證明：由弱對偶定理（CX≤YTb）得由主對偶定理可知最優(yōu)值相等，上述不等式取“=”，26第26頁，課件共35頁，創(chuàng)作于2023年2月對偶問題基本性質(zhì)的應用：利用單純形法，求得對偶問題最優(yōu)解X=(1,0,0,2,0)T，最優(yōu)值z*=9。由互補松弛定理，得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ì)簡化求解27例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

第27頁，課件共35頁，創(chuàng)作于2023年2月影子價格影子價格(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個單位對目標z產(chǎn)生的影響，也是在資源最優(yōu)利用條件下對該資源的估價，稱為該資源的影子價格例如，在例1中yi*是對設備租金的估價注意：若B是最優(yōu)基，y*T=CBB-128第28頁，課件共35頁，創(chuàng)作于2023年2月影子價格的經(jīng)濟含義及應用：

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

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

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

29第29頁，課件共35頁，創(chuàng)作于2023年2月由互補松弛定理，可知如果某種資源未得到充分利用時（松弛變量不為0），則其影子價格為0（對應變量為0）；當資源的影子價格不為0，表明該資源在生產(chǎn)中已耗費完畢。

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

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

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

30第30頁，課件共35頁，創(chuàng)作于2023年2月一般來說，對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當估價。這種估價涉及到資源的最有效利用，如在一個大公司內(nèi)部，可借助資源的影子價格確定內(nèi)部結算價格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。

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

31第31頁，課件共35頁，創(chuàng)作于2023年2月影子價格的應用舉例：

例5：某外貿(mào)公司準備購進兩種產(chǎn)品A1，A2。購進產(chǎn)品A1每件需要10元，占用5平方米的空間，賣出1件可獲純利潤3元；購進產(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

32第32頁，課件共35頁，創(chuàng)作于2023年2月求解后得到最優(yōu)單純形表如下所示：因此，最優(yōu)方案是分別購進兩種產(chǎn)品50件和60件，公司的最大利潤為390元。同時，從表中也可以看到，資金的影子價格為11/45，即增加1元用于購買產(chǎn)品，可以多獲利潤11/45元；倉庫的影子價格為1/9，即增加1平方米的倉庫空間，可以多獲利潤1/9元。33CBXBbx1x2x3x44x260011/9-2/93x15010-1/151/3-z-39000-11/45-1/9第33頁，課件共35頁，創(chuàng)作于2023年2月假設公司現(xiàn)在另有一筆資金585元，準備用于投資。當然，這筆資金用于購買產(chǎn)品或者增加倉庫空間都可以使公司獲得更多的利潤。問題是應該如何合理安排投資，使公司能夠