复件 7.2动态规划2.ppt

k 阶段 uk 决策 fk sk sk 状态 从状态sk到全过程结束的整体最优函数 p1 n u1 u2 un 策略 动态规划的建模及求解 复习 一般的动态规划基本方程可以表示为 fk sk opt dk sk uk fk 1 sk 1 k 1 2 n uk dksk fn 1 sn 1 0 optimization 过程行进方向 动态规划寻优途径 后向动态规划方法 逆序解法 主要内容 前向动态规划方法动态规划的应用设备更新问题货郎担问题 例1 k 0时 f0 s1 f0 A 0 边界条件 k 1时 按f1 s2 的定义有 f1 1 8 f1 2 9 f1 3 5 u1 1 A u1 2 A u1 3 A 前向动态规划方法 k 2时 u2 4 3 u2 5 1 u2 6 1 k 3时 u3 7 6 u3 8 5 k 4时 u4 E 8 1 5 8 A E f4 E 17 8 14 14 12 12 13 9 5 17 标号法 适用范围 动态规划 区别 本例题的前向动态规划的基本方程应怎样写 f0 s1 0 fk sk 1 min d sk 1 uk fk 1 sk k 1 2 3 4 uk f5 s5 0 与后向动态规划的基本方程相比较 区别 1 基本方程形式不同 顺序解法 逆序解法 区别 2 状态转移方式不同 逆序解法中第k段的输入状态为 sk 决策为 uk 由此确定的输出为 sk 1 即第k 1段的状态所以状态转移方程为 sk 1 Tk sk uk 称之为状态sk到状态sk 1的顺序转移方程 顺序解法中第k段的输入状态为 sk 1 决策为 uk 输出为sk 所以 状态转移方程为 sk Tk sk 1 uk 称之为 由状态sk 1到sk的逆序状态转移的方程 后向动态规划方法 逆序解法 前向动态规划方法 顺序解法 区别 3 指标函数的定义不同 逆序解法中 我们定义最优指标函数fk sk 表示第k段从状态sk出发 到终点的后部子过程最优效益值 f1 s1 是整体最优函数值 顺序解法中 应定义最优指标函数fk sk 1 表示第k段从起点到状态sk 1的前部子过程最优效益值 fn sn 1 是整体最优函数值 当初始状态给定时 用逆序解法 后向动态规划方法 比较方便 当终止状态给定时 用顺序解法 前向动态规划方法 比较方便 根据问题灵活掌握 7 4动态规划的应用 设备更新问题 货郎担问题 7 4 1设备更新问题 企业什么时候应该更换新设备 企业为什么需要更换新设备 陈旧 损坏 技术落后 成本与效益 购买的花费 老设备的维修费用 使用新设备能够带来的收益增加 在已知一台设备的效益函数r t 维修费用函数u t 及更新费用函数c t 条件下 在n年内 每年年初做出决策 是继续使用旧设备还是更换一台新设备 使n年总效益最大 在第k年设备已使用过t年 或称役龄为t年 再使用1年时的效益 在第k年设备役龄为t年 再使用1年的维修费用 在第k年卖掉一台役龄为t年的设备 买进一台新设备的更新净费用 为折扣因子 0 1 表示1年以后的单位收入价值相当于现年的 单位 rk t gk t ck t 建立动态规划模型 k 1 2 n 第k年初 设备已使用过的年数 即役龄 第k年年初是更新 还是继续使用旧设备 分别用R与K表示 R是更新 Replace K是保留 Keep 状态变量sk 决策变量uk 阶段k 状态转移方程为 sk 1 sk 1当uk K 1当uk R 阶段指标为 fk sk 表示第k年初 使用一台已用了sk年的设备 到第n年末的最大收益 最优指标函数 逆序动态规划方程 设某台新设备的年效益及年均维修费 更新净费用如表5 2所示 试作今后5年内的更新决策 使总收益最大 设 1 表 5 2 例3 单位 千元 解 当k 5时 状态变量s5可取1 2 3 4 u5 1 K f5 2 u5 2 K u5 4 R u5 3 R f5 3 f5 4 当k 4时 u4 1 R 状态变量s4可取1 2 3 u4 3 R u4 2 R 当k 3时 状态变量s3可取1 2 u3 2 R u3 1 R 当k 2时 状态变量s2只可取1 u2 1 R u1 0 K 当k 1时 s2只可取0 结论 按上述计算递推回去 u1 K s2 1 sk 1 sk 1当uk K 1当uk R f2 1 u2 R s3 1 f3 1 u3 R s4 1 f4 1 u4 R s5 1 f5 1 u5 K 最优策略为 K R R R K 7 4 2货郎担问题 运筹学中的著名问题 一个货郎从某城镇出发 经过若干个城镇一次且仅一次 最后仍回到原出发的城镇 问应如何选择行走路线可使总路程最短 例4 已知4个城市间距离如表5 3所示 求从出发 经其余城市一次且仅一次的最短路径与距离 表 5 3 单位 千米 表示从v1到vi中间所有可能经过的城市集合 S实际上是包含除v1与vi两个点之外其余点的集合 但S中点的个数要随阶段数改变 表示从点出发 经过S集合中所有点一次最后到达vi 最优指标函数fk i S 表示从v1出发经由k个城镇的S集合到vi的最短距离 状态变量 i S S 决策变量pk i s 表示从v1经k个中间城镇的S集合到城镇vi的最短路线上邻接vi的前一个城镇 则动态规划的顺序递推关系为 基本方程 解 由边界条件可知 f0 2 d12 6 f0 3 d13 7 f0 4 d14 9 当k 1时 f1 2 3 f0 3 d32 7 8 15 f1 2 4 f0 4 d42 9 5 14 f1 3 2 f0 2 d23 6 9 15 f1 3 4 f0 4 d43 9 5 14 f1 4 2 f0 2 d24 6 7 13 f1 4 3 f0 3 d34 7 8 15 当k 2时 f2 2 3 4 min f1 3 4 d32 f1 4 3 d42 min 14 8 15 5 20 P2 2 3 4 4 f2 3 2 4 min f1 2 4 d23 f1 4 2 d43 min 14 9 13 5 18 P2 3 2 4 4 f2 4 2 3 min f1 2 3 d24 f1 3 2 d34 min 15 7 15 8 22 P2 4 2 3 2 当k 3时 f3 1 2 3 4 min f2 2 3 4 d21 f2 3 2 4 d31 f2 4 2 3 d41 min 20 8 18 5 22 6 23 P3 1 2 3 4 3 东普鲁士的哥尼斯堡城是一个风景宜人的旅游胜地 也是一个在战争中双方必争的战略要地 哥尼斯堡城中有一条河叫做布勒格尔河 该河横贯城区 它有两条支流 分别称为新河和旧河 两条支流在城中心汇合 成为一条主流 大河 在新旧两河合流处 中间有一个岛形地带 是繁华的商业中心 这种分布情况把全城分为北区 东区 南区及中央的岛区四个区域 这四个区域分别由七座桥相连