三1矩陣表示對(duì)偶問(wèn)題理論影子價(jià)格

對(duì)偶理論與靈敏度分析

(DualTheoriesandSensitivityAnalysis)

單純形法的矩陣描述線性規(guī)劃的對(duì)偶問(wèn)題對(duì)偶問(wèn)題的基本性質(zhì)對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋----影子價(jià)格對(duì)偶單純形法靈敏度分析例

單純形法的矩陣描述

(MatricesDescription)XB

x1x2x3x4x5bx11001/404x500-20.514x2010.5-1/802-z

0

0-3/2-1/80-14CB=[203]

CN=[00]

單純形法的矩陣描述BCBXBCNXNNb

單純形法的矩陣描述

單純形法的矩陣描述B-1NB-1b

單純形法的矩陣描述考慮線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型

A

Cmn,R(A)=m

.可行基相應(yīng)于非基變量的系數(shù)矩陣令A(yù)=(BN)X=(XBXN)TC=(CBCN)

單純形法的矩陣描述

矩陣形式的單純形表

XBXBXNbXB

IB-1NB-1b-z0CN-CBB-1N-CBB-1b單純形表中變量xj

的系數(shù)列向量：B-1aj

單純形表中約束方程的右端項(xiàng)：B-1b

單純形表中目標(biāo)函數(shù)值：CBB-1b單純形表中變量xj

的檢驗(yàn)數(shù)：

Cj-CBB-1aj

單純形法的矩陣描述選定主元，做完初等變換以后（相當(dāng)于對(duì)增廣矩陣/線性方程組兩邊同時(shí)左乘了基的逆矩陣B-1）

單純形法的矩陣描述繼續(xù)討論上例XB

x1x2x3x4x5bx11001/404x500-20.514x2010.5-1/802-z

0

0-3/2-1/80-14CB=[203]

CBB-1=[1.51/80]

單純形法的矩陣描述例

用單純形法求解下述線性規(guī)劃問(wèn)題.

解:

把原問(wèn)題化為標(biāo)準(zhǔn)型

單純形法的矩陣描述用單純形法求解如下:

迭代XBx1x2x3x4x5bRx31210084x44001016-x504001123-z

2

30000XBx1x2x3x4x5bRx31010-0.522x440010164x2

01001/43--z

2

000-3/4-9

單純形法的矩陣描述

迭代

迭代

X*=(4,2)T

z*=14XBx1x2x3x4x5bRx11010-0.52-

x400-41284x201001/4312-z

0

0-20

1/4-13XB

x1x2x3x4x5bRx11001/404x500-20.514x2010.5-1/802-z

0

0-3/2-1/80-14

單純形法的矩陣描述線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題

(DualProblems)1.對(duì)偶問(wèn)題的提出

(DualProblem)例1某工廠用兩臺(tái)機(jī)器生產(chǎn)三種產(chǎn)品,有關(guān)數(shù)據(jù)如下表:

如何組織生產(chǎn)，使總利潤(rùn)最大？

甲(m)乙(m)丙(m)

限制條件機(jī)器I111135機(jī)器II147405利潤(rùn)2311/3

x1,x2,x3

------分別生產(chǎn)甲、乙、丙產(chǎn)品的數(shù)量例2若另一工廠想要租賃這兩臺(tái)機(jī)器用于生產(chǎn)產(chǎn)品，那么該工廠應(yīng)該如何確定合理的租金呢？線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題

y1,y2

----機(jī)器I與機(jī)器II的每臺(tái)時(shí)的租金例1與例2是一個(gè)問(wèn)題的兩個(gè)方面兩個(gè)線性規(guī)劃模型是一對(duì)對(duì)偶問(wèn)題線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題2.原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系

對(duì)稱(chēng)性形式

例3求下列問(wèn)題的對(duì)偶問(wèn)題

對(duì)稱(chēng)性形式的對(duì)偶關(guān)系線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題非對(duì)稱(chēng)性形式

練習(xí)：線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題

原(對(duì)偶)問(wèn)題目標(biāo)函數(shù)maxz=CX≥0n個(gè)變量≤0

自由變量≤m個(gè)約束AX

≥b=

對(duì)偶(原)問(wèn)題目標(biāo)函數(shù)minw=YTb≥n個(gè)約束ATY≤CT=≥0m個(gè)變量≤0

自由變量原問(wèn)題與對(duì)偶問(wèn)題對(duì)偶關(guān)系對(duì)照表線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題例4

求下列問(wèn)題的對(duì)偶問(wèn)題線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題例5

求下列問(wèn)題的對(duì)偶問(wèn)題線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題考慮對(duì)稱(chēng)性關(guān)系的對(duì)偶：對(duì)稱(chēng)性對(duì)偶問(wèn)題的基本性質(zhì)(BasicProperties)對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。弱對(duì)偶性若原(對(duì)偶)問(wèn)題有無(wú)界解，則對(duì)偶(原)問(wèn)題無(wú)可行解.無(wú)界性對(duì)偶問(wèn)題的基本性質(zhì)原對(duì)偶原對(duì)偶不可行不可行無(wú)界不可行可行解是最優(yōu)解時(shí)的性質(zhì)對(duì)偶定理若原問(wèn)題有最優(yōu)解，相應(yīng)的最優(yōu)基為B,則對(duì)偶問(wèn)題也有最優(yōu)解，且最優(yōu)解為(CBB-1)T

；并且目標(biāo)函數(shù)值相等，均為CBB-1b.對(duì)偶問(wèn)題的基本性質(zhì)互補(bǔ)松弛性令

原問(wèn)題的可行解，是對(duì)偶問(wèn)題的可行解，則它們分別是原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解的充要條件是:原問(wèn)題和對(duì)偶問(wèn)題的基解的對(duì)應(yīng)關(guān)系對(duì)偶問(wèn)題的基本性質(zhì)基變量XB非基變量XN檢驗(yàn)數(shù)（原問(wèn)題）0CN-CBB-1N對(duì)偶問(wèn)題的基解-YN-YB例6

已知用單純形法求解下述線性規(guī)劃問(wèn)題所得最終表如下，試確定該問(wèn)題的對(duì)偶問(wèn)題的最優(yōu)解.

對(duì)偶問(wèn)題的基本性質(zhì)解:

由已知得CB=(203),因此，由對(duì)偶定理可得所求問(wèn)題的對(duì)偶問(wèn)題的最優(yōu)解為：XB

x1x2x3x4x5bRx11001/404x500-20.514x2010.5-1/802-z

0

0-3/2-1/80-14其中

x3,x4,x5

為松弛變量。(Y*)Tb=?對(duì)偶問(wèn)題的基本性質(zhì)例7

已知線性規(guī)劃問(wèn)題且其最優(yōu)解為x*1=2,x*2=0,x*3=8.試用對(duì)偶問(wèn)題的性質(zhì)求其對(duì)偶問(wèn)題的最優(yōu)解。對(duì)偶問(wèn)題的基本性質(zhì)解:

將x*1=2,x*2=0,x*3=8代入原線性規(guī)劃問(wèn)題的約束條件中，可知第一個(gè)約束條件為嚴(yán)格不等式，則由互補(bǔ)松弛性得y*1=0.

對(duì)偶問(wèn)題的基本性質(zhì)

又因

x*1

x*3>0，所以對(duì)偶問(wèn)題的第一個(gè)約束條件以及第三個(gè)約束條件均應(yīng)取等式，即8y*1+4y*2+2y*3=60，y*1+1.5y*2+0.5y*3=20.解之得

y*2=10,y*3=10.

因此，對(duì)偶問(wèn)題的最優(yōu)解為

y*1=0,y*2=10,y*3=10.線性規(guī)劃對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋

-----影子價(jià)格

(ShadowPrices)設(shè)與分別是原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解，則由對(duì)偶問(wèn)題的基本性質(zhì)有由此，

變量的經(jīng)濟(jì)意義是：在其他條件不變的情況下，第i種資源的單位改變量所引起的目標(biāo)函數(shù)值的增加量。1影子價(jià)格的解釋

變量的值代表對(duì)第

i種資源的估價(jià)。這種估價(jià)不是資源i

的市場(chǎng)價(jià)格，而是具體工廠根據(jù)資源在生產(chǎn)中做出的貢獻(xiàn)而作的估價(jià)，稱(chēng)它為“影子價(jià)格”。

影子價(jià)格是對(duì)偶解的一個(gè)十分形象的名稱(chēng)，它既表明了對(duì)偶解是對(duì)系統(tǒng)內(nèi)部資源的一種客觀估價(jià)，又表明它是一種虛擬的價(jià)格，而不是真實(shí)的價(jià)格。線性規(guī)劃對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋-影子價(jià)格例某工廠用三臺(tái)機(jī)器生產(chǎn)兩種產(chǎn)品,有關(guān)數(shù)據(jù)如下表:

如何組織生產(chǎn)，使總利潤(rùn)最大？

甲(m)乙(m)可供資源(臺(tái)時(shí))

機(jī)器I1