運(yùn)籌學(xué)課件對偶問題的經(jīng)濟(jì)解釋-影子價(jià)格

§5對偶問題的經(jīng)濟(jì)解釋—影子價(jià)格

(P)的最終單純形表中松弛變量的檢驗(yàn)數(shù)對應(yīng)(D)的最優(yōu)解。當(dāng)某約束條件的右端常數(shù)增加一個單位時(shí)（假設(shè)原問題的最優(yōu)基不變），原問題的目標(biāo)函數(shù)最優(yōu)值增加的數(shù)量。Z*=CX*=Y*b=(y1*,y2*,…,ym*)b1b2﹕﹒bm=y1*b1+y2*b2+…+ym*bm當(dāng)某個右端常數(shù)bibi+1時(shí)bi+1yi*+yi*(bi+1)=Y*b+yi*=Z*+yi*第I種資源的影子價(jià)格是第i個約束條件的右端常數(shù)增加一個單位時(shí)，目標(biāo)函數(shù)增加的數(shù)量甲乙可用量機(jī)械設(shè)備

128原材料A4016原材料B

0412

X(3)=(4，2，0，0,4)T，z3=14cj23000CBXBbx1x2x3x4x5203x1x5x2442100001-2?-3/2?-1/81/8010-1400-3/2-1/80經(jīng)濟(jì)意義：在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。影子價(jià)格

產(chǎn)品資源ⅠⅡ現(xiàn)有資源數(shù)鋼材12100（噸）煤22180（噸）機(jī)時(shí)16240（小時(shí)）利潤（萬元）13x1x2x3x4x5-zXB-13500-3/40-1/4x130103/20-1/2x45000-5/211/2x23501-1/401/4X*=(30,35,0,50,0)T,Z*=135y1*=3/4y2*=0,y3*=1/4影子價(jià)格經(jīng)濟(jì)意義：在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。§6對偶單純形法保持對偶可行性，逐步改進(jìn)主可行性，求解主問題。當(dāng)b有負(fù)分量，A中有一明顯初始對偶可行基(檢驗(yàn)數(shù)均非正)，因而易得一初始解時(shí)，可用對偶單純形法求解。

設(shè)B為一個基基本解X（0）為基本可行解的條件？B-1b≥0X（0）為最優(yōu)解的條件？原原始可行性條件原始最優(yōu)性條件令Y=CBB-1，代入原始最優(yōu)性條件，→YA≥C對偶可行性條件例用對偶單純形法求解單純形法大M法剩余變量、人工變量用（-1）乘不等式兩邊，再引入松弛變量。cj

-1-40-300CBXBb

x1

x2

x3

x4

x5

x600x5x6-3-2-1-21-11021-4-1010-1-40-300先選出基變量后選進(jìn)基變量原問題，符合原始最優(yōu)性條件，但不可行cj

-1-40-300CBXBb

x1

x2

x3

x4

x5

x6-10x1x63-812-11-100-3-2-32130-2-1-2-10cj

-1-40-300CBXBb

x1

x2

x3

x4

x5

x6-10x1x63-812-11-100-3-2-32130-2-1-2-10-10x1x37417/205/2-2-1/203/213/2-1-1/270-1/20-1/2-2-1/2最優(yōu)解X*=（7，0，4，0）TZ*=-7例6用對偶單純形法求解（P）1-4/3---10-5/21/21-1/221-1/23/20-1/20-4-10-1-8/5--22/501-1/5-2/51/511/5107/5-1/5-2/500-3/5-8/5-1/5[][]§7靈敏度分析

系數(shù)bi、cj、aij

變化，最優(yōu)解的最優(yōu)性、可行性是否變化？

系數(shù)在什么范圍內(nèi)變化，最優(yōu)解或最優(yōu)性不變？如何求新的最優(yōu)解？本節(jié)重點(diǎn)7.1靈敏度分析的原理是最優(yōu)解，則可行性條件最優(yōu)性條件正則性

bi非基變量cj基變量cB增加新變量一個非基變量系數(shù)aij的變化，要視aij對應(yīng)的變量是基變量或非基變量而定。7.2br變化的分析影響解的可行性，只要B-1(b+△b)≥0，解的可行性不變，最優(yōu)性也不變。

(B-1)r

是B-1的第r列，解上述不等式，求得保持可行性不變的△br的范圍。≥0例:求第一章例1中的第二個約束條件b2（=16）的變化范圍b2時(shí)，計(jì)算可得

b2

-4/0.25=-16

b2

-4/0.5=-8

b2

2/0.125=16所以，b2的變化范圍是[-8，16]；b2的變化范圍是[8，32]。

例:第一章例1中，若設(shè)備增加4臺時(shí)，求新的最優(yōu)生產(chǎn)計(jì)劃。計(jì)算:得表：用對偶單純形法得：

X*=(4，3，2，0，0)，z*=177.3cr

變化的靈敏度分析cr

cr

+cr不影響解的可行性，影響最優(yōu)性。(1)cr

為非基變量的系數(shù)(2)cr

為基變量的系數(shù)例：第一章例1中c2變化c2，問c2在什么范圍內(nèi)變化時(shí)最優(yōu)解不變。解：對所有的非基變量當(dāng)給定c2，要求新的最優(yōu)解時(shí)，先求新的檢驗(yàn)數(shù)，再用單純形法迭代。

解得：

-3

c2

1

7.4

aij變化的靈敏度分析(1).

aij

為非基變量的系數(shù)只影響xj的檢驗(yàn)數(shù)，從而影響最優(yōu)性。

例:第一章例1，增加一種新產(chǎn)品Ⅲ，它的技術(shù)系數(shù)是(2，6，3)T，利潤系數(shù)是5。問該廠是否應(yīng)生產(chǎn)該產(chǎn)品和生產(chǎn)多少？

解：設(shè)新產(chǎn)品Ⅲ的產(chǎn)量為x3(對于原最優(yōu)解來說是非基變量)。因

故應(yīng)生產(chǎn)產(chǎn)品Ⅲ。

x3進(jìn)基在最終表中的系數(shù)是：

原最終表成為：

用單純形法求解得：(2).aij為基變量系數(shù)基變化，影響最優(yōu)性、可行性。例:第一章例1，若生產(chǎn)產(chǎn)品Ⅰ的工藝結(jié)構(gòu)有改進(jìn)，其技術(shù)系數(shù)變?yōu)椋?，5，2)T，利潤系數(shù)為4，試分析對生產(chǎn)計(jì)劃