1、 本科毕业论文（设计） （ 2011 届） 动态规划在经济管理中的应用 所在学院 专业班级 信息与计算科学 学生姓名 学号 指导教师 职称 完成日期 年 月 本科生毕业论文（设计） I 摘要： 动态规划是考察求解多阶段决策问题的途径和方法，最优化原理是动态规划的基础。动态规划方法求解问题可以有正向和逆 向两种思维方法，一般来说多阶段决策问题多采用动态规划逆向思维方法解决。本文通过动态规划在经济管理的应用举例说明怎样用动态规划方法解决实际问题，对于动态规划的经典问题进行了具体的分析。 给出了动态规划方法的基本原理，建立了动态规划数学模型，通过一些实际应用例子具体说明动态规划求解问题的过程，并总结
2、出动态规划在此类问题中的优越性。并阐述了动态规划方法求解问题的优势和解题注意事项。 关键词 : 动态规划；经济管理；多阶段决策 本科生毕业论文（设计） II Dynamic Programming in Economic Management Abstract ： Dynamic programming is one way to investigate multi-stage decision-making problem ， and the optimization principle is the basis of dynamic programming. Using dynamic p
3、rogramming method to solve problems can have two kinds of thinking methods， forward and reverse. Generally speaking, we always use reverse thinking method to solve multi-stage decision-making problems. This article through the dynamic planning in economic management application illustrates how to us
4、e dynamic programming method to solve practical problems， and gives a concrete analysis in the classic problems for dynamic planning. The article also gives the basic principle of the dynamic programming method, establishes the dynamic programming model， through some practical example specifies how
5、to solve some problems using dynamic programming, summarizes the superiority of dynamic programming in this problem. In the end, this article explains the advantages and attentions when using the dynamic programming method to solve problems Keywords: Dynamic programming; economic management; multi-s
6、tage decision-making 本科生毕业论文（设计） III 目录 1.绪论 . - 1 - 1.1 问题的背景 . - 1 - 1.2 问题的意义 . - 1 - 2.动态规划 . - 2 - 2.1 动态规划概述 . - 2 - 2.2 动态规划的基本概念 . 2 2.3 多阶段决策过程的最优化 . - 4 - 2.4 动态规划建模 . 5 3.动态规划在经济管理中的应用 . 6 3.1 背包问题 . 6 3.2 设备更新问题 . 7 3.3 生产与存储问题 . 8 3.4 资源分配问题 . 9 3.5 动态规划的应用举例 . 10 4.动态规划解题的好处及注意事项 . - 1
7、6 - 4.1 动态规划解题的好处 . - 16 - 4.2 动态规划解题的注意事项 . - 16 - 5.结束语 . - 17 - 致谢 . - 17 - 参考文献 . 19 本科生毕业论文（设计） - 1 - 1.绪论 1.1 问题的背景 21 世纪中国进入到了一个新的时代，随着经济的快速发展和社会的进步，整个社会运行的各个方面 无论是在政治、经济、文化、科技、军事、外交方面，还是在环境、生态、资源问题方面，都将着眼于解决能否实现的问题扩充到更加重视解决如何优化实现的问题，从解决局部的简单问题扩充到解决系统的复杂问题，从静态地解决问题到动态地解决问题，从解决涉及单一领域的独立发展问题扩充到
8、解决 涉及多个领域的协同发展的问题，从通过直接办法解决问题扩充到通过间接的办法解决问题等，都迫切需要动态规划及其应用。 随着计算机技术的发展和普及，动态规划的应用越来越广泛。它已成为人们合理利用有限资源制定最佳决策的有利工具。12 1.2 问题的意义 作为运筹学 O.R.的一个分支，动态规划是分析和解决多阶段决策过程最优化的理论与办法，根据动态规划思想，可以根据人们所采取的措施一步步地控制过程的发展，以实现预定的要求。 这以运筹学分支最初是由美国数学家 Bellman 等人根据一类多阶段决策问题的特性，提出了解决这 类问题的最优化原理，并研究了许多实际问题而建立起来的。 3 虽然动态规划主要用
9、于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对 不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，
10、以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。 本科生毕业论文（设计） - 2 - 2.动态规划 2.1 动态规划概述 动态规划是 解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼（ R Bellman）等人在 20 世纪 50 年代提出的。他们针对多阶段决策问题的特点，提出了解决 这类问题的最优化原理，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支。 1957 年， R Bellman 发表了该分支领域的第一本专著动态规划（ Dynamic Pr
11、ogramming）。 动态规划是现代企业管理中的一种重要决策方法，可用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的最优控制等。由于它有独特的解题思路，在处理某些优化问题时，比线性规划或非线性规划方法更有效。 45 动态规划可以高效地解决许多用“贪心算法”或“分治算法 ”难以解决的最优解的问题。用动态规划解题，首先要把原问题分解为若干子问题，这一点与递归方法类似。动态规划与递归的区别在于：单纯的递归往往会导致子问题的解一旦被求出就会被保存，所以，每个子问题只需求解 1次。6 2.2 动态规划的基本概念 动态规划中描述多阶段决策过程的基本概念有：阶段和阶段
12、变量，状态和状态变量，决策、决策变量和决策序列，状态转移方程，阶段效应和目标函数等。 1 阶段和阶段变量 把所研究的多阶段决策过程恰当地划分为若干个相互独立又相互联系的部分，每一个部分就称为一个阶段。事实上一个阶段也就是 需要做出一个决策的子问题部分。通常阶段是按照过程进行的时间和空间上的先后顺序划分，并用阶段变量 k 表示。阶段数等于多阶段决策过程中从开始到结束所需要作出决策的数目，划分阶段的目的是便于求解。 2 状态和状态变量 在多阶段决策过程中，状态是描述系统情况所必须的信息。一般定义为某一个阶段的初始点、初始位置或初始情况。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息，阶
13、段 k的状态表示为 kx 。比如：在最短路问题中，状态就是网络中的各个节点。 本科生毕业论文（设计） - 3 - 状态变量的取值有一定的允许范围，称为状态可能集。状态可能集是关于状态的约束条件。状态可能集用相应阶段状态 kx 的大写字母 kX 表示，其中 kkxX 。状态可能集可以是一个离散取值的集合，也可以是一个连续的区间，视所给问题而定。 3 决策、决策变量和决策序列 决策就是决策者从本阶段出 发对下一阶段状态的选择。多阶段决策过程的发展是用各个阶段的状态演变来描述的。因为用状态描述的过程具有无后效性，因此在进行阶段决策时，只须根据当前的状态进行而无须考虑过去的历史。在阶段 k ，如果给出
14、了决策变量 ku 随状态变量 kx 变化的对应关系，就确定了根据不同的当前状态作出不同决策的规则。即决策变量 ku 是状态变量 kx 的函数，称为决策函数，表示为 ()kkux。 和状态变量一样，决策变量的取值也有一定的允许范围，称为允许决策集合。允许决策集合是决策的约束条件。 ku 的允许决策集合表示为 kU ， kkuU 。 kU 要根据相应的状态可能集 kX 并结合具体问题来确定。 决策序列叫策略。策略有全过程策略和 k -子策略之分。全过程策略是整个 n 段决策过程中依次进行的阶段决策构成的决策序列称为 k -子策略，表示为 1, , ,k k nu u u 当 1k 时， k -子策
15、略就是全过程策略。相应地，从阶段 k 到阶段 n 的过程称为 k -子过程，当 1k时， k -子过程就是全过程。 在 n 段决策问题中，各阶段的状态可能集和决策允许集确定了决策的允许范围。特别是，过程的初 始状态不同，决策和策略也就不同，即策略是初始状态的函数。 4 状态转移方程 状态转移方程表示从阶段 k 到阶段 1k 的状态转移规律的表达式。 多阶段决策过程的发展就是用阶段状态的相继演变来描述的。对具有无后效性的多段决策过程，系统由阶段 k 到阶段 1k 的状态转移方程表示为 1 ( , ( )k k k k kx T x u x 即阶段 1k 的状态完全由阶段 k 的状态 kx 和决策
16、 ()kkux确定，与系统过去的状态1 2 1, , , kx x x 及其决策 1 1 2 2 1 1( ) , ( ) , , ( )kku x u x u x无关。 ( , )kkkT x u 称为变换函数或变换子。变换函数可以分为两种类型，即 确定型和随机型，据此形成确定型动态规划和随机型动态规划。 5 阶段效应和目标函数 本科生毕业论文（设计） - 4 - 多阶段决策过程中，在阶段 k 的状态 kx 执行决策 ku ，不仅带来系统状态的转移，而且也比必然带来对目标函数的影响。阶段效应就是执行阶段决策时所带来的目标函数的增量。 在具有无后效性的多阶段决策过程中，阶段效应完全由阶段 k
17、的状态 kx 和决策 ku 决定，与阶段 k 以前的状态和决策无关，表示为 ( , )kkkr x u 。 多阶段决策过程关于目标函数的总效应由各阶段效应累积形成。适于动态规划求解的问题的目标，必须具有关于阶段效应的可分离形式、递推性和对于变元 1kR 的严格单调性。 k -子过程的目标函数可以表示为1 1 1 1 1( , , , , , , ) ( , ) ( , ) ( , )k k k k k n n k k k k k k n n nR R x u x u x u r x u r x u r x u 其中 表示某种运算，可以是加、减、乘、除、开方等。经济管理领域中最常见的目标函数取阶
18、段效应之和的形式，即 11( , , , , , , ) ( , )nk k k k k n n i i iikR R x u x u x u r x u 后文要讨论的主要就是这种形式的目标函数。 2.3 多阶段决策过程的最优化 多阶段决策过程，是一类特殊的活动过程，它可以按时间顺序分解成若干相互联系的阶段，每个阶段称为“时段”。在每个时段都需要做出决策，全部过 程的决策是一个决策序故多阶段决策问题属贯决策问题。 多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。由于各阶段决策间有机地联系着，所以本阶段决策的执行将影响到下一段的决策，以至于影响总体效果，故决策者在短阶段决策时不应仅
19、考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全面来讲是最优的决策。 使用动态规划方法解决多阶段决策问题，首先耍将实际问题写成动态规化模型，具体包括以下思想： (一 )将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题 ，然后逐个求解。 (二 )求解时从边界条件开始，逆 (或顺 )过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。 (三 )动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法， 因此每段的最优
20、决策选取是从全局考虑的，与该段的最优选择一般是不同的。本科生毕业论文（设计） - 5 - 动态规划的基本方程是递推逐段求解的根据，一般的动态规划基本方程可以表为： 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 阶段的指标函数值。 7 2.4 动态规划建模 (1)将实际问题的过程划分成恰当阶段，确定阶段变量 根据多 阶段决策问题的实际过程
21、，将其划分为若干个相互独立又相互联系的部分，每一个部分为一个阶段，划分出的每一个阶段通常就是需要做出一个决策的子问题目。阶段通常是按决策进行的时间或空间上的先后顺序划分的，阶段变量用表示。 (2)确定状态，正确选择状态变量 在多阶段决策过程中，状态是描述每个阶段所必须的信息，表示每个阶段开始时所处的自然状况或客观条件。一个阶段有若干个状态，用一个或一组变量来描述，状态变量必须既能描述过程的演变，又要满足无后效性。用表示第个阶段的状态变量。 (3)确定决策变量及允许的决策集合 决策的实质 是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。决策变量用 kx 表示；允许的决策集合
22、是决策变量的取值范围用 ()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 本科生
23、毕业论文（设计） - 6 - 3.动态规划在经济管理中的应用 3.1 背包问题 1)一维背包问题 (1)问题 有一个人带一个背包上山，其可携带物品重量的限度为 a 公斤。设有 n 种物品可供他选择装入背包中，这 n 中物品编号为 1， 2， ， n 。已知第 i 种物品每件重量为 iw 公斤，在上山过程中的作用 (价值 )是携带数量 ix 的函数 ()iicx 。问此人应如何选择携带物品 (各几件 )，使所有作用（总价值 )最大。这就是著名的背包问题，类似的问题有工厂里的下料问题，运输中的货物装载问题，人造卫星内的物品装载问题等等 。 (2)模型及其解法 设 ix 为第 i 种物品的装入件数，
24、则问题的数学模型为： 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 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)模型及其解法： 它的数学模型为：
