动态规划模型及其应用.doc

《动态规划模型及其应用.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、动态规划模型及其应用　　【摘要】在过去五十多年的进程中，动态规划在运筹学、控制论、管理科学等领域的发展中，都发挥了无可比拟的领军作用，动态规则是研究多阶段决策过程最优化的一种方法，在生产实践中有很大的实用价值，成为解决数学建模问题最常用的优化方法之一。　　【关键词】动态规划；模型；应用　　本文主要讨论动态规划模型的建立以及模型的应用。动态规划模型是求解决策过程最优化的数学方法，在生产实践中有很大的实用价值，本文采用数学建模的形式，将生活中的一些实际问题用数学模型表示出来，以生产―库存管理系统为例，并且根据动态规划模型的相关原理，查阅相关文献，用数学的语言

2、提出解决办法，从而实现其为生产实践服务的目的。　　1、国内外对本课题涉及问题的研究现状　　动态规划发源于20世纪50年代左右，是目前用来解决多阶段决策过程最优化的一种方法。国内对动态规划的研究起步较晚，国外对此研究起源较早，且研究范围很广。根据了一类多阶段决策问题的特点，1951年，美国数学家理查德・贝尔曼提出了解决这类问题的“最优化原理”，由此，理查德・贝尔曼及学者将其应用于很多实际生活问题中，研究并解决问题，从而建立了运筹学的一个分支-动态规划。1957年，在美国普林斯顿大学，理查德・贝尔曼发表了第一本正式的著作。随后，理查德・贝尔曼与众多学者和科学

3、工作者发表了一些列动态规划应用的著作，包括动态规划在资源理论、最佳控制论、经济学、工业工程、马尔柯夫变分法和管理科学过程中的应用。因此在国内外，动态规划的发展始终伴随着它的广泛应用而不断臻善的。　　2、动态规划的优点　　动态规划的核心思想是美国数学家理查德・贝尔曼提出的最优化原理，该原理产生了分阶段决策的方法。分阶段决策的方法是在整体最优化的基础之上建立的，在探寻某一阶段决策时，既要对局部的利益进行考虑，而且还应顾及到总体的最优。动态规划通过分阶段处理一个N维变量处理的复杂问题，将N维变量问题转化为求解N个单变量问题，将解决过程大大简化，节省了大量的计算

4、量，这是一个典型的求解极值方法无法做到的。目前，动态规划几乎超越了所有的计算方法，特别是大大超越了经典的优化方法，它可以确定绝对最大或最小，而不是相对的极值，所以我们不再需要再担心的局部最大值或最小值的问题。动态规划的另一个特点是泛函方程的“嵌入”特性。动态规划方法不仅能求出整个过程的某一个特定的状态的一个值，同时也为后面子流程的所有可能出现状态的一族解。　　3、动态规划建模在实际生活中的应用　　下面举例说明动态规划在生产―库存管理系统的模型及求解。设每一个季度为一个阶段，并且取第k季度初具有的产品数为状态变量xk；取第k季度需要生产的产品数为决策变量u

5、k；第k季度的销售量为sk。显然由状态xk采取决策uk后的状态转移方程为：Xk+1=Xk+Uk-Skk=1，2，3，4对现在的问题，效益就是费用，故阶段效益为　　d=Xk+0.005U2k　　若用fk表示从状态xk出发，采用最优策略到第四季度结束时的最小费用，则有如下的模型：　　fk=min{xk+0.005uk2+fk+1}　　f5=0，k=4，3，2，1　　下面，我们用逆推算法求解以上模型。1、先从最后一个季度k=4考虑起，即求：u4≥1200-x4时，f4=min{x4+0.005u42}由x5=0和状态转移方程可得：0=x4+u4-s4=x4+u

6、4-1200从而得到u4=1200-x4，代入f4可得：f4=7200-11x4+0.005x42　　2、再考虑k=3，即求u3≥500-x3时，f3=min{x3+0.005u32+f4}=min{x3+0.005u32+7200-11x4+0.005x42}由状态转移方程可知：x4=x3+u3-s3=x3+u3-500　　代入f3可得：U3≥500-x3，f3=min{x3+0.005u32+7200-11+0.0052}　　利用微积分求极值方法，令0.01u3-11+0.01=0解得u3=800-0.5x3　　f3=7550-7x3+0.0025x

7、32　　3、再考虑k=2，求极值问题。u2≥700-x2时，f2=min{x2+0.005u22+7550-7x3+0.0025x32}仍由状态转移方程可知：x3=x2+u2-700代入可有　　u2≥700-x2时，f2=min{x2+0.005u22+7550-7+0.00252}再令　　0.01u2-7+0.005=0解得：u2=700-x2/3　　f2=10000-6x2+*x22　　4、再考虑k=1，求极值问题。u1≥600-x1，f1=min{x1+0.005u12+10000-6+*2}仍令{x1+0.005u12+10000-6+*2}=0

8、　　可得：0.01u-6+*=0注意到x1=0，于是有：　　u1=600，f1=