毕业论文浅谈动态规划的原理及其应用—动态规划在工业领域的应用.doc

毕业论文毕业论文浅谈动态规划的原理及其应用浅谈动态规划的原理及其应用动态规划在工业领域的应用动态规划在工业领域的应用专业名称：数学与应用数学毕业论文I摘摘要要动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。所谓“动态”，指的是在问题的多阶段决策中，按某一顺序，根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中都有广泛的应用，并且获得了显著的效果。在企业管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等，所以它是现代管理中的一种重要的决策方法。它的应用也越来越受人重视。本文主要运用动态规划的思想设计出有效的数学模型来解决生产领域中遇到的一些问题，对资源进行优化配置，并规划出最优或可行方案。本文首先对“动态规划”的理论基础进行了讨论。给出了动态规划的基本理论和基本方程，其次给出了最优性定理，并加以证明，最后以工业中最典型的两个问题为例，阐述了动态规划思想基本原理的应用。关键词动态规划；最优性原理；生产计划；设备更新；毕业论文IIABSTRACTThe dynamic programming is a branch that it is multi-stagedecision-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 statehave a decision-making sequence.Dynamic programming is to make thedecision,subject to certain conditions,the optimal sequence.DynamicProgramming methods in engineering technology,enterprise management,industrial and agricultural production and have a wide range of sectors suchas military applications.and the effect was remarkable.In businessmanagement,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 productionprocess.So it is an important decision in modern management methods.Ithas been increasing emphasis on the application.In this paper,dynamic programming,the design of effective ideas tosolve the mathematical model produced some of the problems encounteredin the field.optimize the allocation of resources and planning the optimal oroptions.This article of the dynamic planning theoretical basis for thediscussion.Given the basic theory and the dynamic programming equation,followed by the optimal theorem and prove it.Finally,the two industriesmost typical example to explain the basic tenets of the DynamicProgramming.KeywordsDynamic programming;Optimal principle;Productionplanning;Updating equipment;大学毕业论文III目目录录一、引言1二、动 态 规 划 的 基 本 概 念 和 基 本 方 程 1（一）基 本 特 征 1（二）基 本 概 念 2（三）基 本 思 想 3（四）动态规划模型的分类及方法3（五）动态规划的优缺点5三、动 态 规 划 的 最 优 性 原 理 和 最 优 性 定 理 6（一）最优性原理的概念及证明6（二）动态规划的无后效性原理7四、动 态 规 划 在 工 业 中 的 应 用 8（一）生产计划问题（production planning problem）8（二）设备更新问题(equipment replacing problem)11五、结论18参 考 文献20河北经贸大学毕业论文1浅谈动态规划的原理及其应用动态规划在工业领域的应用一、引言动 态 规 划 大 约 产 生 于 50 年 代。1951 年 美 国 数 学 家 贝 尔 曼（R.Bellman）等人，根据一类多阶段决策问题的特点，然后逐个加以解决。与此同时，他提出了解决这类问题的“最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新的方法动态规划。许多问题用动态规划的方法去处理，常比线性规划或非线性规划更有成效。特别对于离散性问题，由于解析数学无法施展其术，而动态规划的方法就成为非常有用的工具。应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体的分析处理。因此在解题时应以丰富的想象力去建立模型，用创造性的技巧去求解。二、动态规划的基本概念和基本方程（一）基本特征动态规划问题具有以下基本特征：1、问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。2、每一阶段都有相应的“状态”与之对应，描述状态的量称为“状态变量”。3、每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态，同时，不同的决策将会导致这一阶段不同的目标函数值。4、每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。能否构造这样的递推归结，是解决动态规划问题的关键。这种递推归结的过程，称河北经贸大学毕业论文2为“不变嵌入”。为了将以上特征形式化，我们提出以下动态规划的基本概念。（二）基本概念1阶段：把所给问题的过程，恰当的分成几个相互联系的有顺序的环节，这些环节即称为阶段。描述阶段的变量成为阶段变量，常用 k表示。阶段的划分一般是根据时间和空间的自然特征来划分。2.状态：即每个阶段开始所处的自然状态或客观条件，他描述了研究问题过程的状况，又称不可控因素。用ks表示第 k 阶段的状态变量。这里所说的状态应具有无后效性（即马尔科夫性）。3.决策：决策是当过程处于某阶段的某个状态时可做出的选择或决定。决策变量可用)(kksu表示，ku表示第 k 阶段当状态处于ks时的决策变量。在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合。常用)(kksD表示第 k 阶段从状态ks出发的允许策略集合。有)()(kkkksDsu.4.策略：策略是一个按顺序排列的决策组成的集合。由每段的决策按顺序排列组成的决策函数序列)(,),(nnkksusu成为 k 字过程策略，简称子策略，即为,()k nkps.即)(,),(),()(11,nnkkkkknksusususp当 k=1时，此 决 策 函 数 序 列 成 为 全 过 程 的 一 个 策 略，简 称 策 略，记)(,),(),()(22111,1nnnsusususp。5.状态转移方程：此方程是确定过程由一状态到另一状态的演变过程。若给定第 k 阶段状态变量ks的值，如果该阶段的决策变量ku一经确定，第 k+1 阶段的状态变量1ks的值也就确定，即1ks的值随ks和ku的值变化而变化。用方程式表示为),(1kkkusFs，它描述了由 k 阶段到k+1 阶段的状态转移规律。6.指标函数和最优指标函数：指标函数包括阶段的指标函数和过程的指标函数。阶段指标函数指对应某一阶段和从该阶段出发的一个阶段决策的某种效益量，用),(kkkusV表示。过程指标函数指从状态ks出发至过程最终，当采取某种子策略时，按预定标准得到的效益值。这个值河北经贸大学毕业论文3既与ks的状态值有关，又与ks以后所选策略有关，它是两者的函数值),(11,nnkkkknkusususV。最优指标函数，指对某一确定状态选取最优策略后得到的指标函数值，也是对应某一最优子策略的效益值nkkkOPTVsf,)(。(三)基本思想1.动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件，即从边界条件开始逐段递推寻优，在每个子问题求解中均利用了它前面子问题的最优化结果，依次进行，最后一个子问题所得的最优解就是整个问题的最优解。2.决策过程中，动态规划方法是把当前段和未来各段分开，同时又把当前效益与未来效益结合起来考虑的最优化方法，因此每段决策是从全局考虑的，与各段的最优选择答案一般不同。3.在求整个问题的最优策略时，由于初始状态已知，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优策略。（四）动态规划模型的分类及方法根据多阶段决策过程的时间变量是离散的还是连续的变量，过程分为离散决策过程和连续决策过程。根据决策过程的演变是确定性的还是随机性的，过程又可分为确定性决策过程和随机性决策过程。组合起来就有离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型。动态规划的方法：动态规划方法有逆序解法和顺序解法之分，那么，他们的动态规划基本方程应如下表述：设指标函数是取各阶段指标的和的形式，既,(,)nk niiii kVV s u河北经贸大学毕业论文4其中),(iiiusV表示第 i 阶段的指标。他显然是满足指标函数三个性质的。所以上式可写成,),(11,1,nknkkkknkssVusvV。当初始状态给定时，过程的策略就被确定，则指标函数就被确定了。因此，指标函数最初状态和策略的函数，可记为)(,knkknksPsV故上面递推关系又可写为,1,11,(,),k nkk nkkkknkknVspv s uVsp其子策略有决策)(,knksp可看成是由决策)(kksu和)(1,1knksp组合而成。即,1,1(),()k nkkknkpusps如果用)(,knksp表示初始状态为ks的后部子过程所有子策略中的最优子策略。则最优值函数为，,*,.,(),(),()k nkkk nkk nkk nkk nkpfsVsPsoptVsps而),(),(),(,11,1,1,nkknkkkkpunkknkppsVusVoptpsVoptnkknk但),()(,11,111,1nkknkpkkpsVoptsfnk所以)(),()(11)(kkkkksDukksfusVoptsfkk1,1,nnk边界条件为11()0nnfs。上述即为动态规划逆序解法的基本方程，根据边界条件，从nk 开始，由后向前逆推，从而逐步可求得各段的最优决策和相应的最优值，最后求出)(11sf时，即得到整个问题的最优解。动态规划顺序解法的基本方程：假定阶段序数 k 和状态变量ks的定义不变，而改变决策变量ku的定义，如取kkkssu)(1，这时的状态转移不是由kkus,去确定1ks，而反过来由kkus,1去确定ks，则状态转移方程一般形式为河北经贸大学毕业论文5),(1kkrkkusTs因而第 k 阶段的允许决策集合也应作相应的改变，记为)(1krksD。指标函数也应换成以1ks和ku的函数表示。于是可得动态规划顺序解法的基本方程为)(),()(11)(111kkkkksDukksfusVoptsfkrkknk,2,1边界条件为0)(10sf式中),(1kkrkkusTs。其求解过程，根据边界条件，从1k开始，由前向后顺推，逐步可求得各段的最优决策和相应的最优值，最后求出)(1nnsf时，就得到整个问题的最优解。（五）动态规划的优缺点与穷举法相比，动态规划的方法有两个明显的优点:(1)大大减少了计算量(2)丰富了计算结果动态规划的最优化概念是在一定条件下，找到一种途径，在对各阶段的效益经过按问题具体性质所确定的运算以后，使得全过程的总效益达到最优。应用动态规划要注意阶段的划分是关键，必须依据题意分析，寻求合理的划分阶段(子问题)方法。而每个子问题是一个比原问题简单得多的优化问题。而且每个子问题的求解中，均利用它的一个后部子问题的最优化结果，直到最后一个子问题所得最优解，它就是原问题的最优解。动态规划方法也有不足之处：到目前为止，还没有一个统一的标准模型可以应用。由于实际问题不同，其动态规划模型就有差异，虽然理论上说可以把某些静态规划的问题转化为动态规划模型来求解，但这种转化优势变得非常困难，需要丰富的想象力和灵活的技巧性。应用的局限性。由于构造静态规划模型时，状态变量必须满足“无后效性”条件，这条件不仅依赖于状态转移规律，还依赖于允许决策集河北经贸大学毕业论文6合和指标函数的结构是一个相当强的条件。不少实际问题在取其自然特征作为状态变量往往不能满足这条件，这就降低了动态规划的通用性。在数值求解时，存在“维数障碍”，在内存限制下，超过三维的动态规划通常是不可取的。对一个实际问题建立动态规划模型时，必须做到下面五点：（一）将问题过程化成适当的阶段；（二）正确选择变量ks，使他既能描述过程的演变，又要满足无后效性；（三）确定决策变量ku及每阶段的允许决策集合)(kksD；（四）正确写出状态转移方程；（五）正确写出指标函数nkV,的关系，他应满足下面三个性质：是定义在全过程和所有后部子过程上的数量函数；要具有可分离性，并满足递推关系，即),(,),(111,11,nkknkkkknkknksusVussksV函数),(,1 nkkkkVus对于变量nkV,1要严格单调。以上五点是构造动态规划模型的基础，是正确写出动态规划基本方程的基本要素。三、动态规划的最优性原理和无后效性（一）最优性原理的概念及证明动态规划的最优性原理可描述为：作为整个过程的最优策略具有这样的性质:即无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略.简言之,一个最优策略的子策略总是最优的。最优性原理：设阶段数为 n 的多阶段决策过程，其阶段编号为1,1,0nk。河北经贸大学毕业论文7允许策略*0,101(,)nnpu uu是最优策略的充要条件,对任何一个 k，0kn-1 和0s0S有0,100,1*0,100,10,10,1()()(,)(,)()knknnks npspfVspoptVsoptV0,k-1k,n-10,k-1k,n-1pppp式中1,11,1*111,1,1*11,.1,11,11(,),()(,)()(),()(),()(,)()0knkKkkkkkkniiii kk nkkknkkkk nkk nkknkknpnnsTsusTsuV s upuspsfsVsPsoptVspfs0,n-10,k-1k,n-1ppp，它是由给定的初始状态0s和子策略1,0kp所确定的 k 段状态。当 V 是效益函数时，opt 取max;当 V 是损失函数时，opt 取 min。推论：若允许策略*0,1np是最优策略，则对任意的 k,0kn-1,它的子策略*,1k np对于*111(,)kkkksTsu为起点的 k 到 n-1 子过程来说必是最优策略（注意：k 段状态*ks是由0s和*0,1kp确定的）。上述定理是动态规划的理论基础。（二）动态规划的无后效性原则所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段 I 中的状态只能由阶段 I+1 中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关河北经贸大学毕业论文8系，这就是无后效性。四、动态规划在工业中的应用（一）生产计划问题（production planning problem）对于一类生产计划问题，阶段按计划时间自然划分，状态定义为每阶段开始时的储存量ks，决策为每阶段的产量kx，即每个阶段的需求量（已知量）为kd，则状态转移方程为kkkkdxss1，0,1,2,kskn设每阶段开工的固定成本费为 a，生产单位数量产品的成本费为 b，每阶段单位数量产品的储存费为 c，阶段指标为阶段成本和储存费之和，即0,0,0,),(kkkkkkkuubuacxxsv指标函数nkV,为kv之和。最优值函数)(kksf为从第 k 段的状态ks出发到过程终结的最小费用，满足1,),(),(min)(11nksfxsvsfkkkkkUukkkk其中允许决策集合kU由每阶段的最大生产能力决定。若设过程终结时允许储存量为01ns，则终端条件是0)(011nnsf构成该问题的动态规划模型。例：某公司与一客户订立合同，在 4 个月内售出一定数量的某种产品。由于各种原因，每月至多生产 100 单位，产量限于 10 的倍数。产品可以贮存，贮存费用每单位 2 元。生产成本及每月销售额如表 1-1 给出。要求确定一个生产过程，使能满足合同要求，在生产能力以内使生产成本最小。解：阶段变量k1,2,3,4表示月份。状态变量kS表示 k 月初已有产河北经贸大学毕业论文9品数。决策变量kx表示决定 k 月的生产数量，满足约束kkkks+xd,x0,10,20,状态转移kkkkdxss1，阶段指标V(,)2kkkkksxcxs。表 1-1月份单位生产成本合同销售额id170602727038012047660k=4（表 1-2）时，由于 1-3 月份最大生产量为 300 单位，合同销售总额为 250 单位，所以 4 月份最大贮存量为 50 单位，即4s可能取值为 0、10、20、30、40、50。求解4444444440100()min(2)xxsdfsc xs得444460 xdss则有444744560)(ssf表 1-24s44()fs*4x0456060103820502030804030234030401600205086010k=3（表 1-3）时，第一，第二月最大生产量为 200 单位，销售合同额为60+70=130，所以 3 月份初最大贮存量为 70 单位。由120333dxs和1003x得203s。所以3s可能的取值为 20、30、40、50、60、70 单位。河北经贸大学毕业论文10求解333333333440100120()min2()xxsdf sc xsfs表 1-33x3s33,344()()v s xfs33()f s*3x5060708090100201260012600100301182011880118209040110401110011160110408050102601032010380104401026070609480954096009660972094806070870087608820888089409000870050k=2(表 1-4)时，1 月份最大生产量为 100 单位，合同销售量为 60，则 2月份最大贮存量为 100-60=40，即2s可能取值 0、10、20、30、40。求解222222222330100()min 2()xxdsfsc xsf s又由322220ssxd，得22229020ssdx表 1-42x2s22,233()()v s xf s22()fs*2x506070809010001908019020190201001018380183201826018260100201768017620175601750017500100301698016920168601680016740167401004016280162201616016100160401598015980100K=1（表 1-5）时，01s，且有河北经贸大学毕业论文1111111111 1122010060(60)()min2()xxsdxf sc xsfs表 1-51x1s11,122()()v s xfs11()f s*1x607080901000232202316023100230402298022980100最小总成本22890)0(1f，最优生产安排如表 1-6 所示。表 1-6月份)(iisixidiic x12s,()iiiv s x10100607000070002401007072008072803705012040001404140406060456004560（二）设备更新问题(equipment replacing problem)例 矿山中型自卸汽车更新问题的研究某矿是一个开采矿石的特大型露天矿山，年产铁矿石为 650 万吨，采剥总量为 15000 万吨左右。所采矿石采用汽车和电机车在线联合运输方式，工艺流程如图 1 所示。由图可知，该矿的矿岩量主要是靠矿用自卸汽车运输，电机车只担负着进入溜作后的矿石输出，故汽车对于该矿每年能否完成向国家上缴1200 万元的税利任务起着重要的作用。这个矿现有矿用自卸汽车 65 台。载重量都是 20t 的。其中 T20-203型汽车只有 40 台，这批汽车来矿后已使用六年多时间。此外，有 BJ371型汽车 25 台，来矿后已使用四年多时间。按国务院有关规定，矿用中型自卸汽车的服务年限为 8 至 10 年。随着使用年限的增加，T20-203型汽车虽然还不到规定的服务年限，但其性能、技术状况都日益恶化，河北经贸大学毕业论文12运输成本增加，综合经济效益逐年下降。再加上随着开采年份的增加，采场作业面不断减少。凡此种种原因，促使有关部门考虑这种汽车是继续留用还是更新的问题。电铲装车矿石入溜场汽车运输溜井配矿机电车运输爆破选矿厂穿孔图 1由于目前我国重型自卸汽车生产厂家不多，产量也很少，且根据该矿具体情况和实践经验，能符合该矿需要吨位的汽车只有两个系列的产品可供选用，即北京重型汽车制造厂引进英国技术生产的 RD 系列汽车和内蒙古第二机械厂与美国联合生产的 33 系列汽车。因此，该矿在近几年内主要使用这两种系列的汽车进行更新。今以年为周期，从 1988 年开始，为使该汽车使用的总收益最大，从1988 年至 1992 年 5 年内每年年初时，对买新车（P：Purchase）还是维修留用旧车（K：Keep）问题作出决策。已知到 1988 年初 T20-203 型汽车已使用 7 年，而 BJ731 型汽车也使用了 5 年。到 1992 年这 5 年内，如果继续使用旧车，对所发生的各项费用或更换新车费用如表 2 所示；如在这 5 年内用 33-001 型汽车更新，各项费用见表 3 所示；如用 RD150-1 型汽车更新，费用如表 4 所示。岩石坠场河北经贸大学毕业论文13表 2（万元）型号T20-203(6 年)BJ731(4 年)使用年数789101156789年收益11.51110.510913.61312.712.311.5年使用费6.78.67.59.58.56.17.36.88.88.4更新车5658606365625254565858606264675456596062表 3（万元）表 4（万元）起始年19881989199019911992使用年数012340123012010年收益283029272528302927293028293030年使用费891112138.59.51211.5 8.5101291010.5更新费384042444639414345404244404241建模为了建立汽车更新的数学模型，规定符号如下：)0(ir第i周期从新购汽车处所获得的收益；)(yri第i周期从已使用了 y 年的汽车处所获得的收益；)0(iu第i周期新汽车的使用费用；)(yui第i周期已使用了 y 年的汽车的使用费用；)(yci第i周期安装，已使用了 y 年的汽车更新费用，该车是在)(yi 年出厂的新车；起始年19881989199019911992使用年数012340123012010年收益252626252425272825262728293030年使用费68108116810.597910910.5 9.5更新费303436384032343638333537353736河北经贸大学毕业论文14T现有汽车的使用年数；A折算系数（因工业利率为 1.5%，故这里 A 的取值为 0.9985）；)(yfi第i周期初，对使用了 y 年的汽车在第mii,1,周期中所获得的最优收益；)(ydi第i周期初，为获得)(yfi作出的决策（决策只有两种，买新车（P）或维修旧车（K）。假定在第i周期初是一辆新车，则在第mii,1,周期所获得的总收益为：第i周期内从新车获得的收益)0(ir减去在第i周期内新车的使用费用)0(iu，再减去在第i周期初已经使用了 y 年的汽车更新费用)(yci，再加上在第mii,2,1周期初已使用了 1 年的汽车所获得的最优收益（将其乘以折算系数 A，折算为第i周期初所获得的最优收益），即A)(yfi，那么更新的总收益为：P：)0(ir-)0(iu-)(yci+A)1(1if同样，在假设第i周期仍然使用已经用了 y 年的汽车，则在第mii,1,周期所获得的总收益为：第i周期内这辆已使用了 y 年的汽车的收益)(yri减去第i周期已使用了 y 年的汽车的使用费用)(yui，加上第mii,2,1期初已使用了 y+1 年的汽车的最优收益（将其乘以折算系数 A，折算为第i周期初所获得的最优收益，即 A1(1)ify，所以留后用的总收益为：K：)(yri-)(yui+A1(y 1)if由此，第i周期已使用了 y 年的汽车，在第,1,i im 周期所获得的总收益)(yfi的基本方程为：)1()()(:)1()()0()0(:max)(11yAfyuyrKAfycurPyfiiiiiiii1,2,;1,2,1,1im yiiT规定：Tmyyfm,2,1,0)(1计算T20-203 型汽车已用了 7 年，BJ371 型汽车已用了 5 年，他们的服务年限均为 8 至 10 年，所以从 1988 年至 1992 年的 5 年内，这两种型号的汽车都需要更新。这里就将此周期定为 5。T20-203 型汽车和 BJ371河北经贸大学毕业论文15型汽车已使用年限数 T 分别为 7 年和 5 年。对于 T20-203 型汽车若采用 33-001 型汽车更新，各周期的最优收益及决策可计算如下：（1）逆序最优目标函数值集合与最优决策集合。当5i时，使用年数1,2,3,4,11y 年，其最优收益和决策为：55565556:(0)(0)(1)(1)y=1,(1)max:(1)(1)(2)P rucAffK ruAf:309.5370.9985016.5max:3010.50.9985019.5PK 故Kd)1(555565556:(0)(0)(2)(1)y=2,(2)max:(2)(2)(3)P rucAffK ruAf:309.537016.5max:27 10017.0PK 故Kd)2(555565556:(0)(0)(3)(1)y=3,(3)max:(3)(3)(4)P rucAffK ruAf=0.160925:5.170385.930:maxKP故Kd)3(555565556:(0)(0)(4)(1)y=4,(4)max:(4)(4)(5)P rucAffK ruAf=0.1301124:5.190405.930:maxKP故Kd)4(555565556:(0)(0)(11)(1)y=11,(11)max:(11)(11)(12)P rucAffK ruAf河北经贸大学毕业论文16=5.005.89:5.440655.930:maxKP故Kd)11(5表 5使用年数123411)(5yf19.517.016.013.00.5)(5ydKKKKK第 5 周期 T20-203 型汽车用 33-001 型汽车更新，在不同使用年数的最优效益)(5yf及其决策)(5yd如表 5 所示。当4i 时，使用年限1,2,3,10y，其最优收益及决策如下：44454445:(0)(0)(1)(1)y=1,(1)max:(1)(1)(2)P rucAffK ruAf:299350.9985 19.54.47max:2890.9985 1735.9736.0PK 故Kd)1(444454445:(0)(0)(2)(1)y=2,(2)max:(2)(2)(3)P rucAffK ruAf:299360.9985 19.53.47max:27 100.9985 16.032.5PK 故Kd)2(444454445:(0)(0)(3)(1)y=3,(3)max:(3)(3)(4)P rucAffK ruAf=:299380.9985 19.51.47max:2580.9985 13.029.9830.0PK 故Kd)3(444454445:(0)(0)(10)(1)y=10,(10)max:(10)(10)(11)P rucAffK ruAf河北经贸大学毕业论文17=:299630.9985 19.523.53max:109.50.9985 0.50.9991.0PK 故Kd)10(4表 6使用年数12310)(4yf36.032.530.01.0)(4ydKKKK第 4 周期 T20-203 型汽车用 33-001 型汽车更新，在不同使用年数的最优效益)(4yf及其决策)(4yd如表 6 所示。可类似计算出第 3 周期和第 2 周期的最优收益及决策如表 7 所示。表 7第 3 周期第 2 周期使用年限12918最优收益52.445.9463.913.3最优决策KKKKK最后，当1i时，7y则)8()7()7(:)1()7()0()0(:max)(21111111AfurKAfcurPyf:256560.9985 63.926.8max:11.56.70.9985 13.318.08PK故Pd)7(1（2）求解情况如下。根据上面的计算结果，T20-203 型汽车用 33-001型汽车更新，在 1988 年以后的 5 年内的最优决策可归纳为表 8 所示。得出 T20-203 型汽车在 1988 年初用 33-001 汽车更新，这样到 1992 年获得的总收益为最大，最大收益为 26.8 万元，并且在 1988 年初更新比保留使用每台将增加收益 8.72 万元。同样，可以计算出其他三种情况，T20-203 型用 RD150-1 型更新、BJ371型用 33-001 型、RD150-1 型更新时，在 1988 年以后的 5 年内最优收益及决策如表 9 所示。河北经贸大学毕业论文18表 8周期使用年限决策171(7):dP212(1):dK323(2):dK434(3):dK545(4):dK表 9RD150-1 更换 T20-20333-001 更换 BJ371RD150-1 更换 BJ3711PPP2KKK3KKK4KKK5KKK最优收益（万元）27.832.731.7结论与分析：由以上的计算结果（表 8 和表 9）可知，该矿现有汽车若采用技术更新方式，原 T20-203 型汽车选用 RD150-1 型汽车在 1988年初更新，计算周期内获得的总收益最大为 27.8 万元，比留用可多获收益 15.6 万元/台。原 BJ371 型汽车选用 33-001 型汽车在 1988 年初更新名计算周期内的最大收益为 32.7 万元，比留用可多获得 7.2 万元/台。如果选用此最优决策的话，该矿就更新一项就可以节约（相对也即收益）（15.640+7.225）万元=804 万元，占该矿一年上缴利税的67%，是一个相当可观的数字。由此可以看出最优化方法的作用所在。但值得注意的是，此处的优化是按一个指标，即 5 年内受益最大为目标进行的。在实际工作中，还需要考虑其他方面的一些因素。比如 1988年初一次性将 65 台汽车全部更新，所需费用相当大，该矿是否承受的了。对于 BJ371 型汽车更新，在收益上只比用 33-001 型汽车少 1 万元。如果 65 台汽车均为 RD150-1 型，则用在维护保养方面都有一定的好处等等。河北经贸大学毕业论文19五、结论动态规划是一种效率很高的技术。这种方法最大优点就是节约了时间，并找到最优解。由以上两个例子可以看出，领悟、理解动态规划的思想，掌握动态规划的解题技，用其解决生产领域的一些问题往往能够达到比较好得效果。使资源能够得到充分的分配利用，有利于我国工业的进一步发展。由于其应用的广泛性，在其他领域的研究也不断加深。河北经贸大学毕业论文20参考文献1 冯小虎，动态规划思想在算法设计中的应用J，安徽电子信息职业技术学院学报，2004 第二期第三卷2 秦裕缓，Bellman 最优性原理论动态规划(I)J，应用数学MATHEMATICAAPPLICATA1994,7(3)：349 3543 朱丽娜，马家余，浅论动态规划优化模型在设备更新中的应用J，沿海企业与科技，2006 年第 3 期 总第 73 期4 阮玉红，设备更新问题的运筹学模型J，机械管理开发，第 1期(总第 70 期)No.l(SCM No.70)5 樊飞，刘启华，运筹学发展的历史回顾J，南京工业大学学报(社会科学版)6 吴厚山，设备更新的最佳年限的决策模型J，数学通讯 2001年第 13 期：25 页7 王宝森，辽宁化工，关于设备更新的经济分析与探讨J，第 31卷第 4 期，2004 年 4 月8 王刚，动态规划的应用实例J，云南财贸学院学报经济管理版，第 15 卷 综合刊 2001 年 6 月9 孙晓君，基于 1VIATLAB 的动态规划逆序算法的实现J，纺织高校基础科学学报，第 15 卷第 1 期，2002 年 3 月10 蒋海波，何莉，李恩，生产计划的优化模型J，成都大学学报(自然科学版)，第 15 卷 第 3 期 1996 年 9 月11 樊孝仁，余建忠，一类生产计划的优化管理J，太原理工大学学报，第 30 卷第 4 期，1999 年 7 月12 孙晚华，关于动态规划顺序求解法的教学探讨J，北京交通大学学报(社会科学版)第 3 卷第 1 期，2004 年 3 月13 朱清新，最优搜索理论及其应用J，世界科技研究与发展，专题:信息技术，2005 年 8 月：394914 卢志文，基于动态规划资源分配算法J，福建电脑，2005 年第 2 期15Frederick S.Hiller,Gerald J.Liberm