动态规划在经济管理中的应用文献综述.doc

动态规划在经济管理中的应用文献综述 文献综述动态规划在经济管理中的应用前言部分 动态规划是解决多阶段决策过程最优化问题的一种数学规划方法这类问题的特点是,它涉及的活动过程可以划分为若干个互相联系的阶段,在每个阶段都需要做出决策,且前一阶段的决策影响后一阶段的决策,从而影响整个过程的活动方式。各个阶段所采取的决策,构成一个决策序列,称为策略。由于每个阶段可供采取的决策通常有多个可以选择,因而也就可以构成多个策略。按不同策略进行活动的经济效果往往不一样,因此,要按给定的评价指标衡量,哪一个策略的效果好,以求得最优策略。 动态规划在经济、工程技术、工业生产及军事等许多领域都有着重要的应用。动态规划的处理方法是用一种称为“最优化原则”的思想方法导出一个函数方程,然后求解。1 线性规划研究目标函数和约束条件都特别简单的优化(极值)问题。2与线性规划相比,动态规划没有一个标准的数学模型。然而,动态规划是一类很普遍的问题解决方法,需要建立特定的方程以适应各种情况。因而,对动态规划问题总体结构要求一定程度上的独创性和洞察力,以识别何时以及如何通过动态规划的方法解决问题,这些能力可以通过大范围的动态规划应用和对其普遍特性的研究形成。3二、主题部分 2.1 动态规划概述 动态规划是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼(R Bellman)等人在20世纪50年代提出的。他们针对多阶段决策问题的特点,提出了解决这类问题的最优化原理,并成功地解决了生产管理、工程技术等方面的许多实际问题,从而建立了运筹学的一个新分支。1957年,R Bellman发表了该分支领域的第一本专著动态规划(Dynamic Programming)。 动态规划是现代企业管理中的一种重要决策方法,可用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的最优控制等。由于它有独特的解题思路,在处理某些优化问题时,比线性规划或非线性规划方法更有效。45 动态规划可以高效地解决许多用“贪心算法”或“分治算法”难以解决的最优解的问题。用动态规划解题,首先要把原问题分解为若干子问题,这一点与递归方法类似。动态规划与递归的区别在于:单纯的递归往往会导致子问题的解一旦被求出就会被保存,所以,每个子问题只需求解1次。6 2.2动态规划在经济管理中的应用 2.2.1多阶段决策过程的最优化7 多阶段决策过程,是一类特殊的活动过程,它可以按时间顺序分解成若干相互联系的阶段,每个阶段称为“时段”。在每个时段都需要做出决策,全部过程的决策是一个决策序故多阶段决策问题属贯决策问题。 多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。由于各阶段决策间有机地联系着,所以本阶段决策的执行将影响到下一段的决策,以至于影响总体效果,故决策者在短阶段决策时不应仅考虑本阶段最优,还应考虑对最终目标的影响,从而做出对全面来讲是最优的决策。 使用动态规划方法解决多阶段决策问题,首先耍将实际问题写成动态规化模型,具体包括以下思想: 一将多阶段决策过程划分阶段,恰当地选取状态变量、决策变量及定义最优指标函数,从而把问题化成一族同类型的子问题,然后逐个求解。 二求解时从边界条件开始,逆或顺过程行进方向,逐段递推寻优。在每一个子问题求解时,都要使用它前面已求出的子问题的最优结果,最后一个子问题的最优解,就是整个问题的最优解。 三动态规划方法是既把当前一段与未来各段分开,又把当前效益和未来效益结合起来考虑的一种最优化方法, 因此每段的最优决策选取是从全局考虑的,与该段的最优选择一般是不同的。动态规划的基本方程是递推逐段求解的根据,一般的动态规划基本方程可以表为:式中可根据求解问题取或,为状态、决策 时对应的第阶段的指标函数值。 2.2.2动态规划建模 1将实际问题的过程划分成恰当阶段,确定阶段变量 根据多阶段决策问题的实际过程,将其划分为若干个相互独立又相互联系的部分,每一个部分为一个阶段,划分出的每一个阶段通常就是需要做出一个决策的子问题目。阶段通常是按决策进行的时间或空间上的先后顺序划分的,阶段变量用表示。 2确定状态,正确选择状态变量 在多阶段决策过程中,状态是描述每个阶段所必须的信息,表示每个阶段开始时所处的自然状况或客观条件。一个阶段有若干个状态,用一个或一组变量来描述,状态变量必须既能描述过程的演变,又要满足无后效性。用表示第个阶段的状态变量。 3确定决策变量及允许的决策集合 决策的实质是关于状态的选择,是决策者从给定阶段状态出发对下一阶段状态作出的选择。决策变量用表示;允许的决策集合是决策变量的取值范围用表示。 4写出状态转移方程 状态转移方程,这里的函数关系因问题的不同而不同,如果给定第个阶段的状态变量,则该阶段的决策变量一经确定,第阶段的状态变量的值也就可以确定。 5列出指标函数 指标函数的关系,并要求具有可分离性及递推性; 6写出动态规划函数基本方程,用表示阶段的最优策略函数: 8 2.2.3 动态规划在经济管理中的应用9 1、背包问题 1一维背包问题 1问题 有一个人带一个背包上山,其可携带物品重量的限度为公斤。设有种物品可供他选择装入背包中,这中物品编号为1,2,。已知第种物品每件重量为公斤,在上山过程中的作用价值是携带数量的函数。问此人应如何选择携带物品各几件,使所有作用(总价值最大。这就是著名的背包问题,类似的问题有工厂里的下料问题,运输中的货物装载问题,人造卫星内的物品装载问题等等。 2模型及其解法 设为第种物品的装入件数,则问题的数学模型为: 它是一个整数规划问题。如果只取0或1,又称为0?1背包问题。下面用动态规划的方法来求解,可写出动态规划的顺序递推关系式为: 然后,逐步计算出最优值函数及相应的决策函数,最后得出的 就是所求的最大价值,其相应的最优策略由反推运算即可得出。 2)二维背包问题 1问题 如果还增加背包体积的限制为,并假设第种物品每件的体积为立方米,问应如何装使得总价值最大。 2模型及其解法:它的数学模型为: 用动态规划方法来解,其思想方法与一维背包问题完全类似,只是这时的状态变量是两个重量和体积的限制,决策变量仍是一个物品的件数。设最优值函数,表示当总重量不超过公斤,总体积不超过立方米。背包中装入第1种到第种物品的最大使用价值。故可写出顺序逆推关系式为:最后算出即为所求的最大价值。10 2.设备更新问题 1问题 从经济上来分析,一种设备应该用多少年后进行更新为恰当,即更新的最佳策略应该如何。从而使在某?时间内的总收入达到最大或总费用达到最小。现以一台机器为例,随着使用年限的增加,机器的使用效率降低,收入减少,维修费用增加,而且机器使用年限越长,它本身的价值就越小,因而更新时所需的净支出费用就愈多。 2模型及其解法 设为在第年机器役龄为年的一台机器运行所得的收入。 为在第年机器役龄为年的一台机器运行所需运行费用。 为在第年机器役龄为年的一台机器更新时所需要更新净费用。 为折扣因子O1,表示一年以后的单位收入的价值视为现年的单位。 表示在第一年开始时,正在使用的机器的役龄。 表示计划的年限总数。表示在第年开始使用一个役龄为年的机器时,第年至第年内的最佳收入。表示给出时,在第年开始时的决策保留或更新。即得递推关系式为:由于研究的是今后年的计划,故还要求:。11 3.生产与存储问题 1问题 要制定一个阶段年的生产或购买计划:设为第阶段对产品的需求量,为第阶段产品的生产或采购量,为第阶段结束时的产品库存量,表示第阶段生产时的成本,表示第阶段结束时有库存量所需的存储费用,表示每阶段产品的最大生产能力。 若第1阶段之初和第阶段结束的库存量为0,每阶段的需求确定,则如何制定生产或采购计划,使阶段的总成本最小? (2)模型及解法 状态转移方程 第阶段的指标为:其中 最优指标函数表示从第1阶段之初库存量为0到第阶段之末库存量为时的最小总费用。12 2.2.4动态规划的应用举例 设某工厂有1 000台机器,生产两种产品、,若投入台机器生产产品,则纯收入为,若投入台机器生产种产品,则纯收入为,又知生产种产品机器的年折损率为20%,生产产品机器的年折损率为10%,问在5年内如何安排各年度的生产计划,才能使总收入最高?解 年度为阶段变量,状态为第年初完好的机器数,决策为第年投入产品的台数。当或不是整数时,将小数部分理解为一年中正常工作时间或纯收入的比例。 因为第年投入产品的台数为,所以状态转移方程是 阶段指标是第年的产量,有 指标函数是阶段指标之和,最优值函数满足 及自由终端条件 利用MATLAB编程求解得第1 、2 年投入产品分别为1000 、900 台,不投入产品,第3 、4 、5 年投入产品分别为720、576、460.8台而不投入产品,获得总收入最高为。13三、总结部分 本文首先介绍了动态规划产生的背景及发展历程,让大家对动态规划有了初步认识。动态规划是解决多阶段决策过程最优化问题的一种数学方法。它在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用。 动态规划方法有一些鲜明的特点:许多问题用动态规划研究求解比线性规划、非线性规划更有效,特别是对离散性问题,解析数学无用武之地,而动态规划就成为得力工具;在某些情况下,用动态规划处理不仅能最定性的描述分析,而且可以利用计算机给出求其数值解的方法。 但是动态规划方法也有致命的弱点:首先是没有统一的处理方法,求解时要根据问题的性质,结合多种数学技巧。因此,实践经验及创造性思维将起重要的引导作用。另外,就是所谓的“维数障碍”:当变量个数太多时,由于计算机内存和速度的限制将导致问题无法解决。有些问题由于涉及的函数没有理想的性质而使问题只能用动态规划描述,而不能用动态规划方法求解。14 然后介绍了动态规划在经济管理中的应用。虽然动态规划是由研究以时间为划分阶段的多阶段问题引出的,但是某些与时间无关的规划问题只要认为地引入时间因素,便可看出多阶段决策过程并用动态规划的方法来求解。此外某些不定期、无限期决策问题及非线性规划问题也可用动态规划的方法来求解。15四、参考文献1 邱菀华,冯允成,魏法杰,周泓.运筹学教程M.北京:机械工业出版社,2004,5:128-128.2 Leonid Nison Vaserstein,Christopher Cattelier Byrne.Introduction to Linear ProgrammingM.北京:机械工业出版社, 2006,1:3-3.3 Frederick S.Hillier,Gerald J.Lieberman. Introduction to Operations ResearchEighth EditionM.北京:清华大学出版社,2006,1:440-440.4 曹卫华,郭正.最优化技术方法及MATLAB的实现M.北京:化学工业出版社,2005,1:4-4.5 胡运权,郭耀煌.运筹学教程第三版M.北京:清华大学出版社,2007,4:191-191.6 曾棕根.动态规划法解算多阶段决策问题研究J.宁波职业技术学院学报.2009,135:82-82.7 宋烊,崔梦天.动态规划在企业生产与储存管理中的应用J.企业科技.2006,6:50-51.8 孙晓燕,李自良,彭雄凤,傅亚力,梁志强.利用动态规划法求解运输问题的最短路径J.机械设计与制造.2010,2:224-224.9 宋达霞.动态规划在经济管理中的应用研究J.科技信息.2007,36:140-141.10 韩伯棠.管理运筹学第2版M.北