动态规划在经济中的应用.doc
《动态规划在经济中的应用.doc》由会员分享,可在线阅读,更多相关《动态规划在经济中的应用.doc(27页珍藏版)》请在咨信网上搜索。
1、 中图分类号: O221.3 本 科 生 毕 业 论 文(设计) (申请学士学位)论文题目 动态规划在经济中的应用 作者姓名 蒋兴龙 专业名称 信息与计算科学 指导教师 王龙芹 2012年4月28日学 号:2008211508论文答辩日期:2012年 月 日指 导 教 师: (签字)滁州学院本科毕业设计(论文)原创性声明本人郑重声明:所呈交的设计(论文)是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写的成果。本人完全意识到本声明的法律后果由本人承担。 作者签名: 年 月 日滁州学院本科毕业论文目 录 摘要1Abst
2、ract11. 动态规划相关背景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动态规划摘要:动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。所谓“动态”,指的是在问题的多阶段决策中,按某一顺序,根据每一步所选决策的不同,将随即引起状态的转移,最终在变化的状
3、态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。动态规划的方法,在工程技术、企业管理、工农业生产及军事等部门中都有广泛的应用,并且获得了显著的效果。在企业管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等,所以它是现代经济管理中的一种重要的决策方法。它的应用也越来越受人重视。本文主要运用动态规划的思想设计出有效的数学模型来解决生产领域中遇到的一些问题,对资源进行优化配置,并规划出最优或可行方案。本文首先对“动态规划”的理论基础进行了讨论。给出了动态规划的基本理论和基本方程,
4、其次给出了最优性定理,并加以证明,最后以工业中最典型的两个问题为例,阐述了动态规划思想基本原理的应用。关键词: 动态规划;最优性原理;经济;生产计划;设备更新中图分类号: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
5、 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
6、 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
7、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
8、 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 the
9、ory 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 相关背景动态规划是一种可以将复杂问
10、题转化成一系列比较简单的问题的最优方法,其简称DP法。它的基本特征是在优化过程中的多阶段性。许多优化问题可以利用动态规划的方法来处理,常有其独特的优越性。特别是对于离散性问题,用数学方法往往难以处理,而动态规划方法则成为解决这些问题一个非常有用的工具。最优化原理是由美国人贝尔曼(Bellman)最先提出来的。最优化原理可以叙述为:“问题整个过程最优策略具有这样的性质:不管前面的状态和策略如何,对于以前的决策所形成的状态而言,余下的所有决策必须构成最优的策略”。利用最优化原理可以把要处理的多阶段决策问题的求解过程看做是一个连续的递推过程,由前向后或者由后向前逐步推算。在求解中,各个阶段以前的决策
11、和状态,对于其后面子问题来说,只不过是相当于它们的初始条件而已,一般不会影响其后面过程的最优策略。所以,可以把一个问题按阶段分解成为多个相互联系的子问题,而每个子问题均是比原问题简单得多的一个优化问题,并且每个子问题的求解中仅仅只利用它的下一阶段子问题的优化后的结果,经依次求解,最后可以求出原问题的最优解1。 稍微了解了动态规划的背景,下面简单介绍动态规划的一些基本概念和基本方程、动态规划的基本思想、模型的分类及方法以及动态规划的优缺点。2 动态规划的相关概念2.1 基本特征动态规划问题具有下列基本特征:1、整个阶段可以按空间划分,也可以按时间人为划分。动态规划问题具有多阶段决策的特征。2、其
12、每一阶段都有相应的“状态”与之对应,我们把描述状态的量称为“状态变量”。3、其每一阶段都面临一个决策,我们选择不同的决策将会导致下一阶段不同的状态,同时不同的决策将会导致这一阶段不同的目标函数值。4、各子问题与原问题具有完全相同的结构,其每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题。而解决动态规划问题的关键是能否构造这样的递推归结。这种递推归结的过程,称为“不变嵌入”。为了将以上特征形式化,我们提出以下动态规划的基本概念2。 2.2 基本概念1阶段:把所给问题的过程恰当的分成几个相互联系的有顺序的环节,这些环节即称为阶段 。描述阶段的变量成为阶段变量,常用k表示。阶段的
13、划分一般是根据空间和时间的自然特征来划分。2.状态:描述了研究问题过程的状况,又称不可控因素,即每个阶段开始所处的自然状态或客观条件。用表示第k阶段的状态变量。这里所说的状态应具有无后效性(即马尔科夫性)。3.决策:决策是当过程处于某阶段的某个状态时可做出的选择或决定。决策变量可用表示,表示第 k 阶段当状态处于时的决策变量。在实际问题中,决策变量的取值往往限制在某一范围之内,此范围称为允许决策集合。常用表示第k阶段从状态出发的允许策略集合。有.4.策略:策略是一个按顺序排列的决策组成的集合。由每段的决策按顺序排列组成的决策函数序列成为k字过程策略,简称子策略,即为.即当k=1时,此决策函数序
14、列成为全过程的一个策略,简称策略,记。5.状态转移方程:若给定第 k 阶段状态变量的值,如果该阶段的决策变量一经确定,第 k+1 阶段的状态变量的值也就确定,即的值随和的值变化而变化。用方程式表示为 ,它描述了由 k 阶段到 k+1 阶段的状态转移规律。此方程是确定过程由一状态到另一状态的演变过程。6.指标函数和最优指标函数:指标函数具体包括阶段的指标函数和过程的指标函数。阶段指标函数指对应某一阶段和从该阶段出发的一个阶段决策的某种效益量,用 表示。过程指标函数指从状态出发至过程最终,当采取某种子策略时,按预定标准得到的效益值。这个值既与的状态值有关,又与以后所选策略有关,它是两者的函数值。最
15、优指标函数,指对某一确定状态选取最优策略后得到的指标函数值,也是对应某一最优子策略的效益值 。下面我们来了解动态规划的灵魂即它的基本思想。2.3 基本思想1.解决动态规划问题的关键在于正确写出基本的递推关系式和恰当的边界条件,即在每个子问题求解中均利用了它前面子问题的最优化结果,从边界条件开始逐段递推寻优,依次进行,最后一个子问题所得的最优解就是整个问题的最优解。2.每段决策是从全局考虑的,与各段的最优选择答案一般不同。因此在决策过程中,动态规划方法是把当前段和未来各段分开,同时又把当前效益与未来效益结合起来考虑的最优化方法。3.在求整个动态规划问题的最优策略时,由于初始状态已知,而每段的决策
16、都是该段状态的函数,故最优策略所经过的各段最优状态便可逐次变换得到,从而确定了最优策略。利用动态规划解决问题时,往往用到不同的模型及方法,下面作简单介绍。2.4 动态规划模型的分类及方法根据多阶段决策过程的时间变量是连续性的还是离散性的变量,过程分为连续决策过程和离散决策过程。根据决策过程的演变是随机性的还是确定性的,过程又可分为随机型决策过程和确定型决策过程。组合起来就有离散确定型、离散随机型、连续确定型、连续随机型四种决策过程模型。动态规划的方法:动态规划方法有逆序解法和顺序解法之分,那么,他们的动态规划基本方程应如下表述:设指标函数是取各阶段指标的和的形式,既其中表示第i阶段的指标。他显
17、然是满足指标函数三个性质的。所以上式可写成。当初始状态给定时,过程的策略就被确定,则指标函数就被确定了。因此,指标函数最初状态和策略的函数,可记为故上面递推关系又可写为其子策略有决策可看成是由决策和组合而成。即如果用表示初始状态为的后部子过程所有子策略中的最优子策略。则最优值函数为,而 但 所以 边界条件为。上述即为动态规划逆序解法的基本方程,根据边界条件,从开始,由后向前逆推,从而逐步可求得各段的最优决策和相应的最优值,最后求出时,即得到整个问题的最优解。动态规划顺序解法的基本方程:假定阶段序数k和状态变量的定义不变,而改变决策变量的定义,如取,这时的状态转移不是由去确定,而反过来由去确定,
18、则状态转移方程一般形式为因而第k阶段的允许决策集合也应作相应的改变,记为。指标函数也应换成以和的函数表示。于是可得动态规划顺序解法的基本方程为 边界条件为式中。其求解过程,根据边界条件,从开始,由前向后顺推,逐步可求得各段的最优决策和相应的最优值,最后求出时,就得到整个问题的最优解4。本论文主要是强调动态规划在经济中的优越性,但是不可否认,动态规划也有其缺点。2.5 动态规划的优缺点动态规划的方法有两个明显的优点,与穷举法相比:(1)计算量得到大大减少(2)计算结果得到丰富在一定条件下找到一种途径,在对各阶段的效益经过按问题具体性质所确定的运算以后,使得全过程的总效益达到最优,这就是动态规划最
19、优化。 要注意阶段的划分是应用动态规划的关键,必须根据题意分析,寻求合理的划分阶段(子问题)方法。而每个子问题是一个比原问题简单得多的优化问题。而且每个子问题的求解中,均利用到它的一个后部子问题的最优化结果,直到最后一个子问题所得到的最优解,它就是原问题的最优解。当然动态规划方法也有不足之处:到目前为止,还没有一个统一的标准模型可以应用到所有问题。由于实际问题复杂和不同,其动态规划模型就有差异,虽然理论上说可以把某些静态规划的问题转化为动态规划模型来求解,但这种转化优势变得非常困难,需要丰富的想象力和灵活的技巧性。还有应用的局限性。由于构造静态规划模型时,状态变量必须满足“无后效性”条件,这条
20、件不仅依赖于状态转移规律,还依赖于允许决策集合和指标函数的结构是一个相当强的条件。不少实际问题在取其自然特征作为状态变量往往不能满足这条件,这就降低了动态规划的通用性。还有在求解数值时,存在“维数障碍”,在内存限制下,超过三维的动态规划通常在现在是不可取的。对一个实际问题建立动态规划模型时,必须做到下面五点:(一)根据实际情况将问题过程化成适当的阶段;(二)正确选择变量,使他既能描述过程的演变,又要满足无后效性;(三)正确确定决策变量及每阶段的允许决策集合;(四)正确写出状态转移方程;(五)正确写出指标函数的关系,它应满足下面三个性质:是定义在全过程和所有后部子过程上的数量函数;要具有可分离性
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 经济 中的 应用
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。