运筹学作业标准答案 (教师用) 21

No.7 动态规划

1、某公司有9个推销员在全国三个不同市场里推销货物，这三个市场里推销员人数与收益的关系如下表，做出各市场推销人员数的分配方案，使总收益最大。

推销员 市场 1 2 3 0 20 40 50 1 32 50 61 2 47 60 72 3 57 71 84 4 66 82 97 5 71 93 109 6 82 104 120 7 90 115 131 8 100 125 140 9 110 135 150 解：令分配到各地区的推销员人数为决策变量xk ，k=1,2,3代表第1、2、3地区；令各地区可供分配的推销员人数为状态变量sk 。最先分配给第1地区，然后第2、第3地区，则 s1=9。

状态转移公式为：sk+1 = sk ?xk ； 目标函数为：f?max() ?dx第1阶段：第3地区， s3 有0～9种可能，由收益表第3行可知d(x3)单调增，故有x3 *= s3；列表如下： 33i?1ix3*= s3 f1* 0 50 1 61 2 72 3 84 4 97 5 109 6 120 7 131 8 140 9 150 第2阶段：第2地区，s2 仍有0～9种可能，列表如下：

x2 0 s2 0 90* 1 101* 2 112* 3 124* 1 100 111 122 2 110 121 3 121 4 5 6 7 8 9 x2* 0 0 0 0 f2* 90 101 112 124 运筹学作业标准答案 (教师用) 4 5 6 7 8 9 s3 137* 134 132 132 132 149* 147 144 143 143 160* 159 157 155 154 171* 170 169 168 166 180 181* 180 180 179 190 190 191* 191* 191* 9 8 7 6 5 143 154 165 177 190 4 154 165 176 188 3 165 176 187 2 175 186 1 0 0 0 0 1 185 2,3,4 0 22 137 149 160 171 181 191 第3阶段：第1地区，由s1 =9， 列表如下：

x1 0 s1 9 211 s2 9 1 2 3 4 215 5 5 208 4 6 206 3 7 202 2 8 201 1 9 200 0 x1* 2 f3* 218 213 218* 217 8 7 6 答：第1地区分配2名推销员，第2 地区

不分配人员，第3地区分配7名推销员，总收益为218。

2、设某工厂要在一台机器上生产两种产品，机器的总运转时间为5小时。生产这两种产品的任何一件都需占用机器一小时。设两种产品的售价与产品产量成线性关系，分别为(12?x1)和(13?2x2)。这里x1和x2分别为两种产品的产量。假设两种产品的生产费用分别是4x1和3x2，问如何安排两种产品的生产量使该机器在5小时内获利最大。(要求用连续变量的动态规划方法求解)

解：设可用机时为状态si，先分配产品1机时，故有状态转移方程

sk+1 = sk ?xk (i =1,2)

运筹学作业标准答案 (教师用) 23

边界值 s1 =5, s3=0

目标函数为：f?max{(12?x)x?4x?(13?2x)x?3x}

?max{(8x?x)?(10x?2x)}

由边界条件s3 = s2 ?x2 =0，得 x2 = s2，因此有

f(s)?10x?2x?10s?2s

则动态规划总效果的递推方程为

?2111222121222?122222222f2?(x1)?max{(8x1?x1)?f1?(s2)}x1?0 ?max{(8x1?x1?02x1)?(10s22?2s2)}

由状态方程 s2 = s1 ?x1 ＝5?x1，代入上

式得

2f2?(x1)?max{(8x1?x1)?10(5?x1)?2(5?x1)2}x1?0?2max{18x1?3x1}x1?0

答：最优策略为第1种产品生产3件，第二种产品生产2件，5小时内最大利润为27元。

f2??18?3?3?9?27令

dfxd()/x?18??6x21110，解得 x1 =3。因此，

No.8 最短路问题

1、求下图中v1到所有点的最短路径及其长度。(要求最短路用双线在图中标出，保留图中的标记值)

运筹学作业标准答案 (教师用)

v23424

56v567v63275711v101854v41v811解：最短路及其长度如图中粗线和节点上永久标记所示，

2、将上图看作

2v64v 无向图，写出边

权邻接矩阵，用Prim算法求最大生成树，并画出该树图。

37解：由图可得邻接矩阵，由Prim 算法的最大生成树如下图，

1 2 3 4 5 6 7 2 8 ?1 1 ?3 2 1 1 (4) 5 v21v154v3356v5732752v7v8v613 (5) 1 6 ?2 3 4 (5) ?6 4 ?4 5 ?5 6 ?7 7 ?8 8 3 5 1 3 (7) 1 v41 (6) (7) 2 3 7 7 2 1 2 (5) 5 答：最大生成树的权值为39。