對偶問題(運籌學)（課堂PPT）

1、.1大連海事大學交通運輸管理學院.22.4.1 對偶問題的提出2.4.2 原問題與對偶問題2.4.3 對偶問題的性質2.4.4 對偶變量的經(jīng)濟含義2.4.5 對偶單純形法.3 某工廠在計劃期內要安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種原材料的消耗，如表1-1所示。每生產(chǎn)一件產(chǎn)品可獲利2元，每生產(chǎn)一件產(chǎn)品可獲利3元，問應如何安排計劃使該工廠獲利最多? .4設 企業(yè)生產(chǎn)甲產(chǎn)品為X1件， 乙產(chǎn)品為X2件，則 (原問題) ( 對偶問題)設第i種資源價格為yi,( i=1, 2, 3) 則有y1y2y30,12416482122232max2121212121xxxxxx xxxx

2、zy4.5一般表示式：原問題： max z = c1 X1 + c2 X2 + + cn Xn s.t a11 X1 + a12 X2 + + a1n Xn b1 a21 X1 + a22 X2 + + a2n Xn b2 am1 X1 + am2 X2 + + amn Xn bm xj 0，j=1,2,n 對偶問題： min w = b1 y1 + b2 y2 + + bm ym s.t a11 y1 + a21 y2 + + am1 ym c1 a12 y1 + a22 y2 + + am2 ym c2 a1n y1 + a2n y2 + + amn ym cn yi 0，(i=1,2,m

3、 ).6典式模型對應對偶結構矩陣表示（1）max z = C X s.t AX b X 0min w = Y b s.t YA C Y 0 對偶問題原問題.7（2）若模型為 max z = C X s.t AX b X 0max z = C X s.t - AX -b X 0變形min w = Y b s.t YA C Y 0 Min w=Y (-b) st. Y (-A) CY 0令 Y=- Y 對偶問題對偶變量Y.8（3）max z = C X s.t AX b X 0變形設X= -Xmax = -CX st. -AX b X 0min w = Y b s.t YA C Y 0則有min

4、w = Y b s.t -YA - C Y 0.9用矩陣形式表示： （1） max z = C X min w = Y b s.t AX b s.t YA C X 0 Y 0 （2） max z = C X min w = Y b s.t AX b s.t YA C X 0 Y 0 （3）max z = C X min w = Y b s.t AX b s.t YA C X 0 Y 0.10 原問題(對偶問題) 對偶問題(原問題) 目標函數(shù)系數(shù) 約束右端項 約束右端項 目標函數(shù)系數(shù) 約束條件系數(shù)列向量 A約束條件系數(shù)行向量 AT 變量個數(shù)約束條件個數(shù)max min 變量 x j : 約束方程

5、i : x j 0 x j 無約束 = x j 0 約束方程: 變量 y i : y i 0 = y i 無約束 y i 0 .11例2-10 寫出下述線性規(guī)劃問題的對偶問題。 無約束43213432243114321432100362422153532x,x ,x,xyxxxyxxxyxxxxxxxxzmin.12則由表中原問題和對偶問題的對應關系，可以直接寫出上述問題的對偶問題無約束3213213213121321001523322645y,y,yyyyyyyyyyyyyyzmax.13練習練習max z = 2y1+5y2+1y3y1+y2 + y3 y1 y2 + y3 3 y1 +1

6、y3 - -1y1 0, y2 0,s.t.解解 min = x1+x2 - -1 x3x1+x2+3x3 2 x1 x2 5 x1+x2+1 x3 1 x10, , x3 0 s.t. .14 性質性質1 規(guī)范原始、對偶問題規(guī)范原始、對偶問題(P1)與與(D1) 互相對偶。即對偶互相對偶。即對偶問題的對偶是原問題。問題的對偶是原問題。 性質性質2 設設X, , 分別為分別為(P1)與與(D1)的任意可行解，則的任意可行解，則 CX b 性質性質3 設設 , ,Y分別為分別為(P1)與與(D1)的任意可行解，則當?shù)娜我饪尚薪?，則當 C= Yb 時，時， , , Y分別是分別是(P1)與與(D1

7、)的最優(yōu)解。的最優(yōu)解。 .15 性質性質4 互為對偶的兩個線性規(guī)劃問題，若其中一個問題的互為對偶的兩個線性規(guī)劃問題，若其中一個問題的，則，則另一個問題另一個問題。 互為對偶的兩個線性規(guī)劃問題，若其中一個問題有最優(yōu)解，則互為對偶的兩個線性規(guī)劃問題，若其中一個問題有最優(yōu)解，則另一個問題也有最優(yōu)解，且二者最優(yōu)值相等。另一個問題也有最優(yōu)解，且二者最優(yōu)值相等。 ： 無界性無界性之逆命題不成立。之逆命題不成立。 因為一個問題因為一個問題時，時， 另一個問題可能另一個問題可能，也可能，也可能。 .16 原始問題的原始問題的給出對偶問題的一個給出對偶問題的一個。 X*= (4, 6, 4, 0, 0)T, z

8、* = 42y1y2y3y4y5Y*= (0, 1/2, 1, 0, 0)T, w* = 42互補基本解互補基本解x3x2x1 x1 x2 x3 x4 x5 3 5 0 0 005 36 0 1 0 1/2 04 0 0 1 1/3 - -1/3 4 1 0 0 - -2/3 1/342 0 0 0 -1/2 -1cj 比值比值 基基 解解 .17 : max z = 3x1 +5x2 x1 8 2x2 12 3x1 + 4x2 36 x1 ， x2 0s.t.( ( P1) ):min w=8y1+12y2+36y3 y1 +3y3 3 2y2+4y3 5 y1 , , y2, , y3 0

9、s.t.( ( D1) ): max z = 3x1 +5x2 x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 x1, , x2 , , x3 , , x4 , , x5 0s.t.( ( Ps s) ):min w=8y1+12y2+36y3 y1 +3y3 -y4 = 3 2y2+4y3 -y5 = 5 y1 , , y2 , , y3 , , y4 , , y5 0s.t.( ( Ds s) )X*= (4 , ,6)TY*= (0 , , , ,1)TX*= (4, 6, 4, 0, 0)T Y*= (0, 1/2, 1, 0, 0)T, z*=

10、42 = w*.18 (P)的基本解的基本解 與與(D)的基本解的基本解 相互對應相互對應, , 且二者目標值相等。且二者目標值相等。我們把這樣一對基本解我們把這樣一對基本解 與與 ，稱為，稱為(P)與與(D)的的互補基本解互補基本解。 (P) 目目 標標 值值 (D) 序序號號 極極點點 基基 本本 解解 k Xk可可 行行 z = w Yk可可 行行 基基 本本 解解 k 1 O (0 ，0 ，8 ， 12 ， 36) 是是 0 否否 (0 ，0 ，0 ，- -3 ，- -5) 2 A (8 ，0 ，0 ， 12 ， 12) 是是 24 否否 (3 ，0 ，0 ， 0 ，- -5) 3 D

11、 (0 ，6 ，8 ，0 ， 12) 是是 30 否否 (0 ， 5/2 ， 0 ，- -3 ， 0) 4 B (8 ，3 ，0 ，6 ， 0) 是是 39 否否 (- 3/4 ， 0 ， 5/4 ， 0 ， 0) 5 C (4 ，6 ，4 ，0 ， 0) 42 (0 ， 1/2 ， 1 ，0 ，0) 6 E (12 ， 0 ，- -4 ， 12 ， 0) 36 (0 , , 0 , , 1 , , 0 , , - -1) 7 G (0 ，9 ，8 ，- -6 ， 0) 否否 45 是是 (0 , , 0 , , 5/4 , , 3/4 , , 0) 8 F (8 ，6 ，0 ，0 , , -

12、 12) 否否 54 是是 (3 , , 5/2 , , 0 , , 0 , , 0) .19為最優(yōu)解。當且僅當，和那么題的可行解，分別為原問題和對偶問若YXXYXYY,XSS,; 00 7. 設設 = ( , , , , , , )T= ( , , , , , , )T是是(P1) (D1)的一對的一對，那么，那么 0， j = 1, 2 , , n 0， i = 1, 2 , , m.20min =2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53 xj0，j=1，2，5已知其對偶問題的最優(yōu)解為y1*=4/5，y2*=3/5；z=5。

13、試用對偶理論找出原問題的最優(yōu)解 。.21max z=4y1+3y2y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20.22得=1/53，=17/55，=7/52 它們?yōu)閲栏癫坏仁剑?由互補松弛性得 x2*=x3*=x4*=0。因y1，y2 0；原問題的兩個約束條件應取等式，故有x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原問題的最優(yōu)解為 X*=(1，0，0，0，1)T；*=5.23對偶變量的意義代表對企業(yè)資源的估價，與該種資源的市場價格不同，因此我們稱之為影子價格影子價格。.24（1）資源的市場價格是已知數(shù)，相對比較穩(wěn)定

14、，而它的影子價格則有賴于資源的利用情況，是未知數(shù)。由于企業(yè)生產(chǎn)任務、產(chǎn)品結構等情況發(fā)生變化，資源的影子價格也隨之改變。（2）影子價格是一種邊際價格，在（2-12）式中將Z對 求偏導數(shù)得 ，這說明 相當于在給定的生產(chǎn)條件下， 每增加一個單位目標函數(shù)Z的增量。（3）資源的影子價格實際上又是一種機會成本。在純市場經(jīng)濟條件下，當?shù)?種資源的市場價格低于1/4時，可以買進這種資源；相反當市場價格高于影子價格時，就會賣出這種資源。隨著資源的買進賣出，它的影子價格也將隨之發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。.25.26由于單純表中同時反映原問題與對偶問題的最優(yōu)解，故可以從求對偶

15、問題最優(yōu)解角度求解LP模型。例： min z=2x1+3x2 max z=-2x1-3x2+0 x3 +0 x4 s.t x1+x23 標準化 s.t x1+x2-x3=3 x1+2x2 4 x1+2x2-x4=4 x10, x20 xj 0, (j=1,2,3,4) max z=-2x1-3x2+0 x3 +0 x4 s.t - x1-x2+x3=-3 - x1-2x2+x4=-4 xj 0, (j=1,2,3,4) .27Cj x1x2x3x4XBbCB-1 -1 1 0 -1 -2 0 1-2 -3 0 0-3 -4x3 x400cj - zj -2-300-1/2 0 1 -1/2 1

16、/2 1 0 -1/2x3 x2-1 2cj - zj -1/2 0 0 -3/2 0 -31 0 -2 1 0 1 1 -1x1 x221cj - zj 0 0 -1 -1-2 -3列單純表計算：.28把把m階階LPLP問題化成問題化成標準形標準形（允許其右端常數(shù)為負允許其右端常數(shù)為負）, 在其系數(shù)陣中找出或構造一個在其系數(shù)陣中找出或構造一個作作, , 。若所有檢驗數(shù)。若所有檢驗數(shù) j j00，則轉，則轉2 2; ：檢查表中檢查表中解列解列各數(shù)值各數(shù)值b bi i；若所有；若所有b bi i0,0, 則問題已得最優(yōu)解，停止計算則問題已得最優(yōu)解，停止計算; 否則轉否則轉3 3。：只要存在一個：

17、只要存在一個b br r00，它所在行中所，它所在行中所有有 a arj rj00，則原始問題無可行解，對偶問題無下界，則原始問題無可行解，對偶問題無下界，停止；否則轉停止；否則轉4 4。.29：先先確定確定離基離基變量，按變量，按 min bmin bi ib bi i 0 0 = b bl 確定第確定第 l 行的基變量行的基變量 xB Bl 離基，第離基，第 l 行為主行；行為主行； 確定確定變量，按變量，按： m in m in j j / / a alj ja alj j 0 0 = k k / / a alk k 確定進基變量確定進基變量 xk k 及主元及主元 a alk k。按主

18、元按主元 a alk k 對當前表格進行一次對當前表格進行一次， 得到一個新單純形表，返得到一個新單純形表，返2 2 。.30min z = 3x1+2x2s.t.2x1+3x2 18 x1 - - x2 2 x1+3x2 10 x1, , x2 0max z= - -3x1 - -2x2s.t.2x1+3x2+x3 = 18 x1 -x2 x4 = 2 x1+3x2 x5 = 10 x1, , x2, , x3, , x4, , x5 0 x1+ x2 +x4 = 2x13x2 +x5 = 10.31max z= - -3x1 - -2x2 2x1+3x2+x3 = 18 - -x1 +x2 +x4 = - -2 - -x1 - -3x2 +x5 = - -10 x1, , x2, , x3, , x4, , x5 0 s.t.cj 基基 解解 x1 x2 x3 x4 x5 -3 -2 0 0 0 2 3 1 0 0 x3x4 x5 18- -2 - -10 - -1 1 0 1 000 0 - -1 - -3 0 0 1 0 -3 -2 0 0 032/3min- -3比比 值值 .32cj 基基 解解 x1 x2 x3 x