动态规划之基本概念和术语
动态规划
引言
1951年，美国数学家贝尔曼（R.Bellman）等根据一类所谓多阶段决策问题的特性，提出了解决这类问题的“最优化原理”，并研究了许多实际问题，从而创立了最优化的一个新分支----动态规划。
动态规划没有统一的数学模型，对不同的问题要采用不同的方法去建立它们的模型。有了模型之后，要想得到数值解，仍然没有统一的处理方法。这是应当注意的。
1 动态规划原理
1.1 最短路问题及其解法
1.2 动态规划的基本概念和术语
1.2.1 多阶段决策问题
如果一个问题的整个过程可以分成若干个互相联系的阶段，每个阶段都需要作出决策，而当每个阶段的决策都确定之后，整个过程就确定了，那么这个问题就叫做多阶段决策问题。动态规划就是解决这类问题的一种重要方法。
一个问题是不是多阶段决策 问题是需要判断的，而这种判断并没有一般规律可循，只能靠经验和技巧。
1.2.2 阶段变量
描述多阶段决策问题阶段数的变量叫阶段变量，记作 k ( k = 1 , 2 , ⋯ ) k(k=1,2,\cdots) k(k=1,2,⋯)。如果阶段变量是确定的、有限的，而且在决策前就知道其数值，则称此问题为定期问题。如果阶段变量虽然是确定的、有限的，但在决策之前并不知道它的数值，则称此问题为不定期问题。
1.2.3 状态变量
对于多阶段决策问题，每一阶段的起始“位置”叫状态，它既是该阶段的某一起点，也是前一阶段的终点。不同问题其状态的含义是不同的。
描述过程状态的变量叫状态变量，用
x
k
x_k
xk表示第
k
k
k阶段的某一状态。
1.2.4 决策变量
将过程由一个状态变到另一个状态的决定或选择叫做决策。描述决策的变量叫决策变量，用 u k ( x k ) u_k(x_k) uk(xk)表示从第 k k k阶段的状态 x k x_k xk处所采取的决策。在第 k k k阶段的状态 x k x_k xk处的所有决策构成的集合叫做决策集合，记作 D k ( x k ) D_k(x_k) Dk(xk)。
1.2.5 整体策略
对于
n
n
n阶段决策问题，当每个阶段的决策都确定以后，由每个阶段的决策
u
k
(
x
k
)
(
k
=
1
,
2
,
⋯
,
n
)
u_k(x_k)(k=1,2,\cdots,n)
uk(xk)(k=1,2,⋯,n)所构成的决策序列称为一个整体策略，简称策略，记作
p
1
,
n
(
x
1
)
p_{1,n}(x_1)
p1,n(x1)，即
p
1
,
n
(
x
1
)
=
∣
u
1
(
x
1
)
,
u
2
(
x
2
)
,
⋯
,
u
n
(
x
n
)
∣
.
p_{1,n}(x_1)=|u_1(x_1),u_2(x_2),\cdots,u_n(x_n)|.
p1,n(x1)=∣u1(x1),u2(x2),⋯,un(xn)∣.
而
p
k
,
n
(
x
k
)
=
∣
u
k
(
x
k
)
,
u
k
+
1
(
x
k
+
1
)
,
⋯
,
u
n
(
x
n
)
∣
p_{k,n}(x_k)=|u_k(x_k),u_{k+1}(x_{k+1}),\cdots,u_n(x_n)|
pk,n(xk)=∣uk(xk),uk+1(xk+1),⋯,un(xn)∣
和
p
1
,
k
(
x
1
)
=
∣
u
1
(
x
1
)
,
u
2
(
x
2
)
,
⋯
,
u
k
(
x
k
)
∣
p_{1,k}(x_1)=|u_1(x_1),u_2(x_2),\cdots,u_k(x_k)|
p1,k(x1)=∣u1(x1),u2(x2),⋯,uk(xk)∣
则分别称为一个后部
k
k
k段子策略和前部
k
k
k段子策略。用
P
1
,
n
(
x
1
)
P_{1,n}(x_1)
P1,n(x1)，
P
1
,
k
(
x
1
)
P_{1,k}(x_1)
P1,k(x1)及
P
k
,
n
(
x
k
)
P_{k,n}(x_k)
Pk,n(xk)分别表示整体策略集合，前部及后部
k
k
k段子策略集合。
如果一个策略使得多阶段决策问题达到所要求的最优，则称此策略为最优策略。
1.2.6 状态转移方程
把过程由一个状态变到另一个状态叫做状态转移，显然它既与状态有关，又与决策有关。
如果第
k
k
k阶段的状态
x
k
x_k
xk和决策
u
k
u_k
uk都确定以后，第
k
+
1
k+1
k+1阶段的状态
x
k
+
1
x_{k+1}
xk+1就随之确定，那么就把这个对应关系记作
x
k
+
1
=
T
k
(
x
k
,
u
k
)
,
x_{k+1}=T_k(x_k,u_k),
xk+1=Tk(xk,uk),
并称它为由状态
x
k
x_k
xk到
x
k
+
1
x_{k+1}
xk+1的顺序状态转移方程。
如果第
k
k
k阶段的状态
x
k
x_k
xk和第
k
−
1
k-1
k−1阶段的决策
u
k
−
1
u_{k-1}
uk−1都确定以后，第
k
−
1
k-1
k−1阶段的状态
x
k
−
1
x_{k-1}
xk−1就随之确定，则把这个对应关系记作
x
k
−
1
=
T
k
−
1
(
u
k
−
1
,
x
k
)
,
x_{k-1}=T_{k-1}(u_{k-1},x_k),
xk−1=Tk−1(uk−1,xk),
并称它为由状态
x
k
x_k
xk到
x
k
−
1
x_{k-1}
xk−1的逆序状态转移方程。
1.2.7 指标函数
每个多阶段决策问题都存在很多策略，而每个策略都会对应某种“效益”。不同问题效益的含义是不同的，同一问题采取不同的策略其效益也会不一样。衡量问题效益优劣的数量指标称为指标函数。
对
n
n
n阶段决策问题，用
F
k
,
n
(
x
k
,
p
k
,
n
)
F_{k,n}(x_k,p_{k,n})
Fk,n(xk,pk,n)表示从第
k
k
k阶段的状态
x
k
x_k
xk出发，采用策略
p
k
,
n
p_{k,n}
pk,n到达终点
x
k
+
1
x_{k+1}
xk+1的后部指标函数。若上述过程采用的是最优策略
p
k
,
n
∗
p^{\ast}_{k,n}
pk,n∗，则相应的后部指标函数记作
f
k
,
n
(
x
k
,
p
k
,
n
∗
)
f_{k,n}(x_k,p^{\ast}_{k,n})
fk,n(xk,pk,n∗)，简记为
f
k
(
x
k
)
f_k(x_k)
fk(xk)，并称为后部最优指标函数，简称为最优函数。
f
k
(
x
k
)
f_k(x_k)
fk(xk)与
F
k
,
n
(
x
k
,
p
k
,
n
)
F_{k,n}(x_k,p_{k,n})
Fk,n(xk,pk,n)间的关系为
f
k
(
x
k
)
=
F
k
,
n
(
x
k
,
p
k
,
n
∗
)
=
o
p
t
p
k
,
n
∈
P
k
,
n
F
k
,
n
(
x
k
,
p
k
,
n
)
,
f_k(x_k)=F_{k,n}(x_k,p^{\ast}_{k,n})=\mathop{opt}\limits_{p_{k,n}\in P_{k,n}}{F_{k,n}(x_k,p_{k,n})},
fk(xk)=Fk,n(xk,pk,n∗)=pk,n∈Pk,noptFk,n(xk,pk,n),
这里
o
p
t
opt
opt是optimization的缩写，表示最优，通常取max或min。这时
f
1
(
x
1
)
f_1(x_1)
f1(x1)表示整体最优函数。
类似地有前部指标函数
F
1
,
k
(
x
1
,
p
1
,
k
)
F_{1,k}(x_1,p_{1,k})
F1,k(x1,p1,k)和前部最优指标函数
f
1
,
k
(
x
1
,
p
1
,
k
∗
)
f_{1,k}(x_1,p^{\ast}_{1,k})
f1,k(x1,p1,k∗)，并同样记作
f
k
(
x
k
)
f_k(x_k)
fk(xk)，且
f
k
(
x
k
)
=
F
1
,
k
(
x
1
,
p
1
,
k
∗
)
=
o
p
t
p
1
,
k
∈
P
1
,
k
F
1
,
k
(
x
1
,
p
1
,
k
)
,
f_k(x_k)=F_{1,k}(x_1,p^{\ast}_{1,k})=\mathop{opt}\limits_{p_{1,k}\in P_{1,k}}{F_{1,k}(x_1,p_{1,k})},
fk(xk)=F1,k(x1,p1,k∗)=p1,k∈P1,koptF1,k(x1,p1,k),
这时
f
n
+
1
(
x
n
+
1
)
f_{n+1}(x_{n+1})
fn+1(xn+1)表示整体最优函数。
用
d
(
x
k
,
x
k
+
1
)
d(x_k,x_{k+1})
d(xk,xk+1)表示状态
x
k
x_k
xk与
x
k
+
1
x_{k+1}
xk+1之间对应的指标，称为阶段指标。当过程是由状态
x
k
x_k
xk出发，采取决策
u
k
u_k
uk到达状态
x
k
+
1
=
T
k
(
x
k
,
u
k
)
x_{k+1}=T_k(x_k,u_k)
xk+1=Tk(xk,uk)时，则把
d
(
x
k
,
x
k
+
1
)
d(x_k,x_{k+1})
d(xk,xk+1)写成
d
(
x
k
,
u
k
)
d(x_k,u_k)
d(xk,uk)；当过程是由状态
x
k
+
1
x_{k+1}
xk+1出发，采取决策
u
k
u_k
uk去确定状态状态
x
k
=
T
k
(
u
k
,
x
k
+
1
)
x_k=T_k(u_k,x_{k+1})
xk=Tk(uk,xk+1)时，则把
d
(
x
k
,
x
k
+
1
)
d(x_k,x_{k+1})
d(xk,xk+1)写成
d
(
u
k
,
x
k
+
1
)
d(u_k,x_{k+1})
d(uk,xk+1)。
指标函数通常采用如下两种形式：
（1）指标函数为阶段指标之和的形式，即
F
k
,
n
=
∑
j
=
k
n
d
(
x
j
,
u
j
)
=
d
(
x
k
,
u
k
)
+
F
k
+
1
,
n
，
F_{k,n}=\sum\limits_{j=k}^n{d(x_j,u_j)}=d(x_k,u_k) + F_{k+1,n}，
Fk,n=j=k∑nd(xj,uj)=d(xk,uk)+Fk+1,n，
F
1
,
k
=
∑
j
=
2
k
d
(
u
j
−
1
,
x
j
)
=
d
(
u
k
−
1
,
x
k
)
+
F
1
,
k
−
1
.
F_{1,k}=\sum\limits_{j=2}^k{d(u_{j-1},x_j)}=d(u_{k-1},x_k) + F_{1,k-1}.
F1,k=j=2∑kd(uj−1,xj)=d(uk−1,xk)+F1,k−1.
（2）指标函数为阶段指标之积的形式，即
F
k
,
n
=
∏
j
=
k
n
d
(
x
j
,
u
j
)
=
d
(
x
k
,
u
k
)
⋅
F
k
+
1
,
n
，
F_{k,n}=\prod\limits_{j=k}^n{d(x_j,u_j)}=d(x_k,u_k) \cdot F_{k+1,n}，
Fk,n=j=k∏nd(xj,uj)=d(xk,uk)⋅Fk+1,n，
F
1
,
k
=
∏
j
=
2
k
d
(
u
j
−
1
,
x
j
)
=
d
(
u
k
−
1
,
x
k
)
⋅
F
1
,
k
−
1
.
F_{1,k}=\prod\limits_{j=2}^k{d(u_{j-1},x_j)}=d(u_{k-1},x_k) \cdot F_{1,k-1}.
F1,k=j=2∏kd(uj−1,xj)=d(uk−1,xk)⋅F1,k−1.