運籌學對偶問題4.1對偶問題(1)對偶問題的提出例1、生產組織與計劃問題A,B各生產多少,可獲最大利潤?可用資源煤勞動力倉庫AB123202單位利潤4050306024Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0目標函數約束條件如果因為某種原因，不愿意自己生產，而希望通過將現有資源承接對外加工來獲得收益，那么應如何確定各資源的使用價格？Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目標函數約束條件兩個原則所得不得低于生產的獲利要使對方能夠接受設三種資源的使用單價分別為y1,y2,y3y1y2y3生產單位產品A的資源消耗所得不少于單位產品A的獲利生產單位產品B的資源消耗所得不少于單位產品B的獲利y1+3y240

2y1+2y2+2y350通過使用所有資源對外加工所獲得的收益W=30y1+60y2+24y3根據原則2，對方能夠接受的價格顯然是越低越好，因此此問題可歸結為以下數學模型：Min

W=30y1+60y2+24y3y1+3y2402y1+2y2+2y350y1,y2,y3

0目標函數約束條件原線性規劃問題稱為原問題，此問題為對偶問題，y1,y2,y3稱為影子價格(2)對偶問題的形式定義設原線性規劃問題為則稱下列線性規劃問題為其對偶問題，其中yi(i=1,2,…,m)稱為對偶變量。上述對偶問題稱為對稱型對偶問題。原問題簡記為(P)，對偶問題簡記為(D)原始問題MaxZ=CXs.t.AX≤b X≥0bAC≤Maxnm對偶問題MinW=Ybs.t. YAT≥C Y≥0≥MinCTATbTnm例2：求線性規劃問題的對偶規劃解：由原問題的結構可知為對稱型對偶問題例3：求線性規劃問題的對偶規劃解：由原問題的結構可知不是對稱型對偶問題，可先化為對稱型，再求其對偶規劃。3x1+2x260MaxZ=40x1+50x2設三種資源的使用單價分別為y1,y2,y3例2：求線性規劃問題的對偶規劃(1)對偶問題的提出(2)對偶單純形法的迭代步驟對偶問題變量類型約束變量02x224(5)產品的差額成本（ReducedCost）ATY-YS=C在一對變量中，其中一個大于0，另一個一定等于0定理5若X,Y分別為(P),(D)的可行解，則X,Y為最優解的充要條件是一個問題無界，則另一問題無可行解。所得不得低于生產的獲利推論2、(P)有可行解,但無有限最優解，則(D)無可行解。,則它們是(P),(D)的最優解。（1）邊際利潤大于0的資源沒有剩余原問題約束類型與0例4：求線性規劃問題的對偶規劃解：由原問題的結構可知不是對稱型對偶問題，可先化為對稱型，再求其對偶規劃。上式已為對稱型對偶問題，故可寫出它的對偶規劃令則上式化為對偶關系對應表原問題對偶問題目標函數類型MaxMin目標函數系數目標函數系數右邊項系數與右邊項的對應關系右邊項系數目標函數系數變量數與約束數變量數n約束數n的對應關系約束數m變量數m原問題變量類型與

0

對偶問題約束類型變量

0約束

的對應關系無限制＝原問題約束類型與

0對偶問題變量類型約束

變量

0的對應關系＝無限制4.2對偶問題的基本性質定理1對偶問題的對偶就是原問題MaxW’=-Ybs.t.-YA≤-C Y≥0MinZ’=-CXs.t.-AX≥-b X≥0MaxZ=CXs.t.AX≤b X≥0MinW=Ybs.t.YA≥C Y≥0對偶的定義對偶的定義定理2(弱對偶定理)分別為(P),(D)的可行解，則有C

bX，yXy證明：由AXb,y0有yAXby由AyC,X0有yAXCX所以CX

yAX

yb推論2、(P)有可行解,但無有限最優解，則(D)無可行解。定理3、yX,分別為(P),(D)的可行解，且XyC=b,則它們是(P),(D)的最優解。證明：對任X，有CX

by=CXX最優

推論1、(P),(D)都有可行解，則必都有最優解。定理4(主對偶定理)若一對對偶問題(P)和(D)都有可行解，則它們都有最優解，且目標函數的最優值必相等。證明：(1)當X*和Y*為原問題和對偶問題的一個可行解有原問題目標函數值對偶問題目標函數值所以原問題的目標函數值有上界，即可找到有限最優解；對偶問題有下界，也存在有限最優解。(2)當X*為原問題的一個最優解，B為相應的最優基,通過引入松弛變量Xs,將問題(P)轉化為標準型令令所以Y*是對偶問題的可行解，對偶問題的目標函數值為X*是原問題的最優解，原問題的目標函數值為推論：若一對對偶問題中的任意一個有最優解，則另一個也有最優解，且目標函數最優值相等。一對對偶問題的關系，有且僅有下列三種：都有最優解，且目標函數最優值相等；兩個都無可行解；一個問題無界，則另一問題無可行解。定理5若X,Y分別為(P),(D)的可行解，則X,Y為最優解的充要條件是同時成立證:(必要性）原問題對偶問題MaxZ=CXs.t. AX+XS=b X,XS≥0MinW=Ybs.t.ATY-YS=C W,WS

≥0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始問題和對偶問題變量、松弛變量的維數y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

對偶問題的變量對偶問題的松弛變量原始問題的變量原始問題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對變量中，其中一個大于0，另一個一定等于04.3對偶問題的解令設原問題為為原問題的一最優解則為對偶問題的一最優解CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CN-CBB-1N-CBB-1例1MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20y1y2y3MinW=30y1+60y2+24y3

y1+3y2+0y3

402y1+2y2+2y3

50

y1,y2,y30MaxW’=-30y1-60y2-24y3

y1+3y2+0y3–y4

=402y1+2y2+2y3

–y5

=50y1,y2,y3,y4,y50MaxW’=-30y1-60y2-24y3+0(y4+

y5)-M(y6+

y7)

y1+3y2+0y3–y4+

y6

=402y1+2y2+2y3

–y5

+

y7

=50y1,y2,y3,y4,y50C-30-60-2400-M-MθCByBby1y2y3y4y5y6y7-My640130-101040/3-My7502220-10125Z-90M-30+3M-60+5M-24+2MMM00

C-30-60-2400-M-MθCByBby1y2y3y4y5y6y7-60y240/31/310-1/301/30

-My770/34/3022/3-1-2/31

Z-800-70M/3-10+4M/30-24+2M2M/3-M

0

-60y240/31/310-1/301/3040-24y335/32/3011/3-1/2-1/31/235/2Z-1080600-12-12

-60y215/201-1/2-1/21/41/6-1/4

-30y135/2103/21/2-3/4-1/23/4

Z-97500-9-15-15/2

例1、MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

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

X1–X50CBXBBX1X2X3X4X5θ40X115101/2-1/20

0X59003/2-1/21

50X215/297501-3/41/40

Z

0

0

-35/2-15/2

0

y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

對偶問題的變量對偶問題的松弛變量原始問題的變量原始問題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對變量中，其中一個大于0，另一個一定等于0C23-5-M0-MθCBXBbX1X2X3X4X5X6-MX471111007-MX6102-510-115Z-17M2+3M3-4M2M-50-M0

-MX4207/21/211/2-1/24/72X151-5/21/20-1/21/2

Z2M-1003M/2+8M/2-60M/2+1-3M/2-1

3X24/7011/72/71/7-1/7

2X145/7106/75/7-1/71/7

Z102/700-50/7-M-16/7-1/7-M+1/7

原線性規劃問題稱為原問題，此問題為對偶問題，推論2、(P)有可行解,但無有限最優解，則(D)無可行解。y1,y2,y30那么xr為進基變量,轉4；對偶問題變量類型約束變量02對偶問題的基本性質例3：求線性規劃問題的對偶規劃分別為(P),(D)的可行解，且目標函數系數目標函數系數右邊項系數對偶問題約束類型變量0約束x1，x20定義設原線性規劃問題為則稱下列線性規劃問題表示減少一件產品所節省的資源可以增加的利潤(2)對偶單純形法的迭代步驟所以原問題的目標函數值有上界，即可找到有限最優解；(P)4.4影子價格(1)原始問題是利潤最大化的生產計劃問題單位產品的利潤（元/件）產品產量（件）總利潤（元）資源限量（噸）單位產品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）(2)對偶問題資源限量（噸）資源價格（元/噸）總利潤（元）對偶問題是資源定價問題，對偶問題的最優解y1、y2、...、ym稱為m種資源的影子價格（ShadowPrice）原始和對偶問題都取得最優解時，最大利潤MaxZ=MinW(3)資源影子價格的性質影子價格越大，說明這種資源越是相對緊缺影子價格越小，說明這種資源相對不緊缺如果最優生產計劃下某種資源有剩余，這種資源的影子價格一定等于0y1y2ym(4)產品的機會成本機會成本表示減少一件產品所節省的資源可以增加的利潤增加單位資源可以增加的利潤減少一件產品可以節省的資源機會成本利潤差額成本(5)產品的差額成本（ReducedCost）差額成本=機會成本-利潤(6)互補松弛關系的經濟解釋在利潤最大化的生產計劃中（1）邊際利潤大于0的資源沒有剩余（2）有剩余的資源邊際利潤等于0（3）安排生產的產品機會成本等于利潤（4）機會成本大于利潤的產品不安排生產4.5對偶單純形法定義：設A=(BN)，其中B是一個非奇異的m×m階方陣，對應地C=(CBCN)，則YB=CB的解Y*=CBB-1稱為對偶問題(D)的一個基本解；若Y*還滿足Y*N≧CN，則稱Y*為(D)的一個基可行解；若有Y*N>CN，則稱Y*為非退化的基可行解，否則稱為退化的基可行解。(1)對偶單純形法的基本原理定義：如果原問題(P)的一個基本解X與對偶問題(D)的基可行解Y對應的檢驗數向量滿足條件則稱X為原問題(P)的一個正則解。原問題(P)的正則解X與對偶問題(D)的基可行解Y一一對應對偶單純形法的基本思想從原規劃的一個基本解出發，此基本解不一定可行(正則解)，但它對應著一個對偶基可行解（檢驗數非正），所以也可以說是從一個對偶基可行解出發；然后檢驗原規劃的正則解是否可行，即是否有負的分量，如果有小于零的分量，則進行迭代，求另一個正則解，此正則解對應著另一個對偶基可行解（檢驗數非正）。如果得到的正則解的分量皆非負則該正則解為最優解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗數非正），使原規劃的正則解由不可行逐步變為可行，當同時得到對偶規劃與原規劃的可行解時，便得到原規劃的最優解。(2)對偶單純形法的迭代步驟建立初始對偶單純形表,對應一個基本解,所有檢驗數均非正,轉2；若b’≥0,則得到最優解,停止;否則,若有bk<0則選k行的基變量為出基變量,轉3