线性规划对偶理论

1、第第1页页 线性规划问题具有对偶性线性规划问题具有对偶性, ,即任何一个线性规划问即任何一个线性规划问 题题, ,都存在另一个线性规划问题问题与之对应都存在另一个线性规划问题问题与之对应. .如果如果 把其中一个问题叫做原问题把其中一个问题叫做原问题, ,则另外一个就叫做它则另外一个就叫做它 的对偶问题的对偶问题. .并称这两个相互联系的问题为一对对并称这两个相互联系的问题为一对对 偶问题偶问题. .研究对偶问题之间的关系及其性质研究对偶问题之间的关系及其性质, ,就是线就是线 性规划的对偶理论性规划的对偶理论(Duality(DualityTheory).Theory). 第第2章章 线性规

2、划的对偶理论线性规划的对偶理论 第第2页页 |1 对偶问题的提出对偶问题的提出 |2 原问题与对偶问题原问题与对偶问题 |3 对偶问题的基本性质对偶问题的基本性质 |4 影子价格影子价格 |5 对偶单纯形法对偶单纯形法 |6 灵敏度分析灵敏度分析 |7 参数线性规划参数线性规划 第第3页页 常山机器厂用常山机器厂用A、B、C三种设备生产三种设备生产I、II两种两种 产品。问该企业应安排生产使总的利润收入为最大。产品。问该企业应安排生产使总的利润收入为最大。 占用设备占用设备 时间时间(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 对偶问题的基本性质对偶问题的基本性质 弱对偶性；强对偶性；弱对偶性；强对偶性； 最优性最优性; 无界性无界性; 互补松弛性互补松弛性 ), 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页页 灵敏度分析的步骤灵敏度分析的步骤 原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的

17、步骤 可行解可行解可行解可行解仍为最优解仍为最优解 可行解可行解非可行解非可行解用单纯形法继续迭代用单纯形法继续迭代 非可行解非可行解可行解可行解用对偶单纯形法继续迭代用对偶单纯形法继续迭代 非可行解非可行解非可行解非可行解引入人工变量引入人工变量, 编制新的单纯表编制新的单纯表, 重新计算重新计算 第第31页页 6-1 价值系数价值系数cj发生变化发生变化(仅影响检验数仅影响检验数) 单单 纯纯 形形 表表 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 原问题原问题对偶问题对偶问题 结论或继续计结论或继续计 算的步骤算的步骤 可行解可行解可行解可行解仍为最优解仍为最优解 可行解可行解非可行解非可行解 用单纯形法继用单纯形法继 续迭代续迭代 非可行解非可行解可行解可行解 用对偶单纯形用对偶单纯形 法继续迭代法继续迭代 非可行解非可行解非可行解非可行解 引入人工变量引入人工变量, 编制新的单纯编制新的单纯

22、 表表, 重新计算重新计算 bi的变化引起基变量的的变化引起基变量的 取值发生变化，有可取值发生变化，有可 能发生能发生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 利用单纯形利用单纯形 法继续迭代法继续迭代 第第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 最优解最优解 最优值最优值 第第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 参数线性规划参数线性规划 灵敏度分析：灵敏度分析： 参数线性规划：参数线性规划： 第第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 迭迭代代利利用用对对偶偶单单纯纯形形法法继继续续时时当当, 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 迭迭代代利利用用对对偶偶单单纯纯形形法法继继续续时时当当, 0,15 1 x 0 x5-50-5/201 0 x416 40010 3x26111/200 cj -zj-10-3/200 15 15 第第58页页 课后习题选讲课后习题选讲 2-1 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题 ), 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 应用对偶理论证明下述线性规划问题为无界解。应用对偶理论证明下述线性规划问题为无界解。 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 已知线性规划问题：已知线性规划问题： )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)已知原问题最优解为已知原问题最优解为 根据对偶理论根据对偶理论, 直接求出对偶直接求出对偶 问题的最优解问题的最优解. )0 , 4 , 2 , 2( X 由互补松弛性得由互补松弛性得 1 43 22 43 4321 421 yy yyyy yyy 由目标函数相等得由目标函数相等得 169668 4321 yyyy 第第62页页 2-5 已知线性规划问题已知线性规划问题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