第九章动态规划法.ppt
《第九章动态规划法.ppt》由会员分享,可在线阅读,更多相关《第九章动态规划法.ppt(45页珍藏版)》请在三一文库上搜索。
1、第九章 动态规划法,动态规划法是求解控制变量限制在一定闭集内的最优控制问题的又一种重要方法,它是由美国学者贝尔曼于1957年提出来的。动态规划法把复杂的最优控制问题变成多级决策过程的递推函数关系,它的基础及核心是最优性原理。本章首先介绍动态规划法的基本概念,然后讨论如何用动态规划法求解离散及连续系统的最优控制问题。,第一节 动态规划法的基本概念,一、多级决策过程,所谓多级决策过程是指把一个过程分成若干级,而每一级都需作出决策,以便使整个过程达到最佳效果。为了说明这个概念,首先讨论一个最短路线问题的例子。,设有路线图如图7-1所示。现在要从 地出发,选择一条最短路线最终到达 地,其间要通过 等中
2、间站,各站又有若干个可供选择的通过点,各地之间的距离已用数字标注在图中。由此可见,通过这些中间站时,有多个方案可供选择。,解决这类问题有两种方法:,探索法(穷举法),将至的所有可能的路线方案都列举出来,算出每条路线的路程,进行比较,找出最短路线。直观可知,这种方法是很费时的,如本例共有38条路线可供选择。如果中间站及各站可供选择的通过点都增为10个,则可供选择的路线将急剧增至1010条,显然计算工作量将急剧增加。,分级决策法,将整个过程分成若干级,逐级进行决策。具体过程如下:,将 至 全程分为五级:第一级由 至 ;第二级由 至 ;第三级由 至 ;第四级由 至 ;第五级由 至 。让我们由后向前逐
3、级分析,先从第五级开始,其起点为 ,终点为 。 至 各只有一条路线,并无选择余地。 至 路程为1, 至 路程为2。第四级起点为 ,终点为 ,其间有六条路线,由 至 的各种可能路线为:,可以发现,如果从 出发,则走 为最短,因此 至 应选 这段路线,称为决策。同理,如果从 出发,应决策 ;从 出发,应决策 。可见作此决策时不能只从本级路程长短出发,应考虑两级路程之和为最短。在整个路线问题中,究竟 哪一点作为起点,则取决于第三级的决策,不过提出的三条可能的最短路线为第三级的决策积累了数据资料。,可见同样方法来分析第三级,其起点为 ,终点为 ,按题意共有八条路线。但是, 至 的最短路线已在第四级讨论
4、中确定,因此 的路线选择问题,实际上只是选定级 的路线问题(即本级决策问题)。因此, 至 只有八条路线,分别为,比较可得分别从 出发时的三条最短路线,它们为: ; ; 。,用同样方法,依次对 级及 级进行讨论,其结果列于表7-1。最后得到最短路线为,相应最短路程为: 。,通过上例的讨论,可以看到多级决策过程具有以下特点:, 把整个过程看成(或人为地分成) 级的多级过程。, 采取逐级分析的方法,一般由最后一级开始倒向进行。, 在每一级决策时,不只考虑本级的性能指标的最优,而是同时考虑本级及以后的总性能指标最优,因此它是根据“全局”最优来作出本级决策的。, 从数学观点,分级决策法与穷举法进行比较:
5、,穷举法:全程五级线路,每一级都可任选,因此全部路程相当于一个“五变量函数”,求全程最短实质上是求这个“五变量函数”的极小值。,分级决策法: 分成五级,从最后一级开始进行分级决策时,每级都是一个“单变量函数”,因此进行每一级决策时,实际上是求一个“单变量函数”的极小值。因此多级决策法把一个求“五变量函数”的极值问题转化成为一个五组求“单变量函数”的极值问题。这组实际解题带来极大好处,使计算工作量在为减少。以前面举的十级中间站并各站具有十个通过点的路线问题为例,用多级决策法只需920次计算,这与1010次相比要少得多。, 在最后一级开始倒向逐级分析中,我们发现,由于各站的起始点并未确定,因此需要
6、把各中间站的所有通过点作为出发点进行计算,并将所有对应的最佳决策存进计算机,建立起一个完整的“档案库”,因此要求计算机有相当大的容量。,(6)第一级起始条件(地)是确定的,因此只有逐级倒向分析到第一级时,才能作出确定的第一级决策,然后再根据第一级决策顺向确定各级的起始条件(各站的通过点),这时由于“档案库”中存有全部“资料”,因此用“查档”的方法就可逐级确定决策。由此可见,一般情况下,多级决策过程包括两个过程:倒向“建档”及顺向“查档”,而大量的计算工作是花费在建立“档案库”上。,二、最优性原理,在前例的分级决策过程中,实际上已应用了这样一个基本原理:设一个过程由 点开始,经 点到达 点,如图
7、9-2所示,如果 为最优过程,则 段也必定是一个最优过程。我们把这原理叙述如下:,一个最优决策具有这样的性质,不论初始状态和初始决策怎样 ,其余的决策对于第一次决策所造成的状态来说,必需构成一个 最优决策。称此为最优性原理。它也可简单地叙述为:最优轨迹的第二段,本身亦是最优轨迹。,最优性原理是动态规划法的基础和核心。动态规划法就是对一个多级过程,应用最优性原理,进行分级决策,求出最优控制的一种数学方法。,3、 多级决策过程的函数方程,应用动态规划法求解过程的最优决策时,首先要根据最优性原理将多级决策过程表示成如下数学表达式:,(9-1),上式表明,为使 级决策过程达到最小消耗,第一级决策应根据
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第九 章动 规划
链接地址:https://www.31doc.com/p-2520286.html