文档介绍：第八章动态规划基本方法
动态规划
动态规划研究的问题: “多阶段决策问题”的优化方法
☆
表示各阶段可供选择的方案
阶段 1 2 3 4 …… n
☆☆☆☆……☆
☆☆☆☆……☆☆☆☆☆……☆
☆☆☆☆……☆☆☆☆☆……☆
各阶段决策组成一个决策序列——策略
二、研究范围:
线性规划、非线性规划、整数规划、网络分析、控制工程等
三、分类:
据多阶段决策过程的时间参数是离散还是连续,决策过程的演变是确定还是随机,多阶段决策过程分为:
离散确定
连续随机
四、应用:
资源分配、存贮问题、生产计划、设备更新、最优控制、加工工件排序
最优化原理
最短路问题:
给定一个线路网络,两点连线上的数字表示两点间的距离,求一条从A到G的铺管线路,使总距离为最短。
A
B1
C1
C2
B2
C3
D1
D2
D3
C4
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
2
3
3
3
5
5
2
6
6
4
3
1、穷举法:
48条路线
比较47次加法138次
2、走一步,看一步,选近的
A——B2——C4——D3——E3——F2——G 路长21
选B2一枝,另一枝抛掉,只考虑近期
3、动态规划方法:
先从终点开始,分别求每一点到终点的最短路线:
只需比较15次,加法28次,求出了每点到终点的最短距离,丰富了技术结果。
A
B1
C1
C2
B2
C3
D1
D2
D3
C4
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
2
3
3
3
5
5
2
6
6
4
3
最优化原理:
一个最优策略应有这样的性质:即:不论过去的决策和状态如何,对于先前决策所确定的状态而言,余下的所有决策必构成最优策略。
上例A——G的最短路线是A—B1—C2—D1—E2—F2—G
则D1—E2—F2—G应该是从D1到G的所有路线中的最短路线。
例:假设AB实线是由状态A的最优策略决定的从A 到B的最优路线,在该路线上任取一点M,则按最优化原理得到的结论就是MB实线是由状态M的最优策略决定的从M到B的最优路线。
A
B
M
反证法:
动态规划基本概念和基本方程

一、基本概念:
:
描述阶段的变量叫阶段变量,常用k表示,k=1,2…,n
:
状态表示每阶段开始所处的自然状况或客观条件,它描述了过程的过去、现在和将来的状况,又称不可控因素。
描述状态的变量叫状态变量,常用sk表示k阶段的状态。
上例:状态变量Sk表示k阶段出发点,第三阶段有4个出发点,就有四个状态,分别为C1、C2、C3、C4。
状态变量的取值有一定的允许集合和范围,叫可达状态集合。
即状态变量取值的全体。
第K阶段的可达状态集合记为Sk= sk
S2= B1,B2
上例:S3= C1、C2、C3、C4
A
5
3
1
3
6
8
7
6
6
8
3
5
3
3
8
4
2
2
1
2
3
3
3
5
5
2
6
6
4
3
B1
B2
C1
C2
C3
C4
D2
E2
D3
D1
E1
E3
F1
F2
G

决策就是确定过程发展的方案。
描述决策的变量叫决策变量,常用Uk(sk)表示k阶段sk状态的决策变量,它是状态变量的函数。
决策变量的取值也有一定的范围叫允许决策集合。常用Dk (sk)表示第k阶段sk状态下的允许决策集合。
上例D2(B1)={C1,C2,C3} 若选择C2,则U2 (B1)=C2
显然Uk(sk)∈ Dk(sk)
A
B1
C1
C2
B2
C3
D1
D2
D3
C4
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
2
3
3
3
5
5
2
6
6
4
3
:是一个按顺序排列的决策组成的集合。
由过程的第k个阶段开始到终止状态为止的过程称为后部子过程。后部子过程中各阶段决策按顺序排列组成的决策序列,称为 k 后部子策略,记为Pk,n( Sk ),
即Pk,n( Sk )= {Uk(Sk)、 Uk+1(Sk+1) …… Un(Sn)}
当k=1时其决策序列为全过程的一个策