文档介绍：动态规划 (Dynamic Programming)
动态规划的基本概念和思想
最短路径问题
投资分配问题
背包问题
排序问题
1
动态规划是运筹学的一个分支,是求解多阶段决策过程最优化问题的数学方法。 动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用,并且获得了显著的效果。 学****动态规划,我们首先要了解多阶段决策问题。
2
最短路径问题:给定一个交通网络图如下,其中两点之间的数字表示距离(或运费),试求从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
3
背包问题有一个徒步旅行者,其可携带物品重量的限度为a 公斤,设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值(作用),问此人应如何选择携带的物品(各几件),使所起作用(使用价值)最大?
物品
1 2 … j … n
重量(公斤/件)
a1 a2 … aj … an
每件使用价值
c1 c2 … cj … cn
类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。
4
生产决策问题:企业在生产过程中,由于需求是随时间变化的,因此企业为了获得全年的最佳生产效益,就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。
机器负荷分配问题:某种机器可以在高低两种不同的负荷下进行生产。要求制定一个五年计划,在每年开始时,决定如何重新分配完好的机器在两种不同的负荷下生产的数量,使在五年内产品的总产量达到最高。
航天飞机飞行控制问题:由于航天飞机的运动的环境是不断变化的,因此就要根据航天飞机飞行在不同环境中的情况,不断地决定航天飞机的飞行方向和速度(状态),使之能最省燃料和完成飞行任务(如软着陆)。
5
根据过程的特性可以将过程按空间、时间等标志分为若干个互相联系又互相区别的阶段。
在每一个阶段都需要做出决策,从而使整个过程达到最好的效果。
各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展。
当各个阶段的决策确定后,就组成了一个决策序列,因而也就决定了整个过程的一条活动路线,这样的一个前后关联具有链状结构的多阶段过程就称为多阶段决策问题。
多阶段决策过程的特点:
6
针对多阶段决策过程的最优化问题,美国数学家Bellman等人在20世纪50年代初提出了著名的最优化原理,把多阶段决策问题转化为一系列单阶段最优化问题,从而逐个求解,
创立了解决这类过程优化问题的新方法:动态规划。
对最佳路径(最佳决策过程)所经过的各个阶段,其中每个阶段始点到全过程终点的路径,必定是该阶段始点到全过程终点的一切可能路径中的最佳路径(最优决策),这就是Bellman提出的著名的最优化原理。
简言之, 一个最优策略的子策略必然也是最优的。
Bellman在1957年出版的《Dynamic Programming》是动态规划领域的第一本著作。
7
例1、从A 地到E 地要铺设一条煤气管道,其中需经过三级中间站,两点之间的连线上的数字表示距离,如图所示。问应该选择什么路线,使总距离最短?
二. 最短路径问题
A
B2
B1
B3
C1
C3
D1
D2
E
5
2
14
1
12
6
10
10
4
3
12
11
13
9
6
5
8
10
5
2
1
C2
8
1 阶段(Stage)
将所给问题的过程,按时间或空间特征分解成若干个相互联系的阶段,以便按次序去求每阶段的解,常用k表示阶段变量。
我们把从A到E看成一个四阶段问题。
2 状态(State)
各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量,常用sk表示第k阶段的状态变量,状态变量的取值集合称为状态集合,用Sk表示。
9
动态规划中的状态具有如下性质:
当某阶段状态给定以后,在这阶段以后的过程的发展不受这段以前各段状态的影响。即:过程的过去历史只能通过当前状态去影响它未来的发展,这称为无后效性。如果所选定的变量不具备无后效性,就不能作为状态变量来构造动态规划模型。
10