运筹学动态规划应用举例.ppt

设备更新问题一般提法：在已知一台设备的效益函数r(t)，维修费用函数u(t)及更新费用函数c(t)条件下，要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年总效益最大。 rk(t)：在第k年设备已使用过t年(或称役龄为t年)，再使用1年时的效益。 uk(t) ：在第k年设备役龄为t年，再使用一年的维修费用。 ck(t) ：在第k年卖掉—台役龄为t年的设备，买进一台新设备的更新净费用。 ?为折扣因子(0???1) ，表示一年以后的单位收入价值相当于现年的?单位。 动态规划模型 阶段变量k：k=1,2,…,n，表示计划使用该设备的年限数。 状态变量sk: 第k年初，设备已使用过的年数，即役龄。 决策变量xk: 是第k年初更新（Replacement），还是保留使用（keep）旧设备，分别用R与K表示。 状态转移方程为： 阶段指标为： 指标函数为： 最优指标函数fk(sk)表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，则可得如下的逆序动态规划方程： 实际上， 例11 设某台新设备的年效益及年均维修费、更新净费用如表7-15所示。试确定今后5年内的更新策略，使总收益最大。（设 ） 役龄 项目 0 1 2 3 4 5 效益 5 4.5 4 3.75 3 2.5 维修费 0.5 ? 1 1.5 2 2.5 3 更新费 0.5 1.5 2.2 2.5 3 3.5 解 如前述建立动态规划模型，n=5 当k=5时， 状态变量s5可取1，2，3，4。 =2.5 =2 =1.5 役龄 项目 0 1 2 3 4 5 效益 5 4.5 4 3.75 3 2.5 维修费 0.5 ? 1 1.5 2 2.5 3 更新费 0.5 1.5 2.2 2.5 3 3.5 当k=4时， 状态变量s4可取1，2，3。 = = 6.5 役龄 项目 0 1 2 3 4 5 效益 5 4.5 4 3.75 3 2.5 维修费 0.5 ? 1 1.5 2 2.5 3 更新费 0.5 1.5 2.2 2.5 3 3.5 = = 5.8 = = 5.5 当k=3时， 状态变量s3可取1，2。 = = 9.5 役龄 项目 0 1 2 3 4 5 效益 5 4.5 4 3.75 3 2.5 维修费 0.5 ? 1 1.5 2 2.5 3 更新费 0.5 1.5 2.2 2.5 3 3.5 = = 8.8 当k=2时， 状态变量s2只能取1 役龄 项目 0 1 2 3 4 5 效益 5 4.5 4 3.75 3 2.5 维修费 0.5 ? 1 1.5 2 2.5 3 更新费 0.5 1.5 2.2 2.5 3 3.5 = = 12.5 当k=1时， 状态变量s1只能取0 役龄 项目 0 1 2 3 4 5 效益 5 4.5 4 3.75 3 2.5 维修费 0.5 ? 1 1.5 2 2.5 3 更新费 0.5 1.5 2.2 2.5 3 3.5 = 17 上述计算递推回去，当 时，由状态转移方程， 则 则查 得： 状态 ，查： 推出 ，查 最优策略为： ，即第一年初购买的设备到第二、三、四年初各更新一次，用到第5年末，其总效益为17万元。 k＝5，s5可取1,2,3,4。 R 1.5 3-2.5 5-0.5-3 K R 4 R 2 3.75-2 5-0.5-2.5 K R 3 K 2.5 4-1.5 5-0.5-2.2 K R 2 K u5* 3.5 f5 4.5-1 5-0.5-1.5 v5+f6 K R u5 1 s5 k＝4, s4可取1,2,3。 R 5.5 3.75-2+1.5 5-0.5-2.5+3.5 K R 3 R 5.8 4-1.5+2 5-0.5-2.2+3.5 K R 2 R u4* 6.5 f4 4.5-1+2.5 5-0.5-1.5+3.5 v4+f5 K R u4 1 s4 k＝3，s3可取1,2。 R 8.8 4-1.5+5.5 5-0.5-2.2+6.5 K R 2 R u4* 9.5 f4 4.5-1+5.8 5-0.5-1.5+6.5