文档介绍：动态规划
1
动态规划 Dynamic programming
五十年代贝尔曼(B. E. Bellman)为代表的研究成果
属于现代控制理论的一部分
以长远利益为目标的一系列决策
最优化原理,可归结为一个递推公式
2
第一节多阶段决策过程及实例
一、多阶段决策过程
在生产和科学试验中,有一类活动的过程,由于它的特殊性,
可将过程分为若干个互相联系的阶段,在它的每一个阶段都需要
作出决策,从而使整个过程达到最好的活动效果。因此,各个阶
段的选取不是任意的,它依赖于当前面临的状态,又影响以后的
发展。当各个阶段的决策确定后,就组成了一个决策序列,因而
也就决定了整个过程的一条活动路线。这种可以把一个问题看作
是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,也称序贯决策过程。这种问题就称为多阶段决策问题。
状态
1
2
……
n
状态
状态
状态
状态
决策
决策
决策
3
在多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前的状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义。因此,把处理它的方法称为动态规划方法。但是,一些与时间没有关系的静态规划问题,只要人为的引进“时间”因素,也可把它视为多阶段决策问题,用动态规划方法去处理。
4
二、实例:
例1 如下图,给定一个线路网络,两点之间连线上的数字表示两点间的距离(或费用),试求一条由A到G的铺管线路,使总距离为最短(或总费用最小)。
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
E3
F1
F2
G
5
3
1
3
6
8
7
6
6
8
3
5
3
3
8
4
2
2
1
2
3
3
3
5
5
2
6
6
4
3
5
解:
k=6 f6(F1)=4 f6(F2)=3
k=5 f5(E1)=min d(E1,F1) + f6(F1) =min{3+4,5+3}=7
d(E1,F2) + f6(F2) , u5(E1)=F1
f5(E2)=min d(E2,F1) + f6(F1) =min{5+4,2+3}=5
d(E2,F2) + f6(F2) , u5(E1)=F2
f5(E3)=min d(E3,F1) + f6(F1) =min{6+4,6+3}=9
d(E3,F2) + f6(F2) , u5(E1)=F2
k=4 f4(D1)=7 u4(D1)=E2
f4(D2)=6 u4(D2)=E2
f4(D3)=8 u4(D3)=E2
6
k=3 f3(C1)=13 u3(C1)=D1
f3(C2)=10 u3(C2)=D1
f3(C3)=9 u3(C3)=D2
f3(C4)=12 u3(C4)=D3
k=1 f5(E1)=min d(A,B1) + f2(B1)
d(A,B2) + f2(B2)
=min{5+13,3+16}=18, u1(A)=B1
k=2 f2(B1)=13 u2(B1)=C2
f2(B2)=16 u3(B2)=C3
7
一、动态规划的基本概念
1、阶段(k=1、2、3、4、5、6)
2、状态(无后效性)
3、决策 u(A)=B1
4、策略 P1n(S1)={U1(S1), U2(S2),…, Un(Sn)}
子策略 Pk,n(Sk)={Uk(Sk), Uk+1(Sk+1),…, Un(Sn)}
第二节动态规划的基本概念和基本方程
5、状态转移方程:Sk+1=uk(Sk)
8
二、动态规划的基本方程
由例1可以看出,在求解的各个阶段,我们利用了k阶段与k+1阶段之间的递推关系:
fk(Sk)=min{dk(Sk,uk(Sk))+fk+1(uk(Sk))},k=6,5,4,3,2,1
f7(S7)=0
一般情况下, k阶段与k+1阶段之间的递推关系可写为:
fk(Sk)=opt{vk(Sk,uk(Sk))+fk+1(uk(Sk))}, k=n,n-1,…,1
边界条件为:
fn+1(Sn+1)=0
9
一、思想
作为整个过程的最优策略具有这样的性质:即
无论过去的状态和决策如何,对前面的状态所形
成的决策而言,余下的诸决策必需构成最优策略。
简而言之,一个最优策略的子策略总是最优的。
第三节动态规划的最优性原理和最优性定理
注意:最优性原理不是对任何决策过程都普遍成立的。而
且,最优性原理与动态规划基本方程并不是无条件等价的,
两者之间也不存在确定的蕴含关系。反映动态规划基本方程
的是最优性定理,它是策略最优性的充要条件,而最优性原