研究生最优控制课堂稿(part3)

⎧ d ( B2 , C1 ) + J 3 (C1 ) ⎫ ⎧4+5⎫ ⎪ ⎪ J 4 ( B2 ) = min ⎨d ( B2 , C2 ) + J 3 (C2 ) ⎬ = min ⎪3 + 11⎪ = 9 ⎨ ⎬ ⎪d ( B , C ) + J (C ) ⎪ ⎪ ⎪ ⎩5 + 8 ⎭ 2 3 3 3 ⎭ ⎩
7
5
D1
7
4
E2
1
11
D2
E1
8
D1
7
E2
2
J 2 ( D3 ) = 7 ⎧ d (C1 , D1 ) + J 2 ( D1 ) ⎫ = min ⎧1 + 4 ⎫ = 5 （3）C级： J 3 (C1 ) = min ⎨ ⎨ ⎬ ⎬ ⎩d (C1 , D2 ) + J 2 ( D2 ) ⎭ ⎩5 + 7 ⎭
4 动态规划
动态规划是由美国学者R.贝尔曼（Bellman）在1957 年提出来的，是控制有约束的情况下求解最优控制问题的 有效方法，其核心是贝尔曼的最优性原理。 最优性原理可归结为一个基本递推关系式，从而使决 策过程连续的转移，可将一个多级决策过程化为多个一级 决策过程，从而简化求解过程。 时至今日，由于计算技术和计算方法的迅速发展，动 态规划在生产、收益、资源分配、设备更新、优化设计、 优化设计、信息处理和模式识别等领域中得到了广泛的应 用。 局限性——问题维数。
14 C1
5
D1
7
4
E2
1
14 B2
9
C1
11
D2
E1
12 C2
8
D1
7
E2
2
（4）B级：J 4 ( B1 ) = 14
J 4 ( B3 ) = 12 ⎧3 + 14 ⎫ ⎧ d ( A, B1 ) + J 4 ( B1 ) ⎫ （5）A级： ⎪ ⎪ ⎪ ⎪ d ( A, B2 ) + J 4 ( B2 ) ⎬ = min ⎨5 + 9 ⎬ = 14 J 5 ( A) = min ⎨ ⎪ ⎪ ⎪ ⎪ ⎩4 + 12 ⎭ ⎩d ( A, B3 ) + J 4 ( B3 ) ⎭
J * [ k ] = min { L [ x ( k ), u ( k ), k ] + J * [ k + 1]}
u ( k )∈Ω
（1）令k=2，有
J * [ 2 ] = min ⎡ x 2 (2) + u 2 (2) ⎤ + J * [3 ] ⎣ ⎦ u (2)
{
}
由代价函数的末值项，结合系统运动方程，有：
1
4.1 多级决策问题
最短路线问题 由A到F的路线图及各地间距离如下图所示。
要求选择一条从A到F的最短路经。 为了确定AF之间的最短路经，可以采用穷举法和动态 规划法两种方法。
2
求解最短路线问题的穷举法 思路： （1）列出所有可能路线 共38条线路 （2）分别计算路程 共做加法 4×38=152次 （3）对比得最短路线 需做37次比较 最短距离：14 最短路径： AB2C1D1E2F
6
4
E2
1
7
E1
7
E2
2
（2）D级： 本级有三种选择，每种选择有2条路线。
J 2 ( D1 ) = 4 J 2 ( D2 ) = 7
⎧ d ( D3 , E1 ) + J1 ( E1 ) ⎫ ⎧ 7 + 1⎫ J 2 ( D3 ) = min ⎨ ⎬ = min ⎨ ⎬ =7 ⎩d ( D3 , E2 ) + J1 ( E2 ) ⎭ ⎩5 + 2 ⎭ 说明D3到F的最短距离是7，路线为D3E2F , S2 ( D3 ) = E2
（2）D级： J 2 ( D1 ) = 4
J 2 ( D2 ) = 7
S3 (C1 ) = D1 S3 (C2 ) = D2
⎧ d (C2 , D1 ) + J 2 ( D1 ) ⎫ ⎧8 + 4 ⎫ ⎪ ⎪ J 3 (C2 ) = min ⎨d (C2 , D2 ) + J 2 ( D2 ) ⎬ = min ⎪4 + 7 ⎪ = 11 ⎨ ⎬ ⎪6 + 7 ⎪ ⎪ ⎪ ⎩ ⎭ ⎩d (C2 , D3 ) + J 2 ( D3 ) ⎭ ⎧ d (C3 , D1 ) + J 2 ( D1 ) ⎫ ⎧4 + 4⎫ ⎪ ⎪ J 3 (C3 ) = min⎨d (C3 , D2 ) + J 2 ( D2 ) ⎬ = min ⎪4 + 7 ⎪ ⎨ ⎬ ⎪d (C , D ) + J ( D ) ⎪ ⎪2 + 7 ⎪ 3 3 2 3 ⎭ ⎩ ⎩ ⎭
5
4
E2
1
7
E1
2
（1）E级： J1 ( E1 ) = 1 J1 ( E2 ) =2 标于上图。 （2）D级： 本级有三种选择，每种选择有2条路线。
⎧ d ( D1 , E1 ) + J1 ( E1 ) ⎫ ⎧ 4 + 1⎫ J 2 ( D1 ) = min ⎨ ⎬ = min ⎨ ⎬ =4 d ( D1 , E2 ) + J1 ( E2 ) ⎭ 2 + 2⎭ ⎩ ⎩ 说明D1到F的最短距离是4，路线为D1E2F , S2 ( D1 ) = E2
J * [ k ] = min { L [ x ( k ), u ( k ), k ] + J * [ k + 1]}
u ( k )∈Ω
从过程的最后一级开始，逐级逆向递推。 具体步骤： （1）令k=N-1,得：
J * [ N − 1] = min J * [ N − 1] = min
u ( N −1)∈Ω
*
（2）令k=N-2,得：
J * [ N − 2] = min
u ( N − 2)∈Ω
（3）分别令k=N-3,N-4,…,1,0,依次得到： u ( N − 3)
u (1), u (0)
15
例14 已知离散系统的动态方程
x ( k + 1) = 2 x ( k ) + u ( k ) x (0 ) = 1
根据最优性原理，始自第k级任一容许状态 x(k ) 的最小代价
J * [ k ] = min { L [ x ( k ), u ( k ), k ] + J * [ k + 1]}
u ( k )∈Ω
称该式为动态规划的基本递推方程。
k = 0,1,
, N −1
14
问题的解法
基本思路： 根据动态规划的基本递推方程
J N ( x ) = min {d [ x , S N ( x ) ] + J N −1 ( S N ( x ))}
SN ( x)
以及
J1 ( x ) = d [ x, F ]
在动态规划中，称这两个方程为函数方程。 由本例的分析过程可见，最优策略（各阶段决策组成 的最佳集合）的选择，应在递推过程结束后进行，而不能 在各级分散确定。这种递推的思想就是贝尔曼提出的最优 性原理。
k = 0,1,
, N −1
{L [ x(N − 1), u (N − 1), N − 1] + J [ N ]}
*
若代价函数中无末值项，则
u ( N −1)∈Ω
J * [N] = 0
{L [ x (N − 1), u (N − 1), N − 1]}
{L [ x(N − 2), u (N − 2), N − 2] + J [ N -1]}
=8
S3 (C3 ) = D1
8
14 C1
5
D1
7
4
E2
1
9
C1
11
D2
E1
Байду номын сангаас
12 C2
8
D1
7
E2
2
J 3 (C3 ) = 8 ⎧9+5⎫ ⎧ d ( B1 , C1 ) + J 3 (C1 ) ⎫ （4）B级： J 4 ( B1 ) = min⎨ ⎬= min ⎨ ⎬ = 14 d ( B1 , C2 ) + J 3 (C2 ) ⎭ ⎩ ⎩5 + 11⎭
12
4.3 动态规划的基本递推方程
设N级过程的动态方程为
x ( k + 1) = f [ x ( k ), u ( k ), k ] x (0 ) = x 0
式中状态约束 x(k ) ∈ X ⊂ R n , 控制（决策）约束 u (k ) ∈ Ω ⊂ R m , * k = 0,1, , N − 1。求容许控制（决策）序列 u (k ), k = 0,1, , N − 1， 使代价函数（或性能指标）
⎧ d ( D2 , E1 ) + J1 ( E1 ) ⎫ ⎧ 6 + 1⎫ J 2 ( D2 ) = min ⎨ ⎬ = min ⎨ ⎬ =7 d ( D2 , E2 ) + J1 ( E2 ) ⎭ 9 + 2⎭ ⎩ ⎩ 说明D2到F的最短距离是7，路线为D2E1F , S2 ( D2 ) = E1
J
*
[3 ] = x 2 (3)
于是， J * [ 2 ] = min ⎡ x 2 (2) + u 2 (2) ⎤ + [ 2 x (2) + u (2) ] ⎣ ⎦ u (2)
{
= [2 x ( 2 ) + u ( 2 ) ]
2
2
}
16
例14（续1）
（1）令k=2，
J 4 ( B2 ) = 9
S5 ( A) = B2
在图中可顺序确定最短路线为：AB2C1 D1 E2 F