1、 毕业论文 开题报告 信息与计算科学 动态规划在经济管理中的应用 一、选题的背景、意义 1.选题的背景 21 世纪中国进入到了一个新的时代，随着经济的快速发展和社会的进步，整个社会运行的各个方面 无论是在政治、经济、文化、科技、军事、外交方面，还是在环境、生态、资源问题方面，都将着眼于解决能否实现的问题扩充到更加重视解决如何优化实现的问题，从解决局部的简单问题扩充到解决系统的复杂问题，从静态地解决问题到动态地解决问题，从解决涉及单一领域的独立发展问题扩充到解决涉及多个领域的协同发展的问题，从通过直接办法 解决问题扩充到通过间接的办法解决问题等，都迫切需要动态规划及其应用。 随着计算机技术的发展
2、和普及，动态规划的应用越来越广泛。它已成为人们合理利用有限资源制定最佳决策的有利工具。 12 2.选题的意义 作为运筹学 OR 的一个分支，动态规划是分析和解决多阶段决策过程最优化的理论与办法，根据动态规划思想，可以根据人们所采取的措施一步步地控制过程的发展，以实现预定的要求。 这以运筹学分支最初是由美国数学家 Bellman 等人根据一类多阶段决策问题的特性，提出了解决这类问题的最优化原理，并研究了许多实际问题而建立起来 的。 3 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便
3、地求解。 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能 的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。 二
4、、研究的基本内容与拟解决的主要问题 2.1 动态规划概述 动态规划是 解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼（ R Bellman）等人在 20 世纪 50 年代提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的最优化原理，并 成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支。 1957 年， R Bellman 发表了该分支领域的第一本专著动态规划（ Dynamic Programming）。 动态规划是现代企业管理中的一种重要决策方法，可用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的
5、最优控制等。由于它有独特的解题思路，在处理某些优化问题时，比线性规划或非线性规划方法更有效。 45 动态规划可以高效地解决许多用“贪心算法”或“分治算法”难以解决的最优解的问题 。用动态规划解题，首先要把原问题分解为若干子问题，这一点与递归方法类似。动态规划与递归的区别在于：单纯的递归往往会导致子问题的解一旦被求出就会被保存，所以，每个子问题只需求解 1次。 6 2.2 动态规划在经济管理中的应用 2.2.1 多阶段决策过程的最优化 7 多阶段决策过程，是一类特殊的活动过程，它可以按时间顺序分解成若干相互联系的阶段，每个阶段称为“时段”。在每个时段都需要做出决策，全部过程的决策是一个决策序故多
6、阶段决策问题属贯决策问题。 多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最 优。由于各阶段决策间有机地联系着，所以本阶段决策的执行将影响到下一段的决策，以至于影响总体效果，故决策者在短阶段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全面来讲是最优的决策。 使用动态规划方法解决多阶段决策问题，首先耍将实际问题写成动态规化模型，具体包括以下思想： (一 )将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题，然后逐个求解。 (二 )求解时从边界条件开始，逆 (或顺 )过程行进方向，逐段递推寻优。在每一个子问题求解
7、时，都要 使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。 (三 )动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法， 因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。动态规划的基本方程是递推逐段求解的根据，一般的动态规划基本方程可以表为： 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
8、 为状态 ks 、 决策 ku 时对应的第 k 阶段的指标函数值。 2.2.2动态规划建模 (1)将实际问题的过程划分成恰当阶段，确定阶段变量 根据多阶段决策问题的实际过程，将其划分为若干个相互独立又相互联系的部分，每一个部分为一个阶段，划分出的每一个阶段通常就 是需要做出一个决策的子问题目。阶段通常是按决策进行的时间或空间上的先后顺序划分的，阶段变量用表示。 (2)确定状态，正确选择状态变量 在多阶段决策过程中，状态是描述每个阶段所必须的信息，表示每个阶段开始时所处的自然状况或客观条件。一个阶段有若干个状态，用一个或一组变量来描述，状态变量必须既能描述过程的演变，又要满足无后效性。用表示第个
9、阶段的状态变量。 (3)确定决策变量及允许的决策集合 决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。决策变量用 kx 表示；允许的决策集合是决策变量的取值范围用 ()kkDs 表示。 (4)写出状态转移方程 状态转移方程 1 ( , )k K k ks T s x ，这里的函数关系 KT 因问题的不同而不同，如果给定第k 个阶段的状态变量 ks ，则该阶段的决策变量 kx 一经确定，第 1k 阶段的状态变量的值也就可以确定。 (5)列出指标函数 指标函数 knv 的关系，并要求具有可分离性及递推性； (6)写出动态规划函数基本方程，用 1()knfs 表示 k
10、n 阶段的最优策略函数： 11( ) 0 ( )nnfx 边 界 条 件 1( ) , , 1 , , 1k k k kf s o p t v f k n n 8 2.2.3 动态规划在经济管理中的应用 9 1背包问题 1)一维背包问题 (1)问题 有一个人带一个背包上山，其可携带物品重量的限度为 a 公斤。设有 n 种物品可供他选择装入背包中，这 n 中物品编号为 1， 2， ， n 。已知第 i 种物品每件重量为 iw公斤，在上山过程中的作用 (价值 )是携带数量 ix 的函数 ()iicx 。问此人应如何选择携带物品(各几件 )，使所有作用（总价值 )最大。这就是著名的背包问题，类似的问
11、题有工厂里的下料问题，运输中的货物装载问题，人造卫星内的物品装载问题等等。 (2)模型及其解法 设 ix 为第 i 种物品的装入件数，则问题的数学模型为： 11m a x ( )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
12、x k n 然后，逐步计算出最优值函数 1 2 3( ) , ( ) , ( ) , ( )nf w f w f w f w及相应的 决策函数1 2 3( ) , ( ) , ( ) , ( )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
13、x bx j n 且 为 整 数用动态规划方法来解，其思想方法与一维背包问题完全类似，只是这时的状态变量是两个 (重量和体积的限制 )，决策变量仍是一个 (物品的件数 )。设最优值函数 ( , )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 即为所求的最大价值。
14、 10 2设备更新问题 (1)问题 从经济上来分析，一种设备应该用多少年后进行更新为恰当，即更新的最佳策略应该如何。从而使在某 时间内的总收入达到最大 (或总费用达到最小 )。现以一台机器为例，随着使用年限的增加，机器的使用效率降低，收入减少，维修费用增加，而且机器使用年限越长，它本 身的价值就越小，因而更新时所需的净支出费用就愈多。 (2)模型及其解法 设 jI 为在第 j 年机器役龄为 t 年的一台机器运行所得的收入。 ()jOt为在第 j 年机器役龄为 t 年的一台机器运行所需运行费用。 ()jCt为在第 j 年机器役龄为 t 年的一台机器更新时所需要更新净费用。 a 为折扣因子 (O
15、a 1)，表示一年以后的单位收入的价值视为现年的 a 单位。 T 表示在第一年开始时，正 在使用的机器的役龄。 N 表示计划的年限总数。 jg()t 表示在第 j 年开始使用一个役龄为 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
16、 j T 由于研究的是今后 n 年的计划，故还要求： 1( ) 0ngt 。 11 3生产与存储问题 (1)问题 要制定一个 n 阶段 (年 )的生产 (或购买 )计划：设 kd 为第 k 阶段对产品的需求量， ix 为第 k 阶段产品的生产 (或采购 )量， kv 为第 k 阶段结束时的产品库存量， ()kkcx 表示第 k 阶段生 产 kx 时的成本， ()kkhv 表示第 k 阶段结束时有库存量 kv 所需的存储费用， m表示每阶段产品的最大生产能力。 若第 1阶段之初和第 n 阶段结束的库存量为 0，每阶段的需求确定，则如何制定生产 (或采购 )计划，使 n 阶段的总成本最小 ? （
17、2）模型及解法 1m i n ( ) ( )nj j j jjZ c x h v 010. . ( ) , 2 , 3 , , 10 , 1 , 2 , ,nkk j jjjvvs 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 阶段之末库存量为 k
18、v 时的最小总费用。 12 2.2.4动态规划的应用举例 设某工厂有 1 000台机器，生产两种产品 A 、 B ,若投入 y 台机器生产 A 产品 ,则纯收入为 5y ， 若投入 y 台机器生产 B 种产品，则纯收入为 4y ， 又知生产 A 种产品机器的年折损率为 20%， 生产 B 产品机器的年折损率为 10%， 问在 5年内如何安排各年度的生产计划，才能使总收入最高？ 解 年度为阶段变量 1,2,3,4,5k ，状态 kx 为第 k 年初完好的机器数，决策 ku 为第 k 年投入产品 A 的台数。当 kx 或 ku 不是整数时，将小数部分理解为一年中正 常工作时间或纯收入的比例。 因为
19、第 k 年投入产品的 B 台数为 kkxu ， 所以状态转移方程是 1 0 . 8 0 . 9 ( ) 0 . 1 0 . 9k k k k k kx u x u u x 阶段指标 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 、
20、2 年投入产品 B 分别为 1000 、 900 台，不投入产品 A ，第 3 、 4 、 5 年投入产品 A 分别为 720、 576、 460.8台而不投入产 品 B ， 获得总收入最高为17482y 。 13 三、研究的方法与技术路线、研究难点，预期达到的目标 1.研究内容 （ 1）了解动态规划产生的背景及意义，知道动态规划的基本发展历程。 （ 2）对动态规划问题有深刻认识，掌握解决动态规划问题的基本方法，了解动态规划研究的基本问题。 （ 3）清楚动态规划理论今后的发展方向及进一步研究需要的知识。 （ 4）对于动态规划在经济管理中的应用问题能很好解决。 2.研究方法及技术路线 本论文主要
21、以查找资料、参考文献，以学过的相关知识，在前人的研究论述基础上，应用动态规划的基本方法来解决基本动态规划问题，并用来优化社会中的常见问题。采取了从大量阅读已有的数据资料 然后对这些内容进行归纳总结 最后运用相关知识来求解及应用的技术路线 。 3、研究难点 （ 1）对动态规划的基本方法及它的应用的掌握程度有待加强，对动态规划的方法及应用的广度有待拓宽； （ 2）动态规划问题没有统一的处理方法，求解时要根据问题的性质，结合多种数学技巧。14 （ 3）当变量个数太多时，由于计算机内存和速度的限制将导致 问题无法解决。 15 （ 4）有些问题由于涉及的函数没有理想的性质而使问题只能用动态规划描述，而不
22、能用动态规划方法解决。 4、预期达到的目标 通过这次论文的撰写更好的了解了动态规划的发展历程，深入的认识了动态规划问题，更好的掌握了解决动态规划问题的方法，并会应用此方法来经济管理中常见的优化问题，同时还可以结合其他知识来综合解决这类问题。除此，对动态规划的掌握，还能更好的学习其他相关理论，能更容易的更好的解决这类问题。 四、论文详细工作进度和安排 第 7 学期第 9 周（ 2010 年 11 月 5 号）至第 7 学期第 19 周（ 2011 年 1 月 10 号） 完成毕业论文文献检索、文献综述、外文文献翻译及开题报告。 第 7 学期第 19 周（ 2011 年 1 月 10 号）至第 8
23、 学期第 3 周（ 2011 年 3 月 11 号） 完成毕业论文的数据收集、论文初稿。 第 8 学期第 3 周（ 2011 年 3 月 11 号）至第 8 学期第 11 周（ 2011 年 5 月 3 号） 1、进入实习单位进行毕业实习，对论文进行修改； 2、第 11 周（ 2011 年 5 月 3 日）前必须返校，完成毕业实习返校，并递交毕业实习报告，进一步完善毕业论文； 第 8 学期第 14 周（ 2011 年 5 月 23 号 2011 年 5 月 28 号）完成第一 轮毕业论文答辩； 第 8 学期第 15 周（ 2011 年 5 月 28 号 2011 年 6 月 3 号） 第一轮毕
24、业论文答辩未通过的学生完成第二轮毕业论文答辩，并随机抽取部分完成较好地毕业论文进行校级答辩。 五、主要参考文献： 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
25、 Research(Eighth Edition)M.北京 :清华大学出版社 ,2006,1:440-440. 4 曹卫华 ,郭正 .最优化技术方法及 MATLAB 的实现 M.北京 :化学工业出版社 ,2005,1:4-4. 5 胡运权 ,郭耀煌 .运筹学教程 (第三版 )M.北京 :清华大学出版社 ,2007,4:191-191. 6 曾棕根 .动态规划法解算多阶段决策问题研究 J.宁波职业技术学院学报 .2009,13(5):82-82. 7 宋烊 ,崔梦天 .动态规划在企业生产与储存管理中的应用 J.企业科技 .2006,(6):50-51. 8 孙晓燕 ,李自良 ,彭雄凤 ,傅亚力
26、,梁志强 .利用动态规划法求解运输问题的最短路径 J.机械设计与制造 .2010,(2):224-224. 9 宋达霞 .动态规划在经济管理中的应用研究 J.科技信息 .2007,(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.
