CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 第五章动态规划 不要过河拆桥
©管理与人文学院 忻展红 1999，4 第五章 动态规划 不要过河拆桥
动态规划 Dynamic programming 五十年代贝尔曼(B.E. Bellman)为代表的研究成果 属于现代控制理论的一部分 以长远利益为目标的一系列决策 最优化原理,可归结为一个递推公式 51动态规划的最优化原理及其算法23 511求解多阶段决策过程的方法 例5.1.1最短路问题
2 动态规划 Dynamic programming • 五十年代贝尔曼(B. E. Bellman)为代表的研究成果 • 属于现代控制理论的一部分 • 以长远利益为目标的一系列决策 • 最优化原理，可归结为一个递推公式 5.1 动态规划的最优化原理及其算法 5.1.1 求解多阶段决策过程的方法 例5.1.1 最短路问题 H L O B I E C A F D J G K N P M 4 3 5 2 3 5 2 3 4 4 7 7 1 1 3 4 2 2 2 5 4 8 1 2
决策树法 可以枚举出20条路径,其中最短的路径长度为16
3 决策树法 A C E H I I F J I F D G J J K 可以枚举出20条路径，其中最短的路径长度为16
例5.1.1最短路题 表现为明显的阶段性 一条从A到B的最短路径 中的任何一段都是最短的 3 10 设S表示由点到B点的最短路 径的长度 则有S4=min dac +sc AD+S 8 因此我们可以从B向回搜索最短路 标记法 6 °如何找出最短路径 最优性原理 最优策略的一部分也是最优的” 每步的决策只与相邻阶段状态有关6⊥54⊥3121阶 而与如何达到这一状态无关
4 例5.1.1 最短路问题 • 表现为明显的阶段性 • 一条从A 到B 的最短路径 中的任何一段都是最短的 H L O B I E C A F D J G K N P M 4 3 5 2 3 5 2 3 4 4 7 7 1 1 3 4 2 2 2 5 4 8 1 2 1 6 1 2 1 4 0 2 1 4 5 7 1 0 8 6 7 1 1 8 9 6 5 4 3 2 1 阶 段 H L O B I E C A F D J G K N P M 4 3 5 2 3 5 2 3 4 4 7 7 1 1 3 4 2 2 2 5 4 8 1 2 1 6 1 2 1 4 0 2 1 4 5 7 1 0 8 6 7 1 1 8 9 6 5 4 3 2 1 阶 段 最优性原理 “最优策略的一部分也是最优的” 每步的决策只与相邻阶段状态有关， 而与如何达到这一状态无关 + + = AD D AC C A i d S d S S S i B 则有 min 径的长度 设 表示由 点到 点的最短路 •因此我们可以从B向回搜索最短路 •标记法 •如何找出最短路径
512动态规划的基本概念及递推公式 状态(每阶段初始的出发点) 最短路问题中,各个节点就是状态 生产库存问题中,库存量是状态 物资分配问题中,剩余的物资量是状态 控制变量(决策变量) 最短路问题中,走哪条路 生产库存问题中,各阶段的产品生产量 物资分配问题中,分配给每个地区的物资量 阶段的编号与递推的方向 一般采用反向递推,所以阶段的编号也是逆向的 当然也可以正向递推
5 5.1.2 动态规划的基本概念及递推公式 • 状态(每阶段初始的出发点) – 最短路问题中，各个节点就是状态 – 生产库存问题中，库存量是状态 – 物资分配问题中，剩余的物资量是状态 • 控制变量(决策变量) – 最短路问题中，走哪条路 – 生产库存问题中，各阶段的产品生产量 – 物资分配问题中，分配给每个地区的物资量 • 阶段的编号与递推的方向 – 一般采用反向递推，所以阶段的编号也是逆向的 – 当然也可以正向递推