2018/11/11
2
动态规划
1 最短路径问题 2 贝尔曼最优化原理 3 WinQSB软件应用
2018/11/11
3
动态规划是解决多阶段决策问题 的一种方法. 1951年，美国数学 家贝尔曼（R.Bellman， 1920～1984）研究了一类多阶 段决策问题的特征，提出了解决 这类问题的基本原理。在研究、 解决了某些实际问题的基础上， 他于1957年出版了《动态规划》 这一名著。本章将简要介绍动态 规划的思想方法及其应用。
min{d ( Sk , X ( Sk )) f k -1 ( X (Sk ))}, k 2,3,..., n, f k ( Sk ) x k ( Sk ) f1 (S1 ) min{d (S1 , X1 (S1 ))} d (S1 , X1 (S1 )).
2018/11/11 22
第10章 动态规划方法
2018/11/11
1
动态规划（Dynamic Programming）同前 面介绍过的线性规划方法不同，它不是一种算法，而 是考察问题的一种途径。动态规划是一种求解多阶段 决策问题的系统技术。由于动态规划不是一种特定的 算法，因而它不像线性规划那样有一个标准的数学表 达式和明确定义的一组规则，动态规划必须对具体问 题进行具体的分析处理。动态规划在自然科学和社会 科学等各个领域都有着广泛的应用，并且获得了显著 的效果。
此关系被称为求最短路径的动态规划基本方程。 求解最短路径问题的过程，本质上是解上述基 本方程的过程。
2018/11/11 19
2 贝尔曼最优化原理
2018/11/11
20
2 贝尔曼最优化原理
将求解最短路径问题的思路推广到一般多 阶段决策问题时，可以表述成： 贝尔曼最优化原理：一个过程的最优策略 具有这样的性质，即无论其初始状态和初 始决策如何，今后的诸决策，对以第一个 决策所形成的状态作为初始状态的过程而 言，必须构成最优策略。 这个原理是动态规划的理论基础。
2018/11/11
d ( B1 , C1 ) f1 (C1 ) 6 5 f 2 ( B1 ) min min 11 5 8 d ( B1 , C2 ) f1 (C2 )
15
1 最短路径问题
从 B1 出发到终点E最短路径为“B1 C1 E ”， * X 决策变量 2 (B1 ) C1 ； 从B2出发到终点E最短路径为“B2 C1 E ”， * X 决策变量 2 (B2 ) C1 ； S3 可以取 A1 , A2 , A3 在阶段3： 中任意一个， 对应的有 d ( A , B ) f ( B ) 6 11
2018/11/11
8
1 最短路径问题
(a)
(b)
2018/11/11 9
1 最短路径问题
分析：如果用枚举法，将有12条不同的路 径，每条路径对应一个由S到E的路径距离， 其中最小值所对应的路径即为最短路径。本 问题的最短路径有3条，路程均为21个单位： 第1条： S A1 B1 C1 E
2018/11/11
21
2 贝尔曼最优化原理
应用动态规划方法解决一般多阶段决策问题时，其求 解过程如下： （1）把实际问题适当地划分成k个阶段，阶段变量 为k (k 1, 2,..., n) ； （2）在每个阶段k，确定状态变量 Sk 为及此阶段可 能的状态集合 {Sk } ； （3）确定决策变量 X k (Sk ) 及每个阶段k的允许决策 xk (Sk ) {X k (Sk )} 集合 ； （4）列出递推关系即动态规划基本方程并计算：
1 2
2018/11/11
23
2 贝尔曼最优化原理
(a)
(b)
2018/11/11 24
2 贝尔曼最优化原理
A B; B C; C D; D E. 解 划分成4个阶段： 阶段变量依次为4，3，2，1，如图2所示. 设 阶段k的状态变量为Sk , k 1, 2,3, 4 。 f1 ( D1 ) 3, f1 ( D2 ) 4 在阶段1： S2 可以取 C1, C2 , C3 在阶段2： 中任意一个， 对应的有 d (C , D ) f ( D ) 1 3
min{d ( Sk , X ( Sk )) f k -1 ( X ( Sk ))}, k 2,3,..., n, f k ( Sk ) X k ( Sk ) f1 (S1 ) min{d (S1 , X 1 (S1 ))} d (S1 , X 1 (S1 )).
f1 (C1 ) 5, f1 (C2 ) 8
在阶段2：S2 可以取 B1, B2 中任意一个，对应的有
d ( B2 , C1 ) f1 (C1 ) 9 5 f 2 ( B2 ) min min 14 8 8 d ( B2 , C2 ) f1 (C2 )
2 贝尔曼最优化原理
【例2】（石油输送管道铺设优选问题）某石 油公司计划从A地到E地铺设一条石油输送管 道，为此在A地与E地之间必须建立三个油泵 加压站，如图2所示， 其中 B, C, D 分别为必 须建站的地区，而 B1, B2 , B3 , C1, C2 , C3 , D , D 分别为可供选择的各站点，各点连线上的数字 表示相邻站点间铺设输送管道所需费用. 问： 如何铺设石油输送管道，能使总费用最少？
2018/11/11 14
1 最短路径问题
以 d (Sk , X k (Sk )) 表示在阶段k的状态变量为 Sk 、决策 变量为 X k (Sk ) 时点 Sk 与 X k (Sk ) 间的距离；记 f k ( Sk ) 为在阶段k由点 Sk 到终点E的最短路径的长度。本例 中要求的是 f4 (S ) 。 在阶段1：S1 可以取 C1, C2 中任意一个，对应的有
* 3 2 1
3 1 1
；
d ( S , A1 ) f3 ( A1 ) 4 17 f 4 ( S ) min d ( S , A2 ) f 3 ( A2 ) min 3 19 21 d (S , A ) f ( A ) 3 18 3 3 3
2018/11/11 13
1 最短路径问题
为了寻找由起点S到E终点的最短路径，我 们考察前面用枚举法找到的第1条最短路径：
S A1 B1 C1 E
A1 B1 C1 E 容易看出：子路径“ ” 也应 A1 是从 出发到终点E的所有路径中最短的一条。
这个现象启发我们从阶段1开始，逐段逆向地 求出各点到终点E的最短路径，最后求得由起 点S到终点E的最短路径，这就是动态规划的 基本思想。
1 1 1 1 f 2 (C1 ) min min 4 4 4 d (C1 , D2 ) f1 ( D2 ) d (C2 , D1 ) f1 ( D1 ) 6 3 f 2 (C2 ) min min 7 3 4 d (C2 , D2 ) f1 ( D2 ) d (C3 , D1 ) f1 ( D1 ) 3 3 f 2 (C3 ) min min 6 3 4 d (C3 , D2 ) f1 ( D2 )
第2条： S A3 B1 C1 E
S A3 B2 C1 E 第3条：
2018/11/11
10
1 最短路径问题
当段数很多时，枚举法的计算量将极其庞大。 现在换个思路，寻找由S到E的最短路径。先 把最短路径问题所考虑的过程分为4个阶段： 由S到 Ai (i 1, 2,3) 为第1阶段； Bj ( j 1, 2) 由 Ai (i 1, 2,3) 到 为第2阶段； 由 由
2018/11/11
6
1 最短路径问题
2018/11/11
7
1 最短路径问题
【例1】设在E城的某公司要从S城运送一批 货物，两城之间有公路相连（见图 1(a)）， 其中 Ai (i 1, 2,3), Bj ( j 1, 2), Cl (l 1, 2) 是可以供选择的途经站点，各点连线上的数 字表示相邻站点间的距离。现在的问题是选择 一条由S到E的路径，使得所经过的路径最短。
2018/11/11 17
1 最短路径问题
因此，由起点S到终点E的最短路径为
S A1 B1 C1 E； S A3 B1 C1 E； S A3 B2 C1 E.
最短路径长度为21单位长度。
2018/11/11
18
1 最短路径问题
由上述计算过程可知，对有n个阶段的最短 路径问题，可以逐段逆向地求出各点到终 点的最短路径，且在求解的每一步都利用 阶段k和阶段k-1间的递推关系：
2018/11/11
16
1 最短路径问题
从 A1出发到终点E最短路径为 A1 B1 C1 E * X “ 3 ( A1 ) B1 ”，决策变量 ； 从 A2 出发到终点E最短路径为A2 B1 C1 E “ X (A ) B ”，决策变量 ； 从 A3 出发到终点E最短路径为 A B C E * X B2 “ ”，决策变量 或 3 (A 3) B 1 S4 只可以取S，于是 最后，在阶段4：
1 1 2 1 f3 ( A1 ) min min 17; 5 14 d ( A1 , B2 ) f 2 ( B2 ) d ( A2 , B1 ) f 2 ( B1 ) 8 11 f3 ( A2 ) min min 19; 6 14 d ( A2 , B2 ) f 2 ( B2 ) d ( A3 , B1 ) f 2 ( B1 ) 7 11 f3 ( A3 ) min min 18 4 14 d ( A3 , B2 ) f 2 ( B2 )