运筹学第6章new.ppt

运筹学
讲授者:张宏民
第六章动态规划
动态规划问题与数学模型
动态规划是运筹学的一个重要的分支,它是一种将复杂的多阶段决策问题转化为一系列比较简单的最优化问题的方法,它的基本特征是优化过程的多阶段性。
动态规划是一种用于处理多阶段决策问题的数学方法,主要是先将一个复杂的问题分解成相互联系的若干阶段,每个阶段即为一个子问题,然后逐个解决,当每个阶段的决策确定之后,整个过程的决策也就确定了,阶段一般用时间段来表示,这就是动态的含义,把这种处理问题的方法称为动态规划方法。
动态规划的创始人是美国数学家贝尔曼().它在四十年代后期和五十年代初期在美国兰德公司工作,针对一些多阶段决策问题提出了解决这类问题的最优化原理,并在1957年出版了动态规划的第一本书《Dynamic programming》.
目前动态规划已经用于解决最优路径问题、资源分配问题、生产调度问题、设备更新问题、复合系统可靠性问题及生产过程最优控制等,并且取得了显著的效果。
所谓多阶段决策问题,是指一个大问题可以划分为若干个阶段,每个阶段形成一个子问题,各个阶段是互相联系的,每个阶段都要作出决策,并且一个阶段的决策确定以后会影响下一阶段的决策,,称为一个策略,对于不同的策略其效果不同(效果可以用数量来衡量).多阶段决策问题就是选择一个最优策略,使在给定的标准下达到最好的效果.
多阶段决策问题中,各个阶段一般是按照时间来划分的,随着时间的发展而产生各个阶段的决策,从而形成决策序列,这就是动态的含义。
在一些与时间无关的静态问题中,可以人为地赋予时间的概念,使其成为一个多阶段决策问题,再用动态规划方法处理。
1
2
n

状态
决策
状态
决策
状态
状态
决策
一、多阶段决策问题举例
属于多阶段决策类的问题很多,例如:
工厂生产过程:由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排。
设备更新问题:一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高。随着使用年限的增加,就会逐渐变为故障多,维修费用增加,可正常使用的工时减少,加工质量下降,经济效益差。并且,使用的年限越长、处理价值也越低,如果卖出旧的买新的,,使总的经济效益最好。
连续生产过程的控制问题:一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此,应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大。
以上所举问题的发展过程都与时间因素有关,因此在这类多阶段决策问题中,阶段的划分常取时间区段来表示,并且各个阶段上的决策往往也与时间因素有关,这就使它具有了“动态”的含义,所以把处理这类动态问题的方法称为动态规划方法。