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

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

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

3、利潤(元元)23 例例1 1 生產計劃問題生產計劃問題 2-1 對偶問題的提出對偶問題的提出 模模 型型 21 32maxxx 1222 21 xx 164 1 x 155 2 x 0, 21 xx s.t. 設設備設設備A, B, C每小時的出租價格分每小時的出租價格分 別為別為y1, y2,和和y3元元 出租條件出租條件: 租金收入租金收入生產的獲利。生產的獲利。 四海機器廠接受條件四海機器廠接受條件: 租金要低租金要低 0, 352 242 151612min 321 31 21 321 yyy yy yy yyyw 第第4頁頁 ), 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頁頁 2-2 原問題與對偶問題原問題與對偶問題 minmax 第第6頁頁 原問題原問題(求極大求極大) c1c2cn右端右端 項項 x1x2xn a11a12a1n a21a22a2n am1am2amn m b b b 2 1 n ccc 21 y1 y2 ym b1 b2 bm 對偶對偶 問題問題 (求極求極 小小) 右端項右端項

5、 第第7頁頁 原問題原問題(對偶問題對偶問題)對偶問題對偶問題(原問題原問題) 無無約約束束 個個 變變量量 0 0 n 個個 約約束束條條件件 m 約約束束條條件件 個個 n 變變量量 個個 0 0 m 目標函數目標函數max目標函數目標函數min 目標函數中變量的系數目標函數中變量的系數約束條件右端項約束條件右端項 約束條件右端項約束條件右端項目標函數中變量的系數目標函數中變量的系數 第第8頁頁 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 無無約約束束 第第9頁頁 0, 0 8374 35 522 .)1( 365max 32 321 321 321 321 xx xxx xxx xxx ts xxxz 321 835minyyyw 無無約約束束 1 y 0 2 y 0 3 y 54 321 yyy 6752 321 yyy 332 321 yyy 第第10頁頁 ), 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 無無約約束束 m i ii ybw 1 min ), 1(0 1 miyi ), 1( 1 mmiyi 無無約約束束 m i jiij njcya 1 1) , 1( m i jiij nnjcya 1 1 ), 1( 第第11頁頁 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 無無約約束束 1 x 0 2 x 8374 321 xxx 5

8、22 321 xxx 第第12頁頁 2-3 對偶問題的基本性質對偶問題的基本性質 弱對偶性；強對偶性；弱對偶性；強對偶性； 最優(yōu)性最優(yōu)性; 無界性無界性; 互補松弛性互補松弛性 ), 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 掌握原問題和掌握原問題和 其對偶問題解其對偶問題解 之間的關系之間的關系 第第13頁頁 ), 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頁頁 ), 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頁頁 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頁頁 , 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頁頁 jjji czy , 第第18頁頁 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頁頁 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頁頁 目標函數值目標函數值 原問題原問題

13、對偶問題對偶問題 第第21頁頁 2-4 影子價格影子價格 m i ii n j jj ybxcz 11 i b i y 影子影子 價格價格 說明：說明： i i y b z 第第22頁頁 , 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頁頁 2-5 對偶單純形法對偶單純形法 單純形法計算的基本思想：單純形法計算的基本思想： 即即 0 1 bB0 1 bB 0 1 ABcc B 對偶單純形法的基本思想：對偶單純形法的基本思想： 0 1 ABcc B 0 1 b

14、B 0 1 ABcc B 即即 第第24頁頁 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 對偶單純形法的初始單純形表：對偶單純形法的初始單純形表： cj zj 0 ( j= 1,n ) ), 1(mibi 第第25頁頁 0|min ii i r bbb ,0min rs ss rj rj jj j a zc a a zc ), 1(0mibi . 0, 10 rjr anjb有有，而而對對所所有有對對 rnrnmmrr bx

15、axax 11, 第第26頁頁 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頁頁 ), 1(0 ), 1( . )0(min 1 1 njx mibxa ts cxcz j n j ijij j n j jj 第第28頁頁 |概況概況 |改變價值向量改變價值向量 |改變右端向量改變右端向量 |增加變量增加變量 |增加約束條件增加約束條件 2-6 靈敏度分析靈敏度分析 第第29頁頁 1. 靈敏度分析的含義靈敏度分析的含義 |概況概況 2. 靈敏度分析研究的問題靈敏度分析研究的問題 3. 如何解決如何解決 第第30頁頁 靈敏度分析的步驟靈敏度分析的步驟 原問題原問題對偶問題對偶問題結論或繼續(xù)計算的步驟結論或繼續(xù)計算的

17、步驟 可行解可行解可行解可行解仍為最優(yōu)解仍為最優(yōu)解 可行解可行解非可行解非可行解用單純形法繼續(xù)迭代用單純形法繼續(xù)迭代 非可行解非可行解可行解可行解用對偶單純形法繼續(xù)迭代用對偶單純形法繼續(xù)迭代 非可行解非可行解非可行解非可行解引入人工變量引入人工變量, 編制新的單純表編制新的單純表, 重新計算重新計算 第第31頁頁 6-1 價值系數價值系數cj發(fā)生變化發(fā)生變化(僅影響檢驗數僅影響檢驗數) 單單 純純 形形 表表 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頁頁 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頁頁 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頁頁 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頁頁 6-2 分析分析bi的變化范圍的變化范圍 cjc1c2cn CB基基bx1x2xn CBXBB-1bIB-1N j0CN - CBB-1N 原問題原問題對偶問題對偶問題 結論或繼續(xù)計結論或繼續(xù)計 算的步驟算的步驟 可行解可行解可行解可行解仍為最優(yōu)解仍為最優(yōu)解 可行解可行解非可行解非可行解 用單純形法繼用單純形法繼 續(xù)迭代續(xù)迭代 非可行解非可行解可行解可行解 用對偶單純形用對偶單純形 法繼續(xù)迭代法繼續(xù)迭代 非可行解非可行解非可行解非可行解 引入人工變量引入人工變量, 編制新的單純編制新的單純

22、 表表, 重新計算重新計算 bi的變化引起基變量的的變化引起基變量的 取值發(fā)生變化，有可取值發(fā)生變化，有可 能發(fā)生能發(fā)生1、3兩種情況兩種情況 第第36頁頁 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頁頁 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頁頁 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頁頁 解：解： 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頁頁 6-3 增加新變量增加新變量(增加新產品增加新產品) 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頁頁 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頁頁 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 構造新表構造新表 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頁頁 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頁頁 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 構造新表構造新表 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頁頁 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 對偶單對偶單 純形法純形法 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頁頁 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頁頁 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頁頁 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頁頁 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 構造新表構造新表 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頁頁 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頁頁 2-7 參數線性規(guī)劃參數線性規(guī)劃 靈敏度分析：靈敏度分析： 參數線性規(guī)劃：參數線性規(guī)劃： 第第52頁頁 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 將參數的變化反映到最將參數的變化反映到最 終單純形表中，

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頁頁 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頁頁 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頁頁 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 將參數的變化反映到最終單純形表中將參數的變化反映到最終單純形表中 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頁頁 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 迭迭代代利利用用對對偶偶單單純純形形法法繼繼續(xù)續(xù)時時當當, 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 時時，本本題題無無可可行行解解當當15 第第57頁頁 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 迭迭代代利利用用對對偶偶單單純純形形法法繼繼續(xù)續(xù)時時當當, 0,15 1 x 0 x5-50-5/201 0 x416 40010 3x26111/200 cj -zj-10-3/200 15 15 第第58頁頁 課后習題選講課后習題選講 2-1 寫出下列線性規(guī)劃問題的對偶問題寫出下列線性規(guī)劃問題的對偶問題 ), 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、 無無約約束束 ), 1(njybj 無無約約束束 m i n j bjjaii ybyaw 11 max ijbjai cyy 第第59頁頁 2-2 判斷下列說法是否正確，為什么？判斷下列說法是否正確，為什么？ 第第60頁頁 2-3 應用對偶理論證明下述線性規(guī)劃問題為無界解。應用對偶理論證明下述線性規(guī)劃問題為無界解。 0, 0, 0 12 2 . max 321 321 321 21 xxx xxx xxx ts xxz 對偶問題對偶問題 原問題原問題 0, 0 0 1 12 . 2min 21 21 21 21 21 yy yy yy yy ts yyw 無可行解無可行解 因為對偶問題無可

41、行解，所因為對偶問題無可行解，所 以原問題無可行解或無界解以原問題無可行解或無界解 而而(0,0,0)是原問題的可行解，是原問題的可行解， 所以原問題無界解所以原問題無界解 第第61頁頁 2-4 已知線性規(guī)劃問題：已知線性規(guī)劃問題： )4 , 3 , 2 , 1(0 9 6 62 83 . 42max 321 432 21 421 4321 jx xxx xxx xx xxx ts xxxxz j 對偶問題對偶問題 )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)寫出其對偶問題；寫出其對偶問題； (b)已知原問題最優(yōu)解為已知原問題最優(yōu)解為 根據對偶理論根據對偶理論, 直接求出對偶直接求出對偶 問題的最優(yōu)解問題的最優(yōu)解. )0 , 4 , 2 , 2( X 由互補松弛性得由互補松弛性得 1 43 22 43 4321 421 yy yyyy yyy 由目標函數相等得由目標函數相等得 169668 4321 yyyy 第第62頁頁 2-5 已知線性規(guī)劃問題已知線性規(guī)劃問題A和和B如下：如下： 問題問題A 問題問題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 對偶對偶 變量變量 對偶對偶 變量變量 3 2 1 y y y 3 2 1 y y y ) 3 , 2 , 1( iyi 第第63頁頁 ), 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