文档介绍：动态规划问题(多阶段决策问题)
多阶段决策过程
多阶段决策过程是活动过程可按时间或空间顺序分解成若干相互独立、相互联系的阶段,在每个阶段的状态下做出决策,整个过程的决策构成一个决策序列,则称多阶段决策过程为序贯决策过程。称问题为多阶段决策问题。
状态1
状态2
状态3
状态4
状态5
决策2
决策3
决策4
决策1
多阶段决策问题的特点
过程可分为若干个相互联系的阶段;每一阶段都对应着一组可供选择的决策;每一决策的选定即依赖于当前面临的状态,又影响以后总体的效果。
1
动态规划实例(单源最短路径)
第1阶段
第2阶段
第3阶段
第4阶段
状态1
状态2
状态4
状态5
状态3
决策1
决策2
决策4
决策3
动态规划
把多阶段过程的问题转化为一系列单阶段的问题,逐个阶段求解的最优化数学方法。
2
动态规划的原理
动态规划的术语
阶段:将过程划分为k个阶段,1k n。
状态:第k个阶段的状态变量为。为初态, 为终态。
状态集合: 允许的取值范围构,记为。
决策:用表示第k阶段状态的决策变量。第k阶段决策变量的取值范围记为, 。
允许决策集合: 的允许取值范围,记为。
策略:一个按顺序排列的决策序列。
子策略:称决策函数序列为k子过程策略。简称子策略,记为:
3
动态规划的原理
当k=1时,此决策函数序列成为全过程的一个策略,简称策略,记为
允许策略集合:选择的策略允许的取值范围,记为。
状态转移方程:从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律,记为。
阶段指标函数:指第k阶段从状态出发,采取决策时的效益,用表示。
过程指标函数:若从第k阶段的某状态出发,采取最优子策略获得的效益记为。
若采取最优子策略,则获得的效益记,其中表示加法或乘法。因此,效益函数具有可加性或可乘性,即效益函数是可分函数。
4
动态规划的原理
表示从第k阶段状态为时采用最佳策略到过程终止时的最佳效益。记为
其中 opt 可根据具体情况取max 或min。
最优值基本方程
式中opt 可根据题意取 max 或 min。
最优值函数
5
最优性定理和基本方程
两种方式的动态规划
寻优过程可以有正序、逆序。当初始状态给定时,用正序方式比较好;当终止状态给定时,用逆序方式较好。
动态规划求解步骤
,确定决策集合
策略是最优策略的充要条件是:对任一k(1kn),当初状态为s1时,有
因此,在策略集上求最优解,等价于先在子策略集上求最优解,然后再求这些子最优解在子策略空间上的最优解。即问题最优解包含子问题最优解。
最优性定理
6
最优性定理和基本方程
式中opt 可根据题意取 max 或 min。
正序基本方程:此为逐段递推计算的依据,一般为:
式中opt 可根据题意取 max 或 min。
逆序基本方程:此为逐段递推计算的依据,一般为:
7
动态规划实例计算
逆向递推计算方法(单源最短路径)
用表示在第k阶段由初始状态到下一阶段的状态的距离。用表示从第k阶段的状态到终点E的最短距离。
= 4
第4阶段有两个初始状态和。若全过程最短路径经过状态,则有= 4 ;若全过程最短路径经过状态,则有= 3 。
k = 3
假设全过程最短路径在第3阶段经过状态,若由,则有。
3. , 及其它阶段的计算类似。,最短路径为。
8
动态规划特点、条件和步骤
动态规划的适用条件
适用动态规划的问题必须满足以下三个条件
 最优化原理
无后效性 
子问题的重叠性
动态规划特点
优点
离散性问题:使解析数学无用武之地;
建模:可用计算机计算;
缺点
无统一处理方法:需要数学技巧与解题经验;
组合爆炸:只能解决中小规模的问题
9
动态规划特点、条件和步骤
最优化原理(最优子结构性质)   一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。  
无后向性   将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。
10