运筹学基础和应用课后习题答案解析[第一二章习题解答]

运筹学基础及应用 习题解答

习题一 P46 1.1 (a)

x2 4x12x244 3 2 1 0 1 2 3 4x16x26x1

1的所有x1,x2，此时目标函数值2该问题有无穷多最优解，即满足4x16x26且0x2z3。 (b)

x2 3 2 0 1 4 x1

用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。

1.3 (a)

(1) 图解法

学习指导参考资料

完美WORD格式编辑

x2 4 3 2 1 0 1 2 3 x1 最优解即为3x14x29353的解x1,，最大值z

25x2x8221(2)单纯形法

首先在各约束条件上添加松弛变量，将问题转化为标准形式 max z10x15x20x30x43x4x2x39s.t. 15x12x2x48

则P3,P4组成一个基。令x1x20

得基可行解x0,0,9,8，由此列出初始单纯形表 cj cB 基 b 10 5 0 0 x1 x2 x3 x4 0 x3 9 0 x4 8 3 4 1 0 [5] 2 0 1 cjzj 10 5 0 0 12。min, cj cB 基 b 210 x3 5810 x1 5538 510 5 0 0 x1 x2 x3 x4 3140  1  552 11 0 55 学习指导参考资料

完美WORD格式编辑

cjzj 0 1 0 2

20，min新的单纯形表为 cj cB 基 b 35 x2 22183, 142210 5 0 0 x1 x2 x3 x4 530 1  141410 x1 1 1 21 0  770 0 525  14143235 2cjzj

1,20，表明已找到问题最优解x11, x2 , x30 , x40。最大值 z*(b)

(1) 图解法 6x12x224x2 12 9 x1x256 3 0 3 6 9 x1 \\\\

最优解即为6x12x2241773的解x,，最大值z

222x1x25(2) 单纯形法

首先在各约束条件上添加松弛变量，将问题转化为标准形式

学习指导参考资料

完美WORD格式编辑

max z2x1x20x30x40x55x2x315s.t. 6x12x2x424xxx5125

则P3，P4，P5组成一个基。令x1x20

得基可行解x0,0,15,24,5，由此列出初始单纯形表 cj 2 1 0 0 0 \\ cB 基 b x1 x2 x3 x4 x5 0 5 1 0 0 [6] 2 0 1 0 1 1 0 0 1 2 1 0 0 0 0 x3 15 0 x4 24 0 x5 5 cjzj 12。min,cj cB 基 b 245,4 612 1 0 0 0 x1 x2 x3 x4 x5 0 5 1 0 0 1 0 x3 15 2 x4 4 0 x5 1 cjzj 11 0 0 360  0  1 3621110 0 0 333315,24,

22520，min新的单纯形表为

学习指导参考资料

完美WORD格式编辑

cj cB 基 b 2 1 0 0 0 x1 x2 x3 x4 x5 152 7x42 2 30 x5 20 x3 cjzj 515  42111 0 0 42310 1 0  24110 0 0 420 0 1 1,20，表明已找到问题最优解x11， x2值 z*715，x40，x50。最大 ，x32217 2 1.8

表1-23

x1 x2 x3 x4 x5 x4 6 x5 1 cjzj 2 4 -2 1 0 1 3 2 0 1 3 1 2 0 0 表1-24 x1 x2 x3 x4 x5 x1 3 x5 1 cjzj 1 2 1 12 0 0 5 1 12 1 0 7 5 32 0 1.10 5 x2 83 0 x5 143 0 x6 293 3 5 4 0 0 0 x1 x2 x3 x4 x5 x6 23 1 0 13 0 0 43 0 5 23 1 0 53 0 4 23 0 1 cjzj 13 0 4 53 0 0 学习指导参考资料

完美WORD格式编辑

5 x2 83 4 x3 1415 0 x6 15 cjzj x1 x2 x3 x4 x5 x6 23 1 0 13 0 0 415 0 1 215 15 0 4115 0 0 215 45 1 1115 0 0 1715 45 0 5 x2 5041 4 x3 6241 3 x1 41 cjzj x1 x2 x3 x4 x5 x6 0 1 0 11 841 1041 0 0 1 1 1 441 1 0 0 241 1241 11 0 0 0 41 2441 1141 最后一个表为所求。

习题二 P76 2.2

(a)错误。原问题存在可行解，对偶问题可能存在可行解，也可能无可行解。

(b)错误。线性规划的对偶问题无可行解，则原问题可能无可行解，也可能为无界解。 (c)错误。 (d)正确。

2.8 将该问题化为标准形式：

max z2x1x2x30x40x5x1x2x3x46s.t. x12x2x54x0i1,5i

用单纯形表求解 cj cB 基 b 2 1 1 0 0 x1 x2 x3 x4 x5 0 x4 6 0 x5 4 [1 ] 1 1 1 0 1 2 0 0 1 2 1 1 0 0 cjzj 6 学习指导参考资料

完美WORD格式编辑

cB 基 b x1 x2 x3 x4 x5 2 x1 6 0 x5 10 cjzj 1 1 1 1 0 0 3 1 1 1 0 3 -1 2 0 由于j0，所以已找到最优解X*6,0,0,0,10，目标函数值z*12 (a) 令目标函数

max z（21）x1（-1+2）x2（1+3）x3

(1)令230，将1反映到最终单纯形表中 cj cB 基 b 21 1 1 0 0 x1 x2 x3 x4 x5 21 x4 6 0 x5 10 1 1 1 1 0 0 3 1 1 1 0 -3-1 - 1 -1 2-1 0 cjzj 表中解为最优的条件：-3-10，- 1 -10，2-10，从而11 (2)令130，将2反映到最终单纯形表中 cj cB 基 b 2 12 1 0 0 x1 x2 x3 x4 x5 2 x1 6 0 x5 10 1 1 1 1 0 0 3 1 1 1 0 2-3 - 1 2 0 cjzj 表中解为最优的条件：2-3 0， 从而23 (3) 令120，将3反映到最终单纯形表中 cj cB 基 b 2 1 13 0 0 x1 x2 x3 x4 x5 学习指导参考资料

完美WORD格式编辑

2 x1 6 0 x5 10 1 1 1 1 0 0 3 1 1 1 0 -3 3 - 1 2 0 cjzj 表中解为最优的条件：3-10， 从而31 (b) 令线性规划问题为

max z2x1x2x3x1x2x364s.t. x12x245x0i1,3 i(1)先分析的变化

1011bB1b110

161使问题最优基不变的条件是bb100，从而16

1(2)同理有0，从而210 1026(c) 由于x(6,0,0,0,10)代入x12x362，所以将约束条件减去剩余变量后的方

程x12x3x62直接反映到最终单纯形表中 cj cB 基 b 2 -1 1 0 0 0 x1 x2 x3 x4 x5 x6 1 1 1 1 0 0 0 3 1 1 1 0 1 0 -2 0 0 1 0 -3 -1 -2 0 0 2 x1 6 0 x5 10 0 x6 -2 cjzj 对表中系数矩阵进行初等变换，得 cj cB 基 b 2 -1 1 0 0 0 x1 x2 x3 x4 x5 x6 学习指导参考资料

完美WORD格式编辑

2 x1 6 0 x5 10 0 x6 -8 1 1 1 1 0 0 0 3 1 1 1 0 0 -1 [-3] -1 0 1 cjzj 0 -3 -1 -2 0 0 cj cB 基 b 2 -1 1 0 0 0 x1 x2 x3 x4 x5 x6 2 x1 10 1 2 0 2 0 1 333330 x5 22 0 8 0 2 1 1 3330 x6 8 3cjzj 1 3338510  0  0  3330 1 1 1 0 因此增加约束条件后，新的最优解为

x1

1082228，x3，x5，最优值为 3333 学习指导参考资料