运筹学第三版_刁在筠课后答案(2-4章)

1、 课后答案网，用心为你服务！ 大学答案 - 中学答案 - 考研答案 - 考试答案 最全最多的课后习题参考答案，尽在课后答案网（）！ khdaw团队一直秉承用心为大家服务的宗旨，以关注学生的学习生活为出发点， 旨在为广大学生朋友的自主学习提供一个分享和交流的平台。 爱校园（） 课后答案网（） 淘答案（） 运筹学作业参考解答 第二章第二章 线性规划线性规划 73 p 4. 将下面的线性规划问题化成标准形式将下面的线性规划问题化成标准形式 123 123 123 1 2 max2 . .236 23 03 16 xxx stxxx xxx x x + + + 解：解：将 max 化为 min， 3

2、x 用 45 xx代替，则 1245 1245 1245 1 2 45 min2() . .23()6 2()3 03 16 ,0 xxxx stxxxx xxxx x x x x + + + 令 22 1xx = + ，则 1245 1245 1245 1 2 45 min12() . .2(1)3()6 2(1)()3 03 07 ,0 xxxx stxxxx xxxx x x x x + + + 将线性不等式化成线性等式，则可得原问题的标准形式 1245 12456 12457 18 29 12456789 min221 . .2334 24 3 7 ,0 xxxx stxxxxx xx

3、xxx xx xx x x xx x xx x + += += += + = 73 p 5、用图解法求解下列线性规划问题： (1) 12 12 1 2 min3 . .20 612 2 xx stxx x x + + 解：解：图2.1的阴影部分为此问题的可行区域.将 目标函数的等值线 12 3xxc+=(c为常数)沿它的 负法线方向()13 t ，移动到可行区域的边界上. 于是交点 t ），（812就是该问题的最优解， 其最优 值为 36. 75 p 16. 用单纯形法求解下列线性规划问题：用单纯形法求解下列线性规划问题： 等值线 20 12 8 x1 o x2 法线方向 图 2.1 w w

4、w .k h d a w .c o m 课后答案网 运筹学作业参考解答 (1) 123 123 123 123 min2 . .360 210 20 0,1, 2,3 j zxxx stxxx xxx xxx xj = + + + + = 解：将此问题化成标准形式标准形式 123 1234 1235 1236 min2 . .360 210 20 0,1, 2,3, 4,5,6 j zxxx stxxxx xxxx xxxx xj = + += += += = 以 456 ,x x x为基变量，可得第一张单纯形表为 以 1 x为进基变量， 5 x为离基变量旋转得 以 2 x为进基变量， 6 x

5、为离基变量旋转得 1 x 2 x 3 x 4 x 5 x 6 x rhs z 21 -1 0 000 4 x 31 1 1 0060 5 x 1-1 2 0 1010 6 x 11 -1 0 0120 1 x 2 x 3 x 4 x 5 x 6 x rhs z 03 -5 0 -20-20 4 x 04 -5 1 -3030 1 x 1-1 2 0 1010 6 x 02 -3 0 -1110 1 1 注意单纯形表的格式！ 2 注意单纯形表的格式！ 2 要用记号把转轴元标出来 3 要用记号把转轴元标出来 3 要记住在单纯形表的左边，用 进基变量代替离基变量 要记住在单纯形表的左边，用 进基变量

6、代替离基变量 注（零行元素的获得） ：先将目标函 数化成求最小值的形式， 再把所有变 量移到等式左边，常数移到等式右 边。 则变量前的系数为零行对应的元 素. 注（零行元素的获得） ：先将目标函 数化成求最小值的形式， 再把所有变 量移到等式左边，常数移到等式右 边。 则变量前的系数为零行对应的元 素. w w w .k h d a w .c o m 课后答案网 运筹学作业参考解答 将第0行的元素化为检验数可得 由于 4 x的检验数01 4 =，并且 4 x在典式中的系数向量0)0, 0, 1, 0( 4 = t a，所 以问题无界. 75 p 17. 用两阶段法求解下列线性规划问题：用两阶段

7、法求解下列线性规划问题： (2) 12 12 12 12 min24 . .232 3 ,0 zxx stxx xx xx =+ + 解：解：将此问题化为标准形式 12 123 124 1234 min24 . .23 2 3 ,0 zxx stxxx xxx xxx x =+ = += 添加人工变量 65,x x得到辅助问题 1 x 2 x 3 x 4 x 5 x 6 x 7 x rhs z -11 -1 0 -11 0 0 5 x 00 3 0 11 0 6 2 x 01 2 -100 0 10 1 x 10 0 0 0-1 0 0 7 x 00 1 0 01 1 6 1 x 2 x 3

8、x 4 x 5 x 6 x 7 x rhs z 00 0 1 01 0 -4 5 x 00 3 0 11 0 6 2 x 01 2 -100 0 10 1 x 10 0 0 0-1 0 0 7 x 00 1 0 01 1 6 注： 必须先将线性方程 组和目标函数化成典 式， 再用单纯形方法开 始判定、迭代！ 注： 必须先将线性方程 组和目标函数化成典 式， 再用单纯形方法开 始判定、迭代！ w w w .k h d a w .c o m 课后答案网 运筹学作业参考解答 56 1235 1246 123456 min . .23 2 3 ,0 gxx stxxxx xxxx xx x xx x

9、=+ += += 以 65,x x为基变量，可得辅助问题的单纯形表为 把g所在的这一行的元素化成检验数 以 1 x为进基变量， 5 x为离基变量旋转得 所以，辅助问题的最优解为 * (1,0,0,0,0,4)tx=，其最优值为 * 40g=.因此，原问题没有 可行解. 1 x 2 x 3 x 4 x 5 x 6 x rhs z -2-4 0 00 00 g 00 0 0-1 -10 5 x 2-3 -1 01 02 6 x -11 0 -10 13 1 x 2 x 3 x 4 x 5 x 6 x rhs z -2-4 0 0000 g 1-2 -1 -1005 5 x 2-3 -1 0102

10、6 x -11 0 -1013 1 x 2 x 3 x 4 x 5 x 6 x rhs z 0-7 -1 01 02 g 0 2 1 2 1 -1 2 1 04 1 x 1 2 3 2 1 0 2 1 01 6 x 0 2 1 2 1 -1 2 1 14 w w w .k h d a w .c o m 课后答案网 运筹学作业参考解答 (4) 1234 1234 1234 1234 max2456 . . 42 8 2 23 41 ,0 zxxxx stxxxx xxxx xxx x =+ += += 解：将此问题化成标准形式 1234 1234 1234 1234 min2456 . . 42

11、 8 2 23 41 ,0 zxxxx stxxxx xxxx xxx x = + += += 添加人工变量 65,x x得到辅助问题 56 12345 12346 123456 min . . 42 8 2 23 4 1 ,0 gxx stxxxxx xxxxx xxx xx x =+ += += 以 56 ,x x为基变量，可得辅助问题的单纯形表为 把g所在的这一行的元素化成检验数 以 4 x为进基变量， 5 x为离基变量旋转得 1 x 2 x 3 x 4 x 5 x 6 x rhs z 2-4 5 -6000 g 00 0 0-1-10 5 x 14 -2 8102 6 x -12 3

12、4011 1 x 2 x 3 x 4 x 5 x 6 x rhs z 2-4 5 -6000 g 06 1 12003 5 x 14 -2 8102 6 x -12 3 4011 w w w .k h d a w .c o m 课后答案网 运筹学作业参考解答 以 3 x为进基变量， 6 x为离基变量旋转得 所以，辅助问题的最优解为 1 (0,0,0,0,0) 4 t x =，其最优值为0g =.因此，原问题的初始 解为 0 1 (0,0,0, ) 4 t x =，其第一张单纯形表为 以 1 x为进基变量， 4 x为离基变量旋转得 1 x 2 x 3 x 4 x 5 x 6 x rhs z 4

13、11 -1 2 7 0 4 3 0 2 3 g 2 3 0 4 0 2 3 00 4 x 8 1 2 1 4 1 1 8 1 0 4 1 6 x 2 3 0 4 0 2 1 10 1 x 2 x 3 x 4 x 5 x 6 x rhs z 16 65 -1 0 0 16 19 8 7 2 3 g 0 0 0 0-1 -1 0 4 x 32 1 2 1 0 1 32 3 16 1 4 1 3 x 8 3 0 1 0 8 1 4 1 0 1 x 2 x 3 x 4 xrhs z 16 65 -1 0 0 2 3 4 x 32 1 2 1 0 1 4 1 3 x 8 3 0 1 00 w w w .

14、k h d a w .c o m 课后答案网 运筹学作业参考解答 因此，原问题的最优解为 * (8,0,3,0)tx =，最优值为31. 76 p 18. 写出下列线性规划问题的对偶规划：写出下列线性规划问题的对偶规划： 123 123 123 123 123 min24 . .2342 263 355 ,0, zxxx stxxx xxx xxx x xx =+ + += + 为自由变量 解：解：先将此问题化成一般形式 123 123 123 123 123 min24 . .2342 263 355 ,0, zxxx stxxx xxx xxx x xx =+ + += 为自由变量 所以，

15、其对偶规划为 123 123 123 123 132 max235 . .221 332 4654 ,0, st + + + += 为自由变量 77 p 20. 给定线性规划问题给定线性规划问题 13 12 23 123 min . .25 1 3 2 ,0 zxx stxx xx x xx =+ + += 记为(p) (1)用单纯形算法解p; 1 x 2 x 3 x 4 x rhs z 0-66 0 -130-31 1 x 116 0 32 8 3 x 06 1 12 3 w w w .k h d a w .c o m 课后答案网 运筹学作业参考解答 (2)写出p的对偶问题d; (3)写出p

16、的互补松紧条件,并利用它们解对偶d; 解：解：(1) 把问题(p)化为标准形式 13 124 23 1234 min . .25 1 3 2 ,0 zxx stxxx xx x xxx =+ += += 以 31,x x为基变量，可得到其单纯形表为: 把第0行化成检验行，得 以 2 x为进基变量， 1 x为离基变量，旋转得 根据最优化准则知，问题(p)的最优解为 * 5 7 (0,) 2 4 t x =, 最优值为 4 7 . (2) 将问题(p)化为一般形式 1 x 2 x 3 x 4 xrhs z -10 -1 00 1 x 12 0 15 3 x 0 2 1 1 03 1 x 2 x 3

17、 x 4 xrhs z 0 2 5 0 18 1 x 12 0 15 3 x 0 2 1 1 03 1 x 2 x 3 x 4 xrhs z 4 5 0 0 4 1 4 7 2 x 2 1 1 0 2 1 2 5 3 x 4 1 0 1 4 1 4 7 w w w .k h d a w .c o m 课后答案网 运筹学作业参考解答 13 12 23 123 min . .25 1 3 2 ,0 zxx stxx xx x xx =+ += 因此其对偶问题(d)为 12 1 12 2 1 max53 . .1 1 20 2 1 0 st + + (3) 由问题(p)的最优解为 * 5 7 (0,

18、) 2 4 t x =以及互补松紧性定律可得 12 2 1 20 2 1 += = 解得 12 1 ,1 4 = .所以，对偶问题(d)的最优解为 * 1 ( ,1) 4 t =，最优值为 4 7 35 21 =+. 77 p 22. 用对偶单纯形法解下列问题用对偶单纯形法解下列问题. (1) 123 123 123 min234 . .23 234 0,1, 2,3. i zxxx stxxx xxx xi =+ + + = 解：解：引入剩余变量将原问题标准化 123 1234 1235 min234 . .23 234 0,1, 2,3, 4,5. i zxxx stxxxx xxxx x

19、i =+ += += = 再将约束条件两边同时乘以 1 得 123 1234 1235 min234 . .23 234 0,1, 2,3, 4,5. i zxxx stxxxx xxxx xi =+ += += = 以 45 ,x x为基变量，可得其单纯形表为 注：若问题存在一个基本解，并且该解 的检验数向量小于等于零，则可使用对 偶单纯形方法。特别地，要将问题典式 化 注：若问题存在一个基本解，并且该解 的检验数向量小于等于零，则可使用对 偶单纯形方法。特别地，要将问题典式 化 w w w .k h d a w .c o m 课后答案网 运筹学作业参考解答 以 5 x为离基变量， 1 x为

20、进基变量，旋转得 以 4 x为离基变量， 2 x为进基变量，旋转得 根据最优化准则知，原问题的最优解为 t x)0, 5 2 , 5 11 ( * =, 最优值为 5 28 . *用对偶单纯形方法求解线性规划问题的步骤： 1 *用对偶单纯形方法求解线性规划问题的步骤： 1 将问题化成标准形式； 2 将问题化成标准形式； 2 找出初始解； 3 找出初始解； 3 写出第一张单纯形表，并化成典式； 4 写出第一张单纯形表，并化成典式； 4 判定和迭代. 判定： 最优解(右端向量 判定和迭代. 判定： 最优解(右端向量0b)； 没有可行解(某个)； 没有可行解(某个 0 r b ，并且在 典式中 ，并

21、且在 典式中 r b所在的这一行内没有负分量) 迭代步骤： 确定离基变量 所在的这一行内没有负分量) 迭代步骤： 确定离基变量 r x (右端向量最小的负分量) (右端向量最小的负分量) 1 x 2 x 3 x 4 x 5 x rhs z -2 -3 -4 0 00 4 x -1 -2 -1 1 0-3 5 x -21 -3 0 1-4 1 x 2 x 3 x 4 x 5 x rhs z 0 -4 -1 0 -1 4 4 x 0 2 5 2 1 1 2 1 -1 1 x 1 2 1 2 3 0 2 1 2 1 x 2 x 3 x 4 x 5 x rhs z 0 0 5 9 5 8 5 1 5

22、28 2 x 0 1 5 1 5 2 5 1 5 2 1 x 1 0 5 7 5 1 5 2 5 11 w w w .k h d a w .c o m 课后答案网 运筹学作业参考解答 确定转轴元 确定转轴元 rk a (离基变量所在的这一行中的负分量与 (离基变量所在的这一行中的负分量与 t 中对应元素 比值最小的) 确定进基变量 中对应元素 比值最小的) 确定进基变量 k x(转轴元所在的这一列对应的非基变量) 迭代计算(利用初等行变换，将转轴元变为 1，转轴元所在的这一列其它元素 全部变为 0)； 用进基变量 (转轴元所在的这一列对应的非基变量) 迭代计算(利用初等行变换，将转轴元变为 1

23、，转轴元所在的这一列其它元素 全部变为 0)； 用进基变量 k x代替离基变量 代替离基变量 r x. . (2) 123 123 13 23 min32 . .6 4 3 0,1, 2,3. i zxxx stxxx xx xx xi =+ + = 解：解：先将原问题标准化 123 1234 135 236 min32 . . 6 4 3 0,1, 2,3, 4,5, 6. i zxxx stxxxx xxx xxx xi =+ += = = = 在第2、3个等式的两端同乘以-1，并以 45 ,xx为基变量，可得其单纯形表为 以 5 x为离基变量， 1 x为进基变量，旋转得 1 x 2 x

24、3 x 4 x 5 x 6 x rhs z -3-2 -1 0 000 4 x 11 1 1 006 5 x -10 1 0 10-4 6 x 0-1 1 0 01-3 w w w .k h d a w .c o m 课后答案网 运筹学作业参考解答 以 6 x为离基变量， 2 x为进基变量，旋转得 所以，原问题没有可行解. 78 p 23. 考虑第20题中的线性规划(p)，利用问题(p)的最优单纯形表继续求解下列问题. (1) 1 c由1变为 4 5 ； 解： 因为只有非基变量 1 x的价值系数 1 c由1变为 4 5 , 故只需要在问题(p)的最优单纯形 表中，把 1 x的检验数按如下规则改

25、变： 1) 4 5 (1 ( 4 5 )( 1111 =+=+=cc，得到新问 题的单纯形表如下 以 1 x为进基变量， 2 x为离基变量，旋转得 1 x 2 x 3 x 4 x 5 x 6 x rhs z 0-2 -4 0 -3012 4 x 01 2 1 102 1 x 10 -1 0 -104 6 x 0-1 1 0 01-3 1 x 2 x 3 x 4 x 5 x 6 x rhs z 00 -6 0 -3-218 4 x 00 3 1 11-1 1 x 10 -1 0 -104 2 x 01 -1 0 0-13 1 x 2 x 3 x 4 xrhs z 1 0 0 4 1 4 7 2

26、x 2 1 1 0 2 1 2 5 3 x 4 1 0 1 4 1 4 7 注：要先写出变化规则， 再由原问题的最优单纯形 表得到新问题的单纯形 表。特别地，该规则是针 对标准形式的。若原问题 不是标准形式，要注意参 数符号的相应变化 注：要先写出变化规则， 再由原问题的最优单纯形 表得到新问题的单纯形 表。特别地，该规则是针 对标准形式的。若原问题 不是标准形式，要注意参 数符号的相应变化 w w w .k h d a w .c o m 课后答案网 运筹学作业参考解答 根据最优化准则知，修改后的线性规划问题的最优解为 t x)0, 3, 0, 5(=,最优值为 4 13 . (4) b由 3

27、 5 变为 3 2 . 解：利用问题(p)的最优单纯形表和问题(p)的标准形式，可知问题(p)的最优解 t x)0, 5 2 , 5 11 ( * =的基变量为 2 x、 3 x，其对应的可行基为 = 1 2 1 02 b.因此， = = 2 5 1 3 2 1 4 1 0 2 1 1b bb， 2 5 2 5 1 ) 1, 0(),( 320 = =bccbcz t b . 所以只需修改(p)的最优单纯形表的最后一列，可得新问题的单纯形表， 根据最优化准则知，新问题的最优解为 t x) 2 5 , 1, 0( * =, 最优值为 2 5 . 1 x 2 x 3 x 4 xrhs z 0 2

28、0 4 5 4 13 1 x 1 2 0 1 5 3 x 0 2 1 1 0 3 1 x 2 x 3 x 4 xrhs z 4 5 0 0 4 1 2 5 2 x 2 1 1 0 2 1 1 3 x 4 1 0 1 4 1 2 5 w w w .k h d a w .c o m 课后答案网 运筹学作业参考解答 第三章第三章 整数规划整数规划 99 p 3. 用 gomory 割平面法求解下面的 ilp 问题. = + = . 2, 1, 0 4 82. . 5min 21 21 21 ix xx xxts xxz i 整数， 解：将原问题标准化标准化 = = =+ = . 4, 3, 2, 1

29、, 0 4 82. . 5min 421 321 21 ix xxx xxxts xxz i 整数， 将第二个等式乘以) 1(加到第一个等式，可得线性方程组的典式 = = =+ = . 4, 3, 2, 1, 0 4 43. . 5min 421 432 21 ix xxx xxxts xxz i 整数， 所以，其松驰问题(p0)的第一张单纯形表为 把零行化成检验行，得 以 2 x为进基变量， 3 x为离基变量，旋转得 1 x 2 x 3 x 4 xrhs z -1 5 0 0 0 3 x 0 3 1 1 4 1 x 1 -1 0 -14 1 x 2 x 3 x 4 xrhs z 0 4 0

30、-14 3 x 0 3 1 1 4 1 x 1 -1 0 -14 w w w .k h d a w .c o m 课后答案网 运筹学作业参考解答 所以，松驰问题(p0)的最优解为 t x)0, 0, 3 4 , 3 16 ( 0 =，它不是整数向量. 所以由第一行生成的割平面条件为 34 111 . 333 xx+ 对应的割平面为 341 111 333 xxs+= . 把它加入到松驰问题(p0)的最优单纯形表中，得到改进的松弛问题(p1)的单纯形表为 利用对偶单纯形方法对偶单纯形方法求解. 以 1 s为离基变量， 3 x为进基变量，旋转得 所以，松弛问题(p1)的最优解为 t x)0, 0,

31、 1, 1, 5( 1 =.因此，原问题的最优解为 t x) 1, 5( * =, 最优值为 0. 1 x 2 x 3 x 4 xrhs z 0 0 3 4 3 7 3 4 2 x 0 1 3 1 3 1 3 4 1 x 1 0 3 1 3 2 3 16 1 x 2 x 3 x 4 x 1 srhs z 0 0 3 4 3 7 0 3 4 2 x 0 1 3 1 3 1 0 3 4 1 x 1 0 3 1 3 2 0 3 16 1 s 0 0 3 1 3 1 1 3 1 1 x 2 x 3 x 4 x 1 srhs z 0 0 0 -1-40 2 x 0 1 0 0 11 1 x 1 0 0

32、-115 3 x 0 0 1 1 -31 w w w .k h d a w .c o m 课后答案网 运筹学作业参考解答 第四章第四章 非线性规划非线性规划 151 p 5. 判断下列函数是否为凸函数. 5. 判断下列函数是否为凸函数. (3) 313221 2 3 2 2 2 1 26293)(xxxxxxxxxxf+= 解： )(xf的hesse矩阵为 = 1862 662 222 )( 2 xf. )( 2 xf的各阶顺序主子式分别为 . 0 1862 662 224 , 08 62 22 , 02= = 因而)( 2 xf为半正定矩阵，所以)(xf是凸函数. 152 p 14、求以下无

33、约束非线性规划问题的最优解. 14、求以下无约束非线性规划问题的最优解. (1) (1) 21 2 21 2 2 2 1 1620)(2)(minxxxxxxxf+= 解：化简目标函数，得 .1620223)( 2121 2 2 2 1 xxxxxxxf+= 所以，)(xf的 hesse 矩阵为 = 42 26 )( 2 xf. 因为)( 2 xf是正定矩阵，所以)(xf是凸函数.另一方面，目标函数的梯度向量为 .)1624,2026()( 1221 t xxxxxf+= 令0)(=xf，即 =+ =+ 01624 02026 12 21 xx xx ，求得目标函数的驻点为 * 12 14 ,

34、 55 t x = . 所以，原问 题的最优解为 * 12 14 , 55 t x = . 152 p 16. 用最速下降法求以下问题: 解: (步骤参看 16. 用最速下降法求以下问题: 解: (步骤参看 124 p- - 125 p例 4.4.2)例 4.4.2) 注：在获得 hesse 矩阵 时，要特别注意对角线 上的元素. 注：在获得 hesse 矩阵 时，要特别注意对角线 上的元素. 注： 对无约束的最优化问题， 若目标函数是凸函数，则它 的驻点就是它最优解. 注： 对无约束的最优化问题， 若目标函数是凸函数，则它 的驻点就是它最优解. w w w .k h d a w .c o m

35、 课后答案网 运筹学作业参考解答 153 p 23 (1). 写出下列问题的 k-t 条件，并求出它们的 k-t 点. 23 (1). 写出下列问题的 k-t 条件，并求出它们的 k-t 点. =+ + + 0,0 042 05. )2()3(min 21 21 2 2 2 1 2 2 2 1 xx xx xxts xx 解：将问题(1)变形为 =+ + + 042 0 0 05. . )2()3(min 21 2 1 2 2 2 1 2 2 2 1 xx x x xxts xx 所以，其 lagrange 函数为 2222 12112213212 ( ,)(3)(2)(5)()()(24)l xxxxxxxxx =+ 所以有 += 2111 1 2)3(2xx x l 22)2(2 3212 2 += xx x l 因此，问题(1)的 k-t 条件是 = = =+ =+ =+ 0, 0)( 0)( 0)5( 022)2(2 02) 3(2 321 23 12 2 2 2 11 3212 2111 x x xx xx xx 作为 k-t 点还应满足可行性条件 =+ + 0, 0 042 05 21 21 2 2 2 1 xx