運(yùn)籌學(xué)第三版__第二章_對偶理論與靈敏度分析

1、1對偶理論與靈敏度分析對偶理論與靈敏度分析1 1 單純形法的矩陣描述單純形法的矩陣描述 設(shè)max z = CX AX = b X 0 A為mn階矩陣 RankA=m ,取B為可行基, N為非基， NBNBCCCNBAXXX , ,0, maxNBNBNNBBXXbNXBXXCXCz2bBCbBNBIBN111- 1 0 0 :矩陣單純形表0zXCXCbNXBXNNBBNBbBCzXNBCCXbBNXBBXBBNBNBNB11111)(0bBCzXXbBNXBIXBNNBNB11103bBCzXXbBNXBIXBNNBNB1110NBCCbBCzbBXXBNNBBN111 , , 0 得令.,0

2、 !出則最優(yōu)解直接由上式求若能找到最優(yōu)為最優(yōu)基的使注BBNbBCzbBXB11 0 目標(biāo)函數(shù)基可行解4求解步驟：.42 .,. 4. ,)()(0)()()(min ,)(0)(max . 3., 0. 2,. 111111111步直到求出結(jié)果重復(fù)的求出此得到新的出基行對應(yīng)的則若入基則若基變換否則轉(zhuǎn)下一步則得最優(yōu)解若求取可行基BBBxlPBbBPBPBbBxNBCCBBllklikikiikkNjNjBNN532利潤12kg40材料B16kg04材料A8臺(tái)時(shí) 21設(shè)備臺(tái)時(shí)限制 2 2 對偶問題的提出對偶問題的提出 eg.1 制定生產(chǎn)計(jì)劃 M1: max z = 2x1 + 3x2 1x1 +

3、2x2 8 4x1 16 4x2 12 x1，x2 0 6 現(xiàn)在出租，設(shè)y1為設(shè)備單位臺(tái)時(shí)的租金 y2,y3為材料A、B轉(zhuǎn)讓附加費(fèi)(kg-1) 則M2為M1的對偶問題，反之亦然。M2: min w = 8y1 + 16y2 + 12y3 y1 + 4y2 2 2y1 + 4y3 3 y1,y2,y3 032利潤12kg40材料B16kg04材料A8臺(tái)時(shí) 21設(shè)備臺(tái)時(shí)限制 0,124 16 482 32max 212121211xxxxxxxxzM7 一般的，原問題：max z = CX AX b X 0 對偶問題：min w = Yb YA C Y 0 比較： max z min w 決策變量

4、為n個(gè) 約束條件為n個(gè) 約束條件為m個(gè) 決策變量為m個(gè) “” “”83 3 對偶問題的化法對偶問題的化法 1、典型情況 eg.2 max z = x1 + 2x2 + x3 2x1 + x2 6 2x2 + x3 8 x1,x2,x3 0對偶：min w = 6y1 + 8y2 2y1 1 y1 + 2y2 2 y2 1 y1,y2 09 2、含等式的情況 eg.3 max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 = 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0對偶：min w = 3y1-3y1”+4y2 2y1-2y1”+ y2 1 y1- y1”

5、+2y2 2 3y1-3y1”+5y2 4 y1,y1”,y2 0令y1=y1-y1”,則： min w = 3y1+4y2 2y1 + y2 1 y1 +2y2 2 3y1 +5y2 4 y2 0，y1無約束一般，原問題第i個(gè)約束取等式，對偶問題第i個(gè)變量無約束。 2x1 + x2 + 3x3 3-2x1 - x2 - 3x3 -310 3、含“”的max問題 eg.4 max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0對偶：min w = -3y1 + 4y2 -2y1 + y2 1 -y1 + 2y2 2

6、 -3y1 + 5y2 4 y1,y2 0令y1 = -y1，則： min w = 3y1 + 4y2 2y1 + y2 1 y1 + 2y2 2 3y1 + 5y2 4 y1 0,y2 0-2x1 - x2 - 3x3 -311一般: max問題第i個(gè)約束取“”，則min問題第i個(gè)變量 0 ； min問題第i個(gè)約束取“”，則max問題第i個(gè)變量 0 ； 原問題第i個(gè)約束取等式，對偶問題第i個(gè)變量 無約束； max問題第j個(gè)變量 0 ,則min問題第j個(gè)約束取“” ； min問題第j個(gè)變量 0 ，則max問題第j個(gè)約束取“” ； 原問題第j個(gè)變量無約束，對偶問題第j個(gè)約束取等式。12 eg.5

7、 min z = 2x1 + 3x2 - 5x3 + x4 x1 + x2 - 3x3 + x4 5 2x1 + 2x3 - x4 4 x2 + x3 + x4 = 6 x1 0,x2,x3 0,x4無約束對偶：max w = 5y1 + 4y2 + 6y3 y1 + y2 2 y1 + y3 3 -3y1 + 2y2 + y3 -5 y1 - y2 + y3 = 1 y1 0,y2 0,y3無約束 134 4 對偶問題的性質(zhì)對偶問題的性質(zhì) 1、對稱性 對偶問題的對偶為原問題.0 )max(0;,min)max(YCYAYbwYCYACYAYbww即0)min(XbAXCXw0 , ,min

8、0 , ,maxYCYAYbwXbAXCXz140)min(XbAXCXw證畢令0 max maxmax)min(XbAXCXzwzCXwww15.,:的可行解分別為原問題和對問題設(shè)證明YXXCXAYCAYCYAbYXAYbXAbAX證畢bYXCbYXAYXC bYXCYX ,. 2則存在為對偶問題的可行解為原問題的可行解設(shè)弱對偶性16推論：(1) max問題任一可解的目標(biāo)值為min問題目標(biāo)值的一個(gè)下界；(2) min問題任一可解的目標(biāo)值為max問題目標(biāo)值的一個(gè)上界。3、無界性 若原問題(對偶問題)為無界解，則對偶問題(原問題)為無可行解。注：該性質(zhì)的逆不存在。若原(對偶)問題為無可行解，對偶

9、(原問題)問題或?yàn)闊o界解，或?yàn)闊o可行解。17 4、最優(yōu)性 設(shè)X*，Y*分別為原問題和對偶問題可行解，當(dāng) CX*=Y*b時(shí)， X*，Y*分別為最優(yōu)解。證畢為最優(yōu)解即為最優(yōu)解即由弱對偶性題的任一可行解分別為原問題和對偶問設(shè)證明 * )2( ) 1 (.,:*YbYbYbYCXbYXCXXCCXbYXCYX18 5、對偶定理 若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解， 且目標(biāo)值相等。*11*1*1*1*11*0)(:, 0.:wbYbBCbBCCCXzbBXbBCbYwYBCYCAYCABCABCCXBNBBBBB則其目標(biāo)值為因原問題最優(yōu)解則為對偶問題的可行解若其中全部檢驗(yàn)數(shù)可表示為則其對應(yīng)的基矩陣

10、存在為原問題的最優(yōu)解設(shè)證明19Y*為對偶問題的最優(yōu)解，且原問題和對偶問題的目標(biāo)值相等。證畢6、松弛性 若X*，Y*分別為原問題及對偶問題的可行解， 那么Ys*X*=0，Y*Xs*=0，當(dāng)且僅當(dāng)X*，Y*分別為 最優(yōu)解。證明：0,0max:SSSXXbXAXXCXz設(shè)原問題為0,0min:SSSYYCYYAYYbw設(shè)對偶問題為200,0maxSSSXXbXAXXCXz0,0minSSSYYCYYAYYbwXYYAXXYYACXzSS)(SSYXYAXXAXYYbw)(將b,Cb,C分別代入目標(biāo)函數(shù)：;,0, 0,*為最優(yōu)解時(shí)當(dāng)為可行解若YXzwXYXYYXSS證畢必有則分別為最優(yōu)解若另一方面0

11、, 0,*SSXYXYzwYX21TSmSSSTnxxxXxxxX) () (*2*1*2*1* ) ( ) ( *2*1*2*1*snSSSmyyyYyyyY 其中：用分量表示： mixynjxySiijSj, 2 , 1 , 0;, 2 , 1 , 0*22 7、檢驗(yàn)數(shù)與解的關(guān)系 (1)原問題非最優(yōu)檢驗(yàn)數(shù)的負(fù)值為對偶問題的一個(gè)基解。 (2)原問題最優(yōu)檢驗(yàn)數(shù)的負(fù)值為對偶問題的最優(yōu)解。 分析：max z = CX + 0Xs = (C 0)(X Xs)T AX + Xs = b X,Xs 0 min w = Yb + YS0 YA - Ys = C Y,Ys 0 檢驗(yàn)數(shù)： = (C 0)- C

12、BB-1(A I) = (C- CBB-1A - CBB-1) = (c s) c = C - CBB-1A X對應(yīng)的檢驗(yàn)數(shù) s = - CBB-1 Xs對應(yīng)的檢驗(yàn)數(shù) 23 eg.6 已知：min w = 20y1 + 20y2 的最優(yōu)解為y1*=1.2,y2*=0.2-ys1 y1 + 2y2 1 試用松弛性求對偶-ys2 2y1 + y2 2 問題的最優(yōu)解。 -ys3 2y1 + 3y2 3 -ys4 3y1 + 2y2 4 y1,y2 0 解：對偶問題 max z = x1 + 2x2 + 3x3 + 4x4 x1 + 2x2 + 2x3 + 3x4 20 +xs1 2x1 + x2 +

13、 3x3 + 2x4 20 +xs2 x1,x2,x3,x4 0 y1*xs1* = 0 y2*xs2* = 0 ys1*x1* = 0 ys2*x2* = 0 ys3*x3* = 0 ys4*x4* = 024 y1*=1.2,y2*0.2 0 xs1* = xs2* = 0 由 y1* + 2y2* = 1.6 1 ys1* 0 x1* = 0 由 2y1* + y2* = 2.6 2 ys2* 0 x2* = 0 由 2y1* + 3y2* = 3 =右邊 ys3* = 0 x3*待定 由 3y1* + 2y2* = 4 =右邊 ys4* = 0 x4*待定 有 2x3* + 3x4*

14、= 20 3x3* + 2x4* = 20 x3* = 4 x4* = 4 最優(yōu)解：x1* = 0 x2* = 0 x3* = 4 x4* = 4 xs1* = 0 xs2* = 0 最大值：z* = 28 = w*255 5 對偶問題的經(jīng)濟(jì)含義對偶問題的經(jīng)濟(jì)含義影子價(jià)格影子價(jià)格 最優(yōu)情況：z* = w* = b1y1* + + biyi* + + bmym*的影子價(jià)格為稱i*i*ibzbyyi*x2x1Q2 eg.7 max z = 2x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 0b1： 8 9 Q2(4，2.5) z* = 15.5 z* = z*- z

15、* = 3/2 = y1*b2：16 17 Q2”(4.25，1.875) z*” = 14.125 z* = z*”- z* = 1/8 = y2*b3：12 13 z* = 0 = y3*Q2Q2”266 6 對偶單純形法對偶單純形法 單純形法：由 XB = B-1b 0，使j 0，j = 1,m對偶單純形法：由j 0(j= 1,n)，使XB = B-1b 0 步驟：步驟：(1)保持j 0，j= 1,n，確定XB，建立計(jì)算表格； (2)判別XB = B-1b 0是否成立？ 若成立，XB為最優(yōu)基變量； 若不成立，轉(zhuǎn)(3)； 27 (4)消元運(yùn)算，得到新的XB。(3)基變換 出基變量， 出基；

16、，則若lliiixmibbb, 10min入基變量， 入基。則若kaljajxalkkljj0min重復(fù)（2）-（4）步，求出結(jié)果。28 eg.8 用對偶單純形法求解 min w = 2x1 + 3x2 + 4x3 x1 + 2x2 + x3 1 2x1 - x2 + 3x3 4 x1,x2,x3 0解：max z = -2x1 - 3x2 - 4x3 + 0 x4 + 0 x5 - x1 - 2x2 - x3 + x4 = -1 -2x1 + x2 - 3x3 + x5 = -4 x1,x2,x3,x4,x5 029-2-3-400CBXBbx1x2x3x4X50 x4-10 x5-4出出出

17、x4,x5 0 最優(yōu)最優(yōu)解：最優(yōu)解：x1* = 2，x2* = 0，x3* = 0，x4* = 1，x5* = 0目標(biāo)值：目標(biāo)值：w* = -z* = 4307 7 靈敏度分析靈敏度分析njpBCcABCCNBCCjBjjBBNN, 2 , 1, 0 0 0 :111 或或最優(yōu)性條件分析 變化對最優(yōu)解的影響。j ,ijiacb0 :1bBXB可行性條件31的變化資源ib 1 . 7TiTmiiiibbbbbbbbbbbb)0b 0 0() ( 21 bBbBbbBbBXB1111)(.,0 11這里用到可行性條件保持問題的最優(yōu)性不變的變化范圍求出由ibbBbB32例1 已知下述問題的最優(yōu)解及最

18、優(yōu)單純形表,0,124 164 82 00032max54321524132154321xxxxxxxxxxxxxxxxxz., ) 12使最優(yōu)基不變的變化范圍求 b. 4 )21時(shí)的最優(yōu)解求b33最優(yōu)單純形表如下:0-1/8-3/2000-1/81/2102311/2-2004001/40014200032bBXBC5x4x3x2x1x1x5x2x14 Z)4 0 0 2 4(,*TX此時(shí)3422216 1) :bbb解08/12/112/1204/101B2441216808/12/112/1204/101*bBXB由最優(yōu)單純形表得:35)(012bbBb221118/12/14/1244

19、0008/12/112/1204/10244)(bbbBbBbbB0008/22/44/4222bbb08/202/404/4222bbb.1682最優(yōu)基不變b36TTbb)0 0 4()0 0 ( )214 44 28024400408/12/112/1204/10244)(111bBbBbbB不可行!用對偶單純形法計(jì)算37-3/4-1/20001/400103x23-1/2-1/41002x3001/40014x120-1/8-3/2000-1/81/2102+2311/2-2004-8x5001/40014+0 x12ix5x4x3x2x1bXBCB00032x23/4-2)(17 :

20、. 0, 0, 2, 3, 4 :*5*4*3*2*1元目標(biāo)值最優(yōu)解zxxxxx38的變化價(jià)值系數(shù)jc 2 . 7.01分兩種情況討論進(jìn)行分析根據(jù)最優(yōu)性條件NBCCBNN的變化非基變量價(jià)值系數(shù)kc. 1kBkkpBCc1:原檢驗(yàn)數(shù)/ :kkkkkccccc變化kkkBkkkcpBCcc1/., 0 :/此時(shí)最優(yōu)解不變令kkkkkcc39例2 求例1 c4的變化范圍,使最優(yōu)解不變.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x204c8/1)8/1(8/1444c由解:. 8/1 4時(shí)最優(yōu)解不變即c40的變

21、化基變量價(jià)值系數(shù)rc. 2NBCCBNN1 原BBBCCC 若NBCNBCNBCCNBCCCBNBBNBBNN1111/ )( 則分析:)0 0 0( ) ( :21 rBmrBcCccccC其中.變化影響所有可見jrc41方法:.0 1/的變化范圍求出令rBNNcNBC例3 求例1 c2的變化范圍,使最優(yōu)解不變.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x242解:0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2

22、) 0 0( ),3 0 2(2cCCBB 1/8)- (-3/2) (43N ) (/4/3/n44414/433313/3pcpBcpcpBcBBBB4302232/120)c 0 0(232233/3cpcB08818/12/14/1)c 0 0(812244/4cpcB1322cc. 13 2時(shí)最優(yōu)解不變即c44的變化技術(shù)系數(shù)jia 3 . 7kBkkpBCc1 原T1k k k 0) a 0( ) ( , lkkTmklkkkkkklllpaaappppaaaa若分析:.k 的變化討論非基變量技術(shù)系數(shù)la45lklkakBkBkkkBkKpBCpBCcppBCc111 )( 則Tlk

23、mlkkBkapBC)00)(11 0lklkka令., 最優(yōu)解不變時(shí)當(dāng)lkkla46例4 求例1 a24的變化范圍,使最優(yōu)解不變.解:242424241, 1aaaa) (0) 1/8 2/3( 3) 0 2(32111BBCB24242448181aa08181 244a令. , 1 24此時(shí)最優(yōu)解不變a47 例5 在例1的基礎(chǔ)上，企業(yè)要增加一個(gè)新產(chǎn)品,每件產(chǎn)品需2個(gè)臺(tái)時(shí)，原材料A 6kg，原材料B 3kg，利潤 5元/件，問如何安排各產(chǎn)品的產(chǎn)量，使利潤最大？解：0,1234 1664 822 532max3213231321321xxxxxxxxxxxxxz532利潤12340料B16604料A8221設(shè)備b則有為新產(chǎn)品生產(chǎn)的件數(shù)設(shè),3x4831 )2pB計(jì)算25. 025 . 136208/12/112/1