文档介绍：第六章动态规划
(Dynamic programming)
1
概述
1951年Bellman提出,1957《动态规划》
动态规划是解决多阶段决策问题的一种数学方法。
动态规划思想:把多阶段决策问题变换为一系列互相联系的单阶段问题,然后逐个加以解决。即:把一个n 维决策问题变换为几个一维最优化问题,从而一个一个地去解决。
需指出:动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种算法。必须对具体问题进行具体分析,运用动态规划的原理和方法,建立相应的模型,然后再用动态规划求解方法去求解。
应用:最短路线、资源分配、生产调度问题
2
主要内容
一、多阶段决策问题
二、动态规划的基本概念
三、动态规划的基本思想
四、动态规划递推求解方法
五、动态规划的最优性原理
六、动态规划的优缺点
七、动态规划问题应用举例
3
一、多阶段决策问题
在多阶段决策过程中,系统的动态过程可以按照时间进程分为状态相互联系而又相互区别的各个阶段;每个阶段都要进行决策,目的是使整个过程的决策达到最优效果。
多阶段决策问题的特点:
(1)系统所处的状态和时刻是进行决策的重要因素,即在系统发展的不同时刻(或阶段)根据系统所处的状态,不断地做出决策;
(2)目的是找到不同时刻的最优决策以及整个过程的最优策略。
4
1
2
n

状态1
决策1
状态2
决策2
状态3
状态n
决策n
多阶段决策问题的典型例子:
1 . 生产决策问题:企业在生产过程中,由于需求是随时间变化的,因此企业为了获得全年的最佳生产效益,就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。
2. 机器负荷分配问题:某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时,产品的年产量g和投入生产的机器数量u1的关系为
g=g(u1)
5
这时,机器的年完好率为a,即如果年初完好机器的数量为u,到年终完好的机器就为au, 0<a<1。
在低负荷下生产时,产品的年产量h和投入生产的机器数量u2的关系为
h=h(u2)
假定开始生产时完好的机器数量为s1。要求制定一个五年计划,在每年开始时,决定如何重新分配完好的机器在两种不同的负荷下生产的数量,使在五年内产品的总产量达到最高。
相应的机器年完好率b, 0< b<1。
6
3. 航天飞机飞行控制问题:由于航天飞机的运动的环境是不断变化的,因此就要根据航天飞机飞行在不同环境中的情况,不断地决定航天飞机的飞行方向和速度(状态),使之能最省燃料和实现目的(如软着落问题)。
、非线性规划等静态决策问题(本质上是一次决策问题)也可以适当地引入“时间”的概念,作为多阶段的决策问题用动态规划方法来解决。
7
5 . 最短路问题:给定一个交通网络图如下,其中两点之间的数字表示距离(或花费),试求从A到G的最短距离(总费用最小)。
1
2
3
4
5
6
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
E3
F1
F2
G
5
3
1
3
6
8
7
6
3
6
8
5
3
3
8
4
2
2
2
1
3
3
3
5
2
5
6
6
4
3
8
18
(1)阶段
(2)状态
(3)决策
(4)策略
(5)状态转移方程
(6)指标函数和最优值函数
9
二、动态规划的基本概念
10
例一、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站,两点之间的连线上的数字表示距离,如图所示。问应该选择什么路线,使总距离最短?
A
B1
B2
C1
C2
C3
D
2
4
3
3
3
3
2
1
1
1
4