动态规划资料.doc

动态规划是运筹学的一个分支。与其说动态规划是一种算法,不如说是一种思维方法来得更贴切。因为动态规划没有固定的框架,即便是应用到同一道题上,也可以建立多种形式的求解算法。第七章动态规划

第一讲概念及最短路问题
动态规划(Dynamic Programming)是20世纪50年代由美国数学家贝尔曼(Richard Bellman)及他的学生们一同建立和发展起来的一种解多阶段决策问题的优化方法。
所谓多阶段决策问题是指一类活动过程。它可按时间或空间把问题分为若干个相互联系的阶段。在每一阶段都要作出选择(决策),这个决策不仅仅决定这一阶段的效益,而且决定下一阶段的初始状态,从而决定整个过程的走向(从而称为动态规划)。每当一阶段的决策一一确定之后,就得到一个决策序列,称为策略。所谓多阶段决策问题就是求一个策略,使各个阶段的效益总和达到最优。
先声明:下面研究的解决多阶段的决策问题的最优化的称之为动态规划的数学方法,仅仅是一种解决问题的思路,而不是一种算法。这一点与线性规划不同。线性规划是一种算法。
下面从一典型的例子去说明动态规划的基本思想与原理:
某地要从A向F地铺设一条输油管道,各点间连线上的数字表示距离。问应选择什么路线,可是总距离最短?
5
C1
2
8
D1

4
3
3
B1
5
4
E1
C2
6
4
5
6
E2
C4
C3
F
A

3
D2

3
2
8
5

1
4
7

3
B2
D3

8
7

4



第一阶段第二阶段第三阶段第四阶段第五阶段

图7-1
先引入几个符号与概念:
(1) 阶段与阶段变量:先把问题从中间站B,C,D,E用空间位置分成5个阶段,阶段用阶段变量k来描述,k=1,表示第一阶段,k=2表示第二阶段,…
(2) 状态与状态变量:每一阶段的左端点(初始条件)集合称为本阶段的状态(即开始的客观条件,或称阶段初态)。如第三阶段有四个状态S3 ={C1 ,C2,C3,C4}, 第四阶段有三个状态 S4={D1, D2 , D3}, …
描述过程状态的变量称为状态变量:用小写s1 ,s2 ,s3 …表示第一,第二,第三…阶段的状态变量。当处在状态C2时,我们可记
s3= C2
“X=2”代表一事件一样。
(3) 决策与决策变量:如当处于C2状态时,下一步怎么走?如何选择路线?即如何决策。是走向D1,还是走向D2?当过程处于某一阶段的某一状态时,可以作出不同的决策(或选择),从而确定下一阶段的状态,这种决定(或选择)叫决策。如选择D2,记
u3(C2)= D2
说,当处于C2状态时,下一步的决策为D2。
其中表示第k阶段当状态处于时的决策变量。
一般地,用表示第k阶段从状态出发的允许决策集合。如
={D1 ,D2}
显然,∈。
(4)策略与最优策略:每一阶段产生一个决策,5个阶段的决策就构成一个决策序列:
,,,,
称为一策略。所谓策略是指按一定的顺序排列的决策组成的集合,也称决策序列。
这里的最短路径成为最优策略。
动态规划就是在允许策略集中选最优策略。
(5)状态转移方程:是描述由第k阶段到第k+1阶段状态转移规律的关系式。
=
上例中状态转移方程为:
=
(6)指标函数与最优指标函数:用于衡量所选定策略优劣的数量指标称为指标函数。相当于动态的目标函数,最后一个阶段的目标函数就是总的目标函数。它分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段,从状态出发,采用决策时的效益,用表示。最优指标函数是指从第k阶段状态采用最优策略到过程终止时的最佳效益值,用表示。
例如:d(C2, D1)是指由C2出发,下一阶段的决策是D1的两点间的距离。即
d(C2, D1)=4。表示从B1到F的最短距离。
整个问题即为=?
逆序递推法:
倒退着从F向A走,每倒退一步,思想上问自己:“从现在出发,退向何处?到F的距离最短?”我们分5步来解决问题:
k=5时
下求=?此时状态集S5={E1,E2},故分情况讨论,先说=?若最佳路径从A出发通过E1的话,由 E1到终点F的最短距离为
=5
同理,=3。(只有唯一的选择)故最优决策为:=F,=F
k=2时下求=?由于S4={D1, D2 , D3},下分四种情况进行讨论:
=min = min =7, = E1.
=min = min =5, = E2.
=min = min =5, = E1.
(3) k=3时 S3 ={C1 ,C2,C3,C4},
=min = min =12, = D1.
同理,=10, = D2.