清華大學(xué)運(yùn)籌學(xué)2對(duì)偶理論.pptx

第二章 線性規(guī)劃對(duì)偶理論,第一節(jié) 線性規(guī)劃對(duì)偶理論 第二節(jié) 對(duì)偶問題基本性質(zhì) 第三節(jié) 影子價(jià)格 第四節(jié) 對(duì)偶單純形法 第五節(jié) 靈敏度分析,1/66,第一節(jié) 線性規(guī)劃對(duì)偶理論,一、對(duì)偶問題的提出 例,2/66,3/66,生產(chǎn)是為贏利（取得收入）。還有別的辦法贏利（取得收入） 。例如，賣出或出租設(shè)備。 問，三種設(shè)備賣價(jià)或租價(jià)各應(yīng)是多少，進(jìn)項(xiàng)才不低于自己生產(chǎn)時(shí)的銷售收入？,原來的問題：兩種產(chǎn)品各生產(chǎn)多少，利潤總額最大？,4/66,用y1、y2和y3分別表示A、 B和 C三種設(shè)備單位臺(tái)時(shí)賣價(jià)或租價(jià)，則，總進(jìn)項(xiàng)w可表示成 w=4y1 +12y2+18y3 生產(chǎn)兩種產(chǎn)品消耗的設(shè)備臺(tái)時(shí)的價(jià)值（或稱出售或出租兩種產(chǎn)品所用設(shè)備臺(tái)時(shí)的進(jìn)項(xiàng)）分別是 1y1 +0y2+3y3 和 0y1 +2y2+2y3 兩種產(chǎn)品售價(jià)分別是3和5。出售或出租產(chǎn)品所用設(shè)備臺(tái)時(shí)的進(jìn)項(xiàng)不能低于售價(jià)。所以，應(yīng)有 1y1 +0y2+3y3 3 和 0y1 +2y2+2y3 5 從另一個(gè)角度看，w=4y1 +12y2+18y3是總消耗。,5/66,回答y1、y2和y3各是多少的問題，可表示如下： Min w=4y1 +12y2+18y3 s.t. y1 +3y3 3 2y2 +2y3 5 y1, y2, y30 該問題叫做原問題(P)的對(duì)偶問題(D)?？煽闯?， Max z=CX Min w=bTY (P) s.t. AXb (D) s.t. ATYCT X0 Y0,6/66,若要問對(duì)偶問題的解是什么，可以看解(P)時(shí)得到的最終單純形表。 最終單純形表,7/66,從該表松弛變量的檢驗(yàn)數(shù)行得到： 3 =0， 4 = -3/2，5 = -1， y1 =0，y2 = 3/2，y3 = 1，將其代入(D): w=40 +123/2+181=36 (1) 0 +31 =3 (2) 23/2+21 =5 (3) y1, y2, y30 (4) 這是對(duì)偶問題有趣的一個(gè)方面。,8/66,二、對(duì)稱的對(duì)偶問題一般形式 上面的例子叫做對(duì)稱的對(duì)偶問題。 三、非對(duì)稱的對(duì)偶問題 請(qǐng)見教科書第三版第52頁或第四版第53頁的表。,9/66,第二節(jié) 對(duì)偶理論基本性質(zhì),一、對(duì)稱形式單純形法矩陣表達(dá) Max z=CX s.t. AXb X0 化成標(biāo)準(zhǔn)形式 Max z=CX+0Xs s.t. AX+IXs=b X，Xs0 Xs =(xs1, xs2, ,xsm)T 是松弛變量,10/66,令 X = XB ，(C, 0)=(CB, CN) Xs XN (A, I)=(B, N) z=CBB-1b+(CN-CBB-1N)XN (1) CN-CBB-1N是非基變量xm+1, xm+2, ,xn的檢驗(yàn)數(shù)，令j =cj -CBB-1Pj，若所有的j 0，即 CN-CBB-1N0 (2) 則表示目前的基可行解最優(yōu)。另外，基變量XB 的檢驗(yàn)數(shù)是 CB-CBB-1B=0 (3),11/66,松弛變量Xs =(xs1, xs2, ,xsm)T的檢驗(yàn)數(shù)是 0-CBB-1I 0，即 -CBB-10 (4) 將(2)和(3)寫在一起： (CB，CN) - (CBB-1B，CBB-1N)0或 (CB，CN) - CBB-1(B，N)0 ，即 C- CBB-1A0 (5),12/66,再將(1) z=CBB-1b 、(5)和(4)寫在一起： z=CBB-1b (1) C- CBB-1A0 (5) -CBB-10 (4) 令YT=CBB-1，w=YTb (1) C- YTA0 (5) -YT0 (4) 或 w=YTb ATYCT Y0,13/66,Min w=YTb (D) s.t. ATYCT Y0 添加剩余變量后，變成 Min w=YTb+0Ys (D) s.t. ATY-IYs=CT Y, Ys0 Ys =(ys1, ys2, ,ys,n-m)T 是剩余變量,14/66,15/66,例 Max z=3x1+5x2 s.t. x1 4 y1 (P) 2x2 12 y2 3x1+2x2 18 y3 x1，x2 0 Min w=4y1 +12y2+18y3 s.t. y1 +3y3 3 x1 (D) 2y2 +2y3 5 x2 y1, y2, y30,Max z=3x1+5x2 +0x3+0x4 +0x5 s.t. x1 + x3 =4 (P) 2x2 + x4 =12 3x1+2x2 + x5 =18 x1，x2 ，x3 ，x4 ，x5 0 Min w=4y1 +12y2+18y3 +0y4+0y5+My6+My7 s.t. y1 +3y3 -y4 +y6 = 3 (D) 2y2 + 2y3 -y5 +y7 =5 y1, y2, y3, y4, y5, y6, y7 0,16/107,17/66,對(duì)偶問題初始單純形表,3應(yīng)當(dāng)是18-5M，但錯(cuò)算為18-2M，所以誤選y2為換入變量。以下將錯(cuò)就錯(cuò)算下去。,18/66,對(duì)偶問題最終單純形表,19/66,重新算一遍， 對(duì)偶問題初始單純形表,20/66,對(duì)偶問題最終單純形表,計(jì)算結(jié)果同上。,21/66,(P)最終單純形表,22/66,(D)對(duì)偶問題最終單純形表,二、對(duì)偶問題基本性質(zhì) 1. 弱對(duì)偶性。若 (1jn)和 (1im)分別是(P)和(D)的可行解，則恒有 C bT 證： C = = ，回想ATYCT ，即 cj PjTY= = ，所以，有 C = = = ( = ) ，另一方面，bT = = ，回想AXb ，即 bi = ，所以，有 bT = = = ( = ) ，證畢。,23/107,推論1 (P)任一可行解目標(biāo)函數(shù)值是(D)目標(biāo)函數(shù)值下界。反之， (D)任一可行解目標(biāo)函數(shù)值是(P)目標(biāo)函數(shù)值上界。 推論2 若(P)有可行解且目標(biāo)函數(shù)值無界，則(D)無可行解；反之， (D)有可行解且目標(biāo)函數(shù)無界，則(P)無可行解。當(dāng) (D)無可行解時(shí)， (P)無可行解或目標(biāo)函數(shù)值無界。 推論3 若(P)有可行解，而(D)無可行解，則(P)目標(biāo)函數(shù)值無界；反之， (D)有可行解，而(P)無可行解，則(D)目標(biāo)函數(shù)值無界。,24/66,2. 最優(yōu)性。若 (j=1, 2, , n)和 (i=1, 2, , m)分別是(P)和(D)的可行解，且有 C =bT 則 和 分別是(P)和(D)的最優(yōu)解。 證明:設(shè)X*和Y *分別是(P)和(D)的最優(yōu)解。則有C CX * ，bTY * bT ，即bTYbT =C CX * 另一方面，根據(jù)性質(zhì)1，CX * bTY * ，這就是說CX * =bTY * ，證畢。,25/107,3. 對(duì)偶定理。若(P)和(D)均有可行解，則均有最優(yōu)解，且兩者的目標(biāo)函數(shù)值相等。 證明:由于(P)和(D)均有可行解，根據(jù)弱對(duì)偶性推論1，(P)目標(biāo)函數(shù)值有上界， (D)目標(biāo)函數(shù)值有下界，因此，(P)和(D)都有最優(yōu)解。另外，根據(jù) ATYCT，Y0，w=YTb=CBB-1b=z知道，當(dāng)(P)取得最優(yōu)解時(shí)，(D)有可行解，且有w=z，根據(jù)性質(zhì)2（最優(yōu)性）， (D)的可行解也是最優(yōu)解，證畢。,26/107,4. 互補(bǔ)松弛性。若 和 分別是(P)和 (D)的可行解，那么， TXs=0和 TYs=0的充分必要條件是 和 分別是(P)和 (D)的最優(yōu)解。 證明: Max z=CX+0Xs (P) s.t. AX+IXs=b X，Xs0 Xs =(xs1, xs2, ,xsm)T 是松弛變量 Min w=bTY-0Ys (D) s.t. ATY-IYs=CT Y，Ys0 Ys =(ys1, ys2, ,ys,n-m)T 是剩余變量,27/107,z=CX+0Xs=(YTA-IYsT)X+0Xs=YTAX-IYsTX w=bTY-0Ys=(AX+IXs)TY-0Ys=XTATY+IXsTY 若 TXs=0和 TYs=0 ，有z=w，根據(jù)性質(zhì)2，知 和 是最優(yōu)解。若 和 是最優(yōu)解，則有z=w，即 CX=YTAX-IYsTX=bTY=XTATY+IXsTY 或 YTAX-IYsTX=XTATY+IXsTY 或 -YsTX=XsTY 即 YsTX=XsTY=0 證畢。,28/107,第三節(jié) 影子價(jià)格,一、影子價(jià)格 在例子 Max z=3x1+5x2 s.t. x1 4 (P) 2x2 12 3x1+2x2 18 x1，x2 0 bT=(4, 12, 18)是資源，即可利用的設(shè)備臺(tái)班量。在討論如何才能贏利最多時(shí)，沒有考慮三種設(shè)備單位臺(tái)班的價(jià)格。它們的價(jià)格藏在深處。,29/66,30/66,有些經(jīng)濟(jì)學(xué)家認(rèn)為，自由的市場(chǎng)交易，商品成交價(jià)格能夠反映其真正價(jià)值。但是，資源的現(xiàn)實(shí)市場(chǎng)價(jià)格并不反映其“真正”價(jià)值。還有些經(jīng)濟(jì)學(xué)家認(rèn)為，影子價(jià)格是原本無交易的資源，在轉(zhuǎn)為其他用途時(shí)的價(jià)格，或者說，另外再增加一個(gè)單位此種資源需要付出的價(jià)格。這個(gè)問題可以利用對(duì)偶問題的解給予某種解釋。 Min w=4y1 +12y2+18y3 s.t. y1 +3y3 3 (D) 2y2 +2y3 5 y1, y2, y30 其解是(Y, Ys)T=(y1, y2, y3, y4, y5) =(0, 3/2, 1, 0, 0),31/66,這就是說，三種設(shè)備每臺(tái)時(shí)的價(jià)格分別是0, 3/2和1。第一種設(shè)備每臺(tái)時(shí)的價(jià)格為0，這是什么意思？ 請(qǐng)看原問題 Max z=3x1+5x2 +0x3+0x4 +0x5 s.t. x1 + x3 =4 (P) 2x2 + x4 =12 3x1+2x2 + x5 =18 x1，x2 ，x3 ，x4 ，x5 0 其解是(X, Xs)T=(x1, x2, x3, x4, x5) =(2, 6, 2, 0, 0),32/66,x3=2，也就說，第一種設(shè)備臺(tái)時(shí)有余裕，再增加其臺(tái)時(shí)，無助于增加利潤，因此，“另外再增加一個(gè)單位此種資源需要付出的價(jià)格”為0。 第i種資源“再增加一個(gè)單位需要付出的價(jià)格”=limit w/ b=w/b=bTY/b=Y，這就是說，Y設(shè)備臺(tái)時(shí)的影子價(jià)格。 w/b1 y1 w= w/b= w/b2 = y2 =Y . . . . . . w/bm ym,33/107,6,12,x1,x2,6,4,4,9,x1=4,2x2=12,3x1+2x2=18,(2, 6),z=3x1+5x2=36,z=15,o,A,B,C,D,E,F,G,34/107,6,12,x1,x2,6,4,4,9,x1=4,2x2=12,3x1+2x2=18,(2, 6),z=3x1+5x2=36,z=15,o,A,B,C,D,E,F,G,x1=5,z=36-36=0,35/107,6,12,x1,x2,6,4,4,9,x1=4,2x2=12,3x1+2x2=18,(5/3, 6.5),z=3x1+5x2=36,z=15,o,A,B,C,D,E,F,G,2x2=13,z=3x1+5x2=37.5,z=37.5-36=1.5,36/107,6,12,x1,x2,6,4,4,9,x1=4,2x2=12,3x1+2x2=18,z=3x1+5x2=36,z=15,o,A,B,C,D,E,F,G,z=3x1+5x2=37,3x1+2x2=19,z=37-36=1,第四節(jié) 對(duì)偶單純形法,一、對(duì)偶單純形法思路 Min w=bTY-0Ys (D) s.t. ATY-IYs=CT Y，Ys0,37/66,二、對(duì)偶單純形法計(jì)算步驟,Step1：找出初始可行基、初始單純形表和初始基解。 Step2：若B-1b0，初始基解是最優(yōu)解，停。否則，下一步。 Step3：取(B-1b)l=min(B-1b)i|(B-1b)i0，第l行基變量換出。若所有的alj0，無可行解，停。 Step4：計(jì)算k/alk=minj/alj|alj0，第k列非基變量換入。 Step5：求基的逆矩陣、新基解和z。回Step2。,38/107,39/66,例1 Min w=4x1+12x2 +18x3 s.t. x1 + 3x3 3 2x2 + 2x3 5 x1，x2 ，x3 0 將其改寫如下： Max -w= -4x1-12x2 -18x3+0x4+0x5 s.t. -x1 - 3x3 +x4 = - 3 -2x2 -2x3 +x5 = -5 x1，x2 ，x3 ，x4 ，x5 0,40/66,初始單純形表,先確定換出變量，再換入變量,41/66,求B-1,再確定換出變量和換入變量，,42/66,求B-1,判斷是否最優(yōu),第五節(jié) 靈敏度分析,問題的由來，先看一個(gè)方程 x1+ x2=10 1.01x1+ x2=11, x1=100, x2= -90 如果1.01增加到1.011，該方程解會(huì)如何變化？ x1+ x2=10 1.011x1+ x2=11, x1=1/0.011=90.91, x2= -80.91 a21/a21 =0.001/1.01=0.1%, x1/x1 =(90.91-100)/100=-9%,43/66,再看另外一個(gè)方程 x1+ x2=10 2.02x1+ x2=11, x1=0.980, x2= 9.020 如果2.02增加到2.022，該方程解會(huì)如何變化？ x1+ x2=10 2.022x1+ x2=11, x1=0.978, x2= 9.022 a21/a21 =0.002/2.02=0.1%, x1/x1 =(0.978-0.980)/0.980=0.2%, 這時(shí)候，可以說，第一個(gè)方程組的解對(duì)于a21敏感，而第一個(gè)方程組則否。,44/66,實(shí)際問題的數(shù)學(xué)模型，應(yīng)當(dāng)避免第一種情況，因?yàn)閷?shí)際中很難避免將1.011算成1.01。 LP問題也會(huì)遇到類似情況。其中A、b和C都是從實(shí)際中收集、歸納和整理的數(shù)字，很難保證與實(shí)際情況絲毫不差。 如果LP問題的解因?yàn)檫@些數(shù)字與實(shí)際稍有偏差就會(huì)相差很大，那就說明利用A、b、C構(gòu)造的LP問題模型不能用做實(shí)際問題的模型。 合理的 LP問題模型不應(yīng)敏感于A、b或C的些小變化。本節(jié)課學(xué)習(xí)，當(dāng) A、b或C發(fā)生小變動(dòng)時(shí)，最優(yōu)解將如何變化，看一看對(duì)這些變化的敏感性。,45/66,靈敏度分析的步驟： 1. 先用最終單純形表中B-1變換A、b和C的增量 b =B-1b， Pj =B-1Pj ， 2. 檢查(P)是否仍為可行解。 3. 檢查(D)是否仍為可行解。 4. 根據(jù)下表中各種情況決定下一步行動(dòng)。,46/66,一、分析C的變化 問題1 若兩種產(chǎn)品單價(jià)分別變成5元/件和3.25元/件，兩種產(chǎn)品最優(yōu)產(chǎn)量是否變化？ 問題2 使最優(yōu)產(chǎn)量不變的第二種單價(jià)變化范圍多大？,47/66,48/66,為了回答問題1，將兩種產(chǎn)品改變后的單價(jià)填入最終單純形表，并重新計(jì)算檢驗(yàn)數(shù)，得到：,為了回答問題2，用5+c2表示第二種產(chǎn)品改變后的單價(jià)，并填入最終單純形表，并重新計(jì)算檢驗(yàn)數(shù)，得到： c4=-3/2-c2/2，若使最優(yōu)解不變，則須有c40 -3/2-c2/20，c2-3,49/66,若回答使最優(yōu)產(chǎn)量不變的第一種產(chǎn)品單價(jià)變化范圍，則用3+c1表示第一種產(chǎn)品改變后的單價(jià)，并填入最終單純形表，并重新計(jì)算檢驗(yàn)數(shù)： c4=-3/2+c1/3， c5=-1-c1/3，若使最優(yōu)解不變，則須有c40，c50，-3/2+c1/30， -1-c1/30， -3c19/2,50/66,二、分析b的變化 若b=(0, b2, 0)T，問最優(yōu)解是否改變，為此，先計(jì)算 b2/3 b =B-1b = = b2/2 -b2/3 將其添入最終單純形表中，得到：,51/66,52/66,為使第二種設(shè)備可用臺(tái)時(shí)改變后的解仍然可行，須有：2+b2/30， 6+b2/20， 2-b2/30， max-6, -12b2min6, -6b26， 對(duì)于b1和b3，同樣處理。,三、分析增添新變量xj的情況 如果增加新產(chǎn)品x6 ，單價(jià)為4元，問如何生產(chǎn)，總收入最多。設(shè)其所需三種設(shè)備臺(tái)時(shí)為 2 5/3 P6= 0 ，變換，得P6 = = 0 1 1/3 將P6 填入最終單純形表，并重新計(jì)算檢驗(yàn)數(shù)：,53/66,54/66,四、分析技術(shù)系數(shù)aij變化時(shí)的情況 如果aij對(duì)應(yīng)的xj是非基變量，處理辦法同“三”。如果xj是基變量，先變換Pj， Pj =B-1Pj 例1第二種產(chǎn)品用設(shè)備臺(tái)時(shí)由 0 改為 0 2 P2 = 2 2 3/2 單價(jià)由5元增加為5.5元/件，用x*2表示這種“新”產(chǎn)品產(chǎn)量，先變換P2如下，然后添入最終單純形表，并重新計(jì)算檢驗(yàn)數(shù)：,55/66,1/6 P