E3 6
=d5(s5,u5)+ V6, 6
1
2
3
4
5
6
• 过程和它的任意子过程的指标是它所包含的各阶 段的指标的乘积。即
可改写成 Vk, n(sk ,uk ,…, sn+1) = vk(sk ,uk) Vk+1, n(sk+1, uk+1, …, sn+1)
最优值函数： 指标函数的最优值，记为 fk (sk)。表示从第 k 阶段
用动态规划解决多阶段决策问题; 重点掌握动态规划模型结构、逆序算法原理、资源 分
配问题、生产与存储问题. 难点为动态规划中状态变量、基本方程等的确定.
动态规划产生于20世纪50年代, 美国数学 家贝尔曼(R. Bellman)等人提出.
动态规划是求解某类问题的一种方法,是考 察问题的一种途径,而不是一种算法.必须对 具体问题进行具体分析,运用动态规划的原理 和方法,划分阶段,建立相应的模型,然后再去 求解.
动态规划是用来解决多阶段决策过程最优化 的一种数量方法.其特点在于,它可以把一个多 阶段决策问题变换为几个相互联系的同类型单 阶段最优化问题,从而一个一个地去解决.
1. 多阶段决策过程及实例
多阶段决策过程（序贯决策过程）
决策
决策
决策
状态
状态
状态 状态
状态
1
2
…
n
收益
收益
收益
2 多阶段决策问题——举例
55 F1 4
E2 2
G
6 F2 3
D3
3 3
E3 6
4
5
6
4、多阶段决策过程
在每个阶段进行决策 控制过程的发展；
其发展是通过一系列的状态转移来实现的；
系统当前的 状态和决策
系统过去的历 史状态和决策
状态转移方程的一般形式 1
5 B1 3
s2=T1(s1, u1)
s3=sT12=(sAs1,2,u=u11?,=sB2,1u,2)
多阶段决策问题的典型例子
1、 生产决策问题
企业在生产过程中，由于需求是随时间变化的 ，因此企业为了获得全年的最佳生产效益，就要在 整个生产过程中逐月或逐季度地根据库存和需求决 定生产计划。
2、机器负荷分配问题
产品的年产量
某种机器
高负荷 g=g(u1)
投入生产的机 器数量
机器的年完好率为a ，0<a<1
A3
6 8
B2 7
6
C1 6
8 C2 3
5
C3 3 3 8
sk+1=Tk(s1, u1, s2, u2 ,, sk, uk) C4 4
2
D1 E1 3
2
D2
1 2
55 F1 4
E2 2
G
6 F2 3
D3
3 3
E3 6
1
2
3
4
5
6
图示如下：
u1
s1
s2
1
u2 s3
2
sk
uk sk+1 k
能用动态规划方法求解的多阶段决策过程是一类 特殊的多阶段决策过程，即具有无后效性的多阶段 决策过程。
1
5 B1 3
A3
6
8
B2 7
6
C1 6
8
C2 3 5
C3 3 3 8
C4 4
2 D1
2
D2 1 2 3
D3 3
E1 3
5 F1 4
5 E2 2
G
6 E3 6
F2
3
1
2
3
4
5
6
（穷举法48条路线
13 1
5 B1 3
A3
6
18
8 B2 7
16 6
1
2
13
C1 6 10 8
C2 3 95 C3 3
3 8 C4 4
E2 2
G
6 F2 3
D3
3 3
E3 6
1
2
3
4
5
6
多阶段决策过程的数学模型: (具有无后效性, 以和式为例 )
opt
{u1, u2,…,un}
sk+1=Tk(sk, uk)
s.t. skSk
ukDk
k=1,2, …,n
小结:
无后效性
动态规划本质上是多阶段决策过程;
概念:阶段变量 k﹑状态变量 sk﹑决策变量 uk ;
不包含时间因素的静态决策问题（一次决策问题 ）也可以适当地引入阶段的概念，作为多阶段的决 策问题用动态规划方法来解决。
4、最短路问题（引例）：给定一个交通网络图如
前，其中两点之间的数字表示距离（或花费），试求 从A点到G点的最短距离（总费用最小）。
动态规划的基本概念
1. 阶段 2. 状态 3. 决策 4. 策略 5. 状态转移方程 6. 指标函数和最优值函数
量，常用 k 表示。
2、状态、状态变量
每个阶段开始所处的自然状态或客观条件,描述过程的
状况,通常一个阶段有若干个状态.
描述过程状态的变 量称为状态变量， 它可用一个数、一 组数或一向量来描 述, 常用 sk 表示第 k 阶段的状态.
1 C1 6
5 B1 3
A3
6 8
B2 7
8 C2 3
5
C3 3 3
6
8
C4 4
uk,Vk+1, n 的函数。
2
D1 E1 3
2
D2
1 2
55 F1 4
E2 2
G
6 F2 3
D3
3 3
E3 6
1
234Fra bibliotek56
常见的指标函数的形式是：
• 过程和它的任一子过程的指标是它所包含的各阶
段的指标和。即
无后效性 的结果
其中V(sj, uj ) 表示第 j 阶段的阶段指标。这时上
式可写成
1 2
55 F1 4
E2 2
G
6 F2 3
D3
3 3
E3 6
1
2
3
4
5
6
§1 动态规划的研究对象和引例
动态系统：
包含随时间变化的因素和变量的系统。 动态决策问题：
系统所处的状态和时刻是进行决策的重要因素. 找到不同时刻的最优决策以及整个过程的最优策略.
状态
决策 状态
1
决策
状态 状态
2
决策 n
阶段
全过程的最优
12 3
7
2 D1
2 6 D2 1
2 3 D3 3 8
7
E1 3
5 5
F1 4
5 E2 2
G
6 E3 6
F2 3 3
9
4
5
6
51
5 B1 3
A3
6
8
B2 7
36
1
2
6
C1 6 88 C2 3 10 5 C3 3
3 8 C4 4
9 3
11 2
D1
13 2 D2 1
2 3 D3 3
13
13
E1 3 17
55 F1 E2 2
4
G
F1 G，f6(F1)=4 F2 G，f6(F2)=3
6 F2 3
D3
3 3
E3
6
k=5，出发点有 E1, E2, E3
C4 4
u5(E1)=F1
E1F1G
u5(E2)=F2
E2F2G
u5(E3)=F2 E3F2G
1 C1 6
Vk, n(sk ,uk ,…, sn+1) = vk(sk ,uk)+ Vk+1, n
5 B1 3
A3
6 8
B2 7
8 C2 3
5
C3 3 3
V5, 6= V5, 6 (s5, u5, V6, 6 )
6
8
C4 4
2
D1 E1 3
2
D2
1 2
55 F1 4
E2 2
G
6 F2 3
D3
3 3
的状态 sk 到第 n 阶段的终止状态的采取最优策略所得 到的指标函数值。即
全过程的最优值函数记为 f1 (s1)
f6 (s6)=？
f6 (F1)=4 f6 (F2)=3
f5 (E1)=？
1 C1 6
5 B1 3
A3
6 8
B2 7
8 C2 3
5
C3 3 3
6
8
C4 4
2
D1 E1 3
2
D2
1 2
55 F1 4
sk+1=Tk(sk, uk)
6、策略
按顺序排列的决策组成的集合。 由过程的第k 终止状态为止的过程，称为问题的 后部子过程（k 子过程）。
由每段的决策按顺序排列组成的决策函数序列称为
k 子过程策略。简称
1 C1 6
子策略，记为pk,n(sk)，5 B1 3
即，
A3
6 8
Pk,n(sk)={uk(sk),uk+1(sk+1), ,un(sn)}
5、无后效性或马尔可夫性
如果某阶段状态给定后，则在这个阶段以后过程的 发展不受这个阶段以前各阶段状态的影响；过程的过 去历史只能通过当前的状态去影响它未来的发展。
构造动态规划模型时，要充分注意状态变量是否满 足无后效性的要求；
状态转移方程？
状态具有无后效性的多阶段决策过程的状态转移 方程如下：
s2=T1(s1, u1) s3=T2(s2, u2)