动态规划在经济中的应用学士学位90903625.doc

【精品文档】如有侵权，请联系网站删除，仅供学习与交流动态规划在经济中的应用学士学位90903625.精品文档.本 科 生 毕 业 论 文（设计） （申请学士学位）论文题目 动态规划在经济中的应用 专业名称 信息与计算科学 滁州学院本科毕业设计（论文）原创性声明本人郑重声明：所呈交的设计（论文）是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果。本人完全意识到本声明的法律后果由本人承担。 作者签名： 年 月 日目 录摘要1Abstract11. 动态规划相关背景32. 动态规划的相关概念32.1 基本特征3 2.2 基本概念42.3 基本思想52.4 动态规划模型的分类和方法5 2.5 动态规划的优缺点63. 动态规划的最优化原理和最优性定理83.1 最优化原理的概念和证明 83.2 动态规划的无后效性原理84. 动态规划在工业中的应用9 4.1 生产计划问题9 4.2 设备更新问题125. 结论20参考文献20致谢21动态规划摘要：动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。所谓“动态”，指的是在问题的多阶段决策中，按某一顺序，根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中都有广泛的应用，并且获得了显著的效果。在企业管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等，所以它是现代经济管理中的一种重要的决策方法。它的应用也越来越受人重视。本文主要运用动态规划的思想设计出有效的数学模型来解决生产领域中遇到的一些问题，对资源进行优化配置，并规划出最优或可行方案。本文首先对“动态规划”的理论基础进行了讨论。给出了动态规划的基本理论和基本方程，其次给出了最优性定理，并加以证明，最后以工业中最典型的两个问题为例，阐述了动态规划思想基本原理的应用。关键词： 动态规划；最优性原理；经济；生产计划；设备更新中图分类号：O221.3Dynamic ProgrammingAbstract: The dynamic programming is a branch that it is multi-stage decision-making process of solving a mathematical optimization method. The so-called "dynamic" refers to the multi-stage in the decision-making, according to a particular sequence, every step of the decision-making choice, the state will immediately cause the transfer of the final changes in the state have a decision-making sequence. Dynamic programming is to make the decision, subject to certain conditions, the optimal sequence. Dynamic Programming methods in engineering technology, enterprise management, industrial and agricultural production and have a wide range of sectors such as military applications. and the effect was remarkable. In business management, dynamic programming can be used to solve the optimal path, resource allocation, production scheduling, inventory loading, scheduling, and the upgrading of equipment, optimal control problems in the production process. So it is an important decision in modern management methods. It has been increasing emphasis on the application. In this paper, dynamic programming, the design of effective ideas to solve the mathematical model produced some of the problems encountered in the field. optimize the allocation of resources and planning the optimal or options. This article of the "dynamic planning" theoretical basis for the discussion. Given the basic theory and the dynamic programming equation, followed by the optimal theorem and prove it. Finally, the two industries most typical example to explain the basic tenets of the Dynamic Programming.Keywords: Dynamic programming; Economy; Optimal principle; Production planning; Updating 1 相关背景动态规划是一种可以将复杂问题转化成一系列比较简单的问题的最优方法，其简称DP法。它的基本特征是在优化过程中的多阶段性。许多优化问题可以利用动态规划的方法来处理，常有其独特的优越性。特别是对于离散性问题，用数学方法往往难以处理，而动态规划方法则成为解决这些问题一个非常有用的工具。最优化原理是由美国人贝尔曼（Bellman）最先提出来的。最优化原理可以叙述为：“问题整个过程最优策略具有这样的性质：不管前面的状态和策略如何，对于以前的决策所形成的状态而言，余下的所有决策必须构成最优的策略”。利用最优化原理可以把要处理的多阶段决策问题的求解过程看做是一个连续的递推过程，由前向后或者由后向前逐步推算。在求解中，各个阶段以前的决策和状态，对于其后面子问题来说，只不过是相当于它们的初始条件而已，一般不会影响其后面过程的最优策略。所以，可以把一个问题按阶段分解成为多个相互联系的子问题，而每个子问题均是比原问题简单得多的一个优化问题，并且每个子问题的求解中仅仅只利用它的下一阶段子问题的优化后的结果，经依次求解，最后可以求出原问题的最优解1。 稍微了解了动态规划的背景，下面简单介绍动态规划的一些基本概念和基本方程、动态规划的基本思想、模型的分类及方法以及动态规划的优缺点。2 动态规划的相关概念2.1 基本特征动态规划问题具有下列基本特征：1、整个阶段可以按空间划分，也可以按时间人为划分。动态规划问题具有多阶段决策的特征。2、其每一阶段都有相应的“状态”与之对应，我们把描述状态的量称为“状态变量”。3、其每一阶段都面临一个决策，我们选择不同的决策将会导致下一阶段不同的状态，同时不同的决策将会导致这一阶段不同的目标函数值。4、各子问题与原问题具有完全相同的结构，其每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题。而解决动态规划问题的关键是能否构造这样的递推归结。这种递推归结的过程，称为“不变嵌入”。为了将以上特征形式化，我们提出以下动态规划的基本概念2。 2.2 基本概念1阶段：把所给问题的过程恰当的分成几个相互联系的有顺序的环节，这些环节即称为阶段 。描述阶段的变量成为阶段变量，常用k表示。阶段的划分一般是根据空间和时间的自然特征来划分。2.状态：描述了研究问题过程的状况，又称不可控因素，即每个阶段开始所处的自然状态或客观条件。用表示第k阶段的状态变量。这里所说的状态应具有无后效性（即马尔科夫性）。3.决策：决策是当过程处于某阶段的某个状态时可做出的选择或决定。决策变量可用表示，表示第 k 阶段当状态处于时的决策变量。在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合。常用表示第k阶段从状态出发的允许策略集合。有.4.策略：策略是一个按顺序排列的决策组成的集合。由每段的决策按顺序排列组成的决策函数序列成为k字过程策略，简称子策略，即为.即当k=1时，此决策函数序列成为全过程的一个策略，简称策略，记。5.状态转移方程：若给定第 k 阶段状态变量的值，如果该阶段的决策变量一经确定，第 k+1 阶段的状态变量的值也就确定，即的值随和的值变化而变化。用方程式表示为 ，它描述了由 k 阶段到 k+1 阶段的状态转移规律。此方程是确定过程由一状态到另一状态的演变过程。6.指标函数和最优指标函数：指标函数具体包括阶段的指标函数和过程的指标函数。阶段指标函数指对应某一阶段和从该阶段出发的一个阶段决策的某种效益量，用 表示。过程指标函数指从状态出发至过程最终，当采取某种子策略时，按预定标准得到的效益值。这个值既与的状态值有关，又与以后所选策略有关，它是两者的函数值。最优指标函数，指对某一确定状态选取最优策略后得到的指标函数值，也是对应某一最优子策略的效益值 。下面我们来了解动态规划的灵魂即它的基本思想。2.3 基本思想1.解决动态规划问题的关键在于正确写出基本的递推关系式和恰当的边界条件，即在每个子问题求解中均利用了它前面子问题的最优化结果，从边界条件开始逐段递推寻优，依次进行，最后一个子问题所得的最优解就是整个问题的最优解。2.每段决策是从全局考虑的，与各段的最优选择答案一般不同。因此在决策过程中，动态规划方法是把当前段和未来各段分开，同时又把当前效益与未来效益结合起来考虑的最优化方法。3.在求整个动态规划问题的最优策略时，由于初始状态已知，而每段的决策都是该段状态的函数，故最优策略所经过的各段最优状态便可逐次变换得到，从而确定了最优策略。利用动态规划解决问题时，往往用到不同的模型及方法，下面作简单介绍。2.4 动态规划模型的分类及方法根据多阶段决策过程的时间变量是连续性的还是离散性的变量，过程分为连续决策过程和离散决策过程。根据决策过程的演变是随机性的还是确定性的，过程又可分为随机型决策过程和确定型决策过程。组合起来就有离散确定型、离散随机型、连续确定型、连续随机型四种决策过程模型。动态规划的方法：动态规划方法有逆序解法和顺序解法之分，那么，他们的动态规划基本方程应如下表述：设指标函数是取各阶段指标的和的形式，既其中表示第i阶段的指标。他显然是满足指标函数三个性质的。所以上式可写成。当初始状态给定时，过程的策略就被确定，则指标函数就被确定了。因此，指标函数最初状态和策略的函数，可记为故上面递推关系又可写为其子策略有决策可看成是由决策和组合而成。即如果用表示初始状态为的后部子过程所有子策略中的最优子策略。则最优值函数为，而 但 所以 边界条件为。上述即为动态规划逆序解法的基本方程，根据边界条件，从开始，由后向前逆推，从而逐步可求得各段的最优决策和相应的最优值，最后求出时，即得到整个问题的最优解。动态规划顺序解法的基本方程：假定阶段序数k和状态变量的定义不变，而改变决策变量的定义，如取，这时的状态转移不是由去确定，而反过来由去确定，则状态转移方程一般形式为因而第k阶段的允许决策集合也应作相应的改变，记为。指标函数也应换成以和的函数表示。于是可得动态规划顺序解法的基本方程为边界条件为式中。其求解过程，根据边界条件，从开始，由前向后顺推，逐步可求得各段的最优决策和相应的最优值，最后求出时，就得到整个问题的最优解4。本论文主要是强调动态规划在经济中的优越性，但是不可否认，动态规划也有其缺点。2.5 动态规划的优缺点动态规划的方法有两个明显的优点，与穷举法相比:(1)计算量得到大大减少(2)计算结果得到丰富在一定条件下找到一种途径，在对各阶段的效益经过按问题具体性质所确定的运算以后，使得全过程的总效益达到最优，这就是动态规划最优化。 要注意阶段的划分是应用动态规划的关键，必须根据题意分析，寻求合理的划分阶段(子问题)方法。而每个子问题是一个比原问题简单得多的优化问题。而且每个子问题的求解中，均利用到它的一个后部子问题的最优化结果，直到最后一个子问题所得到的最优解，它就是原问题的最优解。当然动态规划方法也有不足之处：到目前为止，还没有一个统一的标准模型可以应用到所有问题。由于实际问题复杂和不同，其动态规划模型就有差异，虽然理论上说可以把某些静态规划的问题转化为动态规划模型来求解，但这种转化优势变得非常困难，需要丰富的想象力和灵活的技巧性。还有应用的局限性。由于构造静态规划模型时，状态变量必须满足“无后效性”条件，这条件不仅依赖于状态转移规律，还依赖于允许决策集合和指标函数的结构是一个相当强的条件。不少实际问题在取其自然特征作为状态变量往往不能满足这条件，这就降低了动态规划的通用性。还有在求解数值时，存在“维数障碍”，在内存限制下，超过三维的动态规划通常在现在是不可取的。对一个实际问题建立动态规划模型时，必须做到下面五点：（一）根据实际情况将问题过程化成适当的阶段；（二）正确选择变量，使他既能描述过程的演变，又要满足无后效性；（三）正确确定决策变量及每阶段的允许决策集合；（四）正确写出状态转移方程；（五）正确写出指标函数的关系，它应满足下面三个性质：是定义在全过程和所有后部子过程上的数量函数；要具有可分离性，并满足递推关系，即函数对于变量要严格单调。以上五点是正确写出动态规划基本方程的基本要素，是构造动态规划模型的基础。 下面介绍动态规划的最优性原理和其无后效性。3 动态规划的最优性原理和无后效性3.1最优性原理的概念及证明动态规划的最优性原理可简单的描述为：作为整个过程的最优策略具有这样的性质:无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略.一言蔽之,一个最优策略的子策略总是最优的。最优性原理：设阶段数为n的多阶段决策过程，其阶段编号为。允许策略是最优策略的充要条件,对任何一个k，0<k<n-1和有式中，它是由给定的初始状态和子策略所确定的k段状态。当V是效益函数时，opt取max;当V是损失函数时，opt取min。推论：若允许策略是最优策略，则对任意的k,0<k<n-1,它的子策略对于为起点的k到n-1子过程来说必是最优策略（注意：k段状态是由和确定的）。上述定理是动态规划的理论基础5。3.2 动态规划的无后效性原则所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段 I 中的状态只能由阶段 I+1 中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性7。下面简单列举关于应用动态规划的两个例子，简单介绍其在经济中尤其工业中的作用。4 动态规划在经济尤其工业中的应用4.1 生产计划问题对于生产计划一类问题，阶段按计划时间自然划分，状态定义为每阶段开始时的储存量，决策为每阶段的产量，即每个阶段的需求量（已知量）为，则状态转移方程为设每阶段开工的固定成本费为a，生产单位数量产品的成本费为b，每阶段单位数量产品的储存费为c，阶段指标为阶段成本和储存费之和，即 指标函数为之和。最优值函数为从第k段的状态出发到过程终结的最小费用，满足其中允许决策集合由每阶段的最大生产能力决定。若设过程终结时允许储存量为，则终端条件是构成该问题的动态规划模型。例1：某公司与一客户订立合同，在4个月内售出一定数量的某种产品。由于各种原因，每月至多生产100单位，产量限于10的倍数。产品可以贮存，贮存费用每单位2元。生产成本及每月销售额如表1-1给出。要求确定一个生产过程，使能满足合同要求，在生产能力以内使生产成本最小。解： 阶段变量表示月份。状态变量表示k月初已有产品数。决策变量表示决定k月的生产数量，满足约束状态转移，阶段指标 。表1-1月份单位生产成本合同销售额170602727038012047660k=4（表1-2）时，由于1-3月份最大生产量为300单位，合同销售总额为250单位，所以4月份最大贮存量为50单位，即可能取值为0、10、20、30、40、50。求解得 ，则有。表1-20456060103820502030804030234030401600205086010k=3（表1-3）时，第一，第二月最大生产量为200单位，销售合同额为60+70=130，所以3月份初最大贮存量为70单位。由和得。所以可能的取值为20、30、40、50、60、70单位。求解 表1-35060708090100201260012600100301182011880118209040110401110011160110408050102601032010380104401026070609480954096009660972094806070870087608820888089409000870050k=2(表1-4)时，1月份最大生产量为100单位，合同销售量为60，则2月份最大贮存量为100-60=40，即可能取值0、10、20、30、40。 求解 又由，得。表1-4506070809010001908019020190201001018380183201826018260100201768017620175601750017500100301698016920168601680016740167401004016280162201616016100160401598015980100K=1（表1-5）时，且有表1-5607080901000232202316023100230402298022980100最小总成本，最优生产安排如表1-6所示。表1-6月份101006070000700024010070720080728037050120400014041404060604560045604.2 设备更新问题例2： 矿山中型自卸汽车更新问题的研究某铁矿是一个开采矿石的特大型露天矿山，年产铁矿石为650万吨，采剥总量为15000万吨左右。所采矿石采用汽车和电机车在线联合运输方式，工艺流程如图1所示。由下图可知，该矿的矿岩量主要是靠矿用自卸汽车运输，电机车只担负着进入溜作后的矿石输出，所以汽车对于该矿山每年能否完成向国家上缴1200万元的税利任务起着重要的作用。这个矿山现有铁矿用自卸汽车65台。载重量都是20t的。其中B20-203型汽车只有40台，这批汽车来矿后已使用六年多时间。此外，有TJ371型汽车25台，来矿后已使用四年多时间。按国务院有关规定，矿用中型自卸汽车的服务年限为8至10年。随着使用年限的增加，B20-203型汽车虽然还不到规定的服务年限，但其性能、技术状况都日益恶化，运输成本增加，综合经济效益逐年下降。再加上随着开采年份的增加，采场作业面不断减少。凡此种种原因，促使有关部门考虑这种汽车是继续留用还是更新的问题。岩石坠场电铲装车矿石入溜场汽车运输溜井配矿机电车运输爆破选矿厂穿孔图1但是由于目前我国重型自卸汽车生产厂家不多，产量也很少，且根据该矿具体情况和实践经验，能符合该矿需要吨位的汽车只有两个系列的产品可供选用，即某市重型汽车制造厂引进英国技术生产的RD系列汽车和某省第二机械厂与美国联合生产的33系列汽车。因此，该矿在近几年内主要使用这两种系列的汽车进行更新。今以年为周期，从2007年开始，为使该汽车使用的总收益最大，从2007年至2011年5年内每年年初时，对买新车（P：Purchase）还是维修留用旧车（K：Keep）问题作出决策。已知到2011年初B20-203型汽车已使用7年，而TJ731型汽车也使用了5年。到2011年这5年内，如果继续使用旧车，对所发生的各项费用或更换新车费用如表2所示；如在这5年内用33-001型汽车更新，各项费用见表3所示；如用RD150-1型汽车更新，费用如表4所示。 表2（万元）型号B20-203(6年)TJ731(4年)使用年数789101156789年收益（万元）11.51110.510913.61312.712.311.5年使用费6.78.67.59.58.56.17.36.88.88.4更新车5658606365625254565858606264675456596062 表3（万元）起始年20072008200920102011使用年数012340123012010年收益252626252425272825262728293030年使用费68108116810.597910910.59.5更新费303436384032343638333537353736表4（万元）起始年19881989199019911992使用年数012340123012010年收益283029272528302927293028293030年使用费891112138.59.51211.58.5101291010.5更新费384042444639414345404244404241 我们开始建模：为了建立汽车更新的数学模型规定符号如下：第周期从新购汽车处所获得的收益；第周期从已使用了y年的汽车处所获得的收益；第周期新汽车的使用费用；第周期已使用了y年的汽车的使用费用；第周期安装，已使用了y年的汽车更新费用，该车是在年出厂的新车；T现有汽车的使用年数；A折算系数（因工业利率为1.5%，故这里A的取值为0.9985）；第周期初，对使用了y年的汽车在第周期中所获得的最优收益；第周期初，为获得作出的决策（决策只有两种，买新车（P）或维修旧车（K）。假定在第周期初是一辆新车，则在第周期所获得的总收益为：第周期内从新车获得的收益减去在第周期内新车的使用费用，再减去在第周期初已经使用了y年的汽车更新费用，再加上在第周期初已使用了1年的汽车所获得的最优收益（将其乘以折算系数A，折算为第周期初所获得的最优收益），即A，那么更新的总收益为：P：-+A同样，在假设第周期仍然使用已经用了y年的汽车，则在第周期所获得的总收益为：第周期内这辆已使用了y年的汽车的收益减去第周期已使用了y年的汽车的使用费用，加上第期初已使用了y+1年的汽车的最优收益（将其乘以折算系数A，折算为第周期初所获得的最优收益，即A，所以留后用的总收益为：K：- + A由此，第周期已使用了y年的汽车，在第周期所获得的总收益的基本方程为：规定： 计算B20-203型汽车已用了7年，TJ371型汽车已用了5年，他们的服务年限均为8至10年，所以从2007年至2011年的5年内，这两种型号的汽车都需要更新。这里就将此周期定为5。B20-203型汽车和TJ371型汽车已使用年限数T分别为7年和5年。对于B20-203型汽车若采用B33-001型汽车更新，各周期的最优收益及决策可计算如下： （1）逆序最优目标函数值集合与最优决策集合。当时，使用年数年，其最优收益和决策为：故 故 故 故 故 表5使用年数12341119.517.016.013.00.5KKKKK第5周期B20-203型汽车用B33-001型汽车更新，在不同使用年数的最优效益及其决策如表5所示。当时，使用年限，其最优收益及决策如下：故 故 故 故 表6使用年数1231036.032.530.01.0KKKK第4周期B20-203型汽车用B33-001型汽车更新，在不同使用年数的最优效益及其决策如表6所示。可类似计算出第3周期和第2周期的最优收益及决策如表7所示。表7第3周期第2周期使用年限12918最优收益52.445.9463.913.3最优决策KKKKK最后，当时，则故 （2）具体求解情况如下。根据上面的计算结果，B20-203型汽车用B33-001型汽车更新，在2007年以后的5年内的最优决策可归纳为表8所示。得出B20-203型汽车在2007年初用B33-001汽车更新，这样到2011年获得的总收益为最大，最大收益为26.8万元，并且在2007年初更新比保留使用每台将增加收益8.72万元。 同样，可以计算出其他三种情况，B20-203型用RD150-1型更新、TJ371型用B33-001型、RD150-1型更新时，在2007年以后的5年内最优收益及决策如表9所示。表8周期使用年限决策1721324354 表9RD150-1更换B20-203B33-001更换TJ371RD150-1更换TJ3711PPP2KKK3KKK4KKK5KKK最优收益（万元）27.832.731.7我们可以得出结论与分析：由以上的计算结果（表8和表9）可知，该矿现有汽车若采用技术更新方式，原B20-203型汽车选用RD150-1型汽车在2007年初更新，计算周期内获得的总收益最大为27.8万元，比留用可多获收益15.6万元/台。原TJ371型汽车选用33-001型汽车在2007年初更新名计算周期内的最大收益为32.7万元，比留用可多获得7.2万元/台。如果选用此最优决策的话，该矿就更新一项就可以节约（相对也即收益）（15.6×40+7.2×25）万元=804万元，占该矿一年上缴利税的67%，是一个相当可观的数字。由此可以看出最优化方法的作用所在。但需要注意的是，此处的优化是按一个指标，即5年内受益最大为目标进行的。在实际工作中，还需要考虑其他方面的一些因素。比如2007年初一次性将65台汽车全部更新，所需费用相当大，该矿是否承受的了。对于TJ371型汽车更新，在收益上只比用33-001型汽车少1万元。如果65台汽车均为RD150-1型，则用在维护保养方面都有一定的好处等等。 由以上两例，我们可大概得出如下结论。5 结 论动态规划是其实一种效率很高实用性很强的科学技术。这种运筹方法最大优点就可以讲问题简单化从而节约了时间，并能找出最优解。由以上两个例子可以领悟、理解动态规划的思想，掌握动态规划的解题技，用其解决经济中生产领域的一些问题往往能够达到许多比较好的效果。使资源能够得到充分的分配利用，有利于我国经济的进一步发展，有利于工业的优化发展，有利于我国经济的发展。由于其应用的广泛性和实用性，动态规划在其他领域的研究也不断加深。参考文献1 熊伟. 运筹学（第2版）M. 北京：机械工业出版社，2009(9):188-208.2 焦宝聪，陈兰平. 运筹学的思想方法及应用M. 北京：北京大学出版社，2008(2):63-72.3 叶向. 实用运筹学运用Excel建模和求解M. 北京：北京邮电大学出版社2002(4):32-153.4 韩大卫. 管理运筹学M. 大连理工大学出版社，2003(6).5 胡运权，郭耀煌等. 运筹学M. 北京：清华大学出版社，2005(6).6 赵静，但琦. 数学建模于数学试验M. 北京：高等教育出版社，2004(4).7 刁在筠，郑汉鼎等. 运筹学M. 北京：高等教育出版社，2006(7).8 徐渝，胡奇英等. 运筹学M. 西安：陕西人民出版社，2001:100-1339 Bellman R.E. Dynamic ProgrammingM. Princeton University Press，1957.10 Hillier F.S., Lieberman G. J. Introduction to Oprations ResearchM. 北京：清华大学出版社，2006(1):40-472.致 谢论文完成，意味着要告别大学时代。首先，感谢我的父母和我的兄弟蒋小星以及所有支持我的亲戚，没有他们，我无论如何也完不成大学学业。其次，感谢我的朋友们，没有他们，人生是孤独的。最后，感谢我的老师和同学们，他们使我的大学生活丰富多彩。衷心感谢我的指导老师,谢谢王老师对我的帮助！