北京交通大学(最优控制理论与算法研究生课程)第六章 动态规划与离散系统最优控制

1、动态规划与离散系统最优控制动态规划与离散系统最优控制(1/3)(1/3)第第6章章 动态规划与离散系统最优控制动态规划与离散系统最优控制q 前面讨论了连续系统连续系统最优控制问题的基于经典变分法和庞特庞特里亚金里亚金的极大值原理的两种求解方法。 所谓连续系统,即系统方程是用线性或非线性微分方程描述的动态系统。 该类系统的控制问题是与传统的控制系统和控制元件的模拟形式实现相对应, 如模拟运算放大器件、模拟自动化运算仪表、模拟液压放大元件等。随着计算机技术及其计算机控制技术的发展, 离散系统离散系统的最优控制问题也必然成为最优控制中需深入探讨的控制问题, 而且成为现代控制技术更为关注的问题。动态规

2、划与离散系统最优控制动态规划与离散系统最优控制(2/3)(2/3)q 离散系统的控制问题为人们所重视的原因有二,1) 连续系统在实现控制时，在应用计算机控制技术、数字计算机控制技术、数字控制技术时控制技术时, 须经采样后成为离散化系统, 再加以控制 如许多现代工业控制领域的实际计算机控制问题。2) 有些实际控制问题本身即为离散系统, 如某些经济计划系统、人口系统的时间坐标只能以小时、天或月等标记; 再如机床加工中心的时间坐标是以一个事件(如零件加工活动)的发生或结束为标志的。动态规划与离散系统最优控制动态规划与离散系统最优控制(3/3)(3/3)q 本节将介绍解决离散系统最优控制解决离散系统最

3、优控制的有效工具有效工具贝尔曼动态规划, 以及线性离散系统的二次最优控制问题。 内容为 最优性原理与离散系统的动态规划法最优性原理与离散系统的动态规划法 线性离散系统的二次型最优控制线性离散系统的二次型最优控制最优性原理与离散系统的动态规划法最优性原理与离散系统的动态规划法(1/3)(1/3)6.1 最优性原理与离散系统的动态规划法最优性原理与离散系统的动态规划法q 基于对多阶段决策过程的研究结果, 贝尔曼在20世纪50年代首先提出了求解离散多阶段决策优化问题优化问题的动态规划法。 多阶段决策优化问题多阶段决策优化问题方法在许多领域得到应用和发展, 如在生产计划、资源配置、信息处理、模式识别等

4、方面都有成功的应用。 本节介绍将动态规划优化方法应用于动态系统的最优控动态系统的最优控制制问题, 构成最优控制的两种主要求解方法之一的最优控制动态规划法。最优性原理与离散系统的动态规划法最优性原理与离散系统的动态规划法(2/3)(2/3)q 动态规划的核心是贝尔曼最优性原理 这个原理归结为一个基本的递推公式。求解多阶段决策问题时, 要从末端开始要从末端开始, 逆向递推, 直至始端。 动态规划的离散基本形式受到问题的维数的限制受到问题的维数的限制, 应用有一定的局限性。但对于求解决线性离散系统的二次型二次型性能指标性能指标的最优控制问题特别有效。 至于连续系统的最优控制问题的动态规划法, 不仅是

5、一种可供选择的有充分性充分性的最优控制求解法,它还揭示了动态规划与变分法、极大值原理之间的关系, 具有重要的理论价值。最优性原理与离散系统的动态规划法最优性原理与离散系统的动态规划法(3/3)(3/3)q 下面分别介绍 多阶段决策问题多阶段决策问题 最优性原理一般问题的问题描述最优性原理一般问题的问题描述 离散系统的动态规划法离散系统的动态规划法多阶段决策问题多阶段决策问题(1/12)(1/12)1. 多阶段决策问题多阶段决策问题q 在讨论动态规划法之前,先考察一个简单的最短时间行车问题,简称行车问题。q例例 如图10所示, 某交通工具从S站出发, 终点为 F 站, 全程可分为4段。中间可能经

6、过的各站及站间的行车时间均已标记在图上。图图10 某行车路线图某行车路线图 试求最短行车时间的行车路线。多阶段决策问题多阶段决策问题(2/12)(2/12)q 由S站出发至终点F站可有多种不同的行车路线, 沿各种行车路线所耗费的时间不同。 为使总的行车时间最短,司机在路程的前3段要作出3次决策。p 首先，一开始司机要在经过x1(1)站还是x2(1)站两种情况中作出决策。 到x1(1)站或x2(1)后, 又面临下一站是经过x1(2)站还是x2(2)站的第2次决策。p 同样,在后续的每个阶段都要作出类似的决策。多阶段决策问题多阶段决策问题(3/12)(3/12)q 因此,计算8种不同的行车路线所耗

7、费的总行车时间,取最小者即可求出最短时间行车路线。 若行车问题需作决策的阶段数n较大,每次决策中可供选择的方案较多时,用上述的穷（枚）举法穷（枚）举法来解决最短行车时间问题计算量非常大计算量非常大。 一般说来,用穷举法穷举法计算时间与作决策的阶段数阶段数n和每次决策中可供选择的方案数可供选择的方案数成指数关系指数关系, 即通常所称的指数爆炸、维数灾难。多阶段决策问题多阶段决策问题(4/12)(4/12)q 通过分析发现, 另一种求最短时间行车路线方法的是: 从最后一阶段开始,先分别算出x1(3)站和x2(3)站到终点F的最短时 间 （ 成 本 ） , 并 分 别 记 为Jx1(3)和Jx2(3

8、)。 实际上, 最后一阶段阶段没有选择的余地。 因此,由图10可求得Jx1(3)=4, Jx2(3)=3多阶段决策问题多阶段决策问题(5/12)(5/12)q 为便于今后求解过程的应用,可将从x1(3)站和x2(3)站到终点的最短时间Jx1(3)和Jx2(3)的数值标记于代表该站的小圆圈内, 如图11所示。 其他站的情况依此类推。图图11 最优行车路线图最优行车路线图多阶段决策问题多阶段决策问题(6/12)(6/12)q 由此向后倒推,继续考察倒数第2段, 计算x1(2)站和x2(2)站到终点F的最短时间, 并分别记为Jx1(2)和Jx2(2)。 由图10可知,从x1(2)站到达终点F的路线中

9、下一站只能是x1(3)站和x2(3)站中之一。由于从x1(3)站和x2(3)站分别前往终点的最短时间已经计算出, 因此, 从x1(2)站和x2(2)到终点的最短时间分别为，Jx1(2)=min1+Jx1(3),1+Jx2(3)=4 Jx2(2)=min2+Jx1(3),2+Jx2(3)=5其相应的最短时间行车路线x1(2),x2(3),F和x2(2),x2(3), F。多阶段决策问题多阶段决策问题(7/12)(7/12)q 类似于前面过程,其他各站到终点的最短时间和相应的行车路线如图11所示. 从图11得到各站到终点站F的最短时间行车路线和所耗费的行车时间, 从起点站S到终点站F的最短时间行车

10、路线和所耗费的行车时间。 多阶段决策问题多阶段决策问题(8/12)(8/12)q 上述最短行车时间路线问题及其求解方法可以推广为多阶段多阶段决策优化问题决策优化问题, 如建筑安装工期计划、经济发展计划、资源建筑安装工期计划、经济发展计划、资源合理配置合理配置等, 其相应的最优性指标最优性指标可以为所耗费的时间最短,也可以为所耗费的能源最小、所得到的效益最好等。 因此,前面介绍逆向递推求解最优化问题的方法是一种具有普遍性意义的多阶段决策优化方法,称为动态规划法。 从上述解题的叙述过程可以看出, 动态规划法具有如下特点。多阶段决策问题多阶段决策问题(9/12)(9/12)1) 与穷举法相比, 动态

11、规划法可使计算量大为减少。 事实上, 用动态规划法解多阶段决策问题,只需作一些简单的、非常有限的加法运算加法运算和和求极大运算求极大运算。 如对一个有n个阶段,除最后一段外每一个状态下一步有m种可能决策方案的多阶段决策问题, 共需作(n-2)m2+m=(mn-2m+1)m次加法运算,以及(mn-2m+1)(m-1)次从二取一的极大运算 而对穷举法,则需作mmn-2(n-1)=mn-1(n-1)次加法运算和mn-1-1次的从二取一的极大运算。 如对前面的n=4, m=2的最短时间行车问题,用动态规划法求解共需作10次加法运算和5次从二取一的极大运算。而用穷举法求解,则分别为24次和8次。多阶段决

12、策问题多阶段决策问题(10/12)(10/12) 因此,动态规划法在减少计算量上的效果是显著的。 阶段数n越大, 决策方案m越多, 则动态规划法的优点更为突出。 如对n=10,m=4的多阶段决策问题,用动态规划法求解共需作132次加法运算和33次从二取一的极大运算,而用穷举法求解分别为2359296次和262143次。 因此, 动态规划法的效果是非常显著的。多阶段决策问题多阶段决策问题(11/12)(11/12)2) 用动态规划法求解多阶段决策问题的思路是: 为了最后确定由起点S至终点F的最优路线，首先首先逆向递推逆向递推求出各状态各状态至至终点终点F的最优路线的最优路线 在求取当前状态到终点

13、的极值时,只需知道当前状当前状态值和上一次的最优态值和上一次的最优(集合集合)值值, 就可以得到当前的最优值, 并以此作为下一次优化的初始数据 贝尔曼的最优性原理就是运用这个原理给出递推方法的多阶段决策问题多阶段决策问题(12/12)(12/12)3) 由图11可知,与从起点S至终点F的最优路线S, x2(1), x1(2), x2(3), F 相对应的, 该最优路线的从x2(1)站至终点F部分的路线 x2(1), x1(2), x2(3), F 是从x2(1)站至终点F的最优路线 类似地,从x1(2)站至终点F的最优路线x1(2),x2(3),F是从起点S至终点F的最优路线最优路线S,x2(

14、1),x1(2),x2(3),F的一部分的一部分,也是从x2(1)至终点F的最优路线x2(1), x1(2), x2(3), F的一部分 对于多阶段决策问题,最优路线和最优决策具有这种性质不是偶然偶然的, 而反映了该问题的一种规律性,即所谓的贝尔曼的最优性原理贝尔曼的最优性原理 它是动态规划法的核心 最优性原理一般问题的问题描述最优性原理一般问题的问题描述(1/22)(1/22)2. 最优性原理一般问题的问题描述最优性原理一般问题的问题描述q 动态规划的基本原理动态规划的基本原理 介绍一些专有名词 介绍多阶段决策问题 介绍最优性原理 应用最优性原理求解多阶段决策过程,并推广至离散系统最优控制q

15、 下面将在函数空间中描述N个阶段的决策过程, 为此先引进下述概念与定义。1) 状态向量状态向量x(k), 表示过程在 k 时刻的状态。l 对控制问题, 相当于状态变量向量。最优性原理一般问题的问题描述最优性原理一般问题的问题描述(2/22)(2/22)2) 决策向量决策向量u(k), 表示过程在k时刻的从某一状态转变为另一状态的动因（激励）。l 对控制问题, 则相当于控制输入向量。3) 策略策略u(0),u(1),u(N-1)是各个阶段的决策所组成的决策集合。l 对控制问题, 则相当于控制输入向量的序列。4) 成本成本(cost)J, 由于状态发生转移所耗费的成本。 对最优控制问题, 相当于其

16、性能指标性能指标。最优性原理一般问题的问题描述最优性原理一般问题的问题描述(3/22)(3/22)q 设在决策u(k)的作用下, 发生了状态从x(k)到x(k+1)的转移。 显然新的状态x(k+1)完全取决于原来的状态状态x(k)和和所采所采取的决策取的决策u(k)。 也可以把这种转移看成是在决策u(k)作用下的状态从x(k)到x(k+1)的一种变换, 且这种变换关系是唯一的,即 x(k+1)=f(x(k),u(k),k) 在每一阶段, 通常有若干个决策可供选择,我们用(k)代表第第k个阶段个阶段可供选择的决策集合。l 一般说来, 阶段不同, 其决策集合(k)也不同。l 用代表全部可供选择的决

17、策的集合,即=(0)(1)(N-1)最优性原理一般问题的问题描述最优性原理一般问题的问题描述(4/22)(4/22)q 多阶段的决策问题描述如下多阶段的决策问题描述如下: 设系统由决策u(k), 经变换式(182)把状态从x(k)转移到x(k+1), 其相应耗费的成本为F(x(k),u(k),k), k=0, 1, N-1。 现需通过一变换序列f(x(0),u(0),0), f(x(1),u(1),1), , f(x(N-1),u(N-1),N-1) 将初始状态x(0)经x(1), , x(N-1)转移到终态 x(N), 这N次转移相对应的所耗费的总成本为试求出一个决策序列u(0),u(1),

18、u(N-1), 使N阶段决策问题的总成本最小。) ),(),()1(),.,1 (),0(),0(10NkkkkFNJuxuuuxx(k+1)=f(x(k),u(k),k) (182)最优性原理一般问题的问题描述最优性原理一般问题的问题描述(6/22)(6/22)q 问题(183)的描述形式和最短路径问题有所不同。 如果把(182)看作约束条件, 最短路径问题是一个无约束的动态规划问题, 而问题(183)是一个具有约束的动态规划问题, 因为在每一级优化(决策)的时候,都要考虑状态考虑状态与控制之间的变换关系与控制之间的变换关系。 动态规划法是求解多阶段决策问题的一种最优化方法。 这一问题的核心

19、是最优性原理最优性原理。 最优性原理可以表述如下: 一个最优性决策具有这样的性质, 即不论初始状态初始状态和初始决策如何和初始决策如何, 对于前面决策所形成的状态来说,其余诸决策序列必须构成一个最优决策。 为了证实最优性原理, 有下面的定理.10(1)( ( ), ( ), )(182) (0), (0), (1),., (1)( ( ), ( ), )(183)Nkkkk kJNFkk kxf xuxuuuxu最优性原理一般问题的问题描述最优性原理一般问题的问题描述(7/22)(7/22)定理定理7-177-17q 定理定理17 若用u(0, N-1)表示N阶段决策过程中的一个策略,u(0,

20、 k-1)和u(k, N-1)分别为前前k个阶段个阶段和后后N-k个阶段个阶段的子策略; 并用Jx(0),u(0,N-1)表示N阶段决策过程的总成本, Jx(0),u(0,k-1)和Jx(k),u(k,N-1)分别为前k个阶段和后N-k个阶段的总成本, 即存在如下两个等式u (0, N-1) =u(0,k-1), u(k, N-1)J x(0), u(0, N-1)=Jx(0), u(0,k-1)+Jx(k), u(k, N-1)则策略u*(0,N-1)=u*(0),u*(1),u*(N-1)为最优性决策的充充分必要分必要条件为:对任意k,0kN-1,下列关系成立式中 x(k) = f(x(k

21、-1), u(k-1), k-1) 是后N-k个阶段的初始状态。 *(0,1)( ,1) (0),(0,1)min (0), (0,1)min ( ), ( ,1)kk NJNJkJkk Nuuxuxuxu最优性原理一般问题最优性原理一般问题的问题描述的问题描述(8/22)(8/22)q 证明证明 (1) 必要性证明。由最优策略的定义, 并应用式(184)和式(185),有 由于上式右边括弧中第一项与子策略子策略u(k, N-1)无关,因此有*(0,1)( ,1) (0),(0,1)min (0), (0,1)min ( ), ( ,1)kk NJNJkJkk Nuuxuxuxuu(0,N-1

22、)=u(0,k-1),u(k,N-1) (184)Jx(0),u(0,N-1)=Jx(0),u(0,k-1)+Jx(k),u(k,N-1) (185)*(0,1)(0,1)(0,1), ( ,1) (0),(0,1)min (0), (0,1)min (0), (0,1) ( ), ( ,1)min (0), (0,1) ( ), ( ,1)NNkk NJNJNJkJkk NJkk NJkuuuuxuxuxuxuuxux最优性原理一般问题的问题描述最优性原理一般问题的问题描述(9/22)(9/22)(2) 充分性证明。 设 为任意一个策略, 且是后N-k个阶段的初始状态, 则 于是( ,1)

23、( ), ( ,1)min ( ), ( ,1)k NJkk NJkk Nuxuxu( )( (1), (1),1)kkkkxf xu )1,(),1, 0() 1, 0(NkkNuuu( ,1)(0,1)( ,1) (0), (0,1) (0), (0,1) ( ), ( ,1) (0), (0,1)min ( ), ( ,1)min (0), ( ,1)min ( ), ( ,1)k Nkk NJNJkJkk NJkJkk NJk NJkk Nuuuxuxuxuxuxuxuxu最优性原理一般问题最优性原理一般问题的问题描述的问题描述(10/22)(10/22) 因此, 若式(186)成立,

24、 则对任一策略 ,都有即u*(0, N-1)为最优策略。 q 由上述定理17描述的最优性原理,可得如下推论。q 推论推论2 若u*(0, N-1)是最优策略,则对任一k,0kN-1,其子策略u*(k, N-1)对以x*(k)=f(x*(k-1),u*(k-1),k-1)为初始状态的后N-k个阶段来说,也必是最优策略。 * (0), (0,1) (0),(0,1)JNJNxuxu(0,1)N u *(0,1)( ,1) (0),(0,1)min (0), (0,1)min ( ), ( ,1)(186)kk NJNJkJkk Nuuxuxuxu最优性原理一般问题的问题描述最优性原理一般问题的问题

25、描述(11/22)(11/22)q 证明证明 用反证法。假设u*(k,N-1)是最优策略最优策略，而对于以x*(k)=f(x*(k-1),u*(k-1),k-1)为初始状态的后后N-k个阶段来说不个阶段来说不是最优策略是最优策略, 即有则*( ,1)( ),( ,1)min( ), ( ,1)( ), ( ,1)k NJkk NJkk NJkk Nuxuxuxu *(0,1)*( ,1) (0),(0,1) (0),(0,1)( ),( ,1) (0),(0,1( ), ( ,1)min (0), (0,1) (0), (0,1)min( ), ( ,1),1), (kk NJkk NJkkJ

26、NJkJkk NJkJkJkk NNuuxuxuxuxuxuxuxuxuu最优性原理一般问题的问题描述最优性原理一般问题的问题描述(12/22)(12/22) 即u*(0,k-1), u(k,N-1)为比u*(0,N-1)更优的策略,与u*(0,N-1)为最优策略的假设矛盾。 因此,最优策略u*(0,N-1)的子策略u*(k,N-1)对以x*(k)=f(x*(k-1),u*(k-1),k-1)为初始状态的后N-k个阶段来说,也必是最优策略推论得证。 证毕q 由上述定理和推论,可得最优性原理的另一个表达形式式中, J*x(k),u*(k,N-1)表示以k时刻的状态x(k)为初始状态, 后N-k个

27、阶段在最优策略u*(k, N-1)下的最优总成本, 最优策略u*(k, N-1)为最优策略u*(0, N-1)的后N-k个决策。*(0,1) (0),(0,1)min (0), (0,1) ( ),*( ,1)kJNJkJkk Nuxuxuxu最优性原理一般问题最优性原理一般问题的问题描述的问题描述(13/22)(13/22)q 基于最优性原理的表达形式(187)和总成本的表达式(183), 可推得即1*(0,1)0 (0),(0,1)min( ( ), ( ), ) ( ),*( ,1)kkiJNFii iJkk Nuxuxuxu1*(0)(1,1)1*(0)(1)1*(2,1)2 (0),

28、(0,1)min( (0), (0),0)min( ( ), ( ), ) ( ),*( ,1)min( (0), (0),0)min( (1), (1),1)min( ( ), ( ), ) ( ),*( ,kkikkiJNFFii iJkk NFFFii iJkk Nuuuuuxuxuxuxuxuxuxuxu1). 10*(0,1) (0), (0), (1),., (1)( ( ), ( ), )(183) (0),(0,1)min (0), (0,1) ( ),*( ,1)(187)NkkJNFkk kJNJkJkk Nuxuuuxuxuxuxu最优性原理一般问题的问题描述最优性原理一

29、般问题的问题描述(14/22)(14/22) 因此, 有如下一步逆向递推逆向递推形式 式中, J*x(N), N为总成本的边界条件, 相当于控制性能指标泛函中的末值型指标。 对总成本表达式, 则有如下总成本J的边界条件J*x(N), N=0 *(1)* (1),(1,1)min( (1), (1),1) (),*()NJNNNFNNNJNNuxuxuxu*(2)* (2),(2,1)min( (2), (2),2) (1),*(1,1)NJNNNFNNNJNNNuxuxuxu*(0) (0),(0,1)min( (0), (0),0) (1),*(1,1)JNFJNuxuxuxu最优性原理一般

30、问题最优性原理一般问题的问题描述的问题描述(15/22)(15/22)q 由上述递推解过程,可归纳得如下动态规划法的递推方程,即贝尔曼递推方程q 为了更好地理解动态规划的本质,再作如下说明。1) 结合定理17的推论和式(187), 最优性原理可以表述为:“一个最优性策略具有这样的性质, 即不论过去的状态及过去的决策如何, 如把当前状态视为后续过程的初始状态, 则其后诸决策仍必须构成一最优策略。*(1)* (1),(1,1)min( (1), (1),1) ( ),*( ,1) ,1,.,1kJkkNFkkkJkk NkN Nuxuxuxu*(0,1) (0),(0,1)min (0), (0,

31、1) ( ), *( ,1)(187)kJNJkJkk Nuxuxuxu最优性原理一般问题的问题描述最优性原理一般问题的问题描述(16/22)(16/22)2) 最优性原理得以成立的一个前提条件(必要条件),即所谓的过程无后效性,是当前状态x(k)仅由前一阶段状态x(k-1)和决策u(k-1)唯一决定。 前一阶段状态x(k-1)和决策u(k-1)对后续过程的影响后续过程的影响通过当前状态x(k)起作用, 并无其它直接影响。 这种性质在数学上称为马尔柯夫(Markov)特性。最优性原理一般问题最优性原理一般问题的问题描述的问题描述(17/22)(17/22)3) 在N阶段决策过程中,前k个阶段的

32、子策略对总成本的影响表现在两个方面,v其一是直接决定前k个阶段的局部总成本,v其二通过对状态通过对状态x(k)的影响, 间接地影响后N-k个阶段的局部总成本。 因此,为了构成一个最优策略,其前k个阶段的子策略必须通盘通盘考虑这两个方面的影响。 定理17中式(186) 体现了这一思想, 即在求前k个阶段的子策略时, 应使前应使前k个阶段的局部总成本与后个阶段的局部总成本与后N-k个阶段的局部总成本之和最小个阶段的局部总成本之和最小, 而不是仅使前不是仅使前k个阶段的局部总成本最小个阶段的局部总成本最小。*(0,1)( ,1) (0),(0,1)min (0), (0,1)min ( ), ( ,

33、1)(186)kk NJNJkJkk Nuuxuxuxu最优性原理一般问题最优性原理一般问题的问题描述的问题描述(18/22)(18/22)4) 从动态规划的逆向递推求解公式(194)可知, 欲求出最优决策u*(0), 就得先求出最优决策u*(1); 依此类推,要求出最优决策u*(1),就得先求出最优决策u*(2); ,最后,归结为首先求出最优决策u*(N-1),再逐步递推回代,相继得到最优决策序列u*(N-2),u*(1),u*(0)。q 由此可知,动态规划法的解题顺序和事物的发展进程相反。下面通过一实例进一步说明多阶段决策的动态规划法的应用。*(2)* (1),(1,1)min( (1),

34、 (1),1) ( ), *( ,1),1,.,1(194)NJkkNFkkkJkk NkN Nuxuxuxu最优性原理一般问题的问题描述最优性原理一般问题的问题描述(19/22)(19/22)例例7-147-14q 例例14 图12所示的是某零件的加工工序图,各节点代表机床,箭头代表加工工序,节点间的数字表示零件加工的经济效益。 试求一产生最大经济效益的工序路线。 最优性原理一般问题的问题描述最优性原理一般问题的问题描述(20/22)(20/22)q 解解 根据多阶段决策的动态规划法,反复使用逆向递推公式,则有J*F=0J*x1(4)=4J*x2(4)=3J*x1(3)=max4+J*x1(

35、4)=8J*x2(3)=max1+J*x1(4),3+J*x2(4)=5J*S=max4+J*x1(1),5+J*x2(1)=16最优性原理一般问题的问题描述最优性原理一般问题的问题描述(21/22)(21/22)q 解解 根据将所求得的各点的最佳效益标记在代表各机床的圆圈内,并同时将前面所求得的各相邻机床之间的决策作于工序图上,即可得图13。图图13 某机械加工最优工序图某机械加工最优工序图最优性原理一般问题的问题描述最优性原理一般问题的问题描述(22/22)(22/22) 由图13可以很方便地得到从加工起始机床S到完成最后加 工 的 机 床 F 的 最 佳 经 济 效 益 工 序 路 线S

36、,x2(1),x2(2),x2(3),x1(4),F。 由该图也可以很方便地求出各机床到机床各机床到机床F的最佳路线的最佳路线。 离散系统的动态规划法离散系统的动态规划法(1/9)(1/9)3. 离散系统的动态规划法离散系统的动态规划法q 离散系统的最优控制问题可以归结为一个多阶段决策优化问题,其中决策变量即为其控制输入变量, 总成本为其性能指标泛函。 因此,利用前面的多阶段决策问题的动态规划法,可得离散系统最优控制问题的动态规划解法。离散系统的动态规划法离散系统的动态规划法(2/9)(2/9)定理定理7-187-18q 定理定理18 (离散系统的动态规划法) 设离散系统的状态方程、状态初始条

37、件和性能指标泛函分别为式中, f(x,u,k)和L(x,u,k)都是关于状态x(k)和时间k的连续可微函数; S(x(kf),kf)是关于x(kf)和kf的连续可微函数； u(k)和x(k)分别为r维和n维向量;0001(1)( ( ), ( ), ),() ( )( (),)( ( ), ( ), )fkffk kkkkkkJSkkLkkkxf xuxxuxxu离散系统的动态规划法离散系统的动态规划法(3/9)(3/9) 容许控制u(k)满足u(k)U, kk0,kf式中,U为受不等式不等式约束条件限制的控制量u(k)的Rr空间中的闭集。 设使性能指标泛函(196)极小的最优控制函数为u*(

38、k)、最优状态轨线为x*(k)。 则u*(k)和x*(k)满足如下逆向递推方程,即贝尔曼递推方程*( )* ( ),( ,1)min( ( ), ( ), ) (1),*(1,1)1,.,1,0 (),)( (),)fkUffffffJkk kLkk kJkkkkkJkkSkkuxuxuxuxx01 ( )( (),)( ( ), ( ), )(196)fkffk kJSkkLkk kuxxu离散系统的动态规划法离散系统的动态规划法(4/9)(4/9)q 在离散系统最优控制问题的动态规划求解方法中,若控制量u(k)不受约束,可以在Rr空间中自由取值,则由贝尔曼递推方程(198)求解最优控制量u

39、*(k),可等效地求解如下关系式即*( ) ( ),( ,1)min( ( ), ( ), ) (1), *(1,1)(198)ffk UJkk kLkk kJkkkuxuxuxu* ( ), ( ),(1,1)0( )fJkkkkkxuuu* (1),*(1,1)( ( ), ( ), )( )( ) (1),*(1,1)( ( ), ( ), )( ( ), ( ), )( )( )(1)0ffJkkkLkk kkkJkkkLkk kfkk kkkkxuxuuuxuxuxuuux离散系统的动态规划法离散系统的动态规划法(5/9)(5/9)例例7-157-15q 下面通过一个例子来说明由定理

40、18求解离散系统的最优控制问题。q 例例15 已知被控系统为求在性能指标泛函下的最优控制序列u*(k)和最优轨线x*(k)。 21(1)( )( )( )(0)25x kx kxku kx20( )2 ( )kJx ku k离散系统的动态规划法离散系统的动态规划法(6/9)(6/9)q 解解 由离散系统最优控制问题的贝尔曼逆向递推方程(198),可得 因此,由可解得*(1)* (1),(1,2)min(1)2 (1) ( ), *( ,2)3,2,1 (3),3)0kUJx ku kx ku kJkkkJx uxu*(2) (2),(2)min(2)2 (2)UJxuxuu*( ) ( ),(

41、 ,1)min( ( ), ( ), ) (1),*(1,1)(198)ffkUJkk kLkk kJkkkuxuxuxu*(2)(2), (2),(2)02xuJxu离散系统的动态规划法离散系统的动态规划法(7/9)(7/9) 再由可解得*(1)(1) (1),(1,2)min(1)2 (1) (2), *(2)min(1)2 (1)UUJxuxuJxuxuuu*( ) ( ),( ,1)min( ( ), ( ), ) (1),*(1,1)(228)ffkUJkk kLkk kJkkkuxuxuxu*(1)(1) (1),(1)02xuJxu 最后,由可解得*(1)(1) (0),(0,2

42、)min(0)2 (0) (1), *(1,2)min(0)2 (0)UUJxuxuJxuxuuu*(0)(0) (0),(0)02xuJxu离散系统的动态规划法离散系统的动态规划法(8/9)(8/9) 因此,由初始状态x(0)=2,可解得最优控制序列和最优轨线分别为*351(0)1(1)(2)220515406(1)3(2)(3)10500uuuxxx离散系统的动态规划法离散系统的动态规划法(9/9)(9/9)q 前面讨论了一般求解离散系统最优控制问题的动态规划法,给出了求解方法和基本步骤。 对于一般的非线性离散系统一般的非线性离散系统,采用上述动态规划法很难很难得到其最优控制函数得到其最优

43、控制函数u*(t)和最优状态最优状态x*(t)的解析表达式,使得离散系统最优控制问题的求解较复杂,难以实际应用。 但对于线性离散系统线性离散系统, 当其最优控制问题的性能指标泛函为二次型性能指标二次型性能指标时, 其最优控制函数u*(t)和最优状态x*(t)具有较简洁的解析表达式, 并能很方便地构成最优状态反馈律和闭环最优控制系统。 下面,作为离散最优控制问题的动态规划法的具应用,我们将讨论线性离散系统的二次型性能指标泛函下的最优控制问题, 即离散最优二次型问题。线性离散系统的二次型最优控制线性离散系统的二次型最优控制(1/3)(1/3)6.2 线性离散系统的二次型最优控制线性离散系统的二次型

44、最优控制q 类似于线性连续系统的二次型最优控制问题, 线性离散系统的二次型最优控制律也是线性控制, 易于实现。 下面将介绍线性离散系统的二次型最优控制,内容为： 时变状态调节器时变状态调节器 定常状态调节器定常状态调节器 时变状态调节器时变状态调节器(1/14)(1/14)1. 时变状态调节器时变状态调节器q 线性连续系统的二次型最优控制问题在前面已经作了详细的讨论 下面将会看到, 线性离散系统的二次型最优控制问题的解可最后归结到一个最优状态反馈律和求解一个与黎卡提矩阵微分方程相类似的黎卡提矩阵差分方程。q 线性离散系统的二次型性能指标泛函下的最优控制问题的描述如下。时变状态调节器时变状态调节

45、器(2/14)(2/14)q 线性离散系统的二次型最优控制问题线性离散系统的二次型最优控制问题 设线性时变离散系统的状态方程和初始条件分别为x(k+1)=G(k)x(k)+H(k)u(k) x(k0)=x0式中,控制量u(k)不受约束。 寻找最优控制函数u*(k),使下列二次型性能指标泛函为最小式中,F和Q(k)为非负定矩阵; R(k)为正定矩阵; 末态时刻kf是固定的。01 ( )()()( ) ( ) ( )( ) ( ) ( )fkffk kJkFkk Q kkk R kkuxxxxuu时变状态调节器时变状态调节器(3/14)(3/14)q 下面讨论用动态规划法求解上述离散系统的最优控制

46、问题。 根据贝尔曼的动态规划法,求解上述最优控制问题需从最后一级开始,由后往前按贝尔曼递推公式进行计算。 因此,由贝尔曼递推方程(198),可得如下线性离散系统的二次型最优控制问题的递推计算公式和边界条件*( )* ( ),( ,1)min( ) ( ) ( )( ) ( ) ( ) (1),*(1,1)1,.,1,0 (),)()()fkUffffffJkk kk Q kkk R kkJkkkkkJkkkFkuxuxxuuxuxxx*( ) ( ),( ,1)min( ( ), ( ), ) (1),*(1,1)198ffkUJkk kLkk kJkkkuxuxuxu（）时变状态调节器时变状

47、态调节器(4/14)(4/14) 因此,对最后一级应有*(1)*(1) (1),(1)min(1) (1) (1)(1) (1) (1) (),)(1) (1) (1)min(1) (1) (1)()()fffffffkUfffffffffffkUffJkkkQ kkkR kkJkkkQ kkkR kkkFk uuxuxxuuxxxuuxx*( )* ( ),( ,1)min( ) ( ) ( )( ) ( ) ( ) (1),*(1,1)1,.,1,0fkUffJkk kk Q kkk R kkJkkkkkuxuxxuuxu 将系统的状态方程代入上式,可得*(1) (1),(1)(1) (1

48、) (1)min(1) (1) (1)(1) (1)(1) (1)(1) (1)(1) (1)fffffffffkUffffffffJkkkQ kkkR kkG kkH kkFG kkH kk uxuxxuuxuxu时变状态调节器时变状态调节器(5/14)(5/14) 由于u(k)不受约束,上式对u(k)求极值等价于求解如下方程* (1), (1)(1)2 (1) (1)2(1) (1) (1)(1) (1)0ffffffffffJkkkR kkHkF G kkH kkxuuuxu*( )* ( ),( ,1)min( ) ( ) ( )( ) ( ) ( ) (1),*(1,1)1,.,1,

49、0fkUffJkk kk Q kkk R kkJkkkkkuxuxxuuxu 解得式中,K(kf-1)为如下kf-1时刻的最优状态反馈矩阵*1(-1) (1)(1)(1)(1)(1) (-1)(1) (1)fffffffffkR kHkFH kHkFG kkK kk uxx时变状态调节器时变状态调节器(6/14)(6/14) 将最优控制函数u*(kf-1)代入式(205),则有如下最后一级的最优成本函数* (1),(1)(1) (1)(1) (1)(1)(1)(1)(1)(1)(1)(1) (1)ffffffffffffffJkkkQ kKkR kK kG kH kK kF G kH kK k

50、kxuxx*(1) (1),(1)(1) (1) (1)min(1) (1) (1)()()205fffffffffffkUJkkkQ kkkR kkkFk uxuxxuuxx（）1(1) (1)(1)(1)(1)(1)ffffffK kR kHkFH kHkFG k时变状态调节器时变状态调节器(7/14)(7/14) 定义则式(210)可表示为()(1)(1)(1) (1) (1) (1)(1) (1) (1)(1) (1)(1)(1) (1) (1) (1)(1) (1)() (1)(1) (1)fffffffffffffffffffffffP kFP kQ kK kR kK kG kH

51、kK kF G kH kK kQ kK kR kK kG kH kK kP kG kH kK k* (1),(1)(1) (1)(1) (1)(1)(1)(1)(1)(1)(1)(1) (1)210ffffffffffffffJkkkQ kKkR kK kG kH kK kF G kH kK kkxuxx（）* (1),(1)(1) (1) (1)fffffJkkkP kkxuxx时变状态调节器时变状态调节器(8/14)(8/14)q 最优成本函数的逆向递推的边界条件(204)也可以表示为 因此,上述在最后一级应用动态规划法的递推方程所得到的最优状态反馈矩阵和最优成本函数可总结为其中* (),

52、)() () ()fffffJkkkP kkxxx* (),)()()204ffffJkkkFkxxx（）1*(1)(1)(1) (1)(1)(1) (1) (1) (1),(1)(1) (1) (1)fffffffffffffK kR kHkP kH kHkP kG kJkkkP kkxuxx(1)(1)(1) (1)(1)(1)(1)(1)()(1)(1)(1)ffffffffffffP kQ kKkR kK kG kH kK kP kG kH kK k时变状态调节器时变状态调节器(9/14)(9/14)q 依贝尔曼的逆向递推公式,在倒数第二级应有 比较上式和式(205)可以看出,两式形式

53、上相同。 因此,只要注意两式之间的如下对应关系kf-1kf , kf-2kf-1, P(kf-1) P(kf)=F就可以类似于最后一级的推导,得到在倒数第二级的如下最优控制解的结论*(2)*(2) (2),(2)min(2) (2) (2)(2) (2) (2) (1), (1)(2) (2) (2)min(2) (2) (2)(1) (1) (1)fffffffkUfffffffffffkUfffJkkkQ kkkR kkJkkkQ kkkR kkkP kkuuxuxxuuxuxxuuxx*(1) (1),(1)(1) (1) (1)min(1) (1) (1)()()205ffffffff

54、fffkUJkkkQ kkkR kkkFk uxuxxuuxx（）时变状态调节器时变状态调节器(10/14)(10/14)其中*(2)(2) (2) (2),(2)(2) (2) (2)ffffffffkK kkJkkkP kkuxxuxx1(2) (2)(2) (1)(2)(2) (1) (2)(2)(2)(2) (2)(2) (2)(2)(2)(1) (2)(2)(2)ffffffffffffffffffffK kR kHkP kH kHkP kG kP kQ kKkR kK kG kH kK kP kG kH kK k时变状态调节器时变状态调节器(11/14)(11/14)q 依此类推,

55、我们可以证明如下离散时变系统的二次型性能指标最优控制问题在倒数第步的逆向递推方程1*( )( )( ) (1)( )( ) (1) ( )( )( )( ) ( )( )( )( )( )(1)( )( )( )( )( ) ( ) ( ),( )( ) ( ) ( )K kR kHk P kH kHk P kG kP kQ kKk R k K kG kH k K kP kG kH k K kkK kkJkkk P kk uxxuxx式中,k=kf-1,kf-2,0;逆向递推的边界条件为*() (),)() () ()ffffffP kFJkkkP kkxxx时变状态调节器时变状态调节器(12

56、/14)(12/14)q 从上面的推导可知,离散系统的二次型最优控制问题的最优控制u*(k)是状态变量x(k)的线性反馈,其中rn维矩阵K(k)称为最优状态反馈增益矩阵。 由上述递推计算式可知,K(k)只与G(k),H(k),F,Q(k)和R(k)有关,与系统的初始状态无关。 因此,由最优状态反馈律实现最优二次型闭环控制时,可事先离线计算出K(k),在线控制时仅作简单比例控制运算。时变状态调节器时变状态调节器(13/14)(13/14)q 将反馈增益矩阵K(k)的计算式代入黎卡提矩阵型差分方程,经整理可得黎卡提矩阵型差分方程的另一种表示形式其中1( )( ) (1)(1)( ) ( )( ) (1)( )( ) (1) ( )( )( )( ) ( )( )P kGkP kP kH k R kHk P kH kHk P kG kQ kGk M k G kQ k 1( )(1)(1)( ) ( )( ) (1)( )( ) (1)M kP kP