線性規(guī)劃對(duì)偶理論

1、第第1頁(yè)頁(yè) 線性規(guī)劃問(wèn)題具有對(duì)偶性線性規(guī)劃問(wèn)題具有對(duì)偶性, ,即任何一個(gè)線性規(guī)劃問(wèn)即任何一個(gè)線性規(guī)劃問(wèn) 題題, ,都存在另一個(gè)線性規(guī)劃問(wèn)題問(wèn)題與之對(duì)應(yīng)都存在另一個(gè)線性規(guī)劃問(wèn)題問(wèn)題與之對(duì)應(yīng). .如果如果 把其中一個(gè)問(wèn)題叫做原問(wèn)題把其中一個(gè)問(wèn)題叫做原問(wèn)題, ,則另外一個(gè)就叫做它則另外一個(gè)就叫做它 的對(duì)偶問(wèn)題的對(duì)偶問(wèn)題. .并稱這兩個(gè)相互聯(lián)系的問(wèn)題為一對(duì)對(duì)并稱這兩個(gè)相互聯(lián)系的問(wèn)題為一對(duì)對(duì) 偶問(wèn)題偶問(wèn)題. .研究對(duì)偶問(wèn)題之間的關(guān)系及其性質(zhì)研究對(duì)偶問(wèn)題之間的關(guān)系及其性質(zhì), ,就是線就是線 性規(guī)劃的對(duì)偶理論性規(guī)劃的對(duì)偶理論(Duality(DualityTheory).Theory). 第第2章章 線性規(guī)

2、劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論 第第2頁(yè)頁(yè) |1 對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題的提出 |2 原問(wèn)題與對(duì)偶問(wèn)題原問(wèn)題與對(duì)偶問(wèn)題 |3 對(duì)偶問(wèn)題的基本性質(zhì)對(duì)偶問(wèn)題的基本性質(zhì) |4 影子價(jià)格影子價(jià)格 |5 對(duì)偶單純形法對(duì)偶單純形法 |6 靈敏度分析靈敏度分析 |7 參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃 第第3頁(yè)頁(yè) 常山機(jī)器廠用常山機(jī)器廠用A、B、C三種設(shè)備生產(chǎn)三種設(shè)備生產(chǎn)I、II兩種兩種 產(chǎn)品。問(wèn)該企業(yè)應(yīng)安排生產(chǎn)使總的利潤(rùn)收入為最大。產(chǎn)品。問(wèn)該企業(yè)應(yīng)安排生產(chǎn)使總的利潤(rùn)收入為最大。 占用設(shè)備占用設(shè)備 時(shí)間時(shí)間(h) III 用于生產(chǎn)用于生產(chǎn) 的能力的能力 設(shè)備設(shè)備A2212 設(shè)備設(shè)備B4016 設(shè)備設(shè)備C0515 利潤(rùn)

3、利潤(rùn)(元元)23 例例1 1 生產(chǎn)計(jì)劃問(wèn)題生產(chǎn)計(jì)劃問(wèn)題 2-1 對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題的提出 模模 型型 21 32maxxx 1222 21 xx 164 1 x 155 2 x 0, 21 xx s.t. 設(shè)設(shè)備設(shè)設(shè)備A, B, C每小時(shí)的出租價(jià)格分每小時(shí)的出租價(jià)格分 別為別為y1, y2,和和y3元元 出租條件出租條件: 租金收入租金收入生產(chǎn)的獲利。生產(chǎn)的獲利。 四海機(jī)器廠接受條件四海機(jī)器廠接受條件: 租金要低租金要低 0, 352 242 151612min 321 31 21 321 yyy yy yy yyyw 第第4頁(yè)頁(yè) ), 1(0 ), 1( . max 1 1 njx mi

4、bxa ts xcz j n j ijij n j jj ), 1(0 ), 1( . min 1 1 miy njcya ts ybw i m i jiij m i ii 0 . max X bAX ts CXz 0 . min Y CYA ts Ybw 第第5頁(yè)頁(yè) 2-2 原問(wèn)題與對(duì)偶問(wèn)題原問(wèn)題與對(duì)偶問(wèn)題 minmax 第第6頁(yè)頁(yè) 原問(wèn)題原問(wèn)題(求極大求極大) c1c2cn右端右端 項(xiàng)項(xiàng) x1x2xn a11a12a1n a21a22a2n am1am2amn m b b b 2 1 n ccc 21 y1 y2 ym b1 b2 bm 對(duì)偶對(duì)偶 問(wèn)題問(wèn)題 (求極求極 小小) 右端項(xiàng)右端項(xiàng)

5、 第第7頁(yè)頁(yè) 原問(wèn)題原問(wèn)題(對(duì)偶問(wèn)題對(duì)偶問(wèn)題)對(duì)偶問(wèn)題對(duì)偶問(wèn)題(原問(wèn)題原問(wèn)題) 無(wú)無(wú)約約束束 個(gè)個(gè) 變變量量 0 0 n 個(gè)個(gè) 約約束束條條件件 m 約約束束條條件件 個(gè)個(gè) n 變變量量 個(gè)個(gè) 0 0 m 目標(biāo)函數(shù)目標(biāo)函數(shù)max目標(biāo)函數(shù)目標(biāo)函數(shù)min 目標(biāo)函數(shù)中變量的系數(shù)目標(biāo)函數(shù)中變量的系數(shù)約束條件右端項(xiàng)約束條件右端項(xiàng) 約束條件右端項(xiàng)約束條件右端項(xiàng)目標(biāo)函數(shù)中變量的系數(shù)目標(biāo)函數(shù)中變量的系數(shù) 第第8頁(yè)頁(yè) 0, 0 8374 35 522 .)1( 365max 32 321 321 321 321 xx xxx xxx xxx ts xxxz ), 1( ), 1(0 ), 1( ), 1( .)

6、2( max 1 1 1 1 1 1 1 nnjx nnjx mmibxa mmibxa ts xcz j j n j ijij n j ijij n j jj 無(wú)無(wú)約約束束 第第9頁(yè)頁(yè) 0, 0 8374 35 522 .)1( 365max 32 321 321 321 321 xx xxx xxx xxx ts xxxz 321 835minyyyw 無(wú)無(wú)約約束束 1 y 0 2 y 0 3 y 54 321 yyy 6752 321 yyy 332 321 yyy 第第10頁(yè)頁(yè) ), 1( ), 1(0 ), 1( ), 1( . max 1 1 1 1 1 1 1 nnjx nnjx

7、 mmibxa mmibxa ts xcz j j n j ijij n j ijij n j jj 無(wú)無(wú)約約束束 m i ii ybw 1 min ), 1(0 1 miyi ), 1( 1 mmiyi 無(wú)無(wú)約約束束 m i jiij njcya 1 1) , 1( m i jiij nnjcya 1 1 ), 1( 第第11頁(yè)頁(yè) 321 365maxxxxz 0 0 332 6752 54 . 835min 3 2 321 321 321 321 y y yyy yyy yyy ts yyyw 0 3 x 35 321 xxx 無(wú)無(wú)約約束束 1 x 0 2 x 8374 321 xxx 5

8、22 321 xxx 第第12頁(yè)頁(yè) 2-3 對(duì)偶問(wèn)題的基本性質(zhì)對(duì)偶問(wèn)題的基本性質(zhì) 弱對(duì)偶性；強(qiáng)對(duì)偶性；弱對(duì)偶性；強(qiáng)對(duì)偶性； 最優(yōu)性最優(yōu)性; 無(wú)界性無(wú)界性; 互補(bǔ)松弛性互補(bǔ)松弛性 ), 1(0 ), 1( . . max 1 1 njx mibxa ts xcz j n j ijij n j jj ), 1(0 ), 1( . min 1 1 miy njcya ts ybw i m i jiij m i ii 掌握原問(wèn)題和掌握原問(wèn)題和 其對(duì)偶問(wèn)題解其對(duì)偶問(wèn)題解 之間的關(guān)系之間的關(guān)系 第第13頁(yè)頁(yè) ), 1(njx j ), 1(miyi i m i ij n j j ybxc 11 ), 1(

9、0 ), 1( . 1 njx mibxa ts j n j ijij ), 1(0 ), 1( . 1 miy njcya ts i m i jiij j m i i n j ijj n j i m i ij xyaxya 1111 )( m i ji n j iji m i j n j j i xyayxa 1111 )( j n j j xc 1 i m i i yb 1 n j jjx cz 1 max m i ii ybw 1 min 第第14頁(yè)頁(yè) ), 1(njx j ), 1(miyi i m i ij n j j ybxc 11 j n j jj n j j xcxc 11 i

10、 m i ii m i i ybyb 11 ), 1(njx j ), 1(miyi ), 1(njx j ), 1(miyi 第第15頁(yè)頁(yè) wzminmax ), 1, 1(0, 0 ), 1( . max 1 1 njmixx mibxxa ts xcz sij n j isijij n j jj , 0 Y), 1(0miyi 0 YAC ), 1( 1 njcya n i jiij ), 1(0miyi bBCxc B n j jj 1 1 m i ii yb 1 第第16頁(yè)頁(yè) , 0 i y ; 1 n j ijij bxa, 1 n j ijij bxa0 i y i m i i

11、y b 1 i m i ij n j j ybxc 11 0)( 11 iij m i n j ij ybxa 0, 0 1 i n j jiji bxay ), 1(0 ) ( 1 miybxa iij n j ij m i ji n j j ij n j j xyaxc 111 第第17頁(yè)頁(yè) jjji czy , 第第18頁(yè)頁(yè) 21 32maxxx 1222 21 xx 164 1 x 155 2 x 0, 21 xx s.t. 0, 352 242 151612min 321 31 21 321 yyy yy yy yyyw 54321 00032maxxxxxxz )5 , 1(0 1

12、55 164 1222 52 41 321 jx xx xx xxx j ) 5 , 1( 0 352 242 00151612max 531 421 54321 iy yyy yyy yyyyyw i 第第19頁(yè)頁(yè) cj 23000 CB基基bx1x2x3x4x5 zj - cj 2 0 3301001/5 400-214/5 3101/20-1/5 00101/5 x1 x4 x2 cj-12-16-1500 CB基基by1y2y3y4y5 -12y11120-1/20 -15y31/50-4/511/5-1/5 zj - cj04033 第第20頁(yè)頁(yè) 目標(biāo)函數(shù)值目標(biāo)函數(shù)值 原問(wèn)題原問(wèn)題

13、對(duì)偶問(wèn)題對(duì)偶問(wèn)題 第第21頁(yè)頁(yè) 2-4 影子價(jià)格影子價(jià)格 m i ii n j jj ybxcz 11 i b i y 影子影子 價(jià)格價(jià)格 說(shuō)明：說(shuō)明： i i y b z 第第22頁(yè)頁(yè) , 0 i y; 1 n j ijij bxa, 1 n j ijij bxa0 i y ; 1 1 m i iijjjBjj yacPBCc j c m i iij ya 1 第第23頁(yè)頁(yè) 2-5 對(duì)偶單純形法對(duì)偶單純形法 單純形法計(jì)算的基本思想：?jiǎn)渭冃畏ㄓ?jì)算的基本思想： 即即 0 1 bB0 1 bB 0 1 ABcc B 對(duì)偶單純形法的基本思想：對(duì)偶單純形法的基本思想： 0 1 ABcc B 0 1 b

14、B 0 1 ABcc B 即即 第第24頁(yè)頁(yè) cj c1cmcj cn x1xmxjxnCB基基b c1 c2 cm x1 x2 xm cj -zj00 10 00 01 a1ja1n a2ja2n amjamn m b b b 2 1 cj zjcn -zn 對(duì)偶單純形法的初始單純形表：對(duì)偶單純形法的初始單純形表： cj zj 0 ( j= 1,n ) ), 1(mibi 第第25頁(yè)頁(yè) 0|min ii i r bbb ,0min rs ss rj rj jj j a zc a a zc ), 1(0mibi . 0, 10 rjr anjb有有，而而對(duì)對(duì)所所有有對(duì)對(duì) rnrnmmrr bx

15、axax 11, 第第26頁(yè)頁(yè) 0, 522 33 . 18124min 321 32 31 321 xxx xx xx ts xxxz )5 , 4 , 3 , 2 , 1( 0 522 33 . 0018124max 532 431 54321 ix xxx xxx ts xxxxxw i cj-4-12-1800 CB基基bx1x2x3x4x5 0 x4-3-10-310 0 x5-50-2-201 cj-zj-4-12-1800 0 x4 cj-zj -12x2 cj-zj -12x25/20110-1/2 -3-10-310 -40-60-6 -18x3 11/301-1/30 5/

16、2-1/3101/3-1/2 -200-2-6 第第27頁(yè)頁(yè) ), 1(0 ), 1( . )0(min 1 1 njx mibxa ts cxcz j n j ijij j n j jj 第第28頁(yè)頁(yè) |概況概況 |改變價(jià)值向量改變價(jià)值向量 |改變右端向量改變右端向量 |增加變量增加變量 |增加約束條件增加約束條件 2-6 靈敏度分析靈敏度分析 第第29頁(yè)頁(yè) 1. 靈敏度分析的含義靈敏度分析的含義 |概況概況 2. 靈敏度分析研究的問(wèn)題靈敏度分析研究的問(wèn)題 3. 如何解決如何解決 第第30頁(yè)頁(yè) 靈敏度分析的步驟靈敏度分析的步驟 原問(wèn)題原問(wèn)題對(duì)偶問(wèn)題對(duì)偶問(wèn)題結(jié)論或繼續(xù)計(jì)算的步驟結(jié)論或繼續(xù)計(jì)算的

17、步驟 可行解可行解可行解可行解仍為最優(yōu)解仍為最優(yōu)解 可行解可行解非可行解非可行解用單純形法繼續(xù)迭代用單純形法繼續(xù)迭代 非可行解非可行解可行解可行解用對(duì)偶單純形法繼續(xù)迭代用對(duì)偶單純形法繼續(xù)迭代 非可行解非可行解非可行解非可行解引入人工變量引入人工變量, 編制新的單純表編制新的單純表, 重新計(jì)算重新計(jì)算 第第31頁(yè)頁(yè) 6-1 價(jià)值系數(shù)價(jià)值系數(shù)cj發(fā)生變化發(fā)生變化(僅影響檢驗(yàn)數(shù)僅影響檢驗(yàn)數(shù)) 單單 純純 形形 表表 cjc1c2cn CB基基bx1x2xn CBXBB-1bIB-1N j0CN - CBB-1N 21 32maxxxz 1222 21 xx 164 1 x 155 2 x 0, 21

18、 xx s.t. cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 2211 )3()2(maxxxz 21 、 21 、 第第32頁(yè)頁(yè) cjc1c2cn CB基基bx1x2xn CBXBB-1bIB-1N j0CN - CBB-1N cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 cj 23000 CB基基bx1x2x3x4x5 cj -zj

19、 x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 3x141001/40 0 x5500-5/2 5/41 2x22011/2 -1/40 cj -zj 00-1-1/40 第第33頁(yè)頁(yè) cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 2211 )3()2(maxxxz 21 、 cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 3010

20、01/5 400-214/5 00-101/5 0 2 1 2 1 2 2 2 1 5 1 1 , 0 2 2 1 0 5 1 1 12 1 , 0 1 2 1 第第34頁(yè)頁(yè) cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 2211 )3()2(maxxxz 21 、 cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-101/5 1 2 1 2 2 2 1

21、5 1 21 , 0 2 2 1 1,2 121 2 3 2 3 0 5 1 21 2 1 第第35頁(yè)頁(yè) 6-2 分析分析bi的變化范圍的變化范圍 cjc1c2cn CB基基bx1x2xn CBXBB-1bIB-1N j0CN - CBB-1N 原問(wèn)題原問(wèn)題對(duì)偶問(wèn)題對(duì)偶問(wèn)題 結(jié)論或繼續(xù)計(jì)結(jié)論或繼續(xù)計(jì) 算的步驟算的步驟 可行解可行解可行解可行解仍為最優(yōu)解仍為最優(yōu)解 可行解可行解非可行解非可行解 用單純形法繼用單純形法繼 續(xù)迭代續(xù)迭代 非可行解非可行解可行解可行解 用對(duì)偶單純形用對(duì)偶單純形 法繼續(xù)迭代法繼續(xù)迭代 非可行解非可行解非可行解非可行解 引入人工變量引入人工變量, 編制新的單純編制新的單純

22、 表表, 重新計(jì)算重新計(jì)算 bi的變化引起基變量的的變化引起基變量的 取值發(fā)生變化，有可取值發(fā)生變化，有可 能發(fā)生能發(fā)生1、3兩種情況兩種情況 第第36頁(yè)頁(yè) 21 32maxxxz 1222 21 xx 164 1 x 155 2 x 0, 21 xx s.t. cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 )15,16,12( 321 321 、 321 、 第第37頁(yè)頁(yè) cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3

23、 3101/20-1/5 301001/5 400-214/5 00-10-1/5 ),( 241 PPPB 4 2 2/7 20 12 15 5/100 5/412 5/102/1 1b B T b)20,12,15( 1 cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 101/20-1/5 01001/5 00-214/5 00-10-1/5 7/2 -2 4 2x131001/40 0 x31001-1/2 -2/5 3x2401001/5 cj -zj 000-1/2 -3/5 T )0 , 0 , 1 , 4 ,3( 1 第第38頁(yè)頁(yè) c

24、j 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 3 1 15 16 12 5/100 5/412 5/102/1 bB )15,16,12( 321 b 321 、 ,0 21 )15,16,12( 3 b T 5 3, 5 4 4, 5 3 333 0 5 30 5 4 40 5 3 333 ， 155 3 231 4,0 26,0 132 第第39頁(yè)頁(yè) 解：解： cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/

25、20-1/5 301001/5 400-214/5 00-10-1/5 3 2 1 1 15 16 12 5/100 5/412 5/102/1 bB T 5 3, 5 4 24, 52 3 33 21 31 )15,16,12( 321 b 321 、 0 5 3 0 5 4 24 , 0 52 3 3 3 21 31 15 5/442 65/2 3 312 31 第第40頁(yè)頁(yè) 6-3 增加新變量增加新變量(增加新產(chǎn)品增加新產(chǎn)品) cjc1c2cn CB基基bx1x2xn CBXBB-1bIB-1N j0CN - CBB-1N 分析步驟：分析步驟： jjjBjj YPcPBCc 1 jj P

26、BP 1 0 j 0 j j j P 第第41頁(yè)頁(yè) 21 32maxxxz 1222 21 xx 164 1 x 155 2 x 0, 21 xx s.t. cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 解：解： 1 5 4 2 )5/1, 0, 1(4 6 jj PBP 1 1 4 0 5 4 2 5/100 5/412 5/102/1 1 1 4 0 )3, 0, 2(4 6 第第42頁(yè)頁(yè) cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x

27、4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 構(gòu)造新表構(gòu)造新表 cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 4 x6 0 4 1 1 利用單純形利用單純形 法繼續(xù)迭代法繼續(xù)迭代 第第43頁(yè)頁(yè) 6-4 增加約束條件增加約束條件(增加工序增加工序) 分析步驟：分析步驟： 21 32maxxxz 1222 21 xx 164 1 x 155 2 x 0, 21 xx s.t. cj 23000 CB基基bx1x2

28、x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 1423 21 xx 第第44頁(yè)頁(yè) cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 解：解： 1423 21 xx 構(gòu)造新表構(gòu)造新表 cj 23000 CB基基bx1x2x3x4x5 2x13101/20-1/5 0 x4400-214/5 3x2301001/5 cj -zj00-10-1/5 1423 621 xxx 0 x6

29、 0 0 0 1 0 0 x614 2x13101/20-1/50 0 x4400-214/50 3x2301001/50 0 x6-100-3/201/51 cj -zj00-10-1/50 32000 第第45頁(yè)頁(yè) 2x13101/20-1/50 0 x4400-214/50 3x2301001/50 0 x6-100-3/201/51 cj -zj00-10-1/50 cj 23000 CB基基bx1x2x3x4x5 0 x6 對(duì)偶單對(duì)偶單 純形法純形法 2x18/31000-2/151/3 0 x416/300018/15-4/3 3x2301001/50 0 x32/30010-2/

30、15-2/3 cj -zj0000-1/3-2/3 最優(yōu)解最優(yōu)解 最優(yōu)值最優(yōu)值 第第46頁(yè)頁(yè) 21 32maxxxz 1222 21 xx 164 1 x 155 2 x 0, 21 xx s.t. cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 1623 21 xx 1423 21 xx 第第47頁(yè)頁(yè) 21 32maxxxz 1222 21 xx 164 1 x 155 2 x 0, 21 xx s.t. cj 23000 CB基基bx1x2x3x4x5 cj -z

31、j x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 1423 21 xx 解：解： cj 23000 CB基基bx1x2x3x4x5 2x13101/20-1/5 0 x4400-214/5 3x2301001/5 cj -zj00-10-1/5 0 x6 0 0 0 1 0 0 x6-14-3-2000 1423 621 xxx 第第48頁(yè)頁(yè) cj 23000 CB基基bx1x2x3x4x5 2x13101/20-1/5 0 x4400-214/5 3x2301001/5 cj -zj00-10-1/5 0 x6 0 0 0 1

32、 0 0 x6-14-3-2000 2x13101/20-1/50 0 x4400-214/50 3x2301001/50 0 x61003/20-1/51 cj -zj00-10-1/50 第第49頁(yè)頁(yè) 21 32maxxxz 1222 21 xx 164 1 x 155 2 x 0, 21 xx s.t. cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 1623 21 xx 解：解： 1623 621 xxx 構(gòu)造新表構(gòu)造新表 cj 23000 CB基基bx1x2

33、x3x4x5 2x13101/20-1/5 0 x4400-214/5 3x2301001/5 cj -zj00-10-1/5 0 x6 0 0 0 -1 0 0 x61632000 第第50頁(yè)頁(yè) cj 23000 CB基基bx1x2x3x4x5 2x13101/20-1/5 0 x4400-214/5 3x2301001/5 cj -zj00-10-1/5 0 x6 0 0 0 -1 0 0 x61632000 2x13101/20-1/50 0 x4400-214/50 3x2301001/50 0 x6-1003/20-1/51 cj -zj00-10-1/50 2x1410-100-1

34、 0 x40004104 3x22013/2001 0 x3500-15/201-5 cj -zj00-5/200-1 第第51頁(yè)頁(yè) 2-7 參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃 靈敏度分析：靈敏度分析： 參數(shù)線性規(guī)劃：參數(shù)線性規(guī)劃： 第第52頁(yè)頁(yè) 21 )3()22()(maxxxz 1222 21 xx 164 1 x 155 2 x 0, 21 xx s.t. 解：解： cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 將參數(shù)的變化反映到最將參數(shù)的變化反映到最 終單純形表中，

35、得終單純形表中，得 cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-101/5 22 22 1 5 1 3 3 01 0 5 1 , 11 第第53頁(yè)頁(yè) cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-101/5 22 22 1 5/ )1( 3 3 0 x362010-2/5 0 x41640010 x2301001/5 cj -zj000 22 5/ )3 ( 13

36、 3 0 x31222100 0 x41640010 0 x51505001 cj -zj000 22 11 3 3 第第54頁(yè)頁(yè) cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x5 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-101/5 22 22 1 5/ )1( 3 3 0 x141001/40 0 x5500-5/25/41 x22011/2-1/40 cj -zj000 1 11 3 22 4 1 2 )3( 第第55頁(yè)頁(yè) 21 32maxxxz 1222 21 xx 164 1 x 155 2 x 0, 21 xx

37、s.t. 解：解： cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 3101/20-1/5 301001/5 400-214/5 00-10-1/5 將參數(shù)的變化反映到最終單純形表中將參數(shù)的變化反映到最終單純形表中 cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 101/20-1/5 01001/5 00-214/5 00-101/5 05/3, 05/44, 05/3 155 5 3 5 4 4 5 3 15 16 12 5/100 5/412 5/102/1 1 bB 5/3 5/3 5/44 第第

38、56頁(yè)頁(yè) cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 101/20-1/5 01001/5 00-214/5 00-101/5 155 5/3 5/3 5/44 迭迭代代利利用用對(duì)對(duì)偶偶單單純純形形法法繼繼續(xù)續(xù)時(shí)時(shí)當(dāng)當(dāng), 0,5 4 x 2x141001/40 0 x3 001-1/2-2/5 3x2201001/5 cj -zj000-1/2-3/5 5/3 5/22 515 時(shí)時(shí)，本本題題無(wú)無(wú)可可行行解解當(dāng)當(dāng)15 第第57頁(yè)頁(yè) cj 23000 CB基基bx1x2x3x4x5 cj -zj x1 x4 x2 2 0 3 101/20-1/5

39、 01001/5 00-214/5 00-101/5 155 5/3 5/3 5/44 迭迭代代利利用用對(duì)對(duì)偶偶單單純純形形法法繼繼續(xù)續(xù)時(shí)時(shí)當(dāng)當(dāng), 0,15 1 x 0 x5-50-5/201 0 x416 40010 3x26111/200 cj -zj-10-3/200 15 15 第第58頁(yè)頁(yè) 課后習(xí)題選講課后習(xí)題選講 2-1 寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 ), 1;, 1(0 ), 1( ), 1( . min 1 1 11 njmix njbx miax ts xcz ij m i jij n j iij m i n j ijij ), 1(miyai

40、 無(wú)無(wú)約約束束 ), 1(njybj 無(wú)無(wú)約約束束 m i n j bjjaii ybyaw 11 max ijbjai cyy 第第59頁(yè)頁(yè) 2-2 判斷下列說(shuō)法是否正確，為什么？判斷下列說(shuō)法是否正確，為什么？ 第第60頁(yè)頁(yè) 2-3 應(yīng)用對(duì)偶理論證明下述線性規(guī)劃問(wèn)題為無(wú)界解。應(yīng)用對(duì)偶理論證明下述線性規(guī)劃問(wèn)題為無(wú)界解。 0, 0, 0 12 2 . max 321 321 321 21 xxx xxx xxx ts xxz 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 原問(wèn)題原問(wèn)題 0, 0 0 1 12 . 2min 21 21 21 21 21 yy yy yy yy ts yyw 無(wú)可行解無(wú)可行解 因?yàn)閷?duì)偶問(wèn)題無(wú)可

41、行解，所因?yàn)閷?duì)偶問(wèn)題無(wú)可行解，所 以原問(wèn)題無(wú)可行解或無(wú)界解以原問(wèn)題無(wú)可行解或無(wú)界解 而而(0,0,0)是原問(wèn)題的可行解，是原問(wèn)題的可行解， 所以原問(wèn)題無(wú)界解所以原問(wèn)題無(wú)界解 第第61頁(yè)頁(yè) 2-4 已知線性規(guī)劃問(wèn)題：已知線性規(guī)劃問(wèn)題： )4 , 3 , 2 , 1(0 9 6 62 83 . 42max 321 432 21 421 4321 jx xxx xxx xx xxx ts xxxxz j 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 )4 , 3 , 2 , 1(0 1 1 43 22 . 9668min 31 43 4321 421 4321 iy yy yy yyyy yyy ts yyyyw i 要求要求

42、: (a)寫出其對(duì)偶問(wèn)題；寫出其對(duì)偶問(wèn)題； (b)已知原問(wèn)題最優(yōu)解為已知原問(wèn)題最優(yōu)解為 根據(jù)對(duì)偶理論根據(jù)對(duì)偶理論, 直接求出對(duì)偶直接求出對(duì)偶 問(wèn)題的最優(yōu)解問(wèn)題的最優(yōu)解. )0 , 4 , 2 , 2( X 由互補(bǔ)松弛性得由互補(bǔ)松弛性得 1 43 22 43 4321 421 yy yyyy yyy 由目標(biāo)函數(shù)相等得由目標(biāo)函數(shù)相等得 169668 4321 yyyy 第第62頁(yè)頁(yè) 2-5 已知線性規(guī)劃問(wèn)題已知線性規(guī)劃問(wèn)題A和和B如下：如下： 問(wèn)題問(wèn)題A 問(wèn)題問(wèn)題B ), 1(0 . max 1 33 1 22 1 11 1 njx bxa bxa bxa ts xcz j n j jj n j jj n j jj n j jj ), 1(0 3)3( 55 55 . max 1 1313 1 2 2 1 11 1 njx bbxaa b x a bxa ts xcz j n j jjj n j j j n j jj n j jj 對(duì)偶對(duì)偶 變量變量 對(duì)偶對(duì)偶 變量變量 3 2 1 y y y 3 2 1 y y y ) 3 , 2 , 1( iyi 第第63頁(yè)頁(yè) ), 1(0 . max 1 33 1 22 1 11 1 njx bxa bxa bxa ts xcz j n j jj n j jj n j jj n j jj ), 1(0 3)3( 55 55 . max 1 13