文档介绍：第五章动态规划
§1 多阶段决策过程及实例
§2 动态规划的基本概念和基本方程
§3 动态规划的最优性原理和最优性定理
§4 动态规划与静态规划的关系
§1 多阶段决策过程及实例
在实际中,有一类问题可以看作是一活动的
过程,由于它的特殊性,可将过程分为若干个相
互联系阶段,在每个阶段都要依据该阶段所处的
状态作出相应的决策,该决策又引起该阶段状态
的转移,决定了下一阶段的状态,当每个阶段的
决策确定后,由这些决策组成一个决策序列,即
整个过程的一条活动路线。这类活动过程称为多
阶段决策过程。这类问题称为多阶段决策问题。
1
2
n
状态
状态
状态
……
状态
状态
决策
决策
决策
例1 最短路线问题
如下图,是一线路网络,两点之间连线上的数字表示两点之间的距离(或费用)试求一条由A到G的铺管线路,使总距离为最短(或总费用最小)。
1
状态
状态
状态
状态
状态
决策
决策
决策
2
3
4
5
6
状态
状态
决策
决策
决策
B2
C3
D2
E3
F2
G
B2
C3
D2
E3
F2
G
A
V6,6=3
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
3
3
3
5
5
2
6
6
4
3
2
V1,6=24
V5,6=9
V4,6=11
V3,6=14
V2,6=21
V1,6=24
例2 机器负荷分配问题
某种机器可以在高低两种不同负荷下进行生产。
在高负荷下进行生产时,产品的年产量g和投入生产的机器数u的关系为
在低负荷下进行生产时,产品的年产量h和投入生产的机器数u的关系为
1
状态
状态
状态
状态
状态
决策
决策
决策
2
3
4
5
状态
决策
决策
u1
u2
u3
u4
u5
s2
s3
s4
s5
s6
s1
设:
§2 动态规划的基本概念和基本方程
动态规划的基本概念
1. 阶段
把过程依据一定的时间和空间特征恰当地划分为若干个相互联系的阶段,以便利用动态规划的方法求解。
描述阶段的变量称为阶段变量,用k表示。k=1,2,…,n
2. 状态
每个阶段开始所处的自然状况或客观条件,称为状态。状态是不可控的,是客观存在的。
描述状态的变量称为状态变量,用sk表示。状态变量可以是一个数或一个向量。状态变量sk的取值范围称为可达状态集合,用Sk表示。例1中,S3={C1,C2,C3,C4}。
状态变量的性质(无后效性)
如果某阶段的状态给定后,则该阶段以后的过程的发展不受该阶段以前各阶段状态的影响。即过程的过去历史只能通过当前的状态去影响未来的发展,当前的状态是以往历史的总结,以后发展的依据。这个性质称为无后效性(即马尔科夫性)。
无后效性的特征:在每个阶段所作的决策只依据当前的状态,和以往的状态无关。
在选取状态变量时,一定要保证状态变量具有无后效性,否则不能利用动态规划的方法求解。
3. 决策
在每个阶段所作的决定或选择称为决策或控制。决策依据与当前状态,又决定下一阶段的状态。
描述决策的变量称为决策变量,用uk(sk)表示。他是状态变量sk的函数。决策变量的取值范围称为容许决策集合,用Dk(sk)表示。
在例1中
D1(A)={B1,B2}
D2(B1)={C1,C2,C3},D2(B2)={C2,C3 ,C4}
D4(D1)={E2,E3}
在例2中
D1(s1)={u1(s1) | 0≤{u1(s1)≤s1}
D2(s2)={u2(s2) | 0≤{u2(s2)≤ s2}
Dk(sk)={uk(sk) | 0≤{uk(sk)≤ sk}
4. 策略
按一定顺序排列的决策序列集合称为策略。
由过程的第k阶段开始到终止状态为止的过程,称为问题的后部子过程(或称为k子过程)。
由k子过程的每个阶段的决策函数组成的决策函数序列集合{uk(sk), uk+1(sk+1),…, un(sn)}称为k子过程策略,简称为子策略,记为pk,n(sk),即
pk,n(sk)= {uk(sk), uk+1(sk+1),…, un(sn)}
当k=1时,此决策函数序列称为全过程的一个策略,
简称为策略,记为p1,n(s1)。即
p1,n(sk)= {u1(s1), u2(s2),…, un(sn)}
策略的取值范围称为容许策略集合,用P表示。
在P中,使指