动态规划(运筹学讲义).pdf

第八章 动态规划 Dynamic Programming  §1 动态规划问题实例  §2 动态规划的基本概念  §3 基本原理和基本方程  §4 动态规划的应用 1 §1动态规划问题实例 动态规划DP是运筹学的一个分支，是解决多阶段决策过程 最优化的一种数学方法（一种分析多阶段决策过程的数学方 法），这种方法可根据人们所采取的措施，一步步地控制过程 的发展，以实现预定的要求。 1951年美国数学家R.E. Bellman等人根据一类多阶段决策问 题的特性，提出了解决这类问题的最优化原理，把多阶段过程 转化为一系列单阶段问题逐个求解，并研究了许多实际问题而 建立了动态规划。 许多问题用动态规划研究求解比线性规划、非线性规划更有 效，特别是离散性问题，解析数学无用武之地，而动态规划成 为得力工具； 某些情况下，用动态规划处理不仅能作定性描述分析，且 可利用计算机给出求其数值解的方法。 2 §1动态规划问题实例 多阶段决策过程 由问题的特征可将决策过程按 时间、空间等方式分为若干互相联系的不同阶 段，在每个阶段有若干种不同方案可供选择，进 行决策，每个阶段的决策执行将影响到下一阶段 的决策，决策者根据全局最优在每一阶段做出决 策，从而使整个过程达到最优 3 §1动态规划问题实例 例5.1 最短路问题 下图为一城市若干单向道路组成的交通 图，两点之间连线数字表示两点间的距离，问应该如何选择 路线，使A到G点路程最短 1 C1 6 2 B1 3 3 8 D1 2 E1 5 3 F 1 4 5 6 C2 5 5 1 D2 E2 2 G A 8 3 2 3 7 C3 3 3 6 F 3 B 2 2 8 D3 3 E3 6 6 C 4 1 2 4 3 4 5 6 A →B B →C C →D D →E E →F F →G i i j j k k l l m m (i=12) (j=1,…,3) (k=1,2,3) (l=1,2,3) (m=1,2,3) 6阶段 图8-1