文档介绍：第八、九讲动态规划
§1 引言
§2 动态规划的计算方法——递推方式
§1 引言(1)
动态规划是运筹学的重要分支之一,它是解决多阶段决策过程最优化的一种方法。该法是由美国数学家贝尔曼(R. Bellman)等人在本世纪50年代首先提出的。“动态规划”一书是动态规划方面的第一本著作。目前,动态规划已成功地用于解决资源分配、货物装运、设备更新、生产计划以及复合系统可靠性等许多问题。
§1 引言(2)
一、动态规划求解问题的思路
某旅客需从①号站到达⑩号站,试指出一条最短路径。交通状况如图3-1所示。
[解]一种习惯求解法是首先计算所有可能路线的距离,然后经比较选出一条最短路线,这称为显枚举或穷举法,当维数增大时,该法计算量将急剧增大,从而变得不可行。动态规划是采用递推方式使计算量大减,现简介其思路。
10
8
9
7
6
5
4
3
2
1
16
4
4
2
3
6
13
6
17
6
6
19
10
3
7
10
9
8
8,9
6
12
9
10
9
8
9
5
4
6
8
4
4
4
10
8
10
8
第5阶段
第4阶段
第3阶段
第2阶段
第1阶段
图3-1 最优旅行路线问题
图3-1中,圆圈内数字表示旅行可能通过的站号(状态号);
共分5个阶段;箭头表示旅行路线,箭头旁边数字表示距离。
§1 引言(3)
令x表示状态(站)号;
fi(x)表示从第i阶段x状态到达终点的最短距离;
di(x)表示从第i阶段x状态到达终点取最短路线时应到达的下一个状态(站)号。
1)假设旅客已到达第4阶段的⑧⑨状态
(i) 若已到达状态⑧,则只一条路可到达⑩
故 f4(8)=8 d4(8)=10
(ii)若已到达状态⑨,同理得f4(9)=4,d4(9)=10。
§1 引言(4)
2)假设旅客已到达第3阶段的⑤⑥⑦状态
(i) 若已到达状态⑤,有2条路可选:
⑤→⑧及⑤→⑨
此时应检查这两种选择中能达到的最短距离,即,比较下述i)及ii)并找出最小值。
i)从⑤到⑧的距离与⑧到终点的最短距离和
ii)从⑤到⑨的距离与⑨到终点的最短距离和。这两个值分别为4+f4(8)=12和8+f4(9)=12,两种费用相等,故得 f3(5)=12 d3(5)=8或9
§1 引言(5)
(ii)若已到达状态⑥,同理可得
f3(6)=min =min =10
对应d3(6)=9
(iii)若已到达状态⑦,同样得
f3(7)=min =8
d3(7)=9
按照同样方法,可算出旅客已到第2阶段和第1阶段的结果。
§1 引言(6)
把上述计算结果全部标在图3-1上的状态点附近。其中,圆圈上方数字表示该状态点的最短距离,圆圈下方数字表示该状态点的最优决策。
最后,根据计算结果,可找出从①到⑩的最短路线为
①→④→⑥→⑨→⑩。
§1 引言(7)
二、最优化原理
最优化原理可阐述如下:
“一个最优策略具有这样的性质:不论初始状态和初始决策如何,相对于第1个决策所形成的状态来说,余下决策必定构成一个最优策略”。
如图3-2中,若路线I和II是A到C的最优路线,则根据最优化原理,路线II必是从B到C的最优路线。
A
Ⅰ
C
B
II’
图3-2
II
§1 引言(8)
三、动态规划中的主要名词术语
(Stage):把问题分成几个相互联系的有顺序的几个环节,通常用k表示。
(State):表示某阶段的出发位置或状态值,通常用x表示。
(Decision):从某阶段的1个状态演变到下一阶段某状态的选择,通常用d或u表示。