《动态规划法》ppt课件

《《动态规划法》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

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

6、多。⑸在最后一级开始倒向逐级分析中，我们发现，由于各站的起始点并未确定，因此需要把各中间站的所有通过点作为出发点进行计算，并将所有对应的最佳决策存进计算机，建立起一个完整的“档案库”，因此要求计算机有相当大的容量。(6)第一级起始条件（地）是确定的，因此只有逐级倒向分析到第一级时，才能作出确定的第一级决策，然后再根据第一级决策顺向确定各级的起始条件（各站的通过点），这时由于“档案库”中存有全部“资料”，因此用“查档”的方法就可逐级确定决策。由此可见，一般情况下，多级决策过程包括两个过程：倒向“建档”及顺向“查档”，而大量的计算工作是花费在建立“档

7、案库”上。二、最优性原理在前例的分级决策过程中，实际上已应用了这样一个基本原理：设一个过程由点开始，经点到达点，如图9-2所示，如果为最优过程，则段也必定是一个最优过程。我们把这原理叙述如下：一个最优决策具有这样的性质，不论初始状态和初始决策怎样，其余的决策对于第一次决策所造成的状态来说，必需构成一个最优决策。称此为最优性原理。它也可简单地叙述为：最优轨迹的第二段，本身亦是最优轨迹。最优性原理是动态规划法的基础和核心。动态规划法就是对一个多级过程，应用最优性原理，进行分级决策，求出最优控制的一种数学方法。3、多级决策过程的函数方程应用动态规划法求

8、解过程的最优决策时，首先要根据最优性原理将多级决策过程表示成如下数学表达式：――级决策过程始点处所采取的控制决策，从而使状态转移到下一步