運(yùn)籌學(xué)之對(duì)偶問題

第四章線性規(guī)劃的對(duì)偶理論4.1對(duì)偶問題4.2對(duì)偶問題的基本性質(zhì)4.3對(duì)偶問題的解4.4影子價(jià)格4.5對(duì)偶單純形法2/4/202314.1對(duì)偶問題(1)對(duì)偶問題的提出對(duì)偶理論是線性規(guī)劃中最重要的理論之一，是深入了解線性規(guī)劃問題結(jié)構(gòu)的重要理論基礎(chǔ)。同時(shí)，由于問題提出本身所具有的經(jīng)濟(jì)意義，使得它成為對(duì)線性規(guī)劃問題系統(tǒng)進(jìn)行經(jīng)濟(jì)分析和敏感性分析的重要工具。那么，對(duì)偶問題是怎樣提出的，為什么會(huì)產(chǎn)生這樣一種問題呢？2/4/20232引例——倆家具制造商間的對(duì)話：唉!我想租您的木工和油漆工一用。咋樣？價(jià)格嘛……好說，肯定不會(huì)讓您兄弟吃虧。

王老板做家具賺了大錢，可惜我老李有高科技產(chǎn)品，卻苦于沒有足夠的木工和油漆工咋辦？只有租咯。Hi：王老板，聽說近來家具生意好慘了，也幫幫兄弟我哦!家具生意還真賺錢，但是現(xiàn)在的手機(jī)生意這么好，不如干脆把我的木工和油漆工租給他，又能收租金又可做生意。價(jià)格嘛……好商量，好商量。只是…...

王老板李老板2/4/20233王老板的家具生產(chǎn)模型：x1、

x2是桌、椅生產(chǎn)量。Z是家具銷售總收入（總利潤）。maxZ=50x1+30x2s.t.4x1+3x2

≤120（木工）

2x1+x2

≤50（油漆工）

x1，x2

≥0原始線性規(guī)劃問題，記為（P）王老板的資源出租模型：y1、y2單位木、漆工出租價(jià)格。W是資源出租租金總收入。minW=120y1+50y2s.t.4y1+2y2

≥503y1+y2

≥30y1，y2

≥0對(duì)偶線性規(guī)劃問題，記為（D）所得不得低于生產(chǎn)的獲利要使對(duì)方能夠接受兩個(gè)原則2/4/20234王老板按（D）的解y1、y2出租其擁有的木、漆工資源，既保證了自己不吃虧（出租資源的租金收入并不低于自己生產(chǎn)時(shí)的銷售收入），又使得出租價(jià)格對(duì)李老板有極大的吸引力（李老板所付出的總租金W最少）。按時(shí)下最流行的一個(gè)詞，叫什么來著————2/4/20235Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目標(biāo)函數(shù)約束條件設(shè)三種資源的使用單價(jià)分別為y1,y2,y3y1y2y3生產(chǎn)單位產(chǎn)品A的資源消耗所得不少于單位產(chǎn)品A的獲利生產(chǎn)單位產(chǎn)品B的資源消耗所得不少于單位產(chǎn)品B的獲利y1+3y240

2y1+2y2+2y350例12/4/20236通過使用所有資源對(duì)外加工所獲得的收益W=30y1+60y2+24y3根據(jù)原則2，對(duì)方能夠接受的價(jià)格顯然是越低越好，因此此問題可歸結(jié)為以下數(shù)學(xué)模型：Min

W=30y1+60y2+24y3y1+3y2402y1+2y2+2y350y1,y2,y30s.t目標(biāo)函數(shù)約束條件原線性規(guī)劃問題稱為原問題，此問題為對(duì)偶問題，y1,y2,y3為對(duì)偶變量，也稱為影子價(jià)格2/4/20237(2)對(duì)偶問題的形式定義設(shè)原線性規(guī)劃問題為則稱下列線性規(guī)劃問題為其對(duì)偶問題，其中yi

(i=1,2,…,m)稱為對(duì)偶變量。上述對(duì)偶問題稱為對(duì)稱型對(duì)偶問題。原問題簡記為(P)，對(duì)偶問題簡記為(D)2/4/20238原始問題MaxZ=CXs.t.AX≤b X≥0bAC≤Maxnm對(duì)偶問題MinW=Ybs.t. YAT≥C Y≥0≥MinCTATbTnm2/4/20239例2：求線性規(guī)劃問題的對(duì)偶規(guī)劃解：由原問題的結(jié)構(gòu)可知為對(duì)稱型對(duì)偶問題2/4/202310例3：求線性規(guī)劃問題的對(duì)偶規(guī)劃解：由原問題的結(jié)構(gòu)可知不是對(duì)稱型對(duì)偶問題，可先化為對(duì)稱型，再求其對(duì)偶規(guī)劃。2/4/202311例4：求線性規(guī)劃問題的對(duì)偶規(guī)劃解：由原問題的結(jié)構(gòu)可知不是對(duì)稱型對(duì)偶問題，可先化為對(duì)稱型，再求其對(duì)偶規(guī)劃。2/4/202312上式已為對(duì)稱型對(duì)偶問題，故可寫出它的對(duì)偶規(guī)劃令則上式化為2/4/202313對(duì)偶關(guān)系對(duì)應(yīng)表原問題對(duì)偶問題目標(biāo)函數(shù)類型MaxMin目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù)右邊項(xiàng)系數(shù)與右邊項(xiàng)的對(duì)應(yīng)關(guān)系右邊項(xiàng)系數(shù)目標(biāo)函數(shù)系數(shù)變量數(shù)與約束數(shù)變量數(shù)n約束數(shù)n的對(duì)應(yīng)關(guān)系約束數(shù)m變量數(shù)m原問題變量類型與

0

對(duì)偶問題約束類型變量

0約束

的對(duì)應(yīng)關(guān)系無限制＝原問題約束類型與

0對(duì)偶問題變量類型約束

變量

0的對(duì)應(yīng)關(guān)系

＝無限制2/4/2023144.2對(duì)偶問題的基本性質(zhì)對(duì)偶的定義對(duì)偶的定義2/4/2023152/4/202316定理4(主對(duì)偶定理)若一對(duì)對(duì)偶問題(P)和(D)都有可行解，則它們都有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值必相等。證明：(1)當(dāng)X*和Y*為原問題和對(duì)偶問題的一個(gè)可行解有原問題目標(biāo)函數(shù)值對(duì)偶問題目標(biāo)函數(shù)值所以原問題的目標(biāo)函數(shù)值有上界，即可找到有限最優(yōu)解；對(duì)偶問題有下界，也存在有限最優(yōu)解。2/4/202317(2)當(dāng)X*為原問題的一個(gè)最優(yōu)解，B為相應(yīng)的最優(yōu)基,通過引入松弛變量Xs,將問題(P)轉(zhuǎn)化為標(biāo)準(zhǔn)型令令所以Y*是對(duì)偶問題的可行解，對(duì)偶問題的目標(biāo)函數(shù)值為X*是原問題的最優(yōu)解，原問題的目標(biāo)函數(shù)值為2/4/202318推論：若一對(duì)對(duì)偶問題中的任意一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等。一對(duì)對(duì)偶問題的關(guān)系，有且僅有下列三種：都有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等；兩個(gè)都無可行解；一個(gè)問題無界，則另一問題無可行解。2/4/202319證:(必要性）原問題對(duì)偶問題2/4/202320MaxZ=CXs.t. AX+XS=b X,XS≥0MinW=Ybs.t.ATY-YS=C W,WS

≥0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始問題和對(duì)偶問題變量、松弛變量的維數(shù)2/4/202321

y1

yi

ymym+1

ym+j

yn+m

x1

xj

xnxn+1

xn+i

xn+m

對(duì)偶問題的變量對(duì)偶問題的松弛變量原始問題的變量原始問題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于02/4/2023224.3對(duì)偶問題的解CCBCN0解基系數(shù)基變量XBXNXsCBXBIB-1NB-1B-1bσ0CN-CBB-1N

-CBB-1CBB-1b令設(shè)原問題為為原問題的一最優(yōu)解則為對(duì)偶問題的一最優(yōu)解2/4/202323例1MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.ty1y2y3MinW=30y1+60y2+24y3

y1+3y2+0y3

402y1+2y2+2y3

50

y1,y2,y30s.tMaxW’=-30y1-60y2-24y3

y1+3y2+0y3–y4

=402y1+2y2+2y3

–y5

=50y1,y2,y3,y4,y50s.t2/4/202324MaxW’=-30y1-60y2-24y3+0(y4+

y5)-M(y6+

y7)

y1+3y2+0y3–y4+

y6

=402y1+2y2+2y3

–y5

+

y7

=50y1,y2,y3,y4,y50s.tcj-30-60-2400-M-MB-1bθcByBy1y2y3y4y5y6y7-My6130-10104040/3-My72220-1015050/2σj3M-305M-602M-24-M-M00-90M2/4/202325cj-30-60-2400-M-MB-1bθcByBy1y2y3y4y5y6y7-60y21/310-1/301/3040/3-My74/3022/3-1-2/3170/335/3σj4M/3-1002M-242M/3+20-M-5M/3+200800-70M/3-60y21/310-1/301/3040/340-24y32/3011/3-1/2-1/31/235/335/2σj600-12-12-M+12-M+12-1080-60y201-1/2-1/21/41/2-1/415/2-30y1103/21/2-3/4-1/23/435/2σj00-9-15-15/2-M+30-M-15/2-9752/4/202326例1、MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t

X1+2X2+X3=303X1+2X2+X4=602X2+X5=24

X1–X50s.tcj4050000B-1bcBxBx1x2x3x4x540x1101/2-1/20150x5003/2-1/21950x201-3/41/4015/2σj00-35/2-15/209752/4/2023272/4/2023282/4/2023292/4/2023302/4/202331例3解：2/4/202332cj23-5-M0-MB-1bθcBxBx1x2x3x4x5x6-Mx411110077-Mx62-510-11105σj3M+2-4M+32M-50M0-17M-Mx407/21/211/2-1/224/72x11-5/21/20-1/21/25σj07M/2+8M/2-60M/2+1-3M/2-110-2M3x2011/72/71/7-1/74/72x1106/75/7-1/71/745/7σj00-50/7-M-16/7-1/7-M+1/7102/72/4/202333(P)2/4/2023342/4/202335單位產(chǎn)品消耗的資源(噸/件))4.4影子價(jià)格(1)原始問題是利潤最大化的生產(chǎn)計(jì)劃問題總利潤(元)產(chǎn)品產(chǎn)量(件)單位產(chǎn)品的利潤(元/件)消耗的資源(噸)剩余的資源(噸)資源限量(噸)2/4/202336(2)對(duì)偶問題對(duì)偶問題是資源定價(jià)問題，對(duì)偶問題的最優(yōu)解y1、y2、...、ym稱為m種資源的影子價(jià)格（ShadowPrice）原始和對(duì)偶問題都取得最優(yōu)解時(shí)，最大利潤Maxz=Minw總利潤(元)資源限量(噸)資源價(jià)格(元/噸)2/4/202337(3)資源影子價(jià)格的性質(zhì)影子價(jià)格越大，說明這種資源越是相對(duì)緊缺影子價(jià)格越小，說明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于02/4/2023380X2X1X=(15,7.5)Z=975X=(15.5,7.25)

Z=982.5X=(14.5,8.25)

Z=992.52/4/202339y1y2ym(4)產(chǎn)品的機(jī)會(huì)成本機(jī)會(huì)成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤增加單位資源可以增加的利潤減少一件產(chǎn)品可以節(jié)省的資源2/4/202340機(jī)會(huì)成本利潤差額成本(5)產(chǎn)品的差額成本（ReducedCost）差額成本=機(jī)會(huì)成本-利潤2/4/202341(6)互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋在利潤最大化的生產(chǎn)計(jì)劃中（1）邊際利潤大于0的資源沒有剩余（2）有剩余的資源邊際利潤等于0（3）安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本等于利潤（4）機(jī)會(huì)成本大于利潤的產(chǎn)品不安排生產(chǎn)2/4/2023424.5對(duì)偶單純形法定義：設(shè)A=(BN)，其中B是一個(gè)非奇異的m×m階方陣，對(duì)應(yīng)地C=(CBCN)，則YB=CB的解Y*=CBB-1稱為對(duì)偶問題(D)的一個(gè)基本解；若Y*還滿足Y*N≧CN，則稱Y*為(D)的一個(gè)基可行解；若有Y*N>CN，則稱Y*為非退化的基可行解，否則稱為退化的基可行解。(1)對(duì)偶單純形法的基本原理定義：如果原問題(P)的一個(gè)基本解X與對(duì)偶問題(D)的基可行解Y對(duì)應(yīng)的檢驗(yàn)數(shù)向量滿足條件則稱X為原問題(P)的一個(gè)正則解。原問題(P)的正則解X與對(duì)偶問題(D)的基可行解Y一一對(duì)應(yīng)原問題(P)的基本解X與對(duì)偶問題(D)的基本解Y一一對(duì)應(yīng)原問題(P)的最優(yōu)解X*與對(duì)偶問題(D)的最優(yōu)解Y*一一對(duì)應(yīng)2/4/202343原問題解空間對(duì)偶問題解空間可行解可行解基本解基本解正則解正則解基可行解基可行解最優(yōu)解2/4/202344對(duì)偶單純形法的基本思想從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行(正則解)，但它對(duì)應(yīng)著一個(gè)對(duì)偶基可行解（檢驗(yàn)數(shù)非正），所以也可以說是從一個(gè)對(duì)偶基可行解出發(fā)；然后檢驗(yàn)原規(guī)劃的正則解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)正則解，此正則解對(duì)應(yīng)著另一個(gè)對(duì)偶基可行解（檢驗(yàn)數(shù)非正）。如果得到的正則解的分量皆非負(fù)則該正則解為最優(yōu)解。也就是說，對(duì)偶單純形法在迭代過程中始終保持對(duì)偶解的可行性（即檢驗(yàn)數(shù)非正），使原規(guī)劃的正則解由不可行逐步變?yōu)榭尚校?dāng)同時(shí)得到對(duì)偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解。2/4/202345(2)對(duì)偶單純形法的迭代步驟建立初始對(duì)偶單純形表,對(duì)應(yīng)一個(gè)基本解,所有檢驗(yàn)數(shù)均非正,轉(zhuǎn)2；若b’≥0,則得到最優(yōu)解,停止;否則,若有bk<0則選k行的基變量為出基變量,轉(zhuǎn)3若所有akj’≥0(j=1,2,…,n)，則原問題無可行解,停止;否則,若有akj’<0則選=min{j’/

akj’┃akj’<0}=r’/akr’

那么xr為進(jìn)基變量,轉(zhuǎn)4；以akr’為主元,作矩陣行變換使其變?yōu)?,該列其他元變?yōu)?,轉(zhuǎn)2。2/4/202346例2/4/202347cj-120-5000B-1bcByBy1y2y3y40y3-4-210-500y4-3-101-30σj-120-50000θ-120/-4-50/-2-50y221-1/20250y4-10-1/21-5σj-200-250-1250θ2050-50y201-3/2215-120y1101/2-15σj00-15-20-13502/4/202348例2/4/202349cj23-5-M0B-1bθcBxBx1x2x3x4x5-Mx411110770x5-25-101-10σjM+2M+3M-500-7Mθ3x21111070x5-70-6-51-45σj-10-7-M-3021θ1/77/6(M+3)/53x2011/72/71/74/72x1106/75/7-1/745/7σj00-50/7-(M+16)/7-1/7102/72/4/202350例

2/4/202351cj3-1-100-MB-1bθcBxBx1x2x3x4x5x60x41-2110011110x54-1-2010-3-Mx6-20100111σj-6M+3-1M-1000-Mcj3-1-100-MB-1bθcBxBx1x2x3x4x5x60x43-2010-1100x50-10012-1-1x3-2010011σj1-1000-M+1-12/4/202352cj3-1-100-MB-1bθcBxBx1x2x3x4x5x63x11001/3-2/3-5/34-1x20100-1-21-1x30012/3-4/3-7/39σj000-1/3-1/3-M+2/32cj3-1-100-MB-1bθcBxBx1x2x3x4x5x60x43001-2-512-1x20100-1-21-1x3-2010011σj1000-1-M-1-22/4/202353是是是是否否否否所有所有得到最優(yōu)解計(jì)算計(jì)算典式對(duì)應(yīng)原規(guī)劃的基本解是可行的典式對(duì)應(yīng)原規(guī)劃的基