第四章动态规划 (Dynamic Programming 上个世纪50年代 创始时间 美国数学家贝尔曼 创始人 (Richard. Bellman)
美国数学家贝尔曼 （Richard. Bellman) 创始时间 上个世纪50年代 创始人
是运筹学的一个主要分支 ·是解决多阶段决策过程的最优化的一种方法 多阶段决策过程:是一类特殊的活动过程 这类活动可以按时间顺序 分解成若干个相互联系的 阶段,每个阶段都有若干 个方案可供选择。 多阶段决策过程的最优化的目标: 达到整个活动过程的总体效果最优 ·主要用于解决:最优路径问题,资源分配问题, 排序问题投资问题,装载问题 生产计划与库存问题, 生产过程的最优控制等
• 是运筹学的一个主要分支 • 是解决多阶段决策过程的最优化的一种方法 多阶段决策过程： 资源分配问题， 生产计划与库存问题， 排序问题 ,投资问题，装载问题 生产过程的最优控制等 是一类特殊的活动过程， 这类活动可以按时间顺序 分解成若干个相互联系的 阶段，每个阶段都有若干 个方案可供选择。 多阶段决策过程的最优化的目标： 达到整个活动过程的总体效果最优 •主要用于解决：最优路径问题
离散确定型 动态规划离散随机型 连续确定型 连续随机型
动态规划 离散确定型 离散随机型 连续确定型 连续随机型
4.1动态规划的基本概念 和方法 几个典型的例题
4.1 动态规划的基本概念 和方法 一、几个典型的例题
例1没从甘肃要铺一条煤气管道到北京,途中须经 过三个省:陕西、山西、河北,每省设一个中 最间站。各省建站可供选择的地点及各段距离如 短 路/下图,现要求选择一条甘肃到北京的铺管线路, 问使总距离最短。 题 多阶段决策问题 铺设方案l:骆埏策略y北京、6Q ③20 ①→④→⑤⑧ 河北G8价 铺设方案2:路长=16 山西 陕西 ①4→ 个策略 每一个阶段的决策合在一起构成一个铺设方案 每个策略对应一个路长 寻找路长最短的铺设方案 寻找最优策略
例1 设从甘肃要铺一条煤气管道到北京，途中须经 过三个省：陕西、山西、河北，每省设一个中 间站。各省建站可供选择的地点及各段距离如 下图，现要求选择一条甘肃到北京的铺管线路， 使总距离最短。 ○1 ○2 ○3 ○4 ○5 ○6 ○7 ○8 ○9 ○10 北京 河北 山西 陕西 甘肃 8 4 5 8 9 6 1 6 10 9 6 7 7 3 8 4 2 3 最 短 路 问 题 多阶段决策问题 ○1 ○3 ○5 ○8 ○10 路长=21 ○1 ○4 ○6 ○9 ○10 路长=16 每一个阶段的决策合在一起构成一个铺设方案 铺设方案1： 铺设方案2： 一个策略 每个策略对应一个路长 寻找路长最短的铺设方案 寻找最优策略 策略