對偶理論及其應(yīng)用

第三章

線性規(guī)劃的對偶理論及其應(yīng)用書山有路勤為徑，學(xué)海無涯苦作舟對偶是一種普遍現(xiàn)象1假設(shè)工廠考慮不進(jìn)行生產(chǎn)而把全部可利用的資源都讓給其他企業(yè)，工廠希望給這些資源定出一個合理的價格，即使別的單位愿意購買，又使本工廠能得到生產(chǎn)這些產(chǎn)品所能獲得的最大收益。第一節(jié)對偶問題一、對偶問題的提出實例1（典型示例）：

3

2利潤

12公斤

4

0原料B

16公斤

0

4原料A

8臺時

2

1設(shè)備資源限量

II

I產(chǎn)品y3y2y1決策變量12168資源限量x23402IIx12041I決策變量每臺收益原料B原料A設(shè)備資源產(chǎn)品2y3y2y1決策變量12168資源限量x23402IIx12041I決策變量每臺收益原料B原料A設(shè)備資源產(chǎn)品3y4y3y2y1200300400600限額x330004322Cx240002314Bx120001123A每臺收益丁丙乙甲材料產(chǎn)品假設(shè)工廠考慮不進(jìn)行生產(chǎn)而把全部可利用的資源都讓給其他企業(yè)，工廠希望給這些資源定出一個合理的價格，即使別的單位愿意購買，又使本工廠能得到生產(chǎn)這些產(chǎn)品所能獲得的最大收益。實例2：4比較上述模型，可以得出兩者之間的一些關(guān)系：

1.兩個問題，一個是極大化，另一個是極小化；

2.一個問題的變量數(shù)等于另一問題的方程數(shù)，反之亦然；

3.一個問題的目標(biāo)函數(shù)系數(shù)是另一個問題的約束方程右端常數(shù)，反之亦然；

4.兩個問題的約束方程系數(shù)矩陣互為轉(zhuǎn)置。稱變量yi為第一個LP的第i個對偶變量，或第一個LP的第i約束相應(yīng)的對偶變量5

對偶問題的提出有其理論依據(jù)，可由“單純形法的矩陣描述”加以解釋。

67二、對稱LP問題1.對稱形式的定義必須滿足下列條件：

（1）變量為非負(fù)；（2）約束條件為不等式。對于max，約束為“￡”；對于min，約束為“3”。第一類對稱形式第二類對稱形式82.對稱LP問題的對偶問題9例3：寫出下列LP問題的對偶問題對偶對偶變量y1y2y3原變量x1x210推導(dǎo)過程變形對偶3.對偶問題的對偶11對偶變形結(jié)論：對偶問題的對偶是原問題。12例4：寫出下列LP問題的對偶問題解:上述LP問題的對偶問題為：對偶變量y1y2y3原變量x1x2x313例5：寫出下列LP問題的對偶問題4.非對稱LP問題的對偶問題141516對偶關(guān)系：一個問題第i個變量決定另一問題第i個約束，反之亦然。對稱的對應(yīng)對稱的，非對稱的對應(yīng)非對稱的17直接寫出例5的LP問題的對偶問題1819已知LP問題：1)寫出其對偶模型；2)如果用大M法求解原問題，請列出初始單純形表，并用[]標(biāo)出主元素。補充作業(yè)3-1

20第二節(jié)LP問題的對偶理論定理1弱對偶定理:極大化原問題目標(biāo)函數(shù)值總是不大于其對偶問題的目標(biāo)函數(shù)值。21結(jié)論：在雙方都是可行解的情況下，極大化問題的目標(biāo)函數(shù)值總不大于其對偶問題目標(biāo)函數(shù)值。22推論1：

若LP問題有無界解，則其對偶問題無可行解；若LP問題無可行解，則對偶問題或無解或為無界解。推論2：

極大化問題的任何一個可行解所對應(yīng)的目標(biāo)函數(shù)值都是其對偶問題的目標(biāo)函數(shù)值的下界。

極小化問題的任何一個可行解所對應(yīng)的目標(biāo)函數(shù)值都是其對偶問題的目標(biāo)函數(shù)值的上界。推論3：23例6

考慮下面一對LP問題其對偶問題為：24證明：定理2最優(yōu)性準(zhǔn)則

當(dāng)LP問題目標(biāo)函數(shù)值與其對偶問題目標(biāo)函數(shù)值相等時，各自的可行解即為最優(yōu)解。若X(0),Y(0)分別為PP，DP的可行解,且CTX(0)＝bTY(0)

，則X(0),Y(0)分別為PP，DP的最優(yōu)解。25例726補充作業(yè)3-2

27證明：定理3強(qiáng)對偶定理

若PP，DP均有可行解，則PP，DP均有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等。282930補充作業(yè)3-3

31證明：以PP是max為例。當(dāng)PP為max，則PP的檢驗數(shù)與DP的解之間僅差一個負(fù)號；當(dāng)PP為min，則PP的檢驗數(shù)與DP的解完全相同。推論：用單純形求解LP問題時，PP的檢驗數(shù)對應(yīng)DP的一個解（最優(yōu)時為基可行解，其余為基解）。

323334當(dāng)PP為max，在用單純形法求解LP問題PP的最優(yōu)單純形表中松弛變量的檢驗數(shù)的相反數(shù)就是其DP的最優(yōu)解；YTS10XB－YTS2CN－CBB－1

NXN－CBB－1PP的檢驗數(shù)－YTDP的解XSPP的變量PP檢驗數(shù)與DP解的對應(yīng)關(guān)系表當(dāng)PP為min，在用單純形法求解LP問題PP的最優(yōu)單純形表中松弛變量的檢驗數(shù)就是其DP的最優(yōu)解。35解：化為標(biāo)準(zhǔn)型例8求下列問題對偶問題的最優(yōu)解36

X(0)＝(0,0,8,16,12)T以[1]為主元素進(jìn)行旋轉(zhuǎn)運算，x1為換入變量，x3為換出變量

0

qi

3

0

0

x5

x2

x3

x40

x4

x3XB

b

sj

0

x1CB

2cj

x1

cj

x2

x3

x4

x5

1

4

0

2

0

4

1

0

0

0

1

0

0

0

1

2

3

0

0

0

b816

12

XB

x3

x4

x5

CB

0

0

0以[4]為主元素進(jìn)行旋轉(zhuǎn)運算，x2為換入變量，x5為換出變量

sj

2

3

0

0

0

qi

8/2

—

12/4[4]

x2

3

0

0

0

1/43

1

4

0

1

016

0

0

1

1

0

-1/22X(1)＝(0,3,2,16,0)T

2

0

0

-3/4

016/4

2/1

—

[1]Y(0)＝(0,0,0,-2,-3)TY(1)＝(0,0,3/4,-2,0)T37此時達(dá)到最優(yōu)解。X*=(4,2),maxZ=14。

0

qi

3

0

0

x5

x2

x3

x40

x4

x23

XB

b

sj

x1CB

2cj

0

qi

3

0

0

x5

x2

x3

x4x23

x1XB

b

sj

2

x1CB

2cj

0

0

0

1/43

10

-2

0

1/4

0

x1

2

0

1

1

0

-1/22

[2]

0-4

128

08/2

12

—

x50

0

-2

1/2

14

0

1

0

1/4

04

0

1/2

-1/8

0

02

10

-3/2

-1/8

0

0X(3)＝(4,2,0,0,4)TX(2)＝(2,3,0,8,0)T以[2]為主元素進(jìn)行旋轉(zhuǎn)運算，x5為換入變量，x4為換出變量Y(2)＝(2,0,-1/4,0,0)TY(3)＝(3/2,1/8,0,0,0)T38重要提示：

由上述實例可以看出：在用單純形法求解LP問題時，PP沒有得到最優(yōu)解之前，每迭代一步得到一個基可行解，此時DP得到的是一個基解；而當(dāng)PP得到最優(yōu)解時，DP才得到一個基可行解。根據(jù)強(qiáng)對偶定理，DP得到的這個基可行解一定是DP的最優(yōu)解。39定理4互補松弛定理在最優(yōu)情況下，PP的第i個決策變量與其DP的第i個約束中的松弛變量的乘積恒為零。反之亦然。

(2)(1)(3)(4)設(shè)X(0),Y(0)分別為PP,DP的可行解，則X(0),Y(0)分別為PP,DP的最優(yōu)解的充要條件為,有40例9考慮下面問題41解:則，42已知LP原問題為：已知原問題用兩階段法求得最優(yōu)單純形表如下，試用對偶理論寫出其對偶問題的最優(yōu)解。-230-50

0

-33

0

0

x5

x2

x3

x4-1/3001100002/3-13-214/31-15

x1

x2-33

x4

XBb0sj

030

x1CB

-15cj補充作業(yè)3-4

43第三節(jié)對偶問題的經(jīng)濟(jì)學(xué)解釋——影子價格標(biāo)準(zhǔn)化一、對偶最優(yōu)解的經(jīng)濟(jì)解釋：資源的影子價格441、y*i的數(shù)學(xué)含義45

0

qi

3

0

0

x5

x2

x3

x40x5x23

x1XB

b

sj

2

x1CB

2cj

0

-2

1/2

14

0

1

0

1/4

04

0

1/2

-1/8

0

02

10

-3/2

-1/8

0

0標(biāo)準(zhǔn)化46

做目標(biāo)函數(shù)2x1+3x2的等值線，與陰影部分的邊界相交于Q(4,2)點，表明最優(yōu)生產(chǎn)計劃為：生產(chǎn)I產(chǎn)品4件，生產(chǎn)II產(chǎn)品2件。Q(4,2)x1x24x1=164x2=12x1+2x2=844083Z=14Q(4.25,1.875)Z=14.125Q(4,2.5)Z=15.5Q(4,2)Z=1447

(1)對偶問題的最優(yōu)解——買主的最低出價。

(2)原問題資源的影子價格——當(dāng)該資源增加1單位時引起的總收入的增量——賣主的內(nèi)控價格。

(3)代表在資源最優(yōu)利用條件下對單位第i種資源的估價，這種估價不是資源的市場價格，而是根據(jù)資源在最優(yōu)生產(chǎn)配置中作出的貢獻(xiàn)而作的估價，為區(qū)別起見，稱為影子價格（shadowprice)。資源影子價格≠資源市場價格資源的市場價格是已知數(shù)，相對比較穩(wěn)定，而它的影子價格則有賴于資源的利用情況，是未知數(shù)。由于企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價格也隨之改變。即：市場價格由市場確定；影子價格由生產(chǎn)企業(yè)確定。2、y*i的經(jīng)濟(jì)學(xué)含義48(4)影子價格反映了資源的稀缺性，影子價格越高，則越稀缺。(5)影子價格是一種邊際價格。(6)資源的影子價格實際上又是一種機(jī)會成本。在完全市場經(jīng)濟(jì)條件下,當(dāng)：資源的市場價格<影子價格，應(yīng)買進(jìn)這種資源資源的市場價格>影子價格，應(yīng)賣出這種資源隨著資源的買進(jìn)賣出，它的影子價格也將隨之發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。493、影子價格在企業(yè)管理中的作用

(1)告訴管理者增加何種資源對企業(yè)更有利；

(2)告訴管理者花多大代價購買進(jìn)資源或賣出資源是合適的；

(3)為新產(chǎn)品定價提供依據(jù)。50二、對偶約束的經(jīng)濟(jì)解釋——產(chǎn)品的機(jī)會成本機(jī)會(隱含)成本：表示減少一件第j種產(chǎn)品生產(chǎn)所節(jié)省的資源量可以增加的利潤或產(chǎn)值。51三、對偶松弛變量的經(jīng)濟(jì)解釋——產(chǎn)品的差額成本機(jī)會成本差額成本=機(jī)會成本－利潤或產(chǎn)值差額成本利潤或產(chǎn)值52從對偶松弛變量ym+j看：

差額成本(ym+j)=機(jī)會成本－利潤或產(chǎn)值從檢驗數(shù)σj看：第j種產(chǎn)品的相對價值系數(shù)(σj)=利潤或產(chǎn)值－機(jī)會成本

當(dāng)產(chǎn)品利潤或產(chǎn)值>=機(jī)會(隱含)成本，可生產(chǎn)該產(chǎn)品；否則，不安排生產(chǎn)。——檢驗數(shù)的經(jīng)濟(jì)意義。53這表明在利潤最大化的生產(chǎn)計劃中，如果某種資源bi未得到充分利用時，該種資源的影子價格為零；又當(dāng)資源的影子價格不為零時，表明該種資源在生產(chǎn)中已耗費完畢，反映了資源的稀缺性。由此總結(jié)：

(1)影子價格大于0的資源沒有剩余；

(2)有剩余的資源影子價格等于0；

(3)安排生產(chǎn)的產(chǎn)品機(jī)會成本等于利潤；

(4)機(jī)會成本大于利潤的產(chǎn)品不安排生產(chǎn)。四、互補松弛定理的經(jīng)濟(jì)解釋54對偶典型示例分析：X*＝(4,2,0,0,4)TY*＝(3/2,1/8,0,0,0)T55第四節(jié)對偶單純形法一、基本思想

由單純形法的原理可知：在用單純形法求解LP問題時，PP沒有得到最優(yōu)解之前，每迭代一步得到一個基可行解，此時DP得到的是一個基解；而當(dāng)PP得到最優(yōu)解時，DP才得到一個基可行解。根據(jù)強(qiáng)對偶定理，DP得到的這個基可行解一定是DP的最優(yōu)解。

根據(jù)對偶問題的對稱性，也可始終保持DP為基可行解，PP從基解開始迭代，當(dāng)PP得到基可行解時，表明PP和DP都得到最優(yōu)解。56

為了始終保持DP為基可行解，對于最大化的PP問題，其檢驗數(shù)必須保持非正；對于最小化的PP問題，其檢驗數(shù)必須保持非負(fù)。

由于PP可以從基解開始迭代，因此PP約束條件的右端常數(shù)項可以為非正。57二、步驟(以最大化為例):58建初始表

結(jié)束選出換出和換入變量進(jìn)行運算YN59例11用對偶單純形法求解下列LP問題解：原問題變形為6001021180000101-10-201000-11-1-40b-3-2-1

0

1

1

1

2

0

4

0

0

0

0

1

0

1

-1

0

-2

0

-1

0

0

0

1

-1

1

4-1

b

-3

-2

-10-1-2-3000

40-3-2-1006121130000000-10-1102-2-10-100016-1b-3-2-1

1000-5-10-3注意：對偶單純形法不可理解成是求解對偶問題的單純形法，而是根據(jù)對偶理論，允許原問題從初始非可行基開始迭代求解原問題的單純形法。62三、幾個問題的討論63第五節(jié)靈敏度分析

模型中的參數(shù)A﹑b﹑C一般是預(yù)測估計的確定值，而在計劃實施時，這些值一般不可能正好是事先估計的值，因此有必要在求解后，分析這些參數(shù)值在將來可能變化后對最優(yōu)性的影響。靈敏度分析就是計算為保持原最優(yōu)性質(zhì)不變，模型中某一個參數(shù)（Cj或bi或aij）單獨變化的允許范圍。

一、定義64二、靈敏度分析常用的兩個公式最優(yōu)性(最優(yōu)基)不變的條件：

1.可行條件：XB

≥02.最優(yōu)條件：sj≤0（max）

靈敏度分析就是求出在上述兩個最優(yōu)條件仍成立的情況下，參數(shù)bi﹑cj﹑aij的變化范圍。這需要將上述兩式寫成含有參數(shù)的表達(dá)式。65三、靈敏度分析的幾種結(jié)果可行條件：XB=B-1b≥0。當(dāng)bi發(fā)生變化時，只影響可行性。用XB=B-1b≥0求出bi的變化量，此時最優(yōu)基不變（XB中的基變量名稱沒有變，但數(shù)值一般會改變）。

最優(yōu)條件：sj≤0。當(dāng)cj發(fā)生變化時，只影響最優(yōu)性，用

sj≤0(sj=cj-∑ciaij=cj-CBPj’

)求出cj的變化量，此時只是Z值會改變，而最優(yōu)解不變（最優(yōu)基和基變量值均不變）。1.最優(yōu)基不變，最優(yōu)解保持不變，最優(yōu)目標(biāo)值可能改變。2.最優(yōu)基不變，最優(yōu)解改變，最優(yōu)目標(biāo)值改變。3.最優(yōu)基改變，最優(yōu)解改變，最優(yōu)目標(biāo)值改變。66最優(yōu)基不變，最優(yōu)解有可能變化，不需處理可行解可行解最優(yōu)基改變，用單純形法繼續(xù)迭代求最優(yōu)非可行解可行解非可行解可行解DP最優(yōu)基改變，引進(jìn)人工變量，編制新單純形表，求最優(yōu)最優(yōu)基改變，用對偶單純形法繼續(xù)迭代求最優(yōu)結(jié)果及處理方法非可行解非可行解PP靈敏度分析的幾種結(jié)果及相應(yīng)處理方法67四、常數(shù)項bi改變的靈敏度分析68其單純形表如下所示6910.5-2004x50000x50-0.1250.5102x23-0.1250.25x40-1.500-140014x12x3x2x1bXBCB032cj0100416x40010x50004012x5000x40032

1218x30x3x2x1bXBCB032cj初始單純形表707172730010x6000223130x60001x5012583150x7071x4700x70154648120x50x3x2x1bxBCB154

cj例

13:初始單純形表74-52/15-13/158/15-1/15x600-1/1512/34/308x47-1/15-4/152/15x50105/313/3092x7000x4700x70-19/3-17/302/31/3114x14x3x2x1bxBcB154

cj7576771-12102x23-33x40-1-1x50-300-8

-1011x12x3x2x1bxBcB132

cj78791-12102x23-1-1x50-33x40-300-1011x12x3x2x1bXBCB132

cj例4:下面是一張LP問題的最優(yōu)單純形表,觀察其基變量、非基變量目標(biāo)函數(shù)系數(shù)的改變對檢驗數(shù)的影響五、C的改變8081即，821-12102x23-1-1x50-33x40-300-1011x12x3x2x1bXBCB132

cj83典型示例最優(yōu)解及靈敏度分析目標(biāo)函數(shù)最優(yōu)值為:14

變量最優(yōu)解相差值

x140x220

約束松弛/剩余變量對偶價格

101.520.125340

目標(biāo)函數(shù)系數(shù)范圍:

變量下限當(dāng)前值上限

x11.52無上限

x2034

常數(shù)項數(shù)范圍:

約束下限當(dāng)前值上限

148102816323812無上限84要求xj=0六、A的變化85若xj

是非基變量若xj

是基變量86871-12102x23-1-1x500-33x4000-300-8

-1011x12x3x2x1bxBcB132

cj01-12102x23-1-1-1x513-200-1x60-33x400x6-300-8

-1011x12x3x2x1bxBcBx6881020101x23010x50-1-32001x50-60x40-1-1x60-100-7

1012x12x3x2x1bxBcB132

cj891-12102x23-1-1x50-3-300-8

3x4