對偶問題和運輸問題

1、原問題與對偶問題的關系原問題(或對偶問題)對偶問題(或原問題)目標函數 max z n 個 變 =0 量 = 束 = 條 = 件 約 m個 束 = 約束條件右端項目標函數變量的系數 m 個 =0 變 =5 2x1 +2x3-x4=4 x2+x3+x4 =6 x1=0 x4無約束 Max z=5y1+4y2+6y3 y1+2y2 =0 y1 +y3=0 -3y1+2y2+y3=0,y2=0, y3無約束 3.對偶定理(原問題與對偶問題解的關系）考慮（LP）和（DP） 定理3-1 (弱對偶定理） 若 x, y 分別為（LP) 和（DP）的可行解，那么cTx bTy。 推論 若（LP）可行，那么（L

2、P）無有限最優(yōu)解的充分必要條件是（LD）無可行解。1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題 定理3-2 (最優(yōu)性準則定理) 若x,y分別(LP),(DP)的可行解,且cTx=bTy ，那么x,y分別為(LP)和(DP)的最優(yōu)解。 定理3-3 (主對偶定理) 若(LP)和(DP)均可行 那么(LP)和(DP)均有最優(yōu)解,且最優(yōu)值相等。 以上定理、推論對任意形式的相應性規(guī)劃的對偶均有效1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題4、原始問題和對偶問題最優(yōu)解之間的互補松弛關系min z=CTXs.t. AX-XS=b X, XS0max y=bTWs.t. ATW+WS=C W, WS0min z=CT

3、Xs.t. AXb X 0max y=bTWs.t. ATWC W0對偶引進松弛變量引進松弛變量XTWS=0 WTXS=0互補松弛關系X，XsW，Ws五、對偶的經濟解釋1、原始問題是利潤最大化的生產計劃問題0 xxxxxxbxxaxaxabxxaxaxabxxaxaxa. t . sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111222211單位產品的利潤（元/件）產品產量（件）總利潤（元）資源限量（噸）單位產品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）2、對偶問題0wwwwwwcwwawawacwwawawacwwawa

4、wa. t . swbwbwbyminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211資源限量（噸）資源價格（元/噸）總利潤（元）對偶問題是資源定價問題，對偶問題的最優(yōu)解w1、w2、.、wm稱為m種資源的影子價格（Shadow Price）原始和對偶問題都取得最優(yōu)解時，最大利潤 max z=min y3、資源影子價格的性質影子價格越大，說明這種資源越是相對緊缺影子價格越小，說明這種資源相對不緊缺如果最優(yōu)生產計劃下某種資源有剩余，這種資源的影子價格一定等于0種資源的邊際利潤第種資源的增量第最大利潤的增量iibzwiooimmii2211wbw

5、bwbwbyzmmiii2211wbw)bb(wbwbzziiwbz 影子價格的經濟含義 (1)影子價格是對現有資源實現最大效益時的一種估價 企業(yè)可以根據現有資源的影子價格，對資源的使用有兩種考慮：第一，是否將設備用于外加工或出租，若租費高于某設備的影子價格，可考慮出租該設備，否則不宜出租。第二，是否將投資用于購買設備，以擴大生產能力，若市價低于某設備的影子價格，可考慮買進該設備，否則不宜買進。1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題 需要指出，影子價格不是固定不變的，當約束條件、產品利潤等發(fā)生變化時，有可能使影子價格發(fā)生變化。另外，影子價格的經濟含義（2），是指資源在一定范圍內增加時的情況，

6、當某種資源的增加超過了這個“一定的范圍”時，總利潤的增加量則不是按照影子價格給出的數值線性地增加。這個問題還將在靈敏度分析一節(jié)中討論。1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題 5.由最優(yōu)單純形表求對偶問題最優(yōu)解 標準形式： Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2x1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 01.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題max z=CTXs.t. AX+XS=b X, XS0max y=bTWs.t. ATW-WS=C W, WS0max z=CTXs

7、.t. AX b X 0min y=bTWs.t. ATW C W 0單純形表和對偶對偶問題原始問題引進松弛變量引進松弛變量zXXSRHS1WSTWTCBTB-1b0B-1AB-1B-1bzXXSRHS1-CT0T00AIbmax z=CTXs.t. AX+XS=b X, XS0min y=bTWs.t. ATW-WS=C W, WS0WT=CBTB-1WST=WTA- CT50100000CBXBx1x2x3x4x5i0 x3300111003000 x4400210104000 x52500(1)001250-z050100*0000 x350(1)010-1500 x41502001-1

8、75100 x225001001-z-2500050*000-10050 x1501010-10 x45000-211100 x225001001-z-2750000-500-50-c-cB BT TB B-1-1I IB B=(p p1 1, p, p4 4,p,p2 2 )oTB B-1-1最優(yōu)解 x1 = 50 x2 = 250 x4 = 50影子價格影子價格 y y1 1 = 50 = 50 y y2 2 = 0 = 0 y y3 3 = 50 , = 50 , B B-1-1對應的檢驗數對應的檢驗數 T T = = c cB BT TB B-1-1 。 1. 1.線性規(guī)劃對偶問題線性

9、規(guī)劃對偶問題例3.2：求解線性規(guī)劃問題：求解線性規(guī)劃問題： 標準化：標準化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 2.2.對偶單純形法對偶單純形法 對偶單純形法的基本思想 對偶單純形法的基本思想是：從原規(guī)劃的一個基本解基本解出發(fā)，此基本解不一定可行，但它對應著一個對偶對偶可行解可行解（檢驗數非正），所以也可以說是從

10、一個對偶可行解出發(fā)；然后檢驗原規(guī)劃的基本解是否可行，即是否有負的分量，如果有小于零的分量，則進行迭代，求另一個基本解，此基本解對應著另一個對偶可行解（檢驗數非正）。2.2.對偶單純形法對偶單純形法 如果得到的基本解的分量皆非負則該基本解為最優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗數非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，當同時得到對偶規(guī)劃與原規(guī)劃的可行解時，便得到原規(guī)劃的最優(yōu)解。2.2.對偶單純形法對偶單純形法 對偶單純形法在什么情況下使用 ： 應用前提：有一個基，其對應的基滿足: 單純形表的檢驗數行全部非正（對偶可行）； 變量取值可有負數（非可行解）。 注

11、：通過矩陣行變換運算，使所有相應變量取值均為非負數即得到最優(yōu)單純形表。2.2.對偶單純形法對偶單純形法 1.建立初始對偶單純形表,對應一個基本解,所有檢驗數均非正,轉2； 2.若b0,則得到最優(yōu)解,停止;否則,若有bk0則選k行的滿足min bk0基變量為出基變量,轉3 3.若所有akj0( j = 1,2,n )，則原問題無可行解,停止;否則,若有akj0 則選 =minj / akjakj0=r/akr那么 xr為進基變量,轉4； 4.以akr為轉軸元,作矩陣行變換使其變?yōu)?,該列其他元變?yōu)?,轉2。 對偶單純形法求解線性規(guī)劃問題對偶單純形法求解線性規(guī)劃問題過程：過程：2.2.對偶單純形法

12、對偶單純形法例3.2：求解線性規(guī)劃問題：求解線性規(guī)劃問題： 標準化：標準化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 2.2.對偶單純形法對偶單純形法 表格對偶單純形法CI-2-3-400CBXBbX1X2X3X4X50 X4-3-1-2-1100 X5-4-21-301j-2-3-4000 X4-10-5/21/21

13、-1/2-2 X121-1/23/20-1/2j0-4-10-1-3 X22/501-1/5-2/51/5-2 X111/5107/5-1/5-2/5j00-9/5-8/5-1/52.2.對偶單純形法對偶單純形法單純形法和對偶單純形法步驟是是是是否否否否所有所有得到最優(yōu)解計算計算典式對應原規(guī)劃的基本解是可行的典式對應原規(guī)劃的基本解的檢驗數所有所有計算計算以為中心元素進行迭代以為中心元素進行迭代停沒有最優(yōu)解沒有最優(yōu)解單純形法對偶單純形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min0csMinj/asjasj0brMi

14、n-bi/airair03.3.靈敏度分析靈敏度分析 例3.5: 上例最優(yōu)單純形表如下 C i23000CBX BBX 1X 2X 3X 4X 52 X 141001/400 X 5400-21/213 X 22011/2-1/80j00-1.5-1/803.3.靈敏度分析靈敏度分析 0 0.25 0 這里 B B-1 = -2 0.5 1 0.5 -0.125 0 各列分別對應 b1、b2、b3 的單一變化因此，設 b1 增加 4，則 x1 ,x5 ,x2分別變?yōu)椋?+04=4, 4+(-2)4=-40, 2+0.54=4用對偶單純形法進一步求解，可得：x* = ( 4, 3, 2, 0,

15、0 )T f* = 173.3.靈敏度分析靈敏度分析 增加一個變量 增加變量 xn+1 則有相應的pn+1 ,cn+1 。 那么 計算出B B-1pn+1 , n+1=cn+1-cri ari n+1 填入最優(yōu)單純形表, 若 n+1 0 則 最優(yōu)解不變； 否則，進一步用單純形法求解。3.3.靈敏度分析靈敏度分析例3.6:例3.4增加x6 , p6=( 2, 6, 3 )T, c6=5 計算得到Ci230005CBXBbX1X2X3X4X5X62 X141001/401.50 X5400-21/2123 X22011/2-1/800.25j00-1.5-1/801.25用單純形法進一步求解，可得

16、：x* = ( 1,1.5,0,0,0,2 )T f* = 16.53.3.靈敏度分析靈敏度分析 增加一個約束 增加約束一個之后，應把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入一個新的非負變量（原約束若是小于等于形式可引入非負松弛變量，否則引入非負人工變量），并通過矩陣行變換把對應基變量的元素變?yōu)?，進一步用單純形法或對偶單純形法求解。3.3.靈敏度分析靈敏度分析例3.7:例3.4增加3x1+ 2x215，原最優(yōu)解不滿足這個約束。于是Ci 2 3 0 0 0 0 CB XB b X1 X2 X3 X4 X5 X6 2 X1 4 1 0 0 1/4 0 0 0

17、 X5 4 0 0 -2 1/2 1 0 3 X2 2 0 1 1/2 -1/8 0 0 0 X6 -1 0 0 -1 -1/2 0 1 j 0 0 -1.5 -1/8 0 0 3.3.靈敏度分析靈敏度分析經對偶單純形法一步，可得最優(yōu)解為（3.5, 2.25, 0, 0, 3, 2 )T，最優(yōu)值為 13. 75 A A中元素發(fā)生變化(只討論 N 中某一列變化情況） 與增加變量 xn+1 的情況類似，假設 pj 變化 。那么，重新計算出 B B-1pj j = cj - cri ari j 填入最優(yōu)單純形表，若 j 0 則最 優(yōu)解不變；否則，進一步用單純形法求解。（例子從略）3.3.靈敏度分析靈

18、敏度分析第四章 運輸問題運輸問題的表示網絡圖、線性規(guī)劃模型、運輸表初始基礎可行解西北角法、最小元素法非基變量的檢驗數閉回路法、對偶變量法確定進基變量，調整運量，確定離基變量2321341運輸問題網絡圖s2=27s3=19d1=22d2=13d3=12d4=13s1=14供應量供應地運價需求量需求地6753842759106運輸問題線性規(guī)劃模型0 xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs.t.x6x10 x9x5x7x2x4x8x3x5x7x6zmin343332312423222114131211342414332313322212

19、312111343332312423222114131211343332312423222114131211供應地約束需求地約束運輸問題的表格表示初始基礎可行解西北角法813131466初始基礎可行解最小元素法（1）最小元素法（2）最小元素法（3）最小元素法（4）最小元素法（5）最小元素法（6）-5非基變量xij的檢驗數zij-cij閉回路法(1)z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5-5閉回路法(2)z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5-5-5閉回路法(3)z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7-7-5-5閉回路法(4)z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9-9-5-7-5閉回路法(5)z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11+11-5-7-9-5閉回路法(6)z32-c32=(c22-c23+ c33)-c32=(