运筹学74动态规划应用举例

1、第七章第七章 动态规划动态规划 n多阶段决策过程的最优化多阶段决策过程的最优化 n动态规划的基本概念和基本原理动态规划的基本概念和基本原理 n动态规划模型的建立与求解动态规划模型的建立与求解 n动态规划在经济管理中的应用动态规划在经济管理中的应用 第四节第四节 动态规划在经济管理中的应用动态规划在经济管理中的应用 连续变量的离散化解法连续变量的离散化解法 先介绍连续变量离散化的概念。如投资分配问题先介绍连续变量离散化的概念。如投资分配问题 的一般静态模型为：的一般静态模型为： n i ii xgz 1 )(max ), 2 , 1(0 1 nix ax i n i i 模型中：阶段数、总投资、

2、各阶段投资数、各阶段收益、决策变量、状模型中：阶段数、总投资、各阶段投资数、各阶段收益、决策变量、状 态变量态变量 状态转移方程、基本方程、指标函数、最优指标函数状态转移方程、基本方程、指标函数、最优指标函数 建立它的动态规划模型，其基本方程为：建立它的动态规划模型，其基本方程为： 0)( 1 ,2, 1,)()(max)( 11 11 0 nn kkkk sx kk sf nnksfxgsf kk 其状态转移方程为其状态转移方程为: : kkk xss 1 由于由于 与与 都是连续变量，当各阶段指标都是连续变量，当各阶段指标 没没 有特殊性而较为复杂时，有特殊性而较为复杂时， 要求出要求出

3、会比较困难，因而求会比较困难，因而求 全过程的最优策略也就相当不容易，这时常常采用把连续变量全过程的最优策略也就相当不容易，这时常常采用把连续变量 离散化的办法求其数值解。具体做法如下：离散化的办法求其数值解。具体做法如下： k s k x)( kk xg )( kk sf （1 1） 令令 ， 把区间把区间 0 0，aa进行分割，进行分割， 的大小可的大小可 依据问题所要求的精度以及计算机的容依据问题所要求的精度以及计算机的容 量来定。量来定。 ams k ,2,0 (2) (2) 规定状态变量规定状态变量 及决策变量及决策变量 只在离散点只在离散点 上取值，相应的指标上取值，相应的指标 函

4、数函数 就被定义在这些离散值上，于是递推方就被定义在这些离散值上，于是递推方 程就变为：程就变为： k s k x am,2,0 )( kk sf 0)( )()(max)( 11 1 ,2, 1 ,0 nn kkk qp kk sf psfpgsf 其中其中 pxsq kk , 作为离散化例子，在例作为离散化例子，在例5 5中规定状态变量和决中规定状态变量和决 策变量只在给出的离散点上取值，见例策变量只在给出的离散点上取值，见例6 6。 （ 3 3 ） 按 逆 序 方 法 ， 逐 步 递 推 求按 逆 序 方 法 ， 逐 步 递 推 求 出出 ，最后求出最，最后求出最 优资金分配方案。优资金

5、分配方案。 )(,),( 11 sfsf nn 问如何分配投资数额才能使总效益最大问如何分配投资数额才能使总效益最大? ? 2 333222111 2)(,9)(,4)(xxgxxgxxg 例例5 5 某公司有资金某公司有资金1010万元，若投资于项目万元，若投资于项目 i(i=1,2,3)i(i=1,2,3)的投资额为的投资额为x xi i时，其效益分别为：时，其效益分别为： 例例6 6 连续变量的离散化解法连续变量的离散化解法 )3,2, 1(,0 10 . 294max 321 2 321 ix xxx ts xxxZ i 解解 令令 ，将区间，将区间00，1010分割成分割成0 0，2

6、 2，4 4，6 6，8 8， 1010六个点，即状态变量六个点，即状态变量 集合为集合为 2 k s 10,8,6,4,2,0 允许允许决策集合为决策集合为 ， 与与 均在分割点上取值。均在分割点上取值。 kk sx0 k x k s 动态规划基本方程为：动态规划基本方程为： 0)( 1 ,2, 3)()(max)( 44 1 0 sf kxsfxgsf kkkkk sx kk kk 当当k=3k=3时，时， 2 3 0 33 2max)( 33 x sx sf 式中式中 与与 的集合均为：的集合均为： 计算结果见表计算结果见表7-17-1。 3 s 3 x10,8,6,4,2,0 3 s

7、)( 33 sf * 3 x 0246810 083272128200 0246810 当当k=3时，时， 表表7-1 2 3 0 33 2max)( 33 x sx sf 当当k=2时，时， )(9max)( 2232 0 22 22 xsfxsf sx 0)( 1 , 2 , 3)()(max)( 44 1 0 sf kxsfxgsf kkkkk sx kk kk 计算结果见表计算结果见表7-27-2。 2 s 2 x 32 fg 2 f * 2 x 0246810 00 20 2 40 2 4 60 2 4 6 80 2 4 6 8 10 0 8 18 32 26 3672 50 44

8、54128 90 68 62 72200 146 108 86 80 90 0 18 36 72 128 200 0 24 0 0 0 表表7-2 7-2 当当k=1时，时， 0)( 1 , 2 , 3)()(max)( 44 1 0 sf kxsfxgsf kkkkk sx kk kk 计算结果见表计算结果见表7-37-3。 表表7-3 )(4max)( 1121 100 11 1 xsfxsf x 1 s 1 x 21 fg 1 f * 1 x 10 1010 10 1010 0246810 20013688605040 200 0 最大收益为最大收益为 ，与例，与例5 5结论完全相同。结

9、论完全相同。 10,0,0 * 3 * 2 * 1 xxx 200)10( 1 f 计算结果表明，最优决策为：计算结果表明，最优决策为： 应指出的是：这种方法有可能丢失最优解，应指出的是：这种方法有可能丢失最优解， 一般得到原问题的近似解。一般得到原问题的近似解。 一、背包问题一、背包问题 一位旅行者携带背包去登山，已知他所能承受的背包重一位旅行者携带背包去登山，已知他所能承受的背包重 量限度为量限度为a kg，现有，现有n种物品可供他选择装入背包，第种物品可供他选择装入背包，第i种种 物品的单件重量为物品的单件重量为ai kg，其价值是携带数量，其价值是携带数量xi的函数的函数 ci(xi)

10、(i=1,2,n)，问旅行者应如何选择携带各种物品的件，问旅行者应如何选择携带各种物品的件 数，以使总价值最大？数，以使总价值最大？ ), 2 , 1(0 )(max 1 1 nix axa xcz i n i ii n i ii 且为整数 例例1 有一辆最大货运量为有一辆最大货运量为10t的卡车，用以装载的卡车，用以装载3种货物，种货物， 每种货物的单位重量及相应单位价值见下表，应如何装载可每种货物的单位重量及相应单位价值见下表，应如何装载可 使总价值最大？使总价值最大？ ) 3 , 2 , 1(0 10543 654max 321 321 ix xxx xxxz i 且为整数 货物编号i1

11、23 单位重量(t)345 单位价值ci456 逆序解法：逆序解法： 阶段阶段k： k=1,2,3 状态变量状态变量sk:第第k阶段可以装载第阶段可以装载第k种到第种到第3种货物的重量。种货物的重量。 决策变量决策变量xk:决定装载第决定装载第k种货物的数量。种货物的数量。 状态转移方程状态转移方程:sk+1=sk-akxk 最优指标函数最优指标函数fk(sk):当可装载重量为当可装载重量为sk,装载第装载第k种到第种到第3种货物所获得的种货物所获得的 最大价值。最大价值。 基本方程：基本方程： 0)( 1 , 2 , 3)()(max)( 44 11 / , 1 , 0 sf ksfxcsf

12、 kkkk asx kk kkk 当阶段当阶段k=3时，有时，有6max)( 3 5/, 0 33 33 xsf sx s3012345678910 x3000000 10 10 10 10 10 1 2 c3+f4000000 60 60 60 60 60 6 12 f3000006666612 x3*00000111112 当阶段当阶段k=2时，有时，有)(5max)( 332 4/, 0 22 22 sfxsf sx s2012345678910 x200000 10 10 10 10 1 20 1 20 1 2 c2+f300000 5+06 56 56 56 5 106 5+6 10

13、12 5+6 10 f200005666101112 x2*00001000210 223 4xss 当阶段当阶段k=1时，有时，有)(3max)( 221 3/10, 0 11 1 sfxsf x s110 x10 1 2 3 c1+f312 4+6 8+5 12 f213 x1*2 112 3xss 二、生产经营问题二、生产经营问题 在生产和经营管理中，经常遇到如何合在生产和经营管理中，经常遇到如何合 理地安排生产计划、采购计划以及仓库的存理地安排生产计划、采购计划以及仓库的存 货计划和销售计划，使总效益最高的问题。货计划和销售计划，使总效益最高的问题。 下面通过例子来说明对不同特点问题的

14、不同下面通过例子来说明对不同特点问题的不同 处理技巧处理技巧。 例例2 生产与存贮问题生产与存贮问题 某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月 生产生产j单位产品费用为：单位产品费用为： )()6,2, 1(3 )0(0 )( 千元jj j jC 每月库存每月库存j j单位产品的费用为单位产品的费用为 ，该厂最大库存容量为该厂最大库存容量为3 3单单 位，每月最大生产能力为位，每月最大生产能力为6 6单位，计划开始和计划期末库存量都是单位，计划开始和计划期末库存量都是零零。试制定试制定 四个月四个月的生产计

15、划，在满足用户需求条件下总费用最小。假设第的生产计划，在满足用户需求条件下总费用最小。假设第i+1i+1个月的库个月的库 存量是第存量是第i i个月个月可销售量可销售量与该月用户需求量之差；而第与该月用户需求量之差；而第i i个月的可销售量是本个月的可销售量是本 月初库存量与产量之和。月初库存量与产量之和。 )(5 . 0)(千元jjE )(月i )(需求 i g 1234 2324 用动态规划方法求解时，对有关概念作如下分析：用动态规划方法求解时，对有关概念作如下分析： (1) (1) 阶段：每个月为一个阶段，阶段：每个月为一个阶段，k k1 1，2 2，3 3，4 4。 (2) (2)状态

16、变量：状态变量： 为第为第k k个月初的库存量。个月初的库存量。 k s (3)(3)决策变量：决策变量： 为第为第k k个月的生产量。个月的生产量。 k u (4)(4)状态转移方程：状态转移方程： kkkk guss 1 (5)(5)最优指标函数：最优指标函数： 表示第表示第k k月状态为月状态为 时，采取时，采取 最佳策略生产，从本月到计划结束最佳策略生产，从本月到计划结束( (第第4 4月末月末) )的生产与存贮最的生产与存贮最 低费用。低费用。 （6 6）基本方程：）基本方程： )( kk sf k s 0)( 1 , 2 , 3 , 4)()()(min)( 55 11 sf ks

17、fsEuCsf kkkk u kk k k4，s5=s4+u4-g4=0，所以，所以u4=g4-s4=4-s4，s4可取可取0，1，2，3。 0)()(min)( 44 3 , 2, 1 , 0 44 4 sEuCsf u s40123 u44321 C+E+f576+0.55+14+1.5 f476.565.5 u4*4321 k3，s4=s3+u3-g3，所以，所以u3=s4+ g3-s3，s3可取可取0，1，2，3。 s30123 u32 3 4 51 2 3 40 1 2 30 1 2 C+E+f45+7 6+6.5 7+6 8+5.5 4.5+7 5.5+6.5 6.5+6 7.5+

18、5.51+7 5+6.5 6+6 7+5.5 1.5+6.5 5.5+6 6.5+5.5 f31211.588 u3*2100 k2，s3=s2+u2-g2，所以，所以u2=s3+ g2-s2， s2可取可取0，1，2，3。 s20123 u23 4 5 62 3 4 51 2 3 40 1 2 3 C+E+f36+12 7+11.5 8+8 9+85.5+12 6.5+11.5 7.5+8 8.5+85+12 6+11.5 7+8 8+8 1.5+12 5.5+11.5 6.5+8 7.5+8 f21615.51513.5 u2*5430 k1，s2=s1+u1-g1，所以，所以u1=s2+

19、 g1-s1， s1可取可取0。 s10 u12 3 4 5 C+E+f25+16 6+15.5 7+15 8+13.5 f121 u1*2 反推回去，反推回去， u1*=2， u2*=5， u3*=0， u4*=4。 例例3 3 采购与销售问题采购与销售问题 某商店在未来的某商店在未来的4 4个月里，准备利用它的一个仓库来专门经销某种商个月里，准备利用它的一个仓库来专门经销某种商 品，仓库最大容量能贮存这种商品品，仓库最大容量能贮存这种商品l000l000单位。假定该商店每月只能出卖仓单位。假定该商店每月只能出卖仓 库现有的货。当商店在某月购货时，下月初才能到货。预测该商品未来四库现有的货。

20、当商店在某月购货时，下月初才能到货。预测该商品未来四 个月的买卖价格如表个月的买卖价格如表7 7_12_12所示，假定商店在所示，假定商店在1 1月开始经销时，仓库贮有该月开始经销时，仓库贮有该 商品商品500500单位。试问若不计库存费用，该商店应如何制定单位。试问若不计库存费用，该商店应如何制定1 1月至月至4 4月的订购月的订购 与销售计划，使预期获利最大。与销售计划，使预期获利最大。 月份（月份（k） 购买单价（购买单价（ck）销售单价（销售单价（pk） 11012 298 31113 41517 解解 按月份划分为按月份划分为4个阶段，个阶段，k=l，2，3，4 状态变量状态变量 ：

21、第：第k月初时仓库中的存货量月初时仓库中的存货量(含上月订货含上月订货)。 决策变量决策变量 ：第：第k月卖出的货物数量。月卖出的货物数量。 ：第：第k月订购的货物数量。月订购的货物数量。 状态转移方程：状态转移方程： k s k x k y 最优指标函数最优指标函数 ：第：第k k月初存货量为月初存货量为 时，从第时，从第k k月到月到4 4月末所获最大月末所获最大 利润。利润。 则则有逆序递推关系式为：有逆序递推关系式为： kkkk xyss 1 )( kk sfk s 0)( 1 , 2 , 3 , 4)(max)( 55 11 )(10000 0 sf ksfycxpsf kkkkkk

22、 xsy sx kk kkk kk 当当k=4时时 显然，决策应取显然，决策应取 时才有最大值时才有最大值 1517max)( 44 )(10000 0 44 444 44 yxsf xsy sx 0, * 44 * 4 ysx 444 17)(ssf 0)( 1 , 2 , 3 , 4)(max)( 55 11 )(10000 0 sf ksfycxpsf kkkkkk xsy sx kk kkk kk 当当k=3时时 这个阶段需解一个线性规划问题：这个阶段需解一个线性规划问题： 1764max )(171113max )(1113max)( 333 )(10000 0 33333 )(10

23、000 0 4433 )(10000 0 33 333 33 333 33 333 33 syx xysyx sfyxsf xsy sx xsy sx xsy sx 因为只有两个变量因为只有两个变量x3, y3 ，可以用图解法，也可以用单纯形法，求解得到：，可以用图解法，也可以用单纯形法，求解得到： 时有最大值时有最大值 0, 1000 1764max 33 333 33 333 yx sxy sx syxz 1000, * 33 * 3 ysx 333 136000)(ssf 当当k=2时时 求解线性规划问题：求解线性规划问题： 得得 45136000max )(13600098max )(

24、98max)( 222 )(10000 0 22222 )(10000 0 222322 )(10000 0 22 222 22 222 22 222 22 yxs xysyx xysfyxsf xsy sx xsy sx xsy sx 0, 1000 45136000max 22 222 22 222 yx sxy sx yxsz 22222 91000044000136000)(ssssf 2 * 2 * 2 1000,0syx 当当k=1时时 求解一个线性规划问题：求解一个线性规划问题： 得得 )(1012max)( 111211 )(10000 0 11 111 11 xysfyxsf

25、 xsy sx 500 1 s 145003max )(9100001012max)500( 11 5000 5000 11111 5000 5000 1 11 1 11 1 yx xysyxf xy x xy x 0, 500 500 314500max 11 11 1 11 yx xy x yxz 16000500314500)500(, 0,500 1 * 1 * 1 fyx 最优策略见下表。最大利润为最优策略见下表。最大利润为1600016000。 月份月份期前存货期前存货售出量售出量购进量购进量 15005000 2001000 3100010001000 4100010000 例例

26、4 4 限期采购问题限期采购问题( (随机型随机型) ) 某部门欲采购一批原料，原料价格在五周内可能有某部门欲采购一批原料，原料价格在五周内可能有 所变动，已预测得该种原料今后五周内取不同单价的概所变动，已预测得该种原料今后五周内取不同单价的概 率如表率如表7-147-14所示。试确定该部门在五周内购进这批原料所示。试确定该部门在五周内购进这批原料 的最优策略，使采购价格的的最优策略，使采购价格的期望值期望值最小。最小。 原材料单价（元）原材料单价（元）概率概率 500 600 700 0.3 0.3 0.4 表表7-14 阶段阶段k k：可按采购期限可按采购期限( (周周) )分为分为5 5

27、段，段，k k1 1，2 2，3 3，4 4，5 5。 状态变量状态变量 ：第：第k k周的原料实际价格。周的原料实际价格。 k x 决策变量决策变量 ：第：第k周如采购周如采购 则则 1，若不采购，若不采购 则则 =0 =0。 另外用另外用 表示：当第表示：当第k周决定等待，而在以后采购时的采购价格期望值。周决定等待，而在以后采购时的采购价格期望值。 最优指标函数最优指标函数 ：第：第k周实际价格为周实际价格为 时，从第时，从第k周至第周至第5周采取最周采取最 优策略所花费的最低期望价格。优策略所花费的最低期望价格。 则则有逆序递推关系式为：有逆序递推关系式为： )( kk sfk s 解解

28、 本例与前面所讨论的确定型问题不同，状态的转移不能完全确定，而本例与前面所讨论的确定型问题不同，状态的转移不能完全确定，而 按某种已知的按某种已知的概率分布概率分布取值，即属于取值，即属于随机型随机型动态规划问题。动态规划问题。 k s k xk x kE S )17. 7()( )17. 7(1 , 2 , 3 , 4,min)( 55555 bDsssf akDsSssf kkkEkkk k D为状态集合为状态集合500，600，700。 当当k=5时时 因为若前四周尚未购买，则无论本周价格如何，该部门都因为若前四周尚未购买，则无论本周价格如何，该部门都 必须购买，所以必须购买，所以 )(

29、 1700700 )( 1600600 )( 1500500 )5(5 * 55 * 55 * 55 采购当 采购当 采购当 xs xs xs sf 当当k=4时时 由于由于 所以所以 6107004 . 06003 . 05003 . 0 )700(4 . 0)600(3 . 0)500(3 . 0 5554 fffS E 610,min,min)( 44444 44 sSssf E Ds )(0700610 )( 1600600 )( 1500500 * 44 * 44 * 44 等待当 采购当 采购当 xs xs xs 当当k=3时时 由于由于 所以所以 5746104 .06003 .

30、05003 .0 )700(4 .0)600(3 .0)500(3 .0 4443 fffS E 574,min,min)( 33333 33 sSssf E Ds 0700600574 1500500 * 33 * 33 xs xs 或当 当 当当k=2时时 同理同理 8 .551,min,min)( 22222 sSssf E 07006008 .551 1500500 * 22 * 22 xs xs 或当 当 当当k=1时时 26.536,min,min)( 11111 sSssf E 070060026.536 1500500 * 11 * 11 xs xs 或当 当 所以，最优采购策

31、略为：若第一、二、三周原料价格所以，最优采购策略为：若第一、二、三周原料价格 为为500500，则立即采购，否则在以后的几周内再采购。若第四，则立即采购，否则在以后的几周内再采购。若第四 周价格为周价格为500500或或600600，则立即采购，否则等第五周再采购。，则立即采购，否则等第五周再采购。 而第五周时无论当时价格为多少都必须采购。而第五周时无论当时价格为多少都必须采购。 按照以上策略进行采购，期望价格为：按照以上策略进行采购，期望价格为： 525382.525 26.5364 . 026.5363 . 05003 . 0 )700(4 . 0)600(3 . 0)500(3 . 0)

32、( 11111 fffsf 三、设备更新问题三、设备更新问题 从经济上分析，一台设备应该从经济上分析，一台设备应该 使用多少年更新最使用多少年更新最 合算，这就是设备更新问题。一般来说，一台设备在比合算，这就是设备更新问题。一般来说，一台设备在比 较新时，年运转量大，经济收入高，故障少，维修费用较新时，年运转量大，经济收入高，故障少，维修费用 少，但随着使用年限的增加，年运转量减少因而收入减少，但随着使用年限的增加，年运转量减少因而收入减 少，故障变多少，故障变多, ,维修费用增加。如果更新可提高年净收维修费用增加。如果更新可提高年净收 入，但是当年要支出一笔数额较大的购买费，为了比较入，但是

33、当年要支出一笔数额较大的购买费，为了比较 不同决策的优劣，常常要在一个较长的时间内考虑更新不同决策的优劣，常常要在一个较长的时间内考虑更新 决策问题。决策问题。 设备更新问题一般提法：在已知一台设备的效益函数设备更新问题一般提法：在已知一台设备的效益函数r(t)， 维修费用函数维修费用函数u(t)及更新费用函数及更新费用函数c(t)条件下，要求在条件下，要求在n年内的年内的 每年年初作出决策，是继续使用旧设备还是更换一台新的，使每年年初作出决策，是继续使用旧设备还是更换一台新的，使 n年总效益最大。年总效益最大。 rk(t)：在第：在第k年设备已使用过年设备已使用过t年年(或称役龄为或称役龄为

34、t年年)，再使用，再使用1年时的年时的 效益。效益。 uk(t) ：在第：在第k年设备役龄为年设备役龄为t年，再使用一年的维修费用。年，再使用一年的维修费用。 ck(t) ：在第：在第k年卖掉年卖掉台役龄为台役龄为t年的设备，买进一台新设备的更年的设备，买进一台新设备的更 新净费用。新净费用。 为折扣因子为折扣因子(01) ，表示一年以后的单位收入价值相当于现，表示一年以后的单位收入价值相当于现 年的年的 单位。单位。 动态规划模型动态规划模型 阶段变量阶段变量k：k=1,2,n，表示计划使用该设备的年限数。，表示计划使用该设备的年限数。 状态变量状态变量sk: 第第k年初，设备年初，设备已使

35、用过已使用过的年数，即役龄。的年数，即役龄。 决策变量决策变量xk: 是第是第k年初更新（年初更新（Replacement），还是保留使用（，还是保留使用（keep） 旧设备，分别用旧设备，分别用R与与K表示。表示。 状态转移方程为：状态转移方程为： 阶段指标为：阶段指标为： 1 1 1 k k s s Rx Kx k k 当 当 指标函数为：指标函数为： )()0()0( )()( ),( kkkk kkkk kkj scur susr xsv Rx Kx k k 当 当 ), 2 , 1(),( , nkxsvV n kj kkjnk 最优指标函数最优指标函数fk(sk)表示第表示第k年初

36、，使用一台已用了年初，使用一台已用了sk年的设备，到第年的设备，到第n年年 末的最大收益，则可得如下的逆序动态规划方程：末的最大收益，则可得如下的逆序动态规划方程： 实际上实际上， 0)( )(),(max)( 11 11 nn kkkk RK k kk sf sfxsv x sf k 或 )18. 7( )18. 7( b a )()()0()0( )()()( max)( 11 11 kkkkkk kkkkkk kk sfscur sfsusr sf Rx Kx k k 当 当 例例5 5 设某台新设备的年效益及年均维修费、更新净费用如表设某台新设备的年效益及年均维修费、更新净费用如表7-

37、7- 1515所示。试确定今后所示。试确定今后5 5年内的更新策略，使总收益最大。年内的更新策略，使总收益最大。 （设（设 ） 1 )(trk )(tuk )(tck 役龄役龄 项目项目 012345 效益效益54.543.7532.5 维修费维修费0.5 11.522.53 更新费更新费0.51.52.22.533.5 解解 如前述建立动态规划模型，如前述建立动态规划模型，n=5 当当k=5时时， )()0()0( )()( max)( 5555 5555 55 scur susr sf Rx Kx 5 5 当 当 状态变量状态变量s5可取可取1，2，3，4。 )1 ()0()0( ) 1

38、() 1 ( max) 1 ( 555 55 5 cur ur f Rx Kx 5 5 当 当 5 . 3 5 . 15 . 05 15 . 4 max K) 1 (x5当 =2.5 2 . 25 . 05 5 . 14 max)2( 5 fK)2(x5当 =2 5 . 25 . 05 275. 3 max)3( 5 f R)3(x5当 =1.5 35 .05 5 .23 max)4( 5 fR)2(x 5 当 役龄役龄 项目项目 012345 效益效益 54.54 3.7 5 32.5 维修费维修费0.5 11.522.53 更新费更新费 0.51.52.22.533.5 当当k=4时时，

39、状态变量状态变量s4可取可取1，2，3。 =6.5 役龄役龄 项目项目 012345 效益效益 54.54 3.7 5 32.5 维修费维修费0.5 11.522.53 更新费更新费 0.51.52.22.533.5 ) 1 ()()0()0( ) 1()()( max)( 54444 454444 44 fscur sfsusr sf Rx Kx 4 4 当 当 ) 1 ( 4 f 5 . 35 . 15 . 05 5 . 215 . 4 max R) 1 (x4当 )2( 4 f = 5 . 32 . 25 . 05 215 . 4 max=5.8R)2(x4当 ) 3( 4 f = 5

40、. 35 . 25 . 05 5 . 1275. 3 max=5.5R) 3(x 4 当 当当k=3时时， 状态变量状态变量s3可取可取1，2。 =9.5 役龄役龄 项目项目 012345 效益效益 54.54 3.7 5 32.5 维修费维修费0.5 11.522.53 更新费更新费 0.51.52.22.533.5 ) 1 ()()0()0( ) 1()()( max)( 43333 343333 33 fscur sfsusr sf Rx Kx 3 3 当 当 ) 1 ( 3 f 5 . 65 . 15 . 05 8 . 515 . 4 maxR) 1 (x3当 )2( 3 f= 5 .

41、 62 . 25 . 05 5 . 515 . 4 max =8.8 R)2(x3当 当当k=2时时， 状态变量状态变量s2只能取只能取1 役龄役龄 项目项目 012345 效益效益 54.54 3.7 5 32.5 维修费维修费0.5 11.522.53 更新费更新费 0.51.52.22.533.5 =12.5 ) 1 ()()0()0( ) 1()()( max)( 32222 232222 22 fscur sfsusr sf Rx Kx 2 2 当 当 ) 1 ( 2 f 5 . 95 . 15 . 05 8 . 815 . 4 maxR) 1 (x2当 当当k=1时时， 状态变量状

42、态变量s1只能取只能取0 役龄役龄 项目项目 012345 效益效益 54.54 3.7 5 32.5 维修费维修费0.5 11.522.53 更新费更新费 0.51.52.22.533.5 =17 ) 1 ()()0()0( ) 1()()( max)( 21111 121111 11 fscur sfsusr sf Rx Kx 1 1 当 当 5 .125 . 05 . 05 5 .125 . 05 max)0( 1 f Kx)0( 1 上述计算递推回去，当上述计算递推回去，当 时，由状态转移方程，时，由状态转移方程， 则则 则查则查 得：得： 状态状态 ，查：，查： Kx )0( 1 R

43、x RxfsKxs s 1 * 22211 2 1 )1 (11得，查知 Rx sKxs s 2 322 3 1 11推出 ) 1 ( 3 f Rx * 3 推出推出 ，查，查 1 4 s ) 1 ( 4 f Rx * 4 1 5 s) 1 ( 5 fKx * 5 最优策略为：最优策略为： ，即第一年初购买的设备到第二、三、四年初，即第一年初购买的设备到第二、三、四年初 各更新一次，用到第各更新一次，用到第5年末，其总效益为年末，其总效益为17万元。万元。 KRRRK, k5，s5可取可取1,2,3,4。 s51234 u5K RK RK RK R v5+f64.5-1 5-0.5-1.54-

44、1.5 5-0.5-2.23.75-2 5-0.5-2.53-2.5 5-0.5-3 f53.52.521.5 u5*KKRR k4, s4可取可取1,2,3。 s4123 u4K RK RK R v4+f54.5-1+2.5 5-0.5-1.5+3.5 4-1.5+2 5-0.5-2.2+3.53.75-2+1.5 5-0.5-2.5+3.5 f46.55.85.5 u4*RRR k3，s3可取可取1,2。 s312 u3K RK R v3+f44.5-1+5.8 5-0.5-1.5+6.54-1.5+5.5 5-0.5-2.2+6.5 f49.58.8 u4*RR k2, s2可取可取1。

45、 s21 u2K R v3+f24.5-1+8.8 5-0.5-1.5+9.5 f212.5 u2*R k1, s2可取可取0。 s10 u1K R v1+f25-0.5+12.5 5-0.5-0.5+12.5 f117 u1*K 货郎担问题一般提法为：一个货郎从某货郎担问题一般提法为：一个货郎从某 城镇出发，经过若干个城镇一次，且仅一次，城镇出发，经过若干个城镇一次，且仅一次， 最后仍回到原出发的城镇，问应如何选择行最后仍回到原出发的城镇，问应如何选择行 走路线可使总行程最短，这是运筹学的一个走路线可使总行程最短，这是运筹学的一个 著名问题，实际中有很多问题可以归结为这著名问题，实际中有很多

46、问题可以归结为这 类问题。类问题。 四、货郎担问题四、货郎担问题 设设 是已知的是已知的n n个城镇，城镇个城镇，城镇 到城镇到城镇 的距离为的距离为 ，现求从，现求从 出发，经各城镇一次且仅一次出发，经各城镇一次且仅一次 返回返回 的最短路程。若对的最短路程。若对n n个城镇进行排列，有个城镇进行排列，有 (n(n一一1)!1)!2 2种方案，所以穷举法是不现实的，这里介绍一种方案，所以穷举法是不现实的，这里介绍一 种动态规划方法。种动态规划方法。 货郎担问题也是求最短路径问题，但与例货郎担问题也是求最短路径问题，但与例4 4的最短路的最短路 问题有很大不同，建动态规划模型时，虽然也可按城镇数问题有很大不同，建动态规划模型时，虽然也可按城镇数 目目n n将问题分为将问题分为n n个阶段。但是状态变量不好选择，不容易个阶段。但是状态变量不好选择，不容易 满足无后效性。为保持状态间相互独立，可按以下方法建满足无后效性。为保持状态间相互独立，可按以下方法建 模：模： n vvv, 21