文档介绍：第六章动态规划
适用于年终总结/工作计划/述职报告/策划方案等
2020
3. 决策
在每个阶段所作的决定或选择称为决策或控制。决策依据与当前状态，又决定下一阶段的状态。
描述决策的变量称为决8
4
2
2
1
3
3
3
5
5
2
6
6
4
3
2
4
3
7
5
9
0
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
4
3
7
5
9
7
6
8
0
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
4
3
7
5
9
7
6
8
13
10
9
12
0
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
4
3
7
5
9
7
6
8
13
10
9
12
13
16
0
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
4
3
7
5
9
7
6
8
13
10
9
12
13
16
18
A → B1 → C2 → D1 → E2 → F2 → G
最短路线为：
最优策略为：
P*=
0
该题中，在求解过程中，利用了第k阶段与第k+1阶段之间的递推关系：
一般情况，第k阶段与第k+1阶段之间的递推关系式可表示为：
该递推关系式称为动态规划的基本方程。
边界条件
边界条件
即
一般情况，第k阶段与第k+1阶段之间的递推关系
动态规划模型的建立步骤：
1. 将过程恰当地划分为阶段；
2. 正确选择状态变量sk，既要描述过程的演变，又要满足无后效性；
3. 确定决策变量uk及uk的容许决策集合Dk(sk);
4. 写出状态转移方程 sk+1=Tk(sk,uk);
5. 写出指标函数Vk,n(sk, uk, sk+1,…, sn),应满足：
（1）是定义在全过程和后部子过程上数量函数；
（2）具有可分离性，并满足递推关系；
（3）函数 对于变量 要严格单调；
6. 写出基本方程。
1
状态
状态
状态
状态
状态
决策
决策
2
……
n-1
n
状态
决策
决策
u1
u2
un-1
un
s2
s3
sn-1
sn
sn+1
s1
D(s1)
D(s2 )
D(sn-1)
D(sn)
转移方程
指标函数
基本方程
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
4
3
7
5
9
7
6
8
13
10
9
12
13
16
18
0
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