1、* 1第七章第七章 动态规划动态规划Dynamic Programming， DP美国数学家贝尔曼(Richard Bellman, 1920 1984)创始时间 上个世纪 50年代创始人动态规划是运筹学的主要分支之一 , 是现代企业管理中的一种重要决策方法 , 它是解决多阶段决策过程 的一种最优化方法Date本章主要内容n 多阶段决策过程及其问题举例 q 最短路问题n 动态规划的基本概念和基本方程 n 动态规划应用举例q 资源分配问题q 背包问题q 生产库存问题q Date 27.1 多阶段决策过程及其问题举例n 动态规划研究的问题 多阶段决策问题q 在时间或空间上可以划分为若干阶段，每一阶
2、段都需要根据现阶段的情况做出决策q 决策者每段决策时，不仅要考虑 本阶段目标最优 ，还应考虑 之后各阶段 的目标最优 ，最终达到整个决策活动的 总体目标最优q 当各个阶段的决策确定后，就构成了一个决策序列q 各阶段的决策一般与时间有关，故称 “动态 ”。但某些 “静态 ”问题可通过引进 “时间 ”因素，用动态规划方法来处理1 2状态 状态状态 n 状态决策 决策 决策状态Date 3n 动态规划分类：q 离散确定性 动态规划q 离散随机性 动态规划q 连续确定性 动态规划q 连续随机性 动态规划Date 4GD76543358109745EABC HF例 1 最短路径问题第一阶段 第二阶段 第
3、三阶段 第四阶段求从 A 到 H 的最短路径Date 5* 6n 第一种方法 称做 枚举法 （ 穷举法 ） ： 基本思想是列举出所有可能发生的方案和结果，再对它们进行比较，求出最优方案。这里，从 A 到 H 的路程共有 7条可能的路线，分别算出各条路线的距离，最后进行比较，可得最优路线当节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算n 第二种方法 熟称 贪心算法 ，亦即 “ 局部最优路径 ” 法，只选择当前最短途径， “ 逢近便走 ” ，错误地以为局部最优会致整体最优。在这种想法指导下，所取决策必是A C G H，距离为 4+5+8=17Dated(sk,
4、uk)： 第 k 阶 段，采取策略 uk 所发生的距离fk(sk)： 第 k 阶段，在 sk 状态时到终点 H 的最短距离动态规划的基本思想： 如果起点 A 经过 B, E 而到 H最优，则由 B 出发经 E 到 H 这条子路线，必为从 B 到 H 的最短路线。所以，寻找最短路线，应该从最后一段开始找，然后往前递推假设 sk： 第 k 阶段初所处的节点uk(sk)： 在 sk 状态时第 k 阶段所作的决定GD76543358109745EABC HFDate 7f4(H)=0GD76543358109745EABC HFDate 8f4(H)=0GD76543358109745EABC HFf3(E)=3Date 9f4(H)=0GD76543358109745EABC HFf3(E)=3f3(F)=5Date 10
