4动态规划.ppt

4 动态规划
教学目的与要求
通过对本章的学习,使学生对多阶段决策问题的产生发展和研究现状有基本的了解,对动态规划在现代物流管理中的运用有较全面的认识,了解动态规划方法的含义及其基本特点,明确动态规划模型的基本思想,掌握动态规划的基本概念和动态规划模型的建立,掌握求解动态规划问题的逆序递推法和顺序递推法,能够将动态规划的方法应用在现代物流管理实践中。
动态规划英文名称为“Dynamic Programming”,简称DP,它是规划论的重要内容,同时也是运筹学的一个重要分支,是解决多阶段决策过程最优化问题的一种重要理论和方法。目前已广泛应用于工程技术、经济管理、工业生产及军事等部门,特别是在动态系统的最优控制方面取得了显著的效果。
4 动态规划
多阶段决策问题的提出
动态规划模型
动态规划的解法
动态规划应用举例
◎知识归纳
◎习题与思考题
多阶段决策问题的提出
动态规划概述
规划问题的最终目的就是确定各决策变量的取值,以使目标函数达到极大或极小。在线性规划和非线性规划中,决策变量都是以集合的形式被一次性处理的;然而,有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。
所谓多阶段决策问题是指这样一类活动过程:它可以分解为若干个互相联系的阶段,在每一阶段分别对应着一组可供选取的决策集合,即构成过程的每个阶段都需要进行一次决策。将各个阶段的决策综合起来构成一个决策序列,称为一个策略。显然,由于各个阶段选取的决策不同,对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时,相应可以得到一个确定的效果,采取不同的策略,就会得到不同的效果。多阶段的决策问题,就是要在所有可能采取的策略中选取一个最优策略,以便得到最佳的效果。动态规划同前面介绍过的各种优化方法不同,它不是一种算法,而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术,可以说它横跨整个规划领域(线性规划和非线性规划)。当然,由于动态规划不是一种特定的算法,因而它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则,动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中,有些问题对阶段的划分具有明显的时序性,动态规划的“动态”二字也由此而得名。
动态规划的主要创始人是美国数学家贝尔曼。20世纪40年代末50年代初,当时在兰德公司从事研究工作的贝尔曼首先提出了动态规划的概念。1951年贝尔曼首先提出了动态规划中解决多阶段决策问题的最优化原理,并给出了许多实际问题的解法。1957年贝尔曼出版了他的第一部著作《动态规划》,标志着运筹学这一重要分支的诞生。该著作成为当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作,并于1962年同杜瑞佛思合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时,其他一些学者也对动态规划的发展作了巨大的贡献,其中最值得一提的是爱尔思和梅特顿。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作,并于1964年同尼母霍思尔、威尔德一道创建了处理分支、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点,并且对明晰动态规划路径的数学性质作出了巨大的贡献。
动态规划从创立到现在50多年来,无论在工程技术、企业管理还是在工农业生产及军事等部门都有着广泛的应用,并取得了显著的效果。在管理方面,动态规划可用于资源分配问题、最短路径问题、库存问题、背包问题、设备更新问题、最优控制问题等等,所以动态规划是现代管理学中进行科学决策不可缺少的工具。
动态规划的优点在于,它把一个多维决策问题转化为若干个一维最优化问题,而对一维最优化问题一个一个地去解,这种方法是许多求极值方法所做不到的,它几乎优于所有现存的优化方法。除此之外,动态规划能求出全局极大或极小,这一点也优于其他优化方法。需要指出的是,动态规划是求解最优化问题的一种方法,是解决问题的一种途径,而不是一种算法。在前面我们学习了用单纯形法解线性规划问题,凡是具有线性规划问题那样统一的数学模型都可以用单纯形法去求解,而
动态规划问题的求解却没有统一的方法(类似于单纯形法)。因此在用动态规划求解最优化问题中,必须对具体问题具体分析,针对不同的问题,使用动态规划最优化原理和方法,建立起与其相应的数学模型,然后再用动态规划方法去求解。根据动态规划这些特点,要求我们在学好动态规划的基本原理和方法的同时,还应具有丰富的想象力,只有这样才能建好模型求出问题的最优解。
动态规划在现代物流中的应用
动态规划在现代物流中的应用十分广泛,除了生产过程优化、设备改造更新,还有最优路径、最佳库存、合理配载、资源分配以及排