文档介绍：第六章动态规划 (Dynamic Programming)
教学要求:
了解动态规划的基本思想
掌握一维离散动态规划的建模和求解方法应用
会运用动态规划方法解决一些基本应用问题。
1
动态规划是运筹学的一个分支,是求解多阶段决策过程最优化问题的数学方法。
动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用,并且获得了显著的效果。
学****动态规划,首先要了解多阶段决策问题。
§ 动态规划原理和模型
2
例1:最短路径问题:给定一个交通网络图如下,其中两点之间的数字表示距离(或运费),试求从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到G的6个阶段,一共有48条路线,比较47次。
4
例2:背包问题有一个徒步旅行者,其可携带物品重量的限度为a 公斤,设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值(作用),问此人应如何选择携带的物品(各几件),使其背包所起作用(使用价值)最大?
物品
1 2 … j … n
重量(公斤/件)
a1 a2 … aj … an
每件使用价值
c1 c2 … cj … cn
类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。
5
根据过程的特性可以将过程按空间、时间等标志分为若干个互相联系又互相区别的阶段。
在每一个阶段都需要做出决策,从而使整个过程达到最好的效果。
各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展。
当各个阶段的决策确定后,就组成了一个决策序列,因而也就决定了整个过程的一条活动路线,这样的一个前后关联具有链状结构的多阶段过程就称为多阶段决策问题。
多阶段决策过程:
7
针对多阶段决策过程的最优化问题,美国数学家Bellman等人在20世纪50年代初提出了著名的最优化原理,把多阶段决策问题转化为一系列单阶段最优化问题,从而逐个求解,
创立了解决这类过程优化问题的新方法:动态规划。
对最佳路径(最佳决策过程)所经过的各个阶段,其中每个阶段始点到全过程终点的路径,必定是该阶段始点到全过程终点的一切可能路径中的最佳路径(最优决策),这就是Bellman提出的著名的最优化原理。
简言之, 一个最优策略的子策略必然也是最优的。
Bellman在1957年出版的《Dynamic Programming》是动态规划领域的第一本著作。
8
动态规划的基本概念
最短路问题:某运输公司拟将一批货物从A地运往E地,其间的交通系统网络如下图所示。图上节点表示地点,边表示两地之间的道路,边上的数字表示两地间的运输费用,求运输费用最低的运输路线。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
第2阶段
第3阶段
第4阶段
第1阶段的状态
决策:某阶段状态给定之后,从该状态演变到下一阶段某一状态的选择。比如从第一阶段到第二阶段选择什么路线。 策略:各阶段决策确定后,组成的一个有序的决策序列。
第2阶段的状态
第1阶段
一、动态规划的基本概念
9
1、阶段(k)
将所给问题的过程,按时间或空间特征分解成若干相互联系的阶段,以便按次序求解。
2、状态sk
能表示决策顺序的离散的量,阶段可以确定地表示决策过程当前特征的量。状态可以是数量,也可以是字符,数量状态可以是连续的,也可以是离散的。
10