第六章动态规划多阶段决策过程及实例动态规划的基本概念和基本方程动态规划的最优性原理和最优性定理动态规划与静态规划的关系动态规划应用举例
第六章 动态规划 多阶段决策过程及实例 动态规划的基本概念和基本方程 动态规划的最优性原理和最优性定理 动态规划与静态规划的关系 动态规划应用举例
·动态规划是解决多阶段最优决策的方法，由美国数学家贝尔曼于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
$2动态规划的基本概念和基本方程例1所示的线路网络是一个多阶段决策。由于所选路线不同，会有若干个不同策略，用穷举法可求出其最短路线，从A到G共有C,1C31C,1C,1C,1C,1=48条路径，每条路径要做5次加法，这样就要做240次加法运算。比较48条不同路线的距离值,D最短为F一G当问题的阶段数很多时，其计算量就增加，这种方法就不可能现实
§2 动态规划的基本概念和基本方程 例1所示的线路网络是一个多阶段决策。由于所选 路线不同，会有若干个不同策略，用穷举法可求出 其最短路线，从A到G共有 C2 1C3 1C2 1C2 1C2 1C1 1=48条路径，每条路径要做5 次加法，这样就要做240次加法运算。比较48条 不同路线的距离值，最短为 A G B1 C2 D1 E2 F2 当问题的阶段数很多时，其计算量就增加，这种 方法就不可能现实
动态规划的基本概念和基本方程一口使用动态规划方法求解决策问题首先要将问题改造成符合动态规划求解要求的形式，要涉及以下概念：阶段√状态√决策与策略√状态转移/指标函数
使用动态规划方法求解决策问题首先要将问题 改造成符合动态规划求解要求的形式，要涉及 以下概念： 阶段 状态 决策与策略 状态转移 指标函数 一、动态规划的基本概念和基本方程
划分阶段把一个复杂决策问题按照时间或空间特征分解为若于（n）个相互联系的阶段（stage），以便按照顺序求解阶段一般用下标k表示......-1阶段2阶段3阶段4阶段5阶段6阶段62DE33B5F1DE8B6F32DDE33
1、划分阶段 把一个复杂决策问题按照时间或空间特征分解为若干 （n）个相互联系的阶段（stage）,以便按照顺序求解 阶段一般用下标 k 表示 1阶段 2阶段 3阶段 4阶段 5阶段 6阶段 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
确定状态2.第三阶段状态的可达状态集合为点集合{Ci,C2,C3,C4], 记为 S3= {Ci,C2,C3,C]每阶段有若干状态(stat件，k阶段的状态特征可用状描述；状态有起始、中间、最终壮分，每一阶段的全部状态构成该阶段的可达状态集用S,表示。StES1阶段2阶段3阶段4阶段5阶段6阶段6C8DE32B5C1DE3X123N7SB631F32bD3)4E3Ca
2、确定状态 每阶段有若干状态（state）,表示某一阶段决策所面临的条 件，k 阶段的状态特征可用状态变量sk 描述； 状态有起始、中间、最终状态之分，每一阶段的全部状态 构成该阶段的可达状态集合，用Sk 表示。sk Sk S1 S2 S3 S4 S5 S6 S7 第三阶段状态的可达状态集合为点集合 {C1 ,C2 ,C3 ,C4 },记为 S3= {C1 ,C2 ,C3 ,C4 } 1阶段 2阶段 3阶段 4阶段 5阶段 6阶段 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
3、决策从第二阶段状态B出发，有三种不同的决策其允许决策集为D，（B,)={C1，C2，C}。若选取行的每阶段都要做出的点位C，则C,是状态B,在决策u,(B,)下的一选择。个新的状态，记作u（B）=C2·在k阶段s状态的庆呆衣小外阶段，EuRk状态为S,时对方案的选又值范围由允许决策集合Dk(表示，即uk（sk）S1EE26F3DE33
3、决策 每阶段都要做出决策，表示从某一阶段的某一状态出发进行的 选择。 在 k 阶段 sk 状态的决策由决策变量uk (sk ）描述，表示第k阶段 状态为 sk 时对方案的选择。其取值范围由允许决策集合 Dk （ sk ）表示，即uk （sk ） Dk （sk ）。 从第二阶段状态B1出发，有三种不同的决策， 其允许决策集为D2 (B1 )={C1 ,C2 ,C3 }。若选取 的点位C2，则C2是状态B1在决策u2 (B1 )下的一 个新的状态，记作u2 (B1 ) =C2 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