文档介绍：第三章:动态规划
动态规划的基本概念
一、动态决策问题:
决策过程具有阶段性和时序性(与时间有关)的决策问题。即决策过程可划分为明显的阶段。
二、什么叫动态规划(.– Dynamic Program):
多阶段决策问题最优化的一种方法。
广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。
三、动态规划(.)的起源:
1951年,(美),从而建立动态规划,名著《动态规划》
于1957年出版。
四、动态决策问题分类:
1、按数据给出的形式分为:
离散型动态决策问题。
连续型动态决策问题。
2、按决策过程演变的性质分为:
确定型动态决策问题。
随机型动态决策问题。
五、名词术语
A
B1
B2
B3
C1
C2
C3
D1
D2
D3
E1
E2
F
3
5
4
9
5
4
3
5
1
7
1
5
8
4
6
4
4
2
2
2
6
9
7
5
1
4
1、阶段(stage)n: 作出决策的若干轮次。n = 1、2、3、4、5。
2、状态(state)Sn:每一阶段的出发位置。构成状态集,记为Sn
S1={A},S2={B1,B2,B3},S3={C1,C2,C3},S4={D1,D2,D3},
S5={E1,E2}。阶段的起点。
3、决策(decision)Xn:从一个阶段某状态演变到下一个阶段某状
态的选择。
构成决策集,记为Dn(Sn)。
阶段的终点。
D1(S1)={X1(A)}={B1,B2,B3}= S2,
D2(S2)={X2(B1),X2(B2),X2(B3)}={C1,C2,C3}=S3,
D3(S3)={X3(C1),X3(C2),X3(C3)}={D1,D2,D3}=S4,
D4(S4)={X4(D1),X4(D2),X4(D3)}={E1,E2}=S5
D5(S5)={X5(E1),X5(E2)}={F;F}={F}。
A
B1
B2
B3
C1
C2
C3
D1
D2
D3
E1
E2
F
3
5
4
9
5
4
3
5
1
7
1
5
8
4
6
4
4
2
2
2
6
9
7
5
1
4
A
B1
B2
B3
C1
C2
C3
D1
D2
D3
E1
E2
F
3
5
4
9
5
4
3
5
1
7
1
5
8
4
6
4
4
2
2
2
6
9
7
5
1
4
4、策略(policy):全过程中各个阶段的决策Xn组成的有序总体{Xn}。
如 A B2 C1 D1 E2 F
5、子策略(sub-policy) :剩下的n个阶段构成n子过程,相应的决策系列叫n子策略。
如 C1 D1 E2 F
上例从 A F 共有38种走法,即有38条路线,38个策略。
6、状态转移方程:前一阶段的终点(决策)是后前一阶段的起点
(状态)。
Xn = Sn+1
7、指标函数:各个阶段的数量指标,记为rn(sn,xn)。
如上例中,用dn(sn,xn)表示距离。 d2(B3,C2)=1, d3(C2,D3)=6 等。
8、目标函数:策略的数量指标值,记为
Z=opt[r1(s1,x1)** rn(sn,xn)]。其中:opt为max或min,
*为运算符号。
如上例中 Z=min[d1(s1,x1)+ +dn(sn,xn)]=min[d1+d2+…+ dn]
A
B1
B2
B3
C1
C2
C3
D1
D2
D3
E1
E2
F
3
5
4
9
5
4
3
5
1
7
1
5
8
4
6
4
4
2
2
2
6
9
7
5
1
4
最优化原理
一、:
作为整个过程的最优策略,无任过去的状态和决策如何,对前面的决策形成状态而言, 余下的诸决策必构成最优策略。
即:若M是从A到B最优路线上的任一点,则从M到B的路线也是最优路线。
A
M
B
二、指标递推方程:
fn*(Sn) = opt [r1(s1,x1)** rn(sn,xn)]
xn∈Dn(Sn)
如上例:
fn*(Sn) = min [rn(sn,xn)+ fn+1*(Sn+1) ], n=4、3、2、1
xn∈Dn(Sn)
f5*(S5) = min [r5(s5,x5)]
x5∈