当前位置:首页 >> 电力/水利 >>

动态规划


第6章 动态规划
动态规划是贝尔曼(Bellman)在50年代作为段

(步)决策过程研究出来的,现已在许多技术领域中获
得广泛应用。动态规划是一种分段最优化方法,它既可 以用来求解约束条件下的函数极值问题,也可以用来求 解约束条件下的泛函极值问题。它与极小值原理一样, 是处理控制矢量被限制在一定的闭集内,求解最优控制

问题的有效数学方法之一。

动态规划的核心是最优性原理,它首先将一个 多段决策问题转化为一系列单段决策问题,然后从 最后一段状态开始逆向递推到初始状态为止的一套 求解最优策略的完整方法。 6.1 多级决策问题 动态规划是解决多段决策问题的有力工具。 多级决策过程:把一个过程分成若干阶段,每个 阶段都作出决策,以使整个过程取得最优效果。 最短路线问题是多级决策问题的一个典型例

子。

6.1.1 最短路线问题
9
B1 C1

1 5 8

D1

4 2
E1

3 4

5

1
F

5
A

B2

3
5

C2

4
6 4

D2

6
9 7
E2

4 1
B3

2

4 2
D3

7

C3

5

图6-1 最短路线问题

设由 A 至 F 的路线如上图所示。要求选择一条路程 最短的线路。各地间的距离已标注在图中。由 A 到

B( B1 , B2 , B3 ) ,需要选择一条路线,使 AB之间路程短, 称为一级决策过程;

9
B1

C1

1 5 8

D1

4
2
E1

3 4 5
A

5

1
F

B2

3 5

C2

4 6 4

D2

6 9 7
E2

4 1
B3

2

4

7

C3

2

D3

5

再从 B( B1 , B2 , B3 ) 到 C (C1 , C2 , C3 ) 选择一条路线, 使 ABC 之间路程最短,称为二级决策;

从 ABCD 选择一条路线,使 AD 之间路程最短,称为 三级决策过程;以此类推,上图共有从 A 到 F 五级 决策过程。 为确定 AF之间最短路线,可采用穷举法与动态规划法。

穷举法是列出所有可能的路线,计算各路线的路 程,通过对比后得到最短路线。本例共有38条可能路 线,见p.131的图。由图可知,决定每条路线的长度 需作4次加法,故共需叫法152次,比较37次。最后得 最短路线为 AB2C1D1E2 F , 最短距离 J * ? 14 。

动态规划法是一种逆序计算法,从末端开始,到 x 始端为止,逆向递推。设 N 为多级决策过程的级数; S 表示在任一级所处的位置,称为状态变量; N (x)为决 策变量,表示当状态 x以后还有N 级时,所选取的下 一点;J N (x)表示由状态 x 到终点 F 的 N 级过程的最 短距离。 d ( x, S N )表示 x 点到 S N 的距离。对于图6-1 问题,从最后一级开始计算。

9
B1

C1

1

D1

3 4 5
A

5 8 3
C2

5
2 4
D2

4
E1


1
F

B2

6 9 7
E2

5
4 1
B3

6
4
C3

2

4 2
D3

5



7

(1) N ? 5( E级) J1 ( E1 ) ? 1

J 2 ( E2 ) ? 2
将 E( E1 , E2 )至 F 的距离数字标注于图6-3中,数字括号 内的文字表示相应的决策变量。由于从 E1到 F以及从 E2 到 F 都只有一种可能,所以本级无决策问题。

9
B1

C1

1 5 8

D1


4
2
E1

3 4 5
A

5


1
F

B2

3 5

C2

4 6 4

D2

6 9 7
E2

4 1
B3

2

4

7

C3

2

D3

5



(2) N ? 4( D级) 本级决策有三种选择。每种选择中又有两条可能的路 线。例如,从 D1出发,可达 E1,也可达 E2,所以 ?d ( D1 , E1 ) ? J1 ( E1 ) ? ?4 ? 1 ? J 2 ( D1 ) ? min? ? ? min? ??4 ?2 ? 2? ?d ( D1 , E2 ) ? J1 ( E2 )? D1至 F 的最短距离为4,路线为 D1E2 F 。 S2 ( D1 ) ? E2

9
B1

C1

1 5 8

D1


4
2
E1

3 4 5
A

5


1
F

B2

3 5

C2

4 6 4 4

D2

6 9 7 5
E2


D3

4 1
B3

2

7

C3



2



同理 D2 至 F 最短距离为7,路线为 D2 E1F ,决策 变量为 S ( D ) ? E
2 2 1

同理 D3 至 F 最短距离为7,路线为 D3 E2 F ,决策 变量为 S ( D ) ? E
2 3 2

⒁9
B1

C1

⑤1
5 8 4 6 4 4 2

D1


4 2
E1

3

5


1
F


A


B2

4 3 5


C2

5

D2

6


D3

9
7
E2

4

⑿1
B3

2

7

C3

5



(3) N ? 3(C级) (4) N ? 2( B级) (5) N ? 1( A级)





最后确定最短路线为 AB2C1D1E2 F 最短距离 J * ? J 5 ( A) ? 14

这一方法只用加法24次,比较14 次,计算量比穷举法大为减少。

对于本例,求解时采用的递推方程的一般形式为

J N ( x) ? min{d [ x, S N ( x)] ? J N ?1[ S N ( x)]}
SN ( x)

6-1 6-2

以及

J1 ( x) ? d ( x, F )

6-1,6-2称为函数方程,多段决策化为多个单段决 策,采用逆推方法。 多段决策过程的最优策略具有性质: 不论初始状态和初始决策如何,后段最优决策对初 始决策所形成的状态来说,必定也是一个最优策略。

6.1.2 最优性原理
贝尔曼指出,多级决策过程的最优策略具有这样 的性质:不论初始状态和初始决策如何,当把其中的 任何一级和状态再作为初始级和初始状态时,其余的 决策对此必定也是一个最优策略。 具体说,若有一个初态 为 x(0)的级决策过程,其 最优策略为 {u (0), u (1),? ? ?u ( N ? 1)}。那么,对于以 x(1) 为初态的 N ? 1 级决策过程来说,决策集合

{u (1), u (2),? ? ?u ( N ? 1)} 必定时最优策略。

6.1.3 动态规划的基本递推方程
问题6-1 设 N 级过程的动态方程为

x(k ? 1 ? f [ x(k),u(k),k ], x(0) x0 ) ?

6-3

x(k) X ? R n ,控制(决策)约 ? 式中状态约束 束 u(k) ? ? R m 。求容许控制(决策)序 ? 列 u* k)k ? 0,1,? ? ?N ? 1 ,使代价函数(或性能指标) ( ,
J [ x(0)] ? ? L?x(k ), u (k ), k ?
k ?0 N ?1

6-4

为最小。

x 在问题6-1中, k 表示 N 级决策过程中的阶段变量,(k ) 表示 k ? 1 级初始状态, (k ) 表示第 k ? 1 级所采用的 u 控制(决策)向量,如图6-4所示。为了强调 是控制 u J 的泛函,因此式(6-4)可表示为
J [ x(0), u ] ? ? L?x(k ), u (k ), k ?
k ?0 N ?1

6-5
u ( N ? 1)

u (0) x(0)

u (1) x(1)

u (k )

1

2

x(2)

???

x(k )

k ?1 ? ? ?

x( N ? 1) x(k ? 1)

N

x(N )

图6-4 N 级决策过程

一般情况下,始于任意状态 x(k ) 的代价可记 为 J [ x(k ), u ] 。其中 u ? {u (k ), u (k ? 1),? ? ?, u ( N ? 1)}

J [ x(k ), u ] 表示由任意状态 x(k ) 到过程终点为止,由 任意策略 u 所导致的代价。
因此,始自 x(k ) 的最优代价为 J *[ x(k )] ? J [ x(k ), u* ]

式中u *表示最优策略。对于给定问题,当 x(k ) 固定 * J *[ x(k )] 仅是初始状 时, 是确定的,因此最优代价 u 态 x(k ) 的函数,常记为 J [ x(k )] 。
为了求出问题6-1的最小代价 J *[ x(0),0] ,根据动态 规划的解题思路,把始自 x(k )的待求问题,嵌入到 求 J *[ x(k ), k ] 的问题之中。

研究如下问题:
min J [ x(k ), k ] ?
u??

? L?x( j), u( j), j ?
j ?k

N ?1

6-6

式中 x(k )固定。
状态方程约束为
x( j ? 1) ? f [ x( j ), u ( j ), j ], j ? k , k ? 1,? ? ?, N ? 1

6-7

式中
x(k ) ? X ? R n u (k ) ? ? ? R m k ? 0,1,? ? ?, N ? 1

始自第 k 级任一容许状态 x(k )的最小代价
J *[ x(k ), k ] ? ?
{u ( k ),u ( k ?1),???u ( N ?1)}??

min

{

? L?x( j), u( j), j ?}
j ?k N ?1 j ? k ?1

N ?1

6-8

{u ( k ),u ( k ?1),???u ( N ?1)}??

min

{L[ x(k ), u (k ), k ] ?

? L?x( j), u( j), j ?}

式中第一部分是第 k 级内所付出的代价,第二部分是 从 第 k ? 1 级到第 N 级的代价和。将式(6-8)中求 ) 最小的运算也分解为两部分:在本级决策 u (k下求最 小,以及在剩余决策序列 {u(k ? 1), u(k ? 2),? ? ?u( N ? 1)} 下求 最小。

于是,式(6-8)可写为

J *[ x(k ), k ] ? min ?
N ?1

u ( k )?? {u ( k ),u ( k ?1),???u ( N ?1)}??

min

{L[ x(k ), u (k ), k ]
6-9

j ? k ?1

? L?x( j ), u( j ), j ?}

式中大括号内的第一项仅取决于 u (k ) ,而与 u ( j ),
j ? k ? 1, k ? 2,? ? ?N ? 1 无关,因此对 u (k ) 取极小没有意义。

大括号内的第二项,当 x(k ? 1) 固定时,其值取 决于 j ), j ? k ? 1, k ? 2,? ? ?N ? 1 ,而与 ) 没有直接关 u( u (k 系,但是 u (k ) 通过状态方程(6-7)决定 x(k ? 1) , 从而影响该项的值。

式(6-9)可写为
J *[ x(k ), k ] ? min {L[ x(k ), u (k ), k ]
u ( k )??

?

{u ( k ?1),???u ( N ?1)}??

min

j ? k ?1

? L?x( j), u( j), j ?}

N ?1

6-10

根据最优原理和状态方程(6-3),如下关系式成立
J *[ x(k ? 1), k ? 1] ? J * [ f ( x(k ), u (k ), k ), k ? 1] ?
{u ( k ?1),???u ( N ?1)}??

min

j ? k ?1

? L?x( j), u( j), j ?}

N ?1

6-11

将式(6-11)代入式(6-10),得动态规划基本递推方程
J *[ x(k ), k ] ? min {L?x(k ), u (k ), k ? ? J *[( x(k ? 1), k ? 1]}
u ( k )??

(k ? 0,1,? ? ?N ? 1)

6-12

或者
J *[ x(k ), k ] ? min {L?x( N ? 1), u ( N ? 1), N ? 1? ? J *[ x( N ), N ]}
u ( k )??

(k ? 0,1,? ? ?N ? 1)

6-13

上述递推关系从过程的最后一级开始,逐级逆向递推。 由式(6-12),令 ,得 k ? N ?1
J *[ x( N ? 1), N ? 1] ?
u ( N ?1)??

min {L?x( N ? 1), u( N ? 1), N ? 1? ? J *[( x( N ), N ]}

6-14 式中 J *[ x( N ? 1), N ? 1] 表示代价函数 J 中的末值项。对 于问题(6-1)以及相应的嵌入式(6-6),代价函数 中无末值项,应取 J *[ x( N ), N ] ? 0

于是,式(6-14)可写为
J *[ x( N ? 1), N ? 1] ?
u ( N ?1)??

min L?x( N ? 1), u( N ? 1), N ? 1? 6-15

式(6-15)仅是函数 L?x( N ? 1), u( N ? 1), N ? 1? 对控制 u(N ? 1) ? ? 的单级最优化问题,不再是式 (6-6)那样的多级优化问题,易于求解。求解时, 可以对所有的 x( N ? 1) ? X 求解式(6-15),以便得 * 到 J [ x( N ? 1), N ? 1] ,然后由递推方程(6-12)逆向 逐级递推,求出 J *[ x( N ? 2), N ? 2],? ? ?, J *[ x(1),1], J *[ x(0),0] 这最后一步的递推解 J *[ x(0),0] 以及得到的最优策 略 {u* (0),?u* (1),? ? ?, u* ( N ? 1)} ,正是问题(6-1)要求的 解。
这种把始自 x(0) 的待求问题嵌入到求始自 x(k ) 的 J *[ x(k ), k ] 问题之中的方法,称为嵌套原理。

例6-1 已知离散系统方程: x(k ? 1) ? 2 x(k ) ? u (k )

x(0) ? 1,代价函数: J ? x 3 ? ? x 2 (k ) ? u 2 (k )
k ?0

2

?

?

U ( k ) 无约束试求最优控制序列 ?u * (0), u * (1), u * (2)? 使代价函数取极小。 解:1、 N ? 3, k ? 2
所以:
* J1* ?x(2)? ? min x 2 (2) ? u 2 (2) ? J 0 ?x(3)?

J1* ?x(2)? ? min x 2 (2) ? u 2 (2) ? ?2 x(2) ? u (2)?
u ( 2)

?

* J 0 ?x(3)? ? x 2 (3) ? ?2 x(2) ? u(2)?
2

u ( 2)

?

?

2

?

?J1* ?x(2)? 可令 解得 u * (2) ? ? x(2) 故有 J1* ?x(2)? ? 3x 2 (2) ?0 ?u (2) 2、 N ? 2, k ? 1 时:J 2* ?x(1)? ? min x 2 (1) ? u 2 (1) ? J1* ?x(2)?
u (1)

?

?

? min x 2 (1) ? u 2 (1) ? 3?2 x(1) ? u (1)?
u (1)

?

2

?

所以:u * (1) ? ? 3 x(1)
2

* J 2 ?x(1)? ? 4 x 2 (1)

3、N ? 1, k ? 0时: J 3* ?x(0)? ? min ?x 2 (0) ? u 2 (0)?? J 2* ?x(1)?
u ( 0)

? min x 2 (0) ? u 2 (0) ? 4?2 x(0) ? u (0)?
u ( 0)

?

2

?

解得: * (0) ? ? 8 x(0) J 3* ?x(0)? ? 21 x 2 (0) u
5
5

代入 x(0) ? 1 再正向递推(P138) 可得:
? 8 3 1? u* ? ?? ,? ,? ? ? 5 5 5? ? 2 1 1? x* ? ?1, , , ? ? 5 5 5?

21 J * ? J ?x(0)? ? 5
* 3

6.2

离散动态规划
x(k ? 1) ? f [ x(k ), u(k ), k ], x(0) ? x0

问题 6-2 设状态方程为
(6 ? 16)

式中状态约束 x(k ) ? X ? Rn ,控制约束 u(k ) ?? ? Rm , k ? 0,1,?, N 求最优控制序列 u *(k ), k ? 0,1,?, N ,使代价函数 极小 求解步骤如下:
J N [ x(0)] ? ?[ x( N ), N ] ? ? L[ x(k ),u (k ), k ]
k ?0 N ?1

(6 ? 17)

(1) 求第N级最优控制 u *( N ? 1)
J1 *[ x( N ? 1)] ? min {L[ x( N ? 1), u ( N ? 1), N ? 1] ? J 0 *[ x( N )]}
u ( N ?1)??

解得 u *( N ? 1) ? u *[ x( N ? 1)] 以及
J1 *[ x( N ? 1)]

(2) 求第N-1 级最优控制 u *( N ? 2)
J 2 *[ x( N ? 2)] ? min {L[ x( N ? 2), u ( N ? 2), N ? 2] ? J1 *[ x( N ? 1)]}
u ( N ? 2)??

本步求得 u *[ x( N ? 2)] 及 J 2 *[ x( N ? 2)] ,以下类推。 (3)求第 k ? 1 级的最优控制 u *(k ) 。
J N ?k *[ x(k )] ? min {L[ x(k ), u (k ), k ] ? J N ?k ?1 *[ x(k ? 1)]}
u ( k )??

得到 u *(k ) ? u *[ x(k )] 以及 J N ?k *[ x(k )]

。以下类推

(4)求第 2级的最优控制 u *(1) 。
J N ?1 *[ x(1)] ? min{L[ x(1), u (1),1] ? J N ?2 *[ x(2)]}
u (1)??

式中 J N ?2 *[ x(2)] 是后部N-2段子过程的最小代价函数,已由 x L 上步求出; (2) 为其相应的初态; [ x(1), u(1),1] 为本级代价

(5)求第1级最优控制 u *(0)
J N *[ x(0)] ? min {L[ x(0), u (0),0] ? J N ?1 *[ x(1)]}
u (0)??

x(1)] ? f [ x(0), u (0),0]

求得 u *(0) ? u *[ x(0)] 以及 J N *[ x(0)] 。它们都是 x(0) 的函 数 x *(1) x 最后由已知初态 x(0) ,顺序求出u *(0) , ,u *(1) ,…, *( N ? 1)
u *[ x( N ? 1)] 以及N级过程最小代价函数 J * * * 最小代价函数 J N ?1 , J N ? 2 ,…, J 1。
* N

和各段子过程的

例 6-2 设离散系统方程

x(k ? 1) ? x(k ) ? u(k ), x(0) ? 0, x(4) ? 1 式中 u (k ) ?? ? {?1,0, ?1}。性能指标 3 J ? ? [x 2 (k ) ? u 2 (k )]
k ?0



u *(k ), k ? 0,1, 2,3 以及最优轨线 x *(k ), k ? 0,1, 2,3, 4

解:本例末端固定, (4) ? 1。 x (1)求 u *(3)
因为 所以

x(4) ? x(3) ? u(3) ? 1 x(3) ? 1 ? u(3)

J 0 [ x(4)] ? 0

*

?1,当u (3) ? ?1 * * ? 2 2 2 J 1 ? min{x (3) ? u (3) ? J 0 } ? min{1 ? 2 ? 2u (3)} ? ?1, 当u(3) ? 0 u (3)?? u (3)?? ?5,当u (3) ? ?1 ?
故取

?0,当u *(3) ? ?1 ??1 u (3) ? ? , x *(3) ? ? ?0 ?1,当u *(3) ? 0

J 1 ?1

*

* * ?0,当u *(3) ? ?1 J 2 ? min{x 2 (2) ? u 2 (2) ? J 1} x(3) ? x(2) ? u(2) ? ? u (2)?? 1,当u *(3) ? 0 ?

(2)求 u *(2)

A:取 u *(3) ? ?1, x *(3) ? 0, J 1 ? 1

*

?3,当u (2) ? ?1 * ? 2 J 2 ? min {2u (2) ? 1} ? ?1,当u (2) ? 0 u (2)?? ?3,当u (2) ? ?1 * ? 所以 u *(2) ? 0, x *(2) ? 0, J 2 ? 1
B:取 u *(3) ? 0, x *(3) ? 1, J 1 ? 1
*

x(2) ? ?u(2)

时,因为

时,因为

?2,当u (2) ? ?1 * ? 2 J 2 ? min {1 ? 2u (2) ? 2u (2) ? 1} ? ?2, 当u (2) ? 0 u (2)?? ?

x(2) ? 1 ? u(2)

所以

?1,当u *(2) ? 0 ?0 u (2) ? ? , x *(2) ? ? ??1 ?0,当u *(2) ? ?1 (3)求 u *(1) x(2) ? x(1) ? u(1)

J 2 ?2

*

J 3 ? min{x 2 (1) ? u 2 (1) ? J 2 }
u (1)??

*

*

u *(3) ? 1, x *(3) ? 0, J 1 ? 1 A:取 u *(2) ? 0, x *(2) ? 0, J 2 ? 1
可得
*

*

x(1) ? ?u (1)
?3,当u (1) ? ?1 * ? 2 J 3 ? min{2u (1) ? 1} ? ?1,当u (1) ? 0 u (1)?? ?3,当u (1) ? ?1 ?

应取

u *(1) ? 0, x *(1) ? 0, J 3 ? 1
*

*

B:取 u *(3) ? 0, x *(3) ? 1, J 1 ? 1

u *(2) ? 0, x *(2) ? 1, J 2 ? 2

*

可得

?3,当u (1) ? ?1 * ? 2 J 3 ? min{1 ? 2u (1) ? 2u (1) ? 2} ? ?3, 当u(1) ? 0 u (1)?? ?7,当u (1) ? ?1 ? 应取 * ?0,当u *(1) ? ?1 ??1 u (1) ? ? , x *(1) ? ? J 3 ?3 ?0 ?1,当u *(1) ? 0
C:取 u *(3) ? 0, x *(3) ? 1, J 1 ? 1
*
*

x(1) ? 1 ? u(1)

u *(2) ? ?1, x *(2) ? 0, J 2 ? 2

可得

?4,当u (1) ? ?1 * ? 2 J 3 ? min{2u (1) ? 2} ? ?2,当u (1) ? 0 u (1)?? ?4,当u (1) ? ?1 *? 应取 u *(1) ? 0, x *(1) ? 0, J 3 ? 2 (4)求 u *(0) x(1) ? x(0) ? u(0) * * J 4 ? min {x 2 (0) ? u 2 (0) ? J 3}
u (0)??

x(1) ? ?u (1)

u *(3) ? 1, x *(3) ? 0, J 1 ? 1
A:取

*

u *(2) ? 0, x *(2) ? 0, J 2 ? 1
u *(1) ? 0, x *(1) ? 0, J 3 ? 1
*

*

可得

?3,当u (0) ? ?1 * ? 2 J 4 ? min {2u (0) ? 1} ? ?1,当u (0) ? 0 u (0)?? ?3,当u (0) ? ?1 ? * 应取 u *(0) ? 0, x *(0) ? 0, J 4 ? 1
这一结果已经符合初态值的要求。

x(0) ? ?u(0)

u *(3) ? 0, x *(3) ? 1, J 1 ? 1
B:取

*

u *(2) ? 0, x *(2) ? 1, J 2 ? 2 u *(1) ? 1, x *(1) ? 0, J 3 ? 3 ?5,当u (0) ? ?1 x(0) ? ?u(0) * ? 2 J 4 ? min {2u (0) ? 3} ? ?3,当u (0) ? 0 u (0)?? ?5,当u (0) ? ?1 ?
*

*

可得

应取

u *(0) ? 0, x *(0) ? 0, J 4 ? 3 u *(3) ? 0, x *(3) ? 1, J 1 ? 1
*

*

这一结果也符合初态值的要求。

C:取

u *(2) ? 0, x *(2) ? 1, J 2 ? 2 u *(1) ? 0, x *(1) ? 1, J 3 ? 3
*

*

可得

?4,当u (0) ? ?1 * ? 2 J 4 ? min {1 ? 2u (0) ? 2u (0) ? 3} ? ?4, 当u (0) ? 0 u (0)?? ?8,当u (0) ? ?1 ? 由于取u *(0) ? 0 时,有 x *(0) ? 1 ,不符初态要求,故
应取

x(0) ? 1 ? u(0)

u *(0) ? 1, x *(0) ? 0, J 4 ? 4

*

u *(3) ? 0, x *(3) ? 1, J 1 ? 1 * D:取 u *(2) ? 1, x *(2) ? 0, J 2 ? 2 u *(1) ? 0, x *(1) ? 0, J 3 ? 2
可得
*

*

?4,当u (0) ? ?1 * ? 2 J 4 ? min {2u (0) ? 2} ? ?2,当u (0) ? 0 u (0)?? ?4,当u (0) ? ?1 应取 *? u *(0) ? 0, x *(0) ? 0, J 4 ? 2
这一结果也符合初态值的要求。 本步给出了满足已知初态值的4种可能解,比较知只有第 1种代价最小,故最优解为 * 最优控制序列:u *(k ) ? {0, 0, 0,1} 最优指标: J 4 ? 1 最优轨线序列: *(k ) ? {0, 0, 0, 0,1} x

x(0) ? ?u(0)

6.2.2 动态规划的数值计算方法

例 4-3

设一阶非线性离散系统的状态方程为

x(k ? 1) ? x(k ) ? [ x 2 (k ) ? u(k )]T , x(0) ? 3 u(k ) ? 2, x(k ) ? 5, ?k ? 0,1
J ? ? x (k ) ? u (k ) T
3 1

式中T=0.1。试求使J为极小的最优控制序列 {u *(0), u *(1)} , * 最优轨线序列 {x *(0), x *(1), x *(2)} 以及最优指标 J 分两步进行计算 A:最后一级数值计算。由于 J 0 [ x(2)] ? ?[ x(2)] ? 0 * 所以 3
*

k ?0

J 1[ x(1)] ? min{ x(1) ? u (1) T }
u (1) ? 2

在 x(1) 容许取值范围[-5,5]区间内,取11个数,间隔为1;在 u (1) 容许取值范围[-2,2]区间内,取5个数,间隔也是1。令 x(1) 为 取值范围内的某一固定值,遍取不同的容许 u (1) 值,可以算 * 得相应的 J 1[ x(1)] ;然后,列出 x(1) 为不同的容许值下,不同 * 的 u (1) 值的相应 J 1[ x(1)] 对于不同的 x(1) 值,有不同的 u *(1) 及相应的最优指标J 1[ x(1)] 至于具体哪个 u (0) 为最优控制,由给定的 x(0) 来确定。 B:倒数第二级数值计算。由状态方程知
*

x(1) ? x(0) ? [ x (0) ? u(0)]T
2
* u (0) ? 2

(6 ? 18)
*

因此

J 2 [ x(0)] ? min { x(0) ? u (0) T ? J 1[ x(1)]}
3

? min { x(0) ? u 3 (0) T ? J 1[ x(0)? ( x 2 (0) ? u(0))T ]}
u (0) ? 2

*

代入 x(0) ? 3得 J [ x(0)] ? min {3 ? u 3 (0) T ? J [3 ? (9 ? u (0))T ]} 2 1
* * u (0) ? 2

最后由式

x(2) ? x(1) ? [ x2 (1) ? u(1)]T

算得 x *(2) 本例的最优解为

{u *(0), u *(1)} ? {1,1} {x *(0), x *(1), x *(2)} ? {3,4,5.7}
J ? J 2 [ x(0)] ? 0.5
* *

6.3 连续动态规划 6.3.1 连续时间系统的最优控制问题 问题 6-3 设连续时间系统的状态方程为

? x(t ) ? f [ x(t ), u(t ), t ], x(t0 ) ? x0 式中 x(t ) ? Rn ; u(t ) ?? ? Rm ; f (?) ? R n 且连续可微。 目标约束集 ? [ x(t f ), t f ] ? 0 式中 ? (?) ? Rr , r ? n tf 性能指标 J [ x0 , t0 ] ? ?[ x(t f ), t f ] ? ? L[ x(t ), u (t ), t ]dt
t0

要求在容许控制域中,确定 u *(t ) ,使系统由已知初态转移 到要求的目标集,且使性能指标极小

6.3.2

哈密顿—雅可比方程

设 u[t , t f ] 表示在区间 [t , t f ] 上的控制函数,则最优性能指 标表示为 * tf
u[ t ,t f ]?? t

J [ x(t ), t ] ? min {?[ x(t f ), t f ] ? ? L[ x(? ), u(? ),? ]d? }

将 [t , t f ] 分为[t , t ? ?t ) 和 [t ? ?t , t f ] ,分别求 u *(t ) 根据最优原理上式可写为

J [ x(t ), t ] ? min { min [ ?
u[ t ,t ??t )?? u[ t ??t ,t f ]?? tf

*

t ??t

t

L[ x(? ), u(? ),? ]d? }

??

t ??t

L[ x(? ), u(? ),? ]d? ? ?[ x(t f ), t f ]}
t ??t

(6 ? 25)

根据最优性原理,上式可写为

J [ x(t ), t ] ? min {?
u [ t ,t ??t )??

*

t

L[ x(? ), u (? ),? ]d? ? J *[ x(t ? ?t ), t ? ?t ]} (6 ? 27)

L[ x(? ), u(? ),? ]d? ? L[ x(t ? ??t ), u(t ? ??t ), t ? ??t ]?t t (6 ? 28) 0 ? ? ?1 ?J *[ x(t ), t ] T dx(t ) J *[ x(t ? ?t ), t ? ?t ] ? J *[ x(t ), t ] ? [ ] ?t ?x(t ) dt ?J *[ x(t ), t ] ? ?t ? 0[(?t )2 ] (6 ? 29) ?t
将上面两式代入(6-27)得

?

t ??t

?J *[ x(t ), t ] ? ? min {L[ x(t ? ??t ), u (t ? ??t ), t ? ??t ] u [ t ,t ??t )?? ?t ?J *[ x(t ), t ] T 0[(?t )2 ] ?[ ] f [ x(t ), u(t ), t ] ? } ?x(t ) ?t 当 ?t ? 0 , 0(?t )2 是关于 ?t 的高阶无穷小 ?J * ?J * T ? ? min{L[ x(t ), u (t ), t ] ? ( ) f [ x(t ), u (t ), t ]} (6 ? 30) u ( t )?? ?t ?t

当控制向量 u (t ) 不受约束时,构造哈密顿函数

H ( x, u, ? , t ) ? L( x, u, t ) ? ? T (t ) f ( x, u, t ) * ?J ? (t ) ? ?x 令 ?H ?L ?f T ?J * ? ?( ) ?0 ?u ?u ?u ?x
式中
? ?L ? ? ?u ? ? 1 ? ? ?L ? ?L ? ? ? ?u2 ? ? ?u ?? ? ? ? ?L ? ? ? ?um ? ? ?

(6 ? 31) (6 ? 32) (6 ? 33)
?f 2 ?u1 ?f 2 ?u2 ? ?f 2 ?um ?f n ? ?u1 ? ? ?f n ? ?u2 ? ? ? ? ? ?f n ? ?um ? ?

? ?J * ? ? ?x ? ? 1? ? ?J * ? ? ?J * ? ? ? ?x2 ? ?x ?? ? ? ? * ? ?J ? ? ?x ? ? n? ? ?

? ?f1 ? ?u ? 1 ? ?f1 T ?f ? ? ?u2 ? ?u ? ? ? ? ?f1 ? ?um ?

? ? ? ?

解得

?J * u* ? u *[ x(t ), , t] ?x

(6 ? 34)

将上式代入(6-30)得

?J * ?J * ?J * T ?J * ? ?{L[ x(t ), u *( x(t ), , t ), t ] ? ( ) f [ x(t ), u *( x(t ), , t ), t ]} ?t ?x ?x ?x (6 ? 35)
令 t ? tf

J [ x(t f ), t f ] ? ?[ x(t f ), t f ]

上式对任意的 u (t ) 均成立,故必有

J *[ x(t f ), t f ] ? ?[ x(t f ), t f ], ?( x(t f ), t f ) ?? [ x(t f ), t f ] (6 ? 37)

6.3.3

连续动态规划的基本方程

(1) 最优解的充分条件

?J * ?J * T ? ? min{L( x, u, t ) ? ( ) f ( x, u, t )} ?t u (t )?? ?x
卡尔曼经过严格论证指出

(6 ? 38)

(2) 哈密顿-雅可比方程的解与最优性能指标的关系

? (A) 若 f ( x, u, t ) 、 [ x(t f ), t f ]及 L( x, u, t ) 连续可微,且哈密 顿-雅可比方程的解 J *[ x(t ), t ] 二次可微,则哈密顿-雅可 比方程的解是最优性能指标的必要且充分条件
(B) 由于哈密顿-雅可比方程的求解十分困难,且其解不一 定存在,所以一般来说,哈密顿-雅可比方程的解是最优 性能指标的充分而非必要条件

(C)对于线性二次型问题 ,哈密顿-雅可比方程的求解十分 简单,其解是最优性能指标的充分必要条件 (D) 若 f ( x, u, t ) 和 L( x, u, t ) 不满足连续可微条件,则在哈 密顿-雅可比方程的推导过程中, J *[ x(t ? ?t ), t ? ?t ] 不能展 成泰勒级数.此时哈密顿-雅可比方法不能用来求解连续系 统的最优化问题 (3) 最优解的求取步骤

?J * ?J * (6 ? 39) ? ? min H ( x, u, , t) ?t u (t )?? ?x (A) 求最优控制的隐式解。若 u (t ) 有约束,令 ?J * ?J * H ( x, u*, , t ) ? min H ( x, u, , t ) (6 ? 40) u ( t )?? ?x ?x 若 u (t ) 无约束,令

?H ?L ?f ?J * ? ? ?0 ?u ?u ?u ?x 2 2 T ? H ? L ? ?f ?J * ? 2? ( )?0 2 ?u ?u ?u ?u ?x 可以求得 ?J * u* ? u *( x, , t) ?x (B) 求最优性能指标。消去 u *(t )得 ?J * ?J * H *( x, , t ) ? H ( x, u*, , t) ?x ?x
T

(6 ? 41)

(6 ? 42)

于是, 最优解充分条件为如下一阶偏微分方程:

?J * ?J * ? H *( x, , t) ? 0 ?t ?x

(6 ? 43)

边界条件为:

J *[ x(t f ), t f ] ? ?[ x(t f ), t f ], ?( x(t f ), t f ) ?? [ x(t f ), t f ]
由(6-43)和式(6-44)解出最优性能指标 J *[ x(t ), t ]

(6 ? 44)

(C) 求最优控制显式解。将求得的 J *[ x(t ), t ]代入式(6-42), 可得最优控制的显式解 u *[ x(t ), t ] (D) 求最优轨线。将求得的 u *[ x(t ), t ] 代入系统状态方程式 (6-21), 其解为闭环系统最优轨线 x *(t ) ,而 u *[ x(t ), t ] 则实 现了闭环反馈控制。

例 6-4 设线性定常系统

? x(t ) ? Ax(t ) ? B(u), x(0) ? x0
性能指标
?0 A?? ?0 1? 0? ?

1 ? T J ? ? [x (t )Qx(t ) ? ru 2 (t )]dt 2 0
?0 ? ?1 ? ?2 b ? ? ? x(0) ? ? ? Q ? ? ?1 ? ?0? ?0 0? 0? ?

r?

1 2

试求最优控制 u *(t )最优轨线 x *(t ) 最优指标 J * 解:本例可利用连续动态规划法求解。令

?J * 1 T 1 2 ?J * T ?J * T H ( x, u , ) ? x Qx ? ru ? ( ) Ax ? ( ) bu ?x 2 2 ?x ?x
(A)求隐式解

?H T ?J * ? ru ? b ?0 ?u ?x



?J * ?1 T ?J * u *( x, ) ? ?r b ?x ?x

?2 H ?r ?0 2 ?u ?J * 故求得的 u *( x, ) 可使H极小 ?x ?J * ) 代入 H,有 (B)求 J *[ x(t )] 。将求得的 u *( x, ?x ?J * 1 T ?J * T 1 ?J * T T ?J * ?1 H *( x, ) ? x Qx ? ( ) Ax ? ( ) bb r ?x 2 ?x 2 ?x ?x
因为 由于被控系统是线性定常的,故设

1 T J *[ x(t )] ? x (t ) Px(t ) 2 * 有 ?J 1 T ? ? x (t ) P x(t ) ? 0 ?t 2
将上式代入(6-43)得雅可比方程为

1 T ?J * T 1 ?1 ?J * T 2 x Qx ? ( ) Ax ? r [( ) b] ? 0 2 ?x 2 ?x ?J * 在上式中代入 ? Px(t ) ?x
可得 1

2

x (t )[Q ? PA ? A P ? Pbr b P]x(t ) ? 0
T T

?1 T

该式对所有的非零 x(t ) 均成立,故确定 J *[ x(t )] 的问题, 转化为求下列黎卡提矩阵代数方程的解: 令

PA ? A P ? Pbr b P ? Q ? 0 ? p11 p12 ? 代入相应的A,b,Q及r求得 P?? ? ? 2 1? ? p12 p22 ? P?? ??0 ?1 1?
T

?1 T

于是,最优性能指标

1 T 1 2 2 J *[ x(t )] ? x (t ) Px(t ) ? x1 (t ) ? x1 (t ) x2 (t ) ? x2 (t ) 2 2 令 t ? t0 代入初始条件求得

J *[ x(0)] ? 1 (C)求 u *(t ) 显式解。 * ?1 T ?J ?1 T u *(t ) ? ?r b ? ?r b Px(t ) ? ?2 x1 (t ) ? 2 x2 (t ) ?x

? x(t ) ? ( A ? br ?1bT P) x(t ) ? Ax(t ), x(0) ? x0 ?0 1? ?1 T A ? A ? br b P ? ? ? ? ?2 ?2?

求得闭环系统的状态转移矩阵为
?t ?e?t (cos t ? sin t ) ? e sin t At ?1 ?1 e ? L [(SI ? A) ] ? ? ? ?t ?t e (cos t ? sin t ) ? ? ?2e sin t

?e?t (cos t ? sin t ) ? x* (t ) ? e At x(0) ? ? ? ?t ? ?2e sin t ?

u* (t ) ? ?2e?t (cos t ? sin t )

6.4 动态规划与极小值原理和变分法
6.4.1 动态规划与变分法 变分法的基本问题是确定最优轨线 x* (t ) ,使泛函
J?

?

tf

? L( x, x, t )dt

t0

6-46

取极小值。式中t f及 t 0固定,(t )是连续可微的标量函数。 x 若令
? x(t ) ? u(t )

6-47

将上式代入(6-46),则变分问题转化为:对于系统 (6-47),要求最优控制 u * (t ),使性能指标
J?

?

tf

L( x, u, t )dt

6-48

t0

取极小值。其中 u (t )不受约束。

此时,变分法的所有结果都可由动态规划法导出。 下面分三种情况讨论。 (1)两端固定情况 当两端固定时,系统方程(6-47)的边界条件为

x(t0 ) ? x0 ,

x(t f ) ? x f

假定连续动态规划的全部条件成立,则哈密顿- 雅比方程为

?J ?J ? ? min{L( x, u, t ) ? u} u (t ) ?t ?x
* *

或写为

?J * ?J * min{L( x, u, t ) ? u? }? 0 u (t ) ?x ?t ?J * H ? L ( x, u , t ) ? u ?x

6-49

令哈密顿函数 6-50

则式(6-49)可写为

?J min{H ? }? 0 u (t ) ?t
*

6-51

因为 u (t ) 无约束,故令

?H ?L ?J * ? ? ?0 ?u ?u ?x
解得

6-52

?J * ?L ?? ?x ?u
取式(6-52)对 t 的偏导数,有

6-53

?2L ?2 J * ? ?0 ?t?u ?t?x

6-54

解得

?2 J * ?2L ?? ?t?x ?t?u

6-54

将从式(6-52)中解出的 u 代入式(6-49),自然有

?J * ?J * L ( x, u , t ) ? u? ?0 ?x ?t
上式对 x 求偏导数,得

?L ? ?J * ?2 J * ? ( u) ? ?0 ?x ?x ?x ?x?t

6-55

? 将式(6-53)和(6-54)代入式(6-55 ) ,且令 u ? x 得 2
?L ? ?L ? L ? ? ( x) ? ?0 ? ? ?x ?x ?x ?t?x d ?L ? 2 L ?2L ? ? x? ? ? ? dt ?x ?x?x ?t?x
6-56

考虑到

式(6-56)可写为

?L d ?L ? ?0 ? ?x dt ?x
上式为欧拉方程,代表的是必要条件。

6-57

在连续动态规划中,式(6-51)有极小值的另一条件是

? H ?0 2 ?u
2

6-58

将式(6-50)和(6-47)代入式(6-58 ) ,求 得

?2L ?0 2 ? ?x

6-59

上式为勒让德条件,也是泛函(6-46)取极小值德 必要条件。 由已知初态和末态条件求解欧拉方程(6-57)所 需的两点边值条件。

(2)自由起点情况 当起点自由时,由变分法得到的横截条件为

? ?L ? ? ? ?0 ? ? ?x ? t0
*

6-60
*

因起点自由,故最优轨线 x (t ) 的初始值 x0 必对 应最优性能指标 J *[ x(t ), t ] 在 t ? t0 时的极小值点, 自然应有 ? ?J * ? 6-61 ? ? ?0

? ?x ? ? ? ? t0

将式(6-53)和(6-47)代入式(6-61 ) ,立即得 到式(6-60 ) 。

(3)自由终点情况 当终点自由时,由变分法得到的横截条件为

? ?L ? ? ? ?0 ? ? ?x ? t f
由连续动态规划法知,此时应有

6-62

? ?J * ? ? (t f ) ? ? ? ?x ? ? 0 ? ? ? tf
代入式(6-53)和(6-47)立即得到式(6-62) 。

6.4.2 极小值原理与变分法
当起点固定, (t0 ) ? x0 时,使泛函数(6-46) x 取极值的必要条件使欧拉方程(6-57)成立。 根据极小值原理,构造哈密顿函数

H ? L( x, u, t ) ? ? (t )u (t )
由正则方程

? (t ) ? ?H ? ? ?L ? ?x ?x ?H ?L ? ?? ?0 ?u ?u

6-63

因 u (t ) 无约束,故极值条件为

解得 上式对 t 求导,有

?L ? (t ) ? ? ?u ? (t ) ? ? d ?L ? dt ?u ?L d ?L ? ?0 ?x dt ?u
6-64

比较式(6-63)和(6-64),得

? 因为 u ? x ,故欧拉方程为
?L d ?L ? ?0 ? ?x dt ?x

6.4.3 动态规划与极小值原理 已知系统状态方程

? x(t ) ? f [ x(t ), u (t ), t ],

x(t0 ) ? x0

6-65

x(t ) ? R , u(t ) ? R
n

m

。要求确定最优控制 u * (t ) ? ?

使性能指标

J ? ?[ x(t f ), t f ] ? ? L( x, u, t )dt
t0

tf

t 取极小值。其中 x(t f ) 自由, f 或固定,或自由。

(1)末端时刻固定情况
当 t f固定时,上述问题是时变系统、复合型性 能指标、 f 固定和末端自由的最优控制问题。 t 根据极小值原理,上述问题的最优解应满足如 下必要条件: 由正则方程 式中哈密顿函数

?H ? ?H ? x(t ) ? , ? (t ) ? ? ?? ?x

H ( x, u, ? , t ) ? L( x, u, t ) ? ?T (t ) f ( x, u, t )

边界条件为

x(t0 ) ? x0 ,
极小值条件为

? (t f ) ?

??[ x(t f ), t f ] ?x(t f )

H * ( x, ? , u* , t ) ? min H ( x, ? , u, t )
u??

假定最优性能指标 J *[ x(t ), t ] 存在,且连续可微。 根据连续动态规划法,哈密顿-雅可比方程为如下一 阶偏微分方程:

? ?J * ? ?J * ? H ? x, ,t ? ? 0 ? ?u ? ?t ? ?
*

6-67

其边界条件为

J *[ x(t f ), t f ] ? ?[ x(t f ), t f ]
式中

6-68



? ?J * ? ?J * H * ? x, ? ?u , t ? ? min H ( x, u, ?x , t ) ? u?? ? ?
* * T *

6-69

? ? ?J ?J ? H ? x, u , , t ? ? L ( x, u , t ) ? ? ? ? ?x ?x ? ? ? ?
若 必有

? ? f ( x, u , t ) ? ? 6-70
6-71

? (t ) ? ?J [ x, t ] ? ?x ?H ? x(t ) ? ? f ( x, u , t ) ??
*

6-72

H * x, ? , u* , t ? min H ( x, ? , u, t )
u??

?

?

6-73

式(6-73)表明,在保持 x, ? , t 不变的条件下,选 择 u (t ) ? ? ,使 H 取全局极小值,这就是极小值原 理中的极小值条件。式 (6-74)显然为状态方程。 将式(6-71)对 t 取全导数,有

? ?J * ( x, t ) ? ? 2 J * ( x, t ) ? 2 J * ( x, t ) ? (t ) ? d ? ? ? x ? ?? T dt ? ?x ? ?t?x ?x?x ? ?J * ( x, t ) ? ? 2 J * ( x, t ) ? ? ? f ( x, u , t ) ?? T ?x ? ?t ? ?x?x

将式(6-67)、式(6-49)和式(6-70)代入上式,得
* T ? ? ?2J * ? ?J ? ? ? ? f ( x, u * , t ) ? ? 2 f ( x, u , t ) ? (t ) ? ? ? L( x, u * , t ) ? ? ? ?x ? ?x ? ? ?x ? ? ? ? ?L( x, u * , t ) ? 2 J * ( x, t ) ?? ? f ( x, u * , t ) ?x ?x 2

? ?J * ( x, t ) ? ? ?f T ( x, u * , t ) ? ? 2 J * ( x, t ) ?? f ( x, u , t ) ?? ?? 2 ?x ?x ? ?x ? ? ?

u (t ) ? u * (t ) 因为已设 J *[ x(t ), t ]存在且连续可微,故有 ?J * 且已令 ? (t ) ? ,于是上式可写为 ?x ? (t ) ? ? ? ?L( x, u, t ) ? ?T f ( x, u, t )? ? ? ?H ( x, ? , u, t ) ? 6-74
?x 这就是协态方程。 ?x
由边界条件(6-68),并考虑到式(6-71),得 ?? x(t f ), t f ? ?J * ( x, t ) ? ? (t f ) ? ? ? ? 6-75 ?x ? t ?t ?x(t f ) ? f 这就是横截条件。

?

?

在假定 J *[ x(t ), t ] 存在且连续可微得条件下,由哈密 顿-雅可比方程(6-67) 及其边界条件(6-68),导 出了极小值原理给出的全部必要条件。

(2)末端时刻自由情况 由极小值原理知,对于所讨论的问题,在最优解 应满足的必要条件中,除与 t f 固定时相同的必要条 件外,还有一个必要条件是变化律 H 应为 6-76 ?t f 在连续动态规划中,取边界条件(6-68)对 t f 的 偏导数,得 ?? x(t f ), t f ?J * ?? 6-77 ?t f ?t f

H x(t f ), ? (t f ), u (t f ), t f ? ?
* * * * * *

?

?

?? x(t f ), t f
*

?

*

?

?

?

令 t ? t f * ,并利用式(6-67)和(6-71),立即 得到式(6-76)。

当 t f 自由时,前面导出得式(6-72)、式(6-73)、 式(6-74)以及式(6-75)仍然成立。 以上推证只有形式上的意义,不能认为是极小值 的严格证明。实际上,除了线性二次型问题外,哈密 顿-雅可比方程难以求解,或者根本不存在二次连续 可微的函数 J *[ x(t ), t ] 。


赞助商链接
相关文章:
动态规划与搜索
动态规划与搜索_工作范文_实用文档。动态规划与搜索 动态规划与搜索——动态规划是高效率、高消费算法 同样是解决最优化问题,有的题目我们采用动态规划,而有的题目...
动态规划入门(论文)
动态规划思想入门作者:陈喻(2008 年 10 月 7 日)关键字:动态规划,最优子结构,记忆化搜索 引言 动态规划 (dynamic programming) 是运筹学的一个分支,是求解...
数学模型动态规划
动态规划动态规划(dynamic programming)是运筹学的一个重要分支,它是解决多 阶段决策问题的一种有效的数量化方法.动态规划是由美国学者贝尔曼 (R.Bellman)等人所创立...
动态规划习题
动态规划习题_理学_高等教育_教育专区。数学模型 第七章 动态规划 规划问题的最终目的就是确定各决策变量的取值, 以使目标函数达到极大或极小。 在线 性规划和非...
动态规划(DP)的使用条件
,但从空间复杂度来看,动态规划算法为 O(n2),而搜索 算法为 O(n),搜索算法反而优于动态规划算法。选择动态规划算法是因 为动态规划算法在空间上可以承受,而搜索...
动态规划的技巧——阶段的划分和状态的表示
动态规划的技巧——阶段的划分和状态的表示在动态规划的设计过程中, 阶段的划分和状态的表示是非常重要的两步, 这两步会直接影响该问题的计算复杂性, 有时候阶段...
动态规划与静态规划的关系
动态规划与静态规划的关系 动态规划与静态规划(线性和非线性规划等)研究的对象本质上都是在若 干约束条件下的函数极值问题。 两种规划在很多情况下原则上可以相互 ...
动态规划习题答案
动态规划习题答案_工学_高等教育_教育专区。由复旦大学出版社出版,傅家良主编的运筹学方法与模型第八章动态规划习题答案2.某公司有资金 4 百万元向 A,B 和 C3 ...
动态规划与网络流
动态规划与网络流——动态规划是易设计易实现的算法 由于图的关系复杂而无序,一般难以呈现阶段特征(除了特殊的图如多 段图--参见例一),因此动态规划在图论中的应...
动态规划例1 求解下列整数规划的最优解
动态规划例1 求解下列整数规划的最优解_研究生入学考试_高等教育_教育专区。天大,考研,运筹学,管理科学与工程例1 求解下列整数规划的最优解: max Z ? 4 x1 ...
更多相关标签: