第四章动态规划 4.1一般方法 1.多阶段决策问题 多阶段决策过程:问题的活动过程分为若干相互联系的阶段,任 阶段i以后的行为仅依赖于i阶段的过程状态,而与i阶段之前的过程如何 达到这种状态的方式无关。在每一个阶段都要做出决策,这决策过程称 为多阶段决策过程( multistep decision process) 最优化问题:问题的每一阶段可能有多种可供选择的决策,必须从 选揉二种决策;各阶段的决策构成一个决策序列。决策序列不同,所 问题的结果可 多阶段决策的最优化问题就是:求能够获得问题最优解的决策序 列—最优决策序列。 2021/2/20
2021/2/20 1 第四章 动态规划 4.1 一般方法 1. 多阶段决策问题 多阶段决策过程：问题的活动过程分为若干相互联系的阶段，任一 阶段i以后的行为仅依赖于i阶段的过程状态，而与i阶段之前的过程如何 达到这种状态的方式无关。在每一个阶段都要做出决策，这决策过程称 为多阶段决策过程(multistep decision process) 。 最优化问题：问题的每一阶段可能有多种可供选择的决策，必须从 中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所 导致的问题的结果可能不同。 多阶段决策的最优化问题就是：求能够获得问题最优解的决策序 列——最优决策序列。 云图 V1 V2 云图 V ... 云图 N
2.多阶段决策过程的求解策略 1)枚举法 穷举可能的决策序列,从中选取可以获得最优解的决策序列 2)动态规划 20世纪50年代初美国数学家 REBellman等人在研究多阶段决策过 程的优化问题时,提出了著名的最优化原理( prIncip| e of optimality), 把多阶段过程转化为一系列单阶段问题,创立了解决这类过程优化问 题的新方法—动态规划。 动态规划( dynamic programming)是运筹学的一个分支,是求解决 策过程( ecision process)最优化的数学方法。 应用领域:动态规划问世以来,在经济管理、生产调度、工程技 术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、 资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它 方法求解更为方便 2021/2/20
2021/2/20 2 2. 多阶段决策过程的求解策略 1）枚举法 穷举可能的决策序列，从中选取可以获得最优解的决策序列 2）动态规划 20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过 程的优化问题时，提出了著名的最优化原理(principle of optimality)， 把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问 题的新方法——动态规划。 动态规划(dynamic programming)是运筹学的一个分支，是求解决 策过程(decision process)最优化的数学方法。 应用领域：动态规划问世以来，在经济管理、生产调度、工程技 术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、 资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它 方法求解更为方便
3.最优性原理( Principle of optimalit!y) 过程的最优决策序列具有如下性质:无论过程的初始状 态和初始决策是什么,其余的决策都必须相对于初始决策所 产生的状态构成一个最优决策序列 利用动态规划求解问题的前提 1)证明问题满足最优性原理 如果对所求解问题证明满足最优性原理,则说明用动态 规划方法有可能解决该问题 2)获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键 2021/2/20
2021/2/20 3 3. 最优性原理(Principle of Optimality) 过程的最优决策序列具有如下性质：无论过程的初始状 态和初始决策是什么，其余的决策都必须相对于初始决策所 产生的状态构成一个最优决策序列。 利用动态规划求解问题的前提 1) 证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明用动态 规划方法有可能解决该问题 2) 获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键
例41[多段图问题]多段图G=(V,E)是一个有向图,且具有特性 结点:结点集V被分成k≥2个不相交的集合V,1≤i≤k, 其中V1和V分别只有一个结点:s(源结点)和t(汇点) 段:每一集合V定义图中的一段—一共k段。 边:所有的边(u,v)均具有如下性质:若<u,v>∈E,则 若u∈V;,则u∈Vi+1,即该边将是从某段i指向i+1段, 1≤i≤k-1。 成本:每条边(u,v)均附有成本c(u,v) s到t的路径:是一条从第1段的源点s出发,依次经过第2段的某 结点v2,,经第3段的某结点v3,、…、最后在第k 段的汇点t结束的路径。 该路径的成本是这条路径上边的成本和。 多段图问题:求由s到t的最小成本路径 2021/2/20
2021/2/20 4 例4.1 [多段图问题]多段图G=(V,E)是一个有向图，且具有特性: 结点：结点集V被分成k≥2个不相交的集合Vi，1≤i≤k， 其中V1和Vk分别只有一个结点：s(源结点)和t(汇点)。 段： 每一集合Vi定义图中的一段——共k段。 边： 所有的边(u,v)均具有如下性质： 若<u,v>∈E，则 若u∈Vi，则u∈Vi＋1,即该边将是从某段i指向i+1段， 1≤i≤k－1。 成本：每条边(u,v)均附有成本c(u,v)。 s到t的路径：是一条从第1段的源点s出发，依次经过第2段的某 结点v2,i，经第3段的某结点v3,j、…、最后在第k 段的汇点t结束的路径。 该路径的成本是这条路径上边的成本和。 多段图问题：求由s到t的最小成本路径
V2 4 6 6 5 7 3 2 3 10 12 4 6 8)0→ 11 8 5段图 2021/2/20
2021/2/20 5 1 2345 678 9 10 11 12 9732 4 3 2 7 11 11 8 1 4 563 5 6 425 V 1 V2 V3 V4 V5 5段图