文档介绍：动态规划
第一节动态规划的基本原理
一、动态规划的基本概念
二、递推方程与最优化原理
第二节动态规划的数学模型和求解方法
一、动态规划的数学模型
二、动态规划的求解方法
第三节多维动态规划简介
一、多维动态规划问题的数学模型与求解方法的改进途径
二、动态规划逐次渐近法
三、离散微分动态规划法
四、系统方程的可逆性
1
动态规划
动态规划(Dynamic Programming),缩写为DP,是本世纪50年代初期由美国数学家贝尔曼(Richard )等人提出,逐渐发展起来的数学分支,它是一种解决多阶段决策过程最优化问题的数学规划法。
动态规划的数学模型和求解方法比较灵活,对于系统是连续的或离散的,线性的或非线性的,确定性的或随机性的,只要能构成多阶段决策过程,便可用动态规划推求其最优解。因而在自然科学、社会科学、工程技术等许多领域具有广泛的用途,比线性规划、非线性规划更有成效,特别对于离散型问题,解析数学无法适用,动态规划就成为非常有用的求解工具。
它在广泛应用中的主要障碍是“维数灾”,即当问题中的变量个数(维数)太大时,由于计算机内存贮量和计算速度限制,而无法求解。
2
第一节动态规划的基本原理
一、动态规划的基本概念(一)动态规划的基本思路在客观事物中,存在着这样一类问题:
可以按照时间或空间特性将其划分为若干个互相联系的阶段;
在每个阶段都需要做出决策,并且一个阶段的决策将影响下阶段的状态;
所有阶段决策构成一个决策序列,称为策略;
每个策略都对应一个效果。所选择的策略应使整个过程获得最优效果。
这类问题称为多阶段决策过程,动态规划就是按照上述思路寻求问题最优解的工具。
3
例如,以灌溉或发电为目标的年调节水库调度问题,就是一个多阶段决策过程。一年可以按时间分成若干阶段。在每个阶段,以水库蓄水量(或水位)为状态变量,以放水量为决策变量,把灌溉效益或发电量最大化作为目标函数。在满足约束条件下确定各时段放水量,即组成一个决策序列。如果所选定的各时段放水量能使全年灌溉或发电效益最大,这就是一个最优策略,即最优调度方案。由于各阶段决策与时间进程有关,故称为动态规划。
动态规划不仅能解决与时间有关的优化问题,而且也能解决与时间无关的静态问题。例如,资源分配问题、投资分配问题、最优线路问题、结构优化问题等。只要能够把问题分成多个阶段或步骤进行决策,就可用动态规划寻求最优解。
一、动态规划的基本概念-(一)动态规划的基本思路
4
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
也可称为最短路径问题:求从A到E的最短路径
一、动态规划的基本概念-(一)动态规划的基本思路
下面以一个简单的最优输水线路问题,说明动态规划寻求最优解的基本思路和方法。
[例1]如下图所示,现拟由水源A(起点站),引水到用水地点E(终点站)。在输水途中将经过3级中转站,第一级中转站可以在地点B1、B2或B3中任选一点,第二级中转站可以在地点C1、C2或C3中任选一点,第三级中转站可以在地点D1或D2中任选一点,任何两个地点之间的输水费用已表示在图中的联结线上。问题是要选择一条由水源A到用水地点E总输水费用最小的路线。
5
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f5(E)=0
6
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D1)=5
f5(E)=0
7
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f4(D1)=5
8
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f3(C1)=8
f4(D1)=5
9
2
5
1
12
14
10
6
10
4
13
11