【动态规划法|《动态规划法》PPT课件】1、第九章 动态规划法,动态规划法是求解控制变量限制在一定闭集内的最优控制问题的又一种重要方法 ， 它是由美国学者贝尔曼于1957年提出来的 。
动态规划法把复杂的最优控制问题变成多级决策过程的递推函数关系 ， 它的基础及核心是最优性原理 。
本章首先介绍动态规划法的基本概念 ， 然后讨论如何用动态规划法求解离散及连续系统的最优控制问题,第一节 动态规划法的基本概念,一、多级决策过程,所谓多级决策过程是指把一个过程分成若干级 ， 而每一级都需作出决策 ， 以便使整个过程达到最佳效果 。
为了说明这个概念 ， 首先讨论一个最短路线问题的例子,设有路线图如图7-1所示 。
现在要从 地出发 ， 选择一条最短路线最终到达 地 ， 其间要通过 等中间站 。

2、 ， 各站又有若干个可供选择的通过点 ， 各地之间的距离已用数字标注在图中 。
由此可见 ， 通过这些中间站时 ， 有多个方案可供选择,解决这类问题有两种方法,探索法（穷举法,将至的所有可能的路线方案都列举出来 ， 算出每条路线的路程 ， 进行比较 ， 找出最短路线 。
直观可知 ， 这种方法是很费时的 ， 如本例共有38条路线可供选择 。
如果中间站及各站可供选择的通过点都增为10个 ， 则可供选择的路线将急剧增至1010条 ， 显然计算工作量将急剧增加,分级决策法,将整个过程分成若干级 ， 逐级进行决策 。
具体过程如下,将 至 全程分为五级：第一级由 至 ；第二级由 至 ；第三级由 至 ；第四级由 至 ；第五级由 至。
让我们由后向前逐级分析 ， 先从第 。

3、五级开始 ， 其起点为， 终点为。
至 各只有一条路线 ， 并无选择余地 。
至 路程为1 ，至 路程为2 。
第四级起点为， 终点为， 其间有六条路线 ， 由 至 的各种可能路线为,可以发现 ， 如果从 出发 ， 则走 为最短 ， 因此 至 应选 这段路线 ， 称为决策 。
同理 ， 如果从 出发 ， 应决策 ；从 出发 ， 应决策。
可见作此决策时不能只从本级路程长短出发 ， 应考虑两级路程之和为最短 。
在整个路线问题中 ， 究竟 哪一点作为起点 ， 则取决于第三级的决策 ， 不过提出的三条可能的最短路线为第三级的决策积累了数据资料,可见同样方法来分析第三级 ， 其起点为， 终点为， 按题意共有八条路线 。
但是 ，至 的最短路线已在第四级讨论中确定 ， 因此 的路 。

4、线选择问题 ， 实际上只是选定级 的路线问题（即本级决策问题） 。
因此 ，至 只有八条路线 ， 分别为,比较可得分别从 出发时的三条最短路线 ， 它们为： ； ；,用同样方法 ， 依次对 级及 级进行讨论 ， 其结果列于表7-1 。
最后得到最短路线为,相应最短路程为：,通过上例的讨论 ， 可以看到多级决策过程具有以下特点,把整个过程看成（或人为地分成） 级的多级过程,采取逐级分析的方法 ， 一般由最后一级开始倒向进行,在每一级决策时 ， 不只考虑本级的性能指标的最优 ， 而是同时考虑本级及以后的总性能指标最优 ， 因此它是根据“全局”最优来作出本级决策的,从数学观点 ， 分级决策法与穷举法进行比较,穷举法：全程五级线路 ， 每一级都可任选 ， 因此 。

5、全部路程相当于一个“五变量函数” ， 求全程最短实质上是求这个“五变量函数”的极小值,分级决策法： 分成五级 ， 从最后一级开始进行分级决策时 ， 每级都是一个“单变量函数” ， 因此进行每一级决策时 ， 实际上是求一个“单变量函数”的极小值 。
因此多级决策法把一个求“五变量函数”的极值问题转化成为一个五组求“单变量函数”的极值问题 。
这组实际解题带来极大好处 ， 使计算工作量在为减少 。
以前面举的十级中间站并各站具有十个通过点的路线问题为例 ， 用多级决策法只需920次计算 ， 这与1010次相比要少得多,在最后一级开始倒向逐级分析中 ， 我们发现 ， 由于各站的起始点并未确定 ， 因此需要把各中间站的所有通过点作为出发点进行计算 ， 并将所有 。

6、对应的最佳决策存进计算机 ， 建立起一个完整的“档案库” ， 因此要求计算机有相当大的容量,6)第一级起始条件（地）是确定的 ， 因此只有逐级倒向分析到第一级时 ， 才能作出确定的第一级决策 ， 然后再根据第一级决策顺向确定各级的起始条件（各站的通过点） ， 这时由于“档案库”中存有全部“资料” ， 因此用“查档”的方法就可逐级确定决策 。

来源：(未知)

【学习资料】网址：/a/2021/0323/0021755883.html

标题：动态规划法|《动态规划法》PPT课件