第六章动态规划多阶段决策过程及实例动态规划的基本概念和基本方程动态规划的最优性原理和最优性定理动态规划与静态规划的关系动态规划应用举例
第六章 动态规划 多阶段决策过程及实例 动态规划的基本概念和基本方程 动态规划的最优性原理和最优性定理 动态规划与静态规划的关系 动态规划应用举例
·动态规划是解决多阶段最优决策的方法，由美国数学家贝尔曼于1954年首先提出的，1957年贝尔曼发表动态规划方面的第一部专著《动态规划》，标志着运筹学的一个新分支的创立
动态规划是解决多阶段最优决策的方法，由美 国数学家贝尔曼于1954年首先提出的； 1957年贝尔曼发表动态规划方面的第一部专著 《动态规划》，标志着运筹学的一个新分支的 创立
$1多阶段决策过程及实例线性规划、整数规划--静态性，叙静态的优化方法：述和解决问题都是针对某一时刻发生的情况，与时间的推移无关。另一类问题：包含有与时间相关联的变量--多阶段决策过程。最优性原理系列相互联系的单阶段问题决策决策决策状态状态状态状态状态2n所有决策构成一个决策序列，多阶段决策过程目的是求使整个过程达到最好活动效果。一个决策序列是在变化中产生出来的，这种规划叫动态规划
§1 多阶段决策过程及实例 状态 1 决策 状态 2 决策 状态 状态 . 状态 n 决策 静态的优化方法：线性规划、整数规划-静态性，叙 述和解决问题都是针对某一时刻发生的情况，与时间 的推移无关。 另一类问题：包含有与时间相关联的变量-多阶段决 策过程。 一系列相互联系的单阶段问题 最优性原理 所有决策构成一个决策序列，多阶段决策过程目的是 求使整个过程达到最好活动效果。一个决策序列是在 变化中产生出来的，这种规划叫动态规划
动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题，采用顺序求解方法，通过解一系列小问题达到求解整个问题目的；·动态规划的各个决策阶段不但要考虑本阶段的决策目标，还要兼顾整个决策过程的整体目标，从而实现整体最优决策。。动态规划没有准确的数学表达式和定义精确的算法他强调具体问题具体分析，依赖分析者的经验和技巧
动态规划将复杂的多阶段决策问题分解为一系列简单 的、离散的单阶段决策问题，采用顺序求解方法，通 过解一系列小问题达到求解整个问题目的； 动态规划的各个决策阶段不但要考虑本阶段的决策目 标，还要兼顾整个决策过程的整体目标，从而实现整 体最优决策。 动态规划没有准确的数学表达式和定义精确的算法， 他强调具体问题具体分析，依赖分析者的经验和技巧
例1最短路线问题下图给定一个线路网络，两点之间连线上的数字表示两点间距离（或费用），试求一条由A到G的铺管线路，使总距离为最短（或总费用最小）。DED6F3DE33
例1 最短路线问题 下图给定一个线路网络，两点之间连线上的数字表 示两点间距离（或费用），试求一条由A到G的铺管 线路，使总距离为最短（或总费用最小）。 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 8 4 3 5 3 3 8 2 2 2 1 3 3 3 5 2 5 6 6 4 3