动态规划应用举例 - 图文(10)

解 因第j年开始机龄为t年的机器，其制造年序应为j?t年，因此，I5(0)为第五年新产品的收入，

O3(2) =8。I3(2)为第一年的产品其机龄为2年的收入，)(故I5(0)=32。故I3(2)=20。同理O5(0)=4，而C51是第5年机龄为1年的机器(应为第四年的产品)的更新费用，故C5(1)=33 。同理C5(2)=33，C3(1) =31，其余类推。

当j=5时，由于设T=1 ，故从第5年开始计算时，机器使用了1、2、3、4、5年，则递推关系式为

?R:I5(0)?O5(0)?C5(t)?1?g6(1)?g5(t)?max ??

K:I(t)?O(t)?1?g(t?1)556??因此 g5(1)?max ??R:32?4?33?0??5??23 所以 x5(1)?K ??K:28?5?0?23??R:32?4?33?0??5?g5(2)?max ???18 所以 x5(2)?K

K:24?6?0?18??同理 g5(3)?13,x5(3)?K; g5(4)?6,x5(4)?K;g5(5)?4,x5(5)?K

当j=4时，递推关系为 g4(t)?max? )O0)C4?t()g?R:I4(0?4(?5?(1)?

t)?O4t(?)g5t?(1)??K:I4(? R:30?4?32?23?17?故 g4(1)?max???39 所以 x4(1)?K

K:26?5?18?39??同理 g4(2)?29,x4(2)?K;g4(3)?16,x4(3)?K;g4(4)?13,x4(4)?R

?R:I3(0)?O3(0)?C3(t)?g4(1)?当j=3时，有 g3(t)?max ??

K:I(t)?O(t)?g(t?1)334???R:29?5-31?39?32?g(1)?max 故 3?K:25?6?29?48??48 所以 x3(1)?K ??同理 g3(2)?31,x3(2)?R;g3(3)?27,x3(3)?R

?R:I2(0)?O2(0)?C2(t)?g3(1)?当j=2时，有g2(t)?max ??

K:I(t)?O(t)?g(t?1)223??故 g2(1)?max ??R:27?5?29?48?41??46 所以 x2(1)?K ??K:21?6?31?46??R:27?5?34?48?36?g2(2)?max ???36 x2(2)?R

K:16-8?27?35??

当j=1时，有 g1(t)?max ??R:I1(0)?O1(0)?C1(t)?g2(1)??

K:I(t)?O(t)?g(t?1)?112??R:22?6?32?46?30?故 g1(1)?max ???46 所以 x1(1)?K

K:18?8?36?46??根据上面计算过程反推之，可求得最优策略如表9-12，相应最佳收益为46单位。

表9-12

年 1 2 3 4 5

七、 货郎担问题

机龄 1 2 1 2 3 最 佳 策 略 K R K K K 货郎担问题在运筹学里是一个著名的命题。有一个串村走户卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后仍回到原出发的村庄。问应如何选择行走路线，能使总的行程最短。类似的问题有旅行路线问题，应如何选择行走路线，使总路程最短或费用最少等。

现在把问题一般化。设有n个城市，以1，2，…，n表示之。dij表示从i城到j城的距离。一个推销员从城市1出发到其他每个城市去一次且仅仅是一次，然后回到城市1。问他如何选择行走的路线，使总的路程最短。这个问题属于组合最优化问题，当n不太大时，利用动态规划方法求解是很方便的。

由于规定推销员是从城市1开始的，设推销员走到i城，记

Ni??2,3,?,i?1,i?1,?,n?表示由1城到i城的中间城市集合。

S表示到达i城之前中途所经过的城市的集合，则有S?Ni

因此，可选取(i，S)作为描述过程的状态变量，决策为由一个城市走到另一个城市，并定义最优值函数fk(i,S)为从1城开始经由k个中间城市的S集到i城的最短路线的距离，则可写出动态规划的递推关系为

fk(i,S)?min??fk?1(j,S\\?j?)?dj i??j?s

(k?1,2,?,n?1 。i?2,3,?,n 。S?Ni)边界条件为f0(i,?)?d1i

Pk(i,S)为最优决策函数，它表示从1城开始经k个中间城市的S集到i城的最短路线上紧挨着i城前

面的那个城市。

例11 求解四个城市旅行推销员问题，其距离矩阵如表9-13所示。当推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，问按怎样的路线走，使总的行程距离最短。

表9-13

i 距离 j 1 2 3 4 0 6 7 9 8 0 9 7 5 8 0 9 6 5 5 0 1 2 3 4 解 由边界条件可知：f0(2,?)?d12?8,f0(3,?)?d13?5,f0(4,?)?d14?6 当k=1时，即从1城开始，中间经过一个城市到达i城的最短距离是：

f1(2,?3?)?f0(3,?)?d32?5?9?14f1(2,?4?)?f0(4,?)?d42?6?7?13f1(3,?2?)?8?8?16 f1(3,?4?)?6?8?14f1(4,?2?)?8?5?13 f1(4,?3?)?5?5?10当k=2时，即从1城开始，中间经过二个城市(它们的顺序随便)到达i城的最短距离是：

f2(2,[3,4])?min ??f1(3,?4?)?d32, f1(4,?3?)?d42???min ?14?9,10?7??17 所以 p2(2,?3,4?)?4f2(3,?2,4?)?min ?13?8,13?8??21 所以 p2(3,?2,4?)?2或4f2(4,?2,3?)?min ?14?5,16?5??19 所以 p2(4,?2,3?)?2当k=3时，即从1城开始，中间经过三个城市(顺序随便)回到1城的最短距离是：

f3(1,?2，3，4?)?min ??f2(2,?3,4?)?d21,f2(3,?2,4?)?d31,f2(4,?2,3?)?d41???min ?17?6,21?7,19?9??23所以 p3(1,?2,3,4?)?2

由此可知，推销员的最短旅行路线是1→3→4→2→1，最短总距离为23。