第章动态规划.ppt

当 k=1 时： 矛盾，所以舍去 sk 9/2 故 极大值只能在 [0，10] 的端点取得，比较[0，10]两个端点的函数值 即全部资金投于第3个项目 (解法2) 用顺序解法 1. 阶段划分: （同上） 和决策变量 2. 状态变量: 用 sk 表示可用于第1到第 k-1个项目投资的金额，即对第 k 个项目到第3个项目投资后的剩余资金数量。 3. 决策变量: （同上） 4. 状态转移方程: 5. 决策变量的取值范围： 6. 最优指标函数： 令 fk(sk+1) 表示第 k 段投资额 sk+1 为时，第1到第 k 项目所获的最大收益，此时顺序解法的基本方程为： 当 k=1 时，有 当 k=2 时，有 当 k＝3 时，有 ? x3 = 9/4 为极小点。 极大值应在[0，s4] ＝[ 0，10 ] 端点取得 再由状态转移方程逆推： 5 设备更新问题 设备在使用全过程中会遭受磨损, 使用一段时间后就要维修, 而且使用的时间越长, 维修费用越高, 设备使用多少时间在经济上最合算, 就是设备更新问题。 例: 某设备的年效益和年均维修费用如下表, 如何在未来的5年内进行更新决策。 使用年限 0 1 2 3 4 效益 r 5 4.5 4 3.75 3 维修费u 0.5 1 1.5 2 2.5 更新费c 0.5 1.5 2.2 2.5 3 分析： 阶段 k = 1, 2, 3, 4, 5; sk 表示 k 年初设备已使用的年限; xk 为 k 年初决定设备是继续使用还是更新的决策变量: xk = 1表示继续使用, xk = 0表示更新; 状态转移方程: sk+1 = sk + 1，xk=1; sk+1 = 1，xk=0 阶段函数: vk(sk) = r(skxk) - u(skxk) - c(sk)(1-xk ) r(0) - u(0) - c(sk) (xk= 0) vk(sk) = r(sk) - u(sk ) (xk= 1) 递推函数: fk(sk) = max{vk(sk) + fk+1(sk+1)} k = 5 状态变量 s5 可取 1, 2, 3, 4 f5(1) = maxx1=0,1{r(0) - u(0) - c(1), r(1) - u(1)} = max {5-0.5-1.5, 4.5-1}= 3.5 (x5*=1) f5(2)=max{5-0.5-2.2, 4-1.5}= 2.5 (x5*=1) f5(3)=max{5-0.5-2.5, 3.75-2}= 2 (x5*=0) f5(4)=max{5-0.5-3, 3-2.5} = 1.5 (x5*=0) k = 4 状态变量 s4 可取 1, 2, 3 f4(1) = max{r(0)-u(0)-c(1)+f5(1), r(1)-u(1)+ f5(2)} = max {5-0.5-1.5+3.5, 4.5-1+2.5} = 6.5 (x4* = 0) f4(2) = max {5-0.5-2.2+3.5, 4-1.5+2} = 5.8 (x4* = 0) f4(3) = max {5-0.5-2.5+3.5, 3.75-2+1.5} = 5.5 (x4* = 0) k = 3 状态变量 s3 可取 1, 2, f3(1) = max{r(0) - u(0) - c(1) + f4(1), r(1) - u(1) + f4(2)} = max {5-0.5-1.5+6.5, 4.5-1+5.8} = 9.5 (x3* = 0) f3(2) = max {5-0.5-2.2+6.5, 4-1.5+5.5} = 8.8 (x3* = 0) k = 2 状态变量 s2 可取 1, f2(1) = max{r(0) - u(0) - c(1) + f3(1), r(1) - u(1) + f3(2)} = max {5-0.5-1.5+9.5, 4.5-1+8.8} = 12.5