文档介绍：运筹学第八章动态规划
第八章动态规划
引言
□动态规划是解决多阶段决策过程最优化的一种方法。
□该方法是由美国数学家贝尔曼(R1>. E. Bellman)等人在20世
纪50年代初提出的。并成功地解决了生产管理、工程技术等方
面的许多问题,从而建立了运筹学的一个新的分支,即动态规
划。Bellman在1957年出版了《Dynamic Programming》一
书,是动态规划领域中的第一本著作。
□动态规划与其他规划方法的不同之处在于:
动态规划是求解某类问题(多阶段决策问题)的一种方法,
是考察问题的一种途径,而不是一种特定算法。
因此,它不像线性规划那样有一个标准的数学表达式和明确
定义的一组(算法)规则,而必须对具体问题进行具体分析处
理。因此,学习动态规划时,除对基本概念和基本方法正确理解
外,还应在一定经验积累基础上,以丰富的想像力去建立模型,
用创造性的技巧去求解。
提纲
1 动态规划实例
2 动态规划的基本概念
3 动态规划的基本思想与基本原理
4 逆序解法与顺序解法
学习目标:
1 明确什么是多阶段的决策问题,特别要注意没有明显
的时段背景的问题如何化归为多阶段的决策问题。
1 动态规划实例
P156 例2 机器负荷分配问题(时间阶段问题)
◎设有某种机器设备,用于完成两类工作A和B。若第k年初完好
机器的数量为 xk ,若以数量 uk 用于A,余下的(xk-uk)用于
工作B,则该年的预期收入为 g( uk ) + h( xk-uk )。这里g( uk )
和 h( xk-uk )是已知函数,且 g( 0 ) = h( 0 ) = 0。
◎又机器设备在使用中会有损坏,设机器用于工作A时,一年后
能继续使用的完好机器数占年初投入量的70%;若用于工作B
时,一年后能继续使用的完好机器数占年初投入量的90%。则在
下一年初能继续用于A、B工作的设备数为 xk+1=+(xk-
uk)。
◎设第1年初完好的机器总数为1000台,问在连续5年内每年应如
何分配用于A、B两项工作的机器数,使5年的总收益为最大。
1 动态规划实例
□相应的问题称为多阶段决策问题。
□这是一个多阶段决策过程。
□该过程可以分为相互联系的若干阶段,每一阶段都需作出决
策,从而形成全过程的决策。
第1年
x1=1000
u1
第2年
x2=+
(x1-u1)
u2
第3年
x3=+
(x2-u2)
u3
第4年
u4
第5年
x5=+
(x4-u4)
u5
x4=+
(x3-u3)
x6
P156 例1 最短路线问题(空间阶段的例子)
设有一个旅行者从下图中的A点出发,途中要经过B、C、D等
处,最后到达终点E。从A到E有很多条路线可以选择,各点之间的距
离如图所示,问该旅行者应选择哪一条路线,使从A到达E的总的路程
为最短。
2
5
3
7
5
6
3
2
4
5
5
1
1
4
6
3
3
3
3
4
C1
C3
D1
A
B1
B3
B2
D2
E
C2
1
2
3
4
状态1
决策1
状态2
状态3
状态4
状态5
决策2
决策3
决策4
□可看成
4阶段
的决策
问题。
□从以上两个例子,可以知道
所谓多阶段决策问题是指这样的决策问题:其过程可分为若
干个相互联系的阶段,每一阶段都对应着一组可供选择的决策,
每一决策的选定既依赖于当前面临的状态,又影响以后总体的效
果。
当每一阶段的决策选定以后,就构成一个决策序列,称为一
个策略,它对应着一个确定的效果。多阶段决策问题就是寻找使
此效果最好的策略。
多阶段决策过程的特点
□多阶段决策过程最优化的目的,是要达到整个活动过程的总体
效果最优,而不是某个阶段“局部”的效果最优。因此,各个阶段
决策的选取不是任意确定的。
□前一个决策的选取决定了当前状态,当前状态进行决策后又影
响到下一阶段的状态和决策,以至于影响总体效果。所以决策者
在每个阶段决策时,不应仅考虑本阶段最优,还应考虑对最终目
标的影响,从而做出对全局而言是最优的决策。
□动态规划就是符合这一要求的一种最优化方法。
“时间”有关
□动态规划方法与“时间”关系很密切,随着时间过程的发展而决
定各阶段的决策,从而产生一个决策序列,这就是“动态”的意
思。
□但是,一些与时间无关的静态问题,只要在问题中人为