最优控制动态规划（1）讲解课件

《最优控制动态规划（1）讲解课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划法动态规划是解决多级决策过程最优化的一种数学方法。所谓多级决策过程，是指把一个过程分为若干个阶段，而每一个阶段都需作出决策，以便使整个过程取得最优的效果。最短路线问题问题:要求从A地到F地，选择一条最短的线路。12345678965411354524244957为了便于分析，引入几个符号：N：从某点到终点之间的级数；x：表示在任一级所处的位置，称为状态变量；SN(x)：决策变量，表示当处于状态x，还有N级时，所选取的下一个点；WN(x)：表示从状态x到终点F的N级过程的最短距离；d(x,SN)

2、：表示从状态x到点SN的距离。从最后一级开始计算：12345678965411354524244957从哪下手？SN(x)：决策变量，表示当处于状态x，还有N级时，所选取的下一个点；WN(x)：表示从状态x到终点F的N级过程的最短距离；同理所以，最短路线为最短距离为14一个N级最优过程，不管第一级决策如何，其余N-1级，决策过程至少必须依据第一级决策所形成的状态组成一个N-1级最优过程，在此基础上，在选择第一级决策，使总的N级过程为最优。12345678965411354524244957这种递推关系

3、可以用下列递推方程式来表达：是不是穷举法？再看一个例子最短时间问题问题：设有人要从A点开车到E站，中间要经过任意三个中间站，站名在图中圆圈内表示。站与站之间称为段，每段路程所需时间（小时）标在段上。现要问，这人应如何选择路线才能最快到达目的地？什么是穷举法?从走到一共有六条路线，每条路线由四段组成。这六条路线和对应的行车时间如下路线行车时间（小时）13111413129显然最优路线是，它所花时间为9小时。这里每条路线由四段组成，也可以说是四级决策。为了计算每条路线所花时间，要做三次加法运算，为了计算六

4、条路线所花的时间要作3×6=18次运算。这种方法称为“穷举法”。显然当段数很多时，计算量是很大的。这种方法的特点是从起点站往前进行，而且把这四级决策一起考虑。应注意从到下一站所花的时间为1，而到所花时间为3，但最优路线却不经过。这说明只看下一步的“眼前利益”来作决策是没有意义的。为将问题表达得清楚，引进下面的术语（写法并不完全一样）。令表示由某点到终点的段数（如到为2段，。令表示当前所处点的位置（如），称为状态变量。对比一下最开始的例子令为决策（控制）变量，它表示当处在位置而还有段要走时，所要选取的下

5、一点。例如，从出发，下一点为时，则表示为。令表示在位置，向终点还有段要走时，由到终点的最短时间。例如，从C2到E的最短时间为4，可表示为T2(C2)=4。令表示从点到点的时间。例如，从到的时间为有了这些术语后，就可用动态规划来解这个例子。从最后一段出发进行计算，并将计算出的最短时间用括号表示在相应的点处（见图6-1）。n=1（倒数第一段）考虑从和到的路线，由定义可知，最短时间分别为n=2（倒数第二段）考虑从到的路线。由到有两种路线：，。两种路线中的最短时间由下式确定：最优决策为。由到只有一种路线，其时

6、间为由到E也只有一种路线，其时间为EDC23n=3（倒数第三段）从B2到E有两种路线：和最优决策最短时间为：n=4（倒数第四段）从A到E的路线有两种：和。最优决策为至此求出了A到E的最短时间为9，最优路线为。在图中用粗线表示。这里，为决定最优路线进行了10次加法，比穷举法的18次少了8次。当段数n更多时，节省计算将会更多。以上面的最短时间问题为例，如把当作初始状态，则余下的决策对来讲是最优策略；如把当初始状态，则余下的决策对来讲也构成最优策略。一般来说，如果一个最优过程用状态来表示，最优决策为，则对状

7、态来讲，必定是最优的，这可用图6-2来表示。图6-2最优性原理示意图动态规划的特点：一是它从最后一级反向计算；二是其将一个N级决策问题化为N个单级决策问题。好处：将一个复杂问题化为多个简单问题加以求解。最优性原理贝尔曼的最优性原理可叙述如下：“一个多级决策问题的最优决策具有这样的性质：当把其中任何一级及其状态作为初始级和初始状态时，则不管初始状态是什么，达到这个初始状态的决策是什么，余下的决策对此初始状态必定构成最优策略。”在多数实际问题中，级决策的性能指标取如下形式是由某级状态和决策决定的性能函数，

8、要求寻找决策使J取极小值。最优性原理可表示为根据上式就可证明最优性原理的正确性。若以为初态时，余下的决策不是最优的，那么就存在另一决策序列所决定的指标值，于是这与是极小值发生矛盾，所以余下的决策必须是最优的。6-2离散最优控制问题设控制系统的状态方程为式中x(k)是k时刻的几维状态向量，u(k)是k时刻的p维容许控制向量，设系统在每一步转移中的性能指标为F[x(k),u(k)]如在u(0)的作用下在u(1)的作用下对N级决策过程性能指标要求选择控制序列使