第九章动态规划法ppt课件.ppt

第九章 动态规划法 动态规划法是求解控制变量限制在一定闭集内的最优控制问题的又一种重要方法，它是由美国学者贝尔曼于1957年提出来的动态规划法把复杂的最优控制问题变成多级决策过程的递推函数关系，它的根底及中心是最优性原理本章首先引见动态规划法的根本概念，然后讨论如何用动态规划法求解离散及延续系统的最优控制问题第一节 动态规划法的根本概念一、多级决策过程 所谓多级决策过程是指把一个过程分成假设干级，而每一级都需作出决策，以便使整个过程到达最正确效果为了阐明这个概念，首先讨论一个最短道路问题的例子 设有道路图如图7-1所示如今要从 地出发，选择一条最短道路最终到达 地，其间要经过 等中间站，各站又有假设干个可供选择的经过点，各地之间的间隔已用数字标注在图中由此可见，经过这些中间站时，有多个方案可供选择 处理这类问题有两种方法：1.探求法〔穷举法〕 将至的一切能够的道路方案都列举出来，算出每条道路的路程，进展比较，找出最短道路直观可知，这种方法是很费时的，如本例共有38条道路可供选择假设中间站及各站可供选择的经过点都增为10个，那么可供选择的道路将急剧增至1010条，显然计算任务量将急剧添加。

2.分级决策法将整个过程分成假设干级，逐级进展决策详细过程如下： 将 至 全程分为五级：第一级由 至 ；第二级由 至 ；第三级由 至 ；第四级由 至 ；第五级由 至 让我们由后向前逐级分析，先从第五级开场，其起点为 ，终点为 至 各只需一条道路，并无选择余地 至 路程为1， 至 路程为2第四级起点为 ，终点为 ，其间有六条道路，由 至 的各种能够道路为: 可以发现，假设从 出发，那么走 为最短，因此 至 应选 这段道路，称为决策同理，假设从 出发，应决策 ；从 出发，应决策 。

可见作此决策时不能只从本级路程长短出发，应思索两级路程之和为最短在整个道路问题中，终究 哪一点作为起点，那么取决于第三级的决策，不过提出的三条能够的最短道路为第三级的决策积累了数据资料 可见同样方法来分析第三级，其起点为 ，终点为 ，按题意共有八条道路但是， 至 的最短道路已在第四级讨论中确定，因此 的道路选择问题，实践上只是选定级 的道路问题〔即本级决策问题〕因此， 至 只需八条道路，分别为 比较可得分别从 出发时的三条最短道路，它们为： ； ；  用同样方法，依次对 级及 级进展讨论，其结果列于表7-1最后得到最短道路为相应最短路程为： 经过上例的讨论，可以看到多级决策过程具有以下特点：⑴ 把整个过程看成〔或人为地分成〕 级的多级过程。

⑵ 采取逐级分析的方法，普通由最后一级开场倒向进展 ⑶ 在每一级决策时，不只思索本级的性能目的的最优，而是同时思索本级及以后的总性能目的最优，因此它是根据“全局〞最优来作出本级决策的⑷ 从数学观念，分级决策法与穷举法进展比较：穷举法：全程五级线路，每一级都可任选，因此全部路程相当于一个“五变量函数〞，求全程最短本质上是求这个“五变量函数〞的极小值分级决策法： 分成五级，从最后一级开场进展分级决策时，每级都是一个“单变量函数〞，因此进展每一级决策时，实践上是求一个“单变量函数〞的极小值因此多级决策法把一个求“五变量函数〞的极值问题转化成为一个五组求“单变量函数〞的极值问题这组实践解题带来极大益处，使计算任务量在为减少以前面举的十级中间站并各站具有十个经过点的道路问题为例，用多级决策法只需920次计算，这与1010次相比要少得多 ⑸ 在最后一级开场倒向逐级分析中，我们发现，由于各站的起始点并未确定，因此需求把各中间站的一切经过点作为出发点进展计算，并将一切对应的最正确决策存进计算机，建立起一个完好的“档案库〞，因此要求计算机有相当大的容量 (6)第一级起始条件〔地〕是确定的，因此只需逐级倒向分析到第一级时，才干作出确定的第一级决策，然后再根据第一级决策顺向确定各级的起始条件〔各站的经过点〕，这时由于“档案库〞中存有全部“资料〞，因此用“查档〞的方法就可逐级确定决策。

由此可见，普通情况下，多级决策过程包括两个过程：倒向“建档〞及顺向“查档〞，而大量的计算任务是破费在建立“档案库〞上二、最优性原理 在前例的分级决策过程中，实践上已运用了这样一个根本原理：设一个过程由 点开场，经 点到达 点，如图9-2所示，假设 为最优过程，那么 段也必定是一个最优过程我们把这原理表达如下： 一个最优决策具有这样的性质，不论初始形状和初始决策怎样，其他的决策对于第一次决策所呵斥的形状来说，必需构成一个最优决策称此为最优性原理它也可简单地表达为：最优轨迹的第二段，本身亦是最优轨迹 最优性原理是动态规划法的根底和中心动态规划法就是对一个多级过程，运用最优性原理，进展分级决策，求出最优控制的一种数学方法3、 多级决策过程的函数方程 运用动态规划法求解过程的最优决策时，首先要根据最优性原理将多级决策过程表示成如下数学表达式： ―― 级决策过程始点 处所采取的控制决策，从而使形状转移到下一步 式中 ―― 级决策过程的始点 至终点 的最小耗费； ――由 级决策过程始点 至下一步到达点 的一步 耗费；(9-1) 上式阐明，为使 级决策过程到达最小耗费，第一级决策应根据两部分耗费之和最小的原那么作出。

第一部分 是第一级决策的一步耗费，第二部分 为由下一步到达点 作起点至终点的最小耗费式(7-1)称为多级决策过程的函数方程，它是最优性原理的数学表达方式在上述道路问题中， 至 的四级决策过程的函数方程可表示成：式中: ――四级过程的起点； ――由 出发到达下一步 站的某个能够经过点，它 能够为 或 ； ――由 至 站的道路选择〔本级决策〕；(9-2) ――由 至 之间的路程； ――从 至 终点的最短路程由表7-1可知 三者进展比较，由此作出第一级决策为 即应选 道路这时 最小路程为 函数方程是一个递推方程，普通说来，难于获得解析解，需求用数 字计算机求解第二节 动态规划法解离散系统的 最优控制问题 设系统形状方程为 式中， 为 维形状向量， 为 维控制向量，设 为每一步转移中的性能目的。

(9-3)第一步，系统初始形状 在 作用下转移至 ，即 要求选择控制 ，使 达最小这是一个一级决策过程 (9-4)这时，第一步的性能目的为：(9-5)(9-6) 第二步，系统在 作用下由 转移到 ，转移中的性能目的为 ，那么两步转移的总性能目的为： 这里，由于 知，而 ，因此在上述两步转移的总性能目的中，只需 及 未知如今要求选择 及，使两步性能目的达极小这就是二级决策问题  依次类推，系统形状由 作起点进展 步转移，那么 步转移的总性能目的为： 如今要求选择 使性能目的 达最小，这就是 级决策问题我们可以运用动态规划法来求解根据最优性原理，对 级最优决策过程来说，不论第一级控制向量 怎样选定，余下的 级过程，从 产生的形状 作为起点，必需构成 级最优过程。

(9-7) 假设我们用 表示 级过程的性能目的的极小值， 表示 级过程性能目的的极小值，那么我们就可以列写出级决策过程的函数方程为： 由此可见，第一级决策本质上是函数 对第一级的控制决策 求极值的问题求解递推方程(9-8)，就可解得最优控制决策 (9-8)例9-1 设离散系统形状方程为：初始条件为 ，控制变量 不受限制，性能目的为求最优控制 ，使 达最小解: 为简单起见，设 ，那么这是一个二步控制问题，性能目的 可表示成： 首先思索最后一步，即由某形状 出发到达 的一步，如采用控制 ，那么有或 求最优控制使 为极小 ，那么有解得：可见 为 的函数相应的最优性能目的及 为再思索倒数第二步，即由初始形状 出发到达 的一步，如采用控制 ，那么有令有相应的最优性能目的及 为：最后得最优控制为：最优轨线为：最优性能目的为：上述离散型动态规划可近似地用来求解延续系统的最优控制问题。

设延续系统形状方程为： (9-9) 给定，性能目的为：(9-10) (9-11) 求最优控制 ，使 为最小 由于函数方程是一个递推方程，故特别适宜于求解离散系统的最优控制问题为此要把延续过程问题转化成一个多级决策过程首先将时间间隔 分成 段，每段为 ，为使尽量符合延续过程的实践情况， 应取足够大， 取足够小接着应将延续形状方程进展离散化，使之用以下有限差分方程来近似表示：(9-12) 故(9-13)  这样，就把研讨延续过程问题近似转化成了 级决策过程下面就可按离散过程一样建立函数方程，用递推求解方法逐级进展最优决策，求出最优控制序列来9-14) 这里，假设在每段时间 内， 及 坚持常值同时，将积分型的性能目的用以下序列和的方式来近似第三节 动态规划法解离散线性二次型问题设离散线性系统形状方程为：(9-15) 性能目的为二次型(9-16) 式中， 均为对称矩阵， 为正定矩阵， 为正半定矩阵求最优控制序列 使 为最小。

 如今我们用动态规划法来求解从初始端开场，经过 级决策得到的最优性能目的可表示为(9-17) (9-18) 根据最优性原理，可以建立函数方程如下：假设过程是从第 级开场至终产端，那么这一段的最优性能目的可表示为：假设二次型问题的最优性能目的为形状的二次函数：(9-20) 上式对 成立，代入式(9-19)得： (9-21) 将系统形状方程代入，得：(9-22) 设 不受约束，那么令(9-23) 可得：(9-24) 式中 如今需求确定，将 式(9-24)代入式(9-22)，并利用 的假设，那么式(9-22)可写成：(9-26) 上式对恣意形状变量都满足，由此可得离散系统的黎卡提方程(9-27)  第四节 动态规划法解延续系统的最优控制问题 用离散动态规划法求解延续系统最优控制问题时，能够会由于离散化过程而呵斥一定误差运用最优性原理，对延续系统也可建立起相应的函数方程，经过变换，最后得到一个一阶非线性偏微分方程，解之可得延续方式的最优控制即最优决策。

设延续系统形状方程为(9-28) (9-29) 性能目的为(9-30) 求最优控制 ，使为最小我们知道，对应最优控制 及最优轨线 ，性能目的将取极小值，且为系统初始形状 及初始时辰 的函数，以表示，那么可写成：(9-31) (9-32) 这里， 与 的关系受系统动态方程约束将目的函数的表示式代入，那么显然(9-33)  设时辰 在区间 内，那么根据最优性原理，从 到 这一段过程必需构成最优过程，这一段过程的性能目的极小值可表示为 将 这段最优过程分成二步，第一步 由 到， 是一很小的时间间隔，第二步由 至 ，于是有(9-34) (9-35) 根据最优性原理，从 到 这一段过程也该当构成最优过程，其性能目的极小值可表示为：这样，式(9-35)就变成：(9-36) (9-37) 由于 很小，上式可写成：(9-38) 将 用台劳级数展开(9-39) 式中， 为二次及二次以上各项，代入式(9-38)得：(9-40) 由于 不是 的函数，从而 亦不是 的函数，因此不受最小化运算的影响，可从最小化运算符号析出，于是有(9-41) 简化上式，并以 除之，再取 ，那么(9-42) 定义以下函数(9-43) 那么(9-44) 如求出最优控制 ，那么下式成立(9-45) 式(9-45)称为哈密尔顿-雅可比如程。

当 不受限制时，可由(9-46) 即(9-47) 解得 ，显然它是 的函数，记作(9-48) 将式(9-48)代入哈密尔顿-雅可比如程，并根据如下边境条件(9-49) 可以解出 来再将 代回式(9-48)，就可获得最优控制 这是一个形状反响控制规律，由此可以实现闭环最优控制最后同 代入系统形状方程，就可解得 例9-2 设系统形状方程为初始形状为 ， 不受约束，性能目的为试求 ，使 为最小解 根据式〔9-45〕、式(9-43)有由于 不受约束，可以根据 来求 ，得：为解此偏微分方程，设： ，代入上式，得：因此 联立解得： 从而可很方便地实现闭环形状反响最优控制。