运筹学习题解答蒋邵忠浙大浙江大学.doc

1、习题解答 311 附录 1 习题解答 第一章 线性规划 一、 以下集合中，哪些是凸集，哪些不是凸集？ （ 1） (x1,x2)| x1+x2 1 是凸集 （ 2） (x1,x2,x3)| x1+x2 1,x1-x3 2 是凸集 （ 3） (x1,x2)| x1-x2=0 是凸集 （ 4） (x1,x2,x3)| x1 x2,x1+x2+x3 6 是凸集 （ 5） (x1,x2)| x1=1,|x2| 4 是凸集 （ 6） (x1,x2,x3)| x3=|x2|, x1 4 不是凸集 二、 求出以下不等 式组所定义的多面体的所有极点。 （ 1） x1 +x2 +x3 5 -x1 +x2 +2x3

2、 6 x1, x2, x3 0 解：引进松弛变量 x4， x5 0 x1 +x2 +x3 +x4 =5 -x1 +x2 +2x3 +x5 =6 x1, x2, x3 x4, x5 0 令 10211 0111154321 aaaaaA， 65b在 A矩阵中，一共有 10个行列式不等于 0的方阵，即 10个基。 11 11211 aaB ， 21121212121212111 65xxbB 21 11312 aaB ， 31134313131323112 65xxbB 01 11413 aaB ， 11 66511 10xx 4113 bB 11 01514 aaB ， 1156511 01xx

3、 5114 bB 习题解答 312 21 11325 aaB ， 146511 12xx 3215 bB 01 11426 aaB ， 156511 10xx 4216 bB 11 01527 aaB ， 156511 01xx 5217 bB 02 11438 aaB ， 236510xx21214318 bB 12 01539 aaB ， 456512 01xx 5319 bB 10 015410 aaB ， 656510 01xx 54110 bB 相应的基础解是 X1= （ x1， x2， x3， x4， x5） =（ -1/2， 11/2， 0， 0， 0） X2= （ x1， x2

4、， x3， x4， x5） =（ 4/3， 0， 11/3， 0， 0） X3= （ x1， x2， x3， x4， x5） =（ -6， 0， 0， 11， 0） X4= （ x1， x2， x3， x4， x5） =（ 5， 0， 0， 0， 11） X5= （ x1， x2， x3， x4， x5） =（ 0， 4， 1， 0， 0） X6= （ x1， x2， x3， x4， x5） =（ 0， 5， 0， -1， 0） X7= （ x1， x2， x3， x4， x5） =（ 0， 5， 0， 0， 1） X8= （ x1， x2， x3， x4， x5） =（ 0， 0， 3， 2

5、， 0） X9= （ x1， x2， x3， x4， x5） =（ 0， 0， 5， 0， -4） X10=（ x1， x2， x3， x4， x5） =（ 0， 0， 0， 5， 6） 其中 B2、 B4、 B5、 B7、 B8、 B10是可行基，相应的基础可行解为： X2= （ x1， x2， x3， x4， x5） =（ 4/3， 0， 11/3， 0， 0） X4= （ x1， x2， x3， x4， x5） =（ 5， 0， 0， 0， 11） X5= （ x1， x2， x3， x4， x5） =（ 0， 4， 1， 0， 0） X7= （ x1， x2， x3， x4， x5）

6、=（ 0， 5， 0， 0， 1） X8= （ x1， x2， x3， x4， x5） =（ 0， 0， 3， 2， 0） X10=（ x1， x2， x3， x4， x5） =（ 0， 0， 0， 5， 6） 原问题的极点是： X2= （ x1， x2， x3） =（ 4/3， 0， 11/3） X4= （ x1， x2， x3） =（ 5， 0， 0） X5= （ x1， x2， x3） =（ 0， 4， 1） X7= （ x1， x2， x3） =（ 0， 5， 0） 习题解答 313 X8= （ x1， x2， x3） =（ 0， 0， 3） X10=（ x1， x2， x3） =（

7、0， 0， 0） （ 2） x1 +x2 +x3 1 -x1 +2x2 4 x1, x2, x3 0 解：引进松弛变量 x4， x5 0 x1 +x2 +x3 +x4 =1 -x1 +2x2 +x5 =4 x1, x2, x3 x4, x5 0 令 10021 0111154321 aaaaaA， 41bA矩阵中共有 9个基。 x1、 x2为基变量，得到： x1 +x2 =1 -x1 +2x2 =4 求解这个方程组，得到 x1=-2/3， x2=5/3；（ x1,x2,x3,x4,x5） =（ -2/3,5/3,0,0,0） x1、 x3为基变量，得到： x1 +x3 =1 -x1 =4 求解

8、这个方程组，得到 x1=-4， x3=5；（ x1,x2,x3,x4,x5） =（ -4,0,5,0,0） x1、 x4为基变量，得到： x1 +x4 =1 -x1 =4 求解这个方程组，得到 x1=-4， x4=5；（ x1,x2,x3,x4,x5） =（ -4,0,0,5,0） x1、 x5为基变量，得到： x1 =1 -x1 +x5 =4 求解这个方程组，得到 x1=1， x2=5；（ x1,x2,x3,x4,x5） =（ 1,0,0,0,5） x2、 x3为基变量，得到： x2 +x3 =1 2x2 =4 求解这个方程组，得到 x2=2， x3=-1；（ x1,x2,x3,x4,x5）

9、 =（ 0,2,-1,0,0） x1、 x4为基变量，得到： x2 +x4 =1 2x2 =4 求解这个方程组，得到 x2=2， x4=-1；（ x1,x2,x3,x4,x5） =（ 0,2,0,-1,0） 习题解答 314 x2、 x5为基变量，得到： x2 =1 2x2 +x5 =4 求解这个方程组，得到 x1=1， x5=2；（ x1,x2,x3,x4,x5） =（ 0,1,0,0,2） x3、 x5为基变量，得到： x3 =1 x5 =4 求解这个方程组，得到 x3=1， x5=4；（ x1,x2,x3,x4,x5） =（ 0,0,1,0,4） x4、 x5为基变量，得到： x4 =1

10、 x5 =4 求解这个方程组，得到 x4=1， x5=4；（ x1,x2,x3,x4,x5） =（ 0,0,0,1,4） 其中的基础可行解有： （ x1,x2,x3,x4,x5） =（ 1,0,0,0,5） （ x1,x2,x3,x4,x5） =（ 0,1,0,0,2） （ x1,x2,x3,x4,x5） =（ 0,0,1,0,4） （ x1,x2,x3,x4,x5） =（ 0,0,0,1,4） 原问题的极点是： （ x1,x2,x3） =（ 1,0,0） （ x1,x2,x3） =（ 0,1,0） （ x1,x2,x3） =（ 0,0,1） （ x1,x2,x3） =（ 0,0,0） 三、

11、用图解法求解以下线性规划问题： （ 1） max z= x1 +3x2 s.t. x1 +x2 10 -2x1 +2x2 12 x1 7 x1, x2 0 x2 10 (2,8) 6 x1 习题解答 315 -6 0 7 10 最优解为（ x1,x2） =（ 2,8）， max z=26 (2) min z= x1 -3x2 s.t. 2x1 -x2 4 x1 +x2 3 x2 5 x1 4 x1, x2 0 x2 5 3 x1 0 2 3 4 最优解为 （ x1， x2） =（ 0， 5）， min z=-15 （ 3） max z= x1 +2x2 s.t. x1 -x2 1 x1 +2x

12、2 4 x1 3 x1, x2 0 x2 2 x1 0 1 2 3 4 习题解答 316 多个最优解，两个最优极点为（ x1， x2） =（ 2， 1），和 (x1， x2)=(0， 2)， max z=5 （ 4） min z= x1 +3x2 s.t. x1 +2x2 4 2x1 +x2 4 x1, x2 0 x2 x1=0 4 x4=0 2 x3=0 x2=0 x1 0 2 4 最优解为（ x1， x2） =（ 4， 0）， min z=4 四、 max z= 2x1 +x2 -x3 s.t. x1 +x2 +2x3 6 x1 +4x2 -x3 4 x1, x2, x3 0 A a a

13、a a a1 2 3 4 5 1 1 2 1 01 4 1 0 1 （ 1） B a a B1 21 1 11 4 4 3 1 31 3 1 31 1,/ / / 习题解答 317 X B b XB Nxxxxx 12 113454 3 1 31 3 1 36420 32 3000/ / / ,B1不是可行基， X XB Nxxxxx 1234520 32 3000/ ,不是基础可行解。 （ 2） B a a B12 3 211 21 1 1 3 2 31 3 1 3, / / / X B b XB Nxxxxx 13 212451 3 2 31 3 1 36414 32 3000/ / /

14、,B2 是可行基， X XB Nxxxxx 1324514 32 3000/ ,是基础 可行解，目标函数值为： z c c xxBT C B b2 1 1 3 13 2 1 14 32 3 26 3/ / （ 3） B a a B13 4 3 11 11 0 0 11 1, X B b XB Nxxxxx 14 312350 11 16442000, B3是基础可行解， X XB Nxxxxx 1423542000,是基础可行解，目标函数值为： z c c xxBT C B b3 1 1 4 14 2 0 42 8 （ 4） B a a B4 1 5 4 11 01 1 1 01 1, 习题解

15、答 318 X B b XB Nxxxxx 15 412341 01 16462000, B4不是可行基， X XB Nxxxxx 1523462000,不是基础可行解。 （ 5） B a a B5 2 3 5 11 24 1 1 9 2 94 9 1 9, / / / X B b XB Nxxxxx 23 511451 9 2 94 9 1 96414 920 9000/ / / ,B5是可行基， X XB Nxxxxx 2314514 920 9000/ ,是基础可行解，目标函数值为： z c c xxBT C B b5 1 2 3 23 1 1 14 920 9 6 9 2 3/ / /

16、 （ 6） B a a B6 2 4 6 11 14 0 0 1 41 1 4, / / X B b XB Nxxxxx 24 611350 1 41 1 46415000/ ,B6是可行基， X XB Nxxxxx 2413515000,是基础可行解，目标函数值为： z c c xxBT C B b6 1 2 4 24 1 0 15 1 （ 7） B a a B7 2 5 7 11 04 1 1 04 1, 习题解答 319 X B b XB Nxxxxx 25 711341 04 16462000, B7不是可行基， X XB Nxxxxx 2513462000,不是基础可行解。 （ 8）

17、 B a a B8 3 4 8 12 11 0 0 11 2, X B b XB Nxxxxx 34 811250 11 264414000, B8不是可行基， X XB Nxxxxx 34125414000,不是基础可行解。 （ 9） B a a B9 3 5 9 12 01 1 1 2 01 2 1, / X B b XB Nxxxxx 35 911241 2 01 2 16437000/ ,B9是可行基， X XB Nxxxxx 3512437000,是基础可行解，目标函数值为： z c c xxBT C B b9 1 3 5 35 1 0 37 3 （ 10） B a a B10 4

18、5 10 11 00 1 1 00 1, X B b XB Nxxxxx 45 1011231 00 16464000, 习题解答 320 B10是基础可行解， X XB Nxxxxx 4512364000,目标函数值为： z c c xxBT C B b10 1 4 5 45 0 0 64 0 在可行基 B2、 B3、 B5、 B6、 B9、 B10中，最优基为 B2，最优解为： X B b XB Nxxxxx 13 212451 3 2 31 3 1 36414 32 3000/ / / ,是基础可行解，目标函数值为： z c c xxBT C B b2 1 1 3 13 2 1 14 32 3 26 3/ / 五、对于以下约束 （ 1） (1) x1 +2x2 6 x1 -x2 4 x2 2 x1, x2 0 （ 1） 画出该可行域，并求出各极点的坐标 （ 2） 从原点开始，从一个基础可行解移到下一个“相邻的”基础可行解，指出每一次叠代，哪个变量进基，哪个变量离基。 (1) x1 +2x2 +x3 =6 x1 -x2 +x4 =4 x2 +x5 =2 x1, x2, x3, x4, x5 0 x2 3 x3=0 2 C(2,2) x5=0 D(0,2) B(14/3,2/3) 0 x2=0 4 O(0,0) A(4,0) x1=0 x4=0