多阶段决策过程图示
决策 决策
决策
第第
第
1
2
n
阶阶
阶
段段
段
动态规划的基本概念
C1 5
2
8 D1 3
4
A
B1 3
4
6
C2
5
58
3
5 6 D2 2
E1 4 3
F
B2 7 C3 4
1
E2
7
8
D3 3
C4 4
1
2
3
4
5
阶段: k=1,2,3,4,5
基本概念（续一）
C1 5
2
8 D1 3
B1 3
4
4
A
6
C2
第七章 动态规划
动态规划简介
多阶段决策过程最优化
多阶段决策过程，是指一类特殊的过程， 它们可以按时间顺序分解成若干个相互联 系的阶段，称为“时段”，在每个时段都 要做决策，全部过程的决策是一个决策序 列。多阶段决策问题也称为序贯决策问题。 多阶段决策问题的目标是要达到整个活动 过程的总体最优。在每个阶段进行决策时 不应仅考虑本阶段最优，尤其应考虑对最 终目标的影响，从而做出对全局来说最优 的决策。 动态规划是符合这种要求的一种决策方法。
C1 5
2
8 D1 3
4
A
B1 3
4
6
C2
5
58
3
5 6
D2
2
E1 4 3
F
B2 7 C3 4
1
E2
7
8
D3 3
C4 4
第二步，k=4，状态变量s4可以取三个值D1，D2，D3。于是
f
4
(
D1
)

mindd
( (
D1 D1
, ,
E1) E2 )
ff55((EE12))

min53

4 3

7
f
4
(
D2
)

mindd
( (
D2 D2
, ,
E1) E2 )
ff55((EE12))

min62

4 3

5
f
4
(
D3
)

mindd
(D3 (D3
, ,
E1) E2 )
ff55((EE12))

min1343
ff33((CC12))

min32
1102

13
d (B1, C3 ) f3 (C3 )
6 8
f2 (B2 )

min
dd
( (
B2 B2
, ,
C2 C3
) )

f3 f3
((CC32))

min87 180
15
(C2 (C2
, ,
D1) D2 )
ff44((DD12))

min54

7
5


10
f3 (C3 )

mindd
(C3 (C3
, ,
D2 ) D3 )
f4 f4
(D2 (D3
)
)


min34

5 5

8
f3 (C4 )

mindd
d (B2 , C4 ) f3 (C4 )
表示决策的变量称为决策变量，uk(sk)就表示 第k阶段当状态为sk时的决策变量。 决策变量的取值常常限制在一定的范围内，这 一范围称为允许决策集合，常用记号Dk(sk)表 示第k阶段状态为sk时的允许状态集合。
基本概念（续三）
各阶段的决策确定后，整个过程各阶段的决策 就构成一个决策序列，称为策略，用p1,n{u1(s1), u2(s2), …, un(sn)}表示。 此外还常常需要考虑后部子策略pk,n{uk(sk), …, un(sn)}。 动态规划要求的就是使整个问题达到最优的策 略。
最短路线问题的解
C1 5
2
8 D1 3
4
A
B1 3
4
6
C2
5
58
3
5 6 D2 2
B2 7 C3 4
1
7
8
D3 3
C4 4
E1 4
F
3
E2
动态规划最通常的 解法，就是逆序递 推的方式求解。
第一步，从k=5开始，状态变量s5可以取两种状态 E1，E2，从它们到终点F的距离分别为4，3。即
f5(E1)=4, f5(E2)=3
fk (sk ) Vk,n (sk , pk*,n ) optVk,n (sk , pk,n )
pk ,n
特别地，f1(s1)就是从初始状态s1到全过程结 束的整体最优函数。
对最短路线问题阶段指标函数就是两点间 的距离。后部子过程pk,n的指标函数Vk,n(sk, pk,n)就是在第k阶段位于点sk时到终点的距离， 而fk(sk)就是到终点的最短距离。 最短路线问题，就是要求f1(A)以及相应的 路线。
基本概念（续四）
状态转移方程：动态规划中一个阶段的状态 常常是上一阶段的状态和决策的结果。如果 给定了第k阶段的状态sk，和第k阶段的决策 uk(sk)，则第k+1阶段的状态sk+1也就完全确 定了，这一关系可用下面的方程表示
sk+1=Tk(sk, uk) 称之为状态转移方程，它表示了由第k阶段 到第k+1阶段状态转移的规律
(C4 (C4
, ,
D2 D3
) )

f4 f4
((DD32))

min84

5 5

9
k=2
C1 5
2
8 D1 3
B1 3
4
4
A
6
C2
5
58
3
B2 7 C3 4
5
D2
6 2
1
E1 4 E2 3
F
7
8
D3 3
C4 4
f
2
( B1 )

mindd
(B1, (B1,
C1) C2)
基本概念（续五）
指标函数：用于衡量决策或策略优劣的数量指标称为 指标函数。
阶段指标函数：它通常是指在第k阶段，从状态sk出 发，采用决策uk时的效益，记为d(sk, uk)。 过程指标函数：它通常表示在第k阶段时的状态为sk 时，采用后部子策略pk,n的效益值，记为Vk,n(sk, pk,n)。 最优指标函数记为fk(sk)，表示第k阶段的状态为sk时， 采用了最优后部子策略p*k,n的指标函数值， Vk,n(sk, pk,n)与fk(sk)的关系是

5
k=3
C1 5
2
8 D1 3
B1 3 4
4
A
6
C2
5
58
3
B2 7 C3 4
5
D2
6 2
1
E1 4 E2 3
F
7
8
D3 3
C4 4
f3
(C1) D2 )
ff44((DD12))

min85

7
5


12
f3
(C2
)

mindd
5
58
3
5 6 D2 2
E1 4 3
F
B2 7 C3 4
1
E2
7
8
D3 3
C4 4
状态：各阶段开始时的客观条件。表示状态的变
量称为状态变量，常用sk表示第k阶段的状态变量， 第k阶段所有状态变量的集合记为Sk。动态规划考 虑的状态应该具有“无后效性”
基本概念（续二）
决策：当一个阶段的状态取定了后，就可以作 出不同决定（或选择），从而确定下一阶段的 状态，这种决定称为决策。