动态规划 Dynamic Programming（DP）第四章 动态规划.doc

动态规划 Dynamic Programming(DP)第四章动态规划
动态规划 Dynamic Programming(DP)
动态规划
动态规划 Dynamic Programming(DP)
引言
动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。
1951年, R3>.Bellman
多阶段决策问题
一系列相互联系的
单阶段决策问题
最优性原理
贝尔曼的名著《动态规划》于1957年出版,这成了动态规划的第一本著作。
动态规划 Dynamic Programming(DP)
引言
动态规划的方法,在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用,并且获得了显著的效果。
最优路径问题
资源分配问题
生产与库存问题
设备更新问题
经济管理方面的应用
…
动态规划 Dynamic Programming(DP)
引言
由于动态规划的方法在众多方面的应用,使他已经成为现代企业管理中的一种重要的决策方法。

此外,许多实际问题采用动态规划方法去处理,常比线性规划或非线性规划更加有效。
特别对于离散型的问题,由于解析数学无法施展其术,而动态规划方法就成为一种非常有效的工具。
动态规划 Dynamic Programming(DP)
多阶段决策过程的最优化
多阶段决策过程:
整个决策过程可按时间或空间顺序分解成若干相互联系的阶段,每一阶段都需作出决策,全部过程的决策是一个决策序列。
多阶段决策过程最优化的目标:
达到整个活动过程的总体效果最优,而非各单个阶段最优的简单总和。
动态规划 Dynamic Programming(DP)
动态规划典例
例——最短路线问题
5
3
1
3
6
8
7
6
6
8
3
5
3
4
2
1
3
8
2
2
3
3
3
5
5
2
6
6
4
3
A
B1
B2
C2
C3
C4
C1
D3
D2
D1
E3
E2
E1
F2
F1
G
动态规划 Dynamic Programming(DP)
动态规划典例----最短路问题
寻找A点到G点的最短线路
4
3
7
5
9
7
6
8
13
10
9
12
13
16
18
该点到G点的
最短距离
动态规划 Dynamic Programming(DP)
动态规划典例----最短路问题
A点到G点的最短线路如下,最短距离18。
A
B1
C2
D1
E2
F2
G
对于以上的最短线路问题:
逆序动态递推的方法
简单的枚举方法
575次运算
43次运算
?运算量
动态规划 Dynamic Programming(DP)
动态规划的基本概念
1、阶段(stage)
对整个决策过程的自然划分,通常根据时间顺序或空间特征来划分阶段,以便按阶段的次序逐段解决整个过程的优化问题。阶段变量通常用k表示(k = 1,2,3,…,n)。
2、状态(state)
每个阶段开始时过程所处的自然状况或客观条件。它应能描述过程的特征并具有“无后效性”,即当前阶段状态给定时,这个阶段以后过程的演变与该阶段以前各阶段的状态无关。
状态变量—— sk(state variable)
允许状态集合—— Sk(set of admissible states)
动态规划 Dynamic Programming(DP)
动态规划的基本概念
3、决策(decision)
当一个阶段的状态确定后,可以作出不同的决定或选择,从而演变到下一阶段的某个状态,这种决定或选择称为决策。
决策变量—— uk(sk) (decision variable)简记为 uk
允许决策集合—— Dk(sk)(set of admissible decision)
4、策略(policy)
一组有序的决策序列构成一个策略,从第k阶段至第n阶段的一个策略称为后部子策略记为 pk,n
→(uk,uk+1,…,un)。
动态规划 Dynamic Programming(DP)
动态规划的基本概念
5、状态转移方程(equation of state transition)
在动态规划中,本阶段的状态往往是上一阶段的状态和决策共同作用的结果。当给定了上一阶段的状态sk ,以及作出了本阶段的决策uk 后,则下一阶段(K+1阶段)的状态sk+1 便完全确定。用状态转移方程反映这种状态间的演变规律,写作:
sk+1 = Tk(sk,uk) k =1,2,…,n
6、阶段