第6章_动态规划.ppt

第六章动态规划
动态规划的基本概念和基本原理
动态规划的建立与求解
本章内容重点
1
引言
动态规划(Dynamic Programming,DP)是解决多阶段决策问题及其他一些决策过程最优化的一种数量化方法,最早由美国数学家Bellman所建立。所谓多阶段决策问题,是指这样一类活动过程,即根据问题本身的特点,可以将其求解的全过程划分为若干个相互联系的阶段(即将问题划分为许多个相互联系的子问题),在它的每一阶段都需要作出决策,并且在一个阶段的决策确定以后再转移到下一个阶段。
2
前一个阶段的决策要影响到后一个阶段的决策,从而影响整个过程。人们把这样的决策过程称做多阶段决策过程(Multi-Stage decision process)。各个阶段所确定的决策就构成了一个决策序列,称为一个策略。一般来说,由于每一阶段可供选择的决策往往不止一个,因此,对于整个过程,就会有许多可供选择的策略。
3
1)工厂生产过程:由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排。
动态规划在企业管理方面的应用举例
4
2)设备更新问题:一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,维修费用增加,可正常使用的工时减少,加工质量下降,经济效益差,并且,使用的年限越长、处理价值也越低,自然,如果卖去旧的买新的,,使总的经济效益最好。
5
3)连续生产过程的控制问题:一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此,应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大。
6
4)最短路问题:如图6-1所示的运输网络,点间连线上的数字表示两地距离(也可是运费、时间等),要求从A至E的最短路线。
这种运输网络问题也是静态决策问题。但是,按照网络中点的分布,可以把它分为4个阶段,而作为多阶段决策问题来研究。
7
图6-1 最短路图示
C
B
A
B
D
B
C
D
E
C
5
1
2
3
2
3
1
2
7
7
7
6
6
8
9
8
8
8
7
8
5
8
9
8
D3
1
6
1
2
3
4
8
依据上述例子对动态规划的一些基本术语进一步加以说明和定义:
动态规划基本概念及基本原理
B
A
B
D
B
C
D
E
C
5
1
2
3
2
3
1
2
7
7
7
6
6
8
9
8
8
8
7
8
5
8
9
8
D3
C
1
6
1
2
3
4
图6-2 最短路图示
9
为了便于求解和表示决策及过程的发展顺序,而把所给问题恰当地划分为若干个相互联系又有区别的子问题,称之为多段决策问题的阶段。一个阶段,就是需要作出一个决策的子问题,通常,阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量,,图6—2所示的最短路问题就是一个四阶段决策过程。
(一) 阶段和阶段数
10