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

1、 毕业论文文献综述 信息与计算科学 动态规划在经济管理中的应用 一、 前言部分 动态规划是解决多阶段决策过程最优化问题的一种数学规划方法这类问题的特点是，它涉及的活动过程可以划分为若干个互相联系的阶段，在每个阶段都需要做出决策，且前一阶段的决策影响后一阶段的决策，从而影响整个过程的活动方式。各个阶段所采取的决策，构成一个决策序列，称为策略。由于每个阶段可供采取的决策通常有多个可以选择，因而也就可以构成多个策略。按不同策略进行活动的经济效果往往不一样，因此，要按给定的评价指标衡量，哪一个策略的效果好，以求得最优策略。 动态规划在经济、工程技术、工业生产及军事等许多领域都有着重要的应用。动态规划的

2、处理方法是用一种称为“最优化原则”的思想方法导出一个函数方程，然后求解。 1 线性规划研究目标函数和约束条件都特别简单的优化（极值）问题。 2与线性规划相比，动态规划没有一个标准的数学模型。然而，动态规划是一类很普遍的问题解决方法，需要建立特定的方程以适应各种情况。因而，对动态规划问题总体结构要求一定程度上的独创性和洞察力，以识别何时以及如何通过动态规划的方法解决问题，这些能力可以通过大范围的动态规划应用和对其普遍特性的研究 形成。 3 二、主题部分 2.1 动态规划概述 动态规划是 解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼（ R Bellman）等人在 20 世纪

3、50 年代提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的最优化原理，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支。 1957 年， R Bellman 发表了该分支领域的第一本专著动态规划（ Dynamic Programming）。 动态规划是现代企业管理中的一种重要决策方法，可用于解决最优路径问题、资源 分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的最优控制等。由于它有独特的解题思路，在处理某些优化问题时，比线性规划或非线性规划方法更有效。 45 动态规划可以高效地解决许多用“贪心算法”或“分治算法”难以解决的最优解的问题。用

4、动态规划解题，首先要把原问题分解为若干子问题，这一点与递归方法类似。动态规划与递归的区别在于：单纯的递归往往会导致子问题的解一旦被求出就会被保存，所以，每个子问题只需求解 1次。 6 2.2 动态规划在经济管理中的应用 2.2.1 多阶段决策过程的最优化 7 多 阶段决策过程，是一类特殊的活动过程，它可以按时间顺序分解成若干相互联系的阶段，每个阶段称为“时段”。在每个时段都需要做出决策，全部过程的决策是一个决策序故多阶段决策问题属贯决策问题。 多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。由于各阶段决策间有机地联系着，所以本阶段决策的执行将影响到下一段的决策，以至于影响总体效果

5、，故决策者在短阶段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全面来讲是最优的决策。 使用动态规划方法解决多阶段决策问题，首先耍将实际问题写成动态规化模型， 具体包括以下思想： (一 )将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题，然后逐个求解。 (二 )求解时从边界条件开始，逆 (或顺 )过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。 (三 )动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一

6、种最优化方法， 因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。动态规划的基本方 程是递推逐段求解的根据，一般的动态规划基本方程可以表为： 11()11( ) ( , ) ( ) , 1 , , 1( ) 0k k kk k k k k k ku D Snnf S o p t v S u f S k n nfS 式中 opt 可根据求解问题取 min 或 max ， ( , )k k kv s u 为状态 ks 、 决策 ku 时对应的第 k 阶段的指标函数值。 2.2.2动态规划建模 (1)将实际问题的过程划分成恰当阶段，确定阶段变量 根据多阶段决策问题的实际过程，将其划

7、分为若干个相互独立又相互联系的部分，每一个部分为一个阶段，划分出的每一个阶段通常就是需要做出一个决策的子问题目。阶段通常是按决策进行的时间或空间上的先后顺序划分的，阶段变量用表示。 (2)确定状态，正确选择状态变量 在多阶段决策过程中，状态是描述每个阶段所必须的信息，表示每个阶段开始时所处的自然状况或客观条件。一个阶段有若干个状态，用一个或一组变量来 描述，状态变量必须既能描述过程的演变，又要满足无后效性。用表示第个阶段的状态变量。 (3)确定决策变量及允许的决策集合 决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。决策变量用 kx 表示；允许的决策集合是决策变

8、量的取值范围用 ()kkDs 表示。 (4)写出状态转移方程 状态转移方程 1 ( , )k K k ks T s x ，这里的函数关系 KT 因问题的不同而不同，如果给定第k 个阶段的状态变量 ks ，则该阶段的决策变量 kx 一经确定，第 1k 阶段的状态变量的值也就可以确定。 (5)列出指标函数 指标函数 knv 的关系，并要求具有可分离性及递推性； (6)写出动态规划函数基本方程，用 1()knfs 表示 kn 阶段的最优策略函数： 11( ) 0 ( )nnfx 边 界 条 件 1( ) , , 1 , , 1k k k kf s o p t v f k n n 8 2.2.3 动态

9、规划在经济管理中的应用 9 1、背包问题 1)一维背包问题 (1)问题 有一个人带一个背包上山，其可携带物品重量的限度为 a 公斤。设有 n 种物品可供他选择 装入背包中，这 n 中物品编号为 1， 2， ， n 。已知第 i 种物品每件重量为 iw公斤，在上山过程中的作用 (价值 )是携带数量 ix 的函数 ()iicx 。问此人应如何选择携带物品(各几件 )，使所有作用（总价值 )最大。这就是著名的背包问题，类似的问题有工厂里的下料问题，运输中的货物装载问题，人造卫星内的物品装载问题等等。 (2)模型及其解法 设 ix 为第 i 种物品的装入件数，则问题的数学模型为： 11m a x (

10、)0 ( 1 , 2 , )nn iiiiiiiw x af c xx i n 且 为 整 数它是一个整数规划问题。如果 ix 只取 0或 1，又称为 0 1背包问题。下面用动态规划的方法来 求解，可写出动态规划的顺序递推关系式为： 11 1 10 ,1 ,( ) m a x ( )kwx wf w c x 10 ,1 ,( ) m a x ( ) ( ) , 2k kk k k k kwxwfk w c x f w w x k n 然后，逐步计算出最优值函数 1 2 3( ) , ( ) , ( ) , ( )nf w f w f w f w及相应的决策函数1 2 3( ) , ( ) ,

11、( ) , ( )nx w x w x w x w，最后得出的 ()nfa ( 就是所求的最大价值，其相应的最优策略由反推运算即可得出。 2）二维背包问题 (1)问题 如果还增加背包体积的限制为 b ，并假设第 i 种物品每件的体积为 iv 立方米，问应如何装使得总价值最大。 (2)模型及其解法： 它的数学模型为： 111m a x ( ), 1 , 2 , ,niiikni i i iiiiw x af c x v x bx j n 且 为 整 数用动态规划方法来解，其思想方法与一维背包问题完全类似，只是这时的状态变量是两个 (重量和体积的限制 )，决策变量仍是一个 (物品的件数 )。设最优

12、值函数 ( , )kf wv ，表 示当总重量不超过 w 公斤，总体积不超过 v 立方米。背包中装入第 1种到第 k 种物品的最大使用价值。故可写出顺序逆推关系式为 : 10 ( , )( , ) m a x ( ) ( , , ) , 1k kkk k k k k k k kwvxwvf w v c x f w w x v v x k n 0( , ) 0f wv 最后算出 ( , )nf ab 即为所求的最大价值。 10 2设备更新问题 (1)问题 从 经济上来分析，一种设备应该用多少年后进行更新为恰当，即更新的最佳策略应该如何。从而使在某 时间内的总收入达到最大 (或总费用达到最小 )。

13、现以一台机器为例，随着使用年限的增加，机器的使用效率降低，收入减少，维修费用增加，而且机器使用年限越长，它本身的价值就越小，因而更新时所需的净支出费用就愈多。 (2)模型及其解法 设 jI 为在第 j 年机器役龄为 t 年的一台机器运 行所得的收入。 ()jOt为在第 j 年机器役龄为 t 年的一台机器运行所需运行费用。 ()jCt为在第 j 年机器役龄为 t 年的一台机器更新时所需要更新净费用。 a 为折扣因子 (O a 1)，表示一年以后的单位收入的价值视为现年的 a 单位。 T 表示在第一年开始时，正在使用的机器的役龄。 N 表示计划的年限总数。 jg()t 表示在第 j 年开始使用一个

14、役龄为 t 年的机器时，第 j 年至第 n 年内的最佳收入。()jxt表示给出 jg()t 时 ,在第 j 年开始时的决策 (保留或更新 )。 即得递推关系式为： 1j1: (0 ) (0 ) ( ) ( 1 )g ( ) m a x ,: ( ) ( ) ( 1 )( 1 , 2 , , ; 1 , 2 , 1 , 1 )j j j jj j jR I O C t a gtK I t O t a g tj n t j j T 由于研究的是今后 n 年的计划，故还要求： 1( ) 0ngt 。 11 3生产与存储问题 (1)问题 要制定一个 n 阶段 (年 )的生产 (或购买 )计划：设 kd

15、 为第 k 阶段对产品的需求量， ix 为第 k 阶段产品的生产 (或采购 )量， kv 为第 k 阶段结束时的产品库存量， ()kkcx 表示第 k 阶段生产 kx 时的成本， ()kkhv 表示第 k 阶段结束时有库存量 kv 所需的存储费用， m表示每阶段产品的最大生产能力。 若第 1阶段之初和第 n 阶段结束的库存量为 0，每阶段的需求确定，则如何制定生产 (或采购 )计划，使 n 阶段的总成本最小 ? （ 2）模型及解法 1m i n ( ) ( )nj j j jjZ c x h v 010. . ( ) , 2 , 3 , , 10 , 1 , 2 , ,nkk j jjjvvs

16、 t v x d k nx m j n 且 为 整 数 ，状态转移方程 1 , 1 , 2 , ,k k k kv v x d k n 第 k 阶段的指标为： ( ) ( ) ( )k k k k k kf v c x h v其中 0 , 0( ) , 1 , 2 , ,kk k k kkxc x k a c x mxm 当当当最优指标函数 ()kkfx 表示从第 1阶段之初库存量为 0到第 k 阶段之末库存量为 kv 时的最小总费用。 12 2.2.4动态规划的应用举例 设某工厂有 1 000台机器，生产两种产品 A 、 B ,若投入 y 台机器生产 A 产品 ,则纯收入为 5y ， 若投入

17、 y 台机器生产 B 种产品，则纯收入为 4y ， 又知生产 A 种产品机器的年折损率为 20%， 生产 B 产品机器的年折损率为 10%， 问在 5年内如何安排各年度的生产计划，才能使总收入最高？ 解 年度为阶段变量 1,2,3,4,5k ，状态 kx 为第 k 年初完好的机器数，决策 ku 为第 k 年投入产品 A 的台数。当 kx 或 ku 不是整数时，将小数部分理解为一年中正常工作时间或纯收入的比例。 因为第 k 年投入产品的 B 台数为 kkxu ， 所以状态转移方程是 1 0 . 8 0 . 9 ( ) 0 . 1 0 . 9k k k k k kx u x u u x 阶段指标

18、kv 是第 k 年的产量，有 ( , ) 5 4 4k k k k k k k kv x u y u x u y u x 指标函数是阶段指标之和，最优值函数 ()kkfx 满足 110( ) m a x , , 0 1 0 0 0 , 5 , 4 , 3 , 2 , 1kkk k k k k k k kuxf x v x u f x x k 。 及自由终端条件 660fx 利用 MATLAB编程求解得第 1 、 2 年投入产品 B 分别为 1000 、 900 台，不投入产品 A ，第 3 、 4 、 5 年投入产品 A 分别为 720、 576、 460.8台而不投入产品 B ， 获得总收入

19、最高为17482y 。 13 三、总结部分 本文首先介绍了动态规划产生的背景及发展历程，让大家对动态规划有了初步认识。 动态规划是解决多阶段决策过程最优化问题的一 种数学方法。它在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用。 动态规划方法有一些鲜明的特点：许多问题用动态规划研究求解比线性规划、非线性规划更有效，特别是对离散性问题，解析数学无用武之地，而动态规划就成为得力工具；在某些情况下，用动态规划处理不仅能最定性的描述分析，而且可以利用计算机给出求其数值解的方法。 但是动态规划方法也有致命的弱点：首先是没有统一的处理方法，求解时要根据问题的性质，结合多种数学技巧。

20、因此，实践经验及创造性思维将起重要的引导作用。另外，就是所谓的“维数 障碍”：当变量个数太多时，由于计算机内存和速度的限制将导致问题无法解决。有些问题由于涉及的函数没有理想的性质而使问题只能用动态规划描述，而不能用动态规划方法求解。 14 然后介绍了动态规划在经济管理中的应用。虽然动态规划是由研究以时间为划分阶段的多阶段问题引出的，但是某些与时间无关的规划问题只要认为地引入时间因素，便可看出多阶段决策过程并用动态规划的方法来求解。此外某些不定期、无限期决策问题及非线性规划问题也可用动态规划的方法来求解。 15 四、参考文献 1 邱菀华 ,冯允成 ,魏法杰 ,周泓 .运筹学教程 M.北京 :机械

21、工业出版社 ,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 Research(Eighth Edition)M.北京 :清华大学出 版社 ,2006,1:440-440. 4 曹卫华 ,郭正 .最优化技术方法及 MATLAB 的实现 M.北京

22、:化学工业出版社 ,2005,1:4-4. 5 胡运权 ,郭耀煌 .运筹学教程 (第三版 )M.北京 :清华大学出版社 ,2007,4:191-191. 6 曾棕根 .动态规划法解算多阶段决策问题研究 J.宁波职业技术学院学报 .2009,13(5):82-82. 7 宋烊 ,崔梦天 .动态规划在企业生产与储存管理中的应用 J.企业科技 .2006,(6):50-51. 8 孙晓燕 ,李自良 ,彭雄凤 ,傅亚 力 ,梁志强 .利用动态规划法求解运输问题的最短路径 J.机械设计与制造 .2010,(2):224-224. 9 宋达霞 .动态规划在经济管理中的应用研究 J.科技信息 .2007,(

23、36):140-141. 10 韩伯棠 .管理运筹学 (第 2 版 )M.北京 :高等教育出版社 ,2005,7:209-214. 11 宁宣熙 ,王可定 ,党耀国 .管理运筹学教程 M.北京 :清华大学出版社 ,2007,8:155-157. 12 鲍祥霖 .运筹学 M.北京 :机械工业出版社 ,2005,8:91-92. 13 吴庆丰 , 刘兵兵 . 利 用 动 态 规 划 求 解 资 源 分 配 问 题 J. 安 庆 师 范 学 院 学 报 ( 自然科学版 ).2008,14(2):75-75. 14 徐渝 ,贾涛 .运筹学 (上册 )M.北京 :清华大学出版社 ,2005， 2:95-95. 15 袁子宁 .动态规划在投资分配问题中的应用 J.科技信息 .2007,(36):581-581.