动态规划应用.ppt

文档介绍：第六章动态规划
(Dynamic programming)
多阶段决策过程及实例
动态规划的基本概念和基本方程
动态规划的最优性原理和最优性定理
动态规划与静态规划的关系
动态规划应用举例
学****方法建议:
第一步先看问题,充分理解问题的条件、情况及求解目标。
第二步结合前面讲到的理论和解题过程,考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素、一个方程”——这一步在开始时会感到困难,但是一定要下决心去思考,在思考过程中深入理解前文讲到的概念和理论。
动态规划应用举例
第三步动手把求解思路整理出来,或者说,把该问题作为****题独立的来做。
第四步把自己的求解放到一边,看书中的求解方法,要充分理解教材中的论述。
第五步对照自己的求解,分析成败。

①状态变量及其可能集合 xkXk
②决策变量及其允许集合 ukUk
③状态转移方程 xk+1=Tk(xk,uk)
④阶段效应 rk(xk,uk )
2. 动态规划基本方程
fn+1(xn+1) = 0 (边界条件)
fk(xk) = opt u{rk ( xk , uk ) + fk+1(xk+1) }
k = n,…,1
求最短路径
例1
将问题分成五个阶段,第k阶段到达的具体地点用状态变量xk表示,例如:x2=B3表示第二阶段到达位置B3,等等。这里状态变量取字符值而不是数值。将决策定义为到达下一站所选择的路径,例如目前的状态是x2=B3,这时决策允许集合包含三个决策,它们是D2(x2)=D2(B3)={B3C1,B3C2,B3C3}
最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为 f5(x5)=f5(E)=0其含义是从E到E的最短路径为0。
第四阶段的递推方程为:
从f5(x5)到f4(x4)的递推过程用下表表示:
其中*表示最优值,在上表中,由于决策允许集合D4(x4)中的决策是唯一的,因此这个值就是最优值。
由此得到f4(x4)的表达式。由于这是一个离散的函数,取值用列表表示:
第三阶段的递推方程为: