运筹学7动态规划课件

第七章动态规划主要内容:71多阶段决过程的量优化动态的基本念和基本原求解74动应器教学要求1.掌握动态规划的基本概念:阶段、状态、决策、策略、状夵转移方程、指标函数和最优值函数、最优策略L线2.了解动态规划的基本理论:最优性定理和最优性原理3.掌握动态规划基本思想和基本方程4.牢固掌握动态规划的顺序解法和逆序解法。会处理动态与静态规划的关系5.了解和掌握若干典型问题的动态规划模型及求解技巧:如最短路线、资源分配、生产计划、货物存储设备更新与系统可靠性问题、背包问题、推销商问题6.了解多维动态规划降维方法和减少离散状态点数方法7.了解随机性问题的动态规划求解方法重点:动态规划顺序解法和逆序解法;若干典型问题动态规划模型及求解技巧;难点:建立动态规划数学模型的状态转移方程。87.1多阶段决策过程的最优化动态规划(DynamicProgramming)是运筹学的一个重要分支,它是解决多阶段决策过程最优化的一种方法。美国数学家贝尔曼(RE.Bellman)等人在50年代初提出了解决多阶段决策问题的“最优性原理”(PrincipleofOptimality)。1957年贝尔曼出版了专著“动态规划”,该书是动态规划的第一本著作。目前动态规划已经用于解决最优路径问题、资源分配问题、生产调度问题、设备更新问题、复合系统可靠性问题及生产过程最优控制等,并且取得了显著的效果回本章目录动态规划是求解问题的一种方法,而不是算法(线性规划是一种算法),因而没有标准的数学表达式,对于具体问题需要具体分析。、多阶段决策问题在生产经营活动中,某些问题决策过程可以划分为若于相互联系的阶段,每个阶段需要做出决策,从而使整个过程取得最优。由于各个阶段不是孤立的,而是有机联系的,也就是说,本阶段的决策将影响过程下一阶段的发展从而影响整个过程效果,所以决策者在进行决策时不能够仅考虑选择的决策方案使本阶段最优,还应该考虑本阶段决策对最终目标产生的影响,从而做出对全局来讲是最优的决策。当每个阶段的决策确定以后,全部过程的决策就是这些阶段决策所组成的一个决策序列,所以多阶段决策趣也称为序贯决策问题。决策状态状态状态状态决策决策多阶段决策问题中,各个阶段一般是按照时间来划分的,随着时间的发展而产生各个阶段的决策,从而形成决策序列,这就是动态的含义。在一些与时间无关的静态问题中(如非线性规划等),可以人为地赋予时间的概念,使其成为一个多阶段决策问题,再用动态规划方法处理二、多阶段决策问题举例属于多阶段决策类的问题很多,例如例1工厂生产过程:由于市场需求是随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者还季度地根据库存和需求情况决定生产计划安排例2设备更新问题:一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,维修费用增加,可正常使用的工时减少,加工质量下降,经济效益差,并且,使用的年限越长、处理价值也越低,自然,如果卖去旧的买新的,还需要付出更新费.因此就需要综合权衡决定设备的使用年限,使总的经济效益最好。例3连续生产过程的控制问题:一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此,应该如何