运筹学课程作业——动态规划算法的应用 .pdfVIP

真诚为您提供优质参考资料，若有不当之处，请指正。

中国地质大学

研究生课程论文封面

课程名称运筹学

教师姓名王广民

研究生姓名谢盼盼

研究生学号120100887

研究生专业工商管理

所在院系经济管理学院

类别:A.博士B.硕士C.进修生

日期:2010年12月25日

1/10

真诚为您提供优质参考资料，若有不当之处，请指正。

评语

对课程论文的评语:

平时成绩：课程论文成绩：

总成绩：评阅人签名：

注：1、无评阅人签名成绩无效；

2、必须用钢笔或圆珠笔批阅，用铅笔阅卷无效；

3、如有平时成绩，必须在上面评分表中标出，并计算入总成绩。

2/10

真诚为您提供优质参考资料，若有不当之处，请指正。

动态规划算法的应用

摘要：从动态规划的基本概念入手，介绍了多阶段决策问题、阶段与状态、决策与策略等一些专有

名词的定义；利用一些常见的实例阐述了动态规划在设计与实现时的多样性、模式性和技巧性等特

点；最后通过一个具体问题的解决过程，可以看出动态规划是一个必不可少的有利工具。通过问题

描述、样例分析、算法设计、问题实现、测试结果等几个步骤详细讨论了动态规划在应用中的实现

过程和思考方法，体现出在应用中相应的实践指导意义。

关键词：动态规划；算法

1引言

动态规划（DynamicProgramming）是运筹学的一个分支，是求解决策过程（DecisionProcess）

最优化的数学方法。20世纪50年代初美国数学家R.EBellman等人在研究多阶段决策过程（Multistep

DecisionProcess)的优化问题时，提出了著名的最优化原理(PrincipleofOptimality)，把多阶段过程转

化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。

动态规划问世以来，在城市规划、经济管理、生产调度、工程技术和最优控制等方面得到了广

泛的应用。例如神经网络、生物有机体DNA的相似程度分析、最短路线、库存管理、资源分配、资

产投资、证券交易、经营决策、企业生产物流控制、农业灌溉阅、施工计划安排、单一品种项目的

生产批量问题、设备更新、最优化设计、学习方法、排序、装载等问题，用动态规划方法比用其它

方法求解更为方便。动态规划主要用于求解以时间划分阶段的动态过程的优化问题，而且一些与时

间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策

过程，也可以用动态规划方法方便地求解。

2动态规划的基本概念

动态规划是算法设计的一种重要手段，在各行各业的程序设计中被应用得越来越普遍。因此，

如何更深入地了解动态规划，从而更为有效地运用算法设计的这个有力武器，是一个值得深入研究

的问题。首先来了解一些动态规划的基本概念：

（1）阶段与阶段变量

将所有问题的过程，按照时间或空间特征，划分成若干个相互联系的子问题，则每个子问题称

为一个阶段。用来表示阶段的变量称为阶段变量。

（2）状态与状态变量

过程中各个阶段开始时所处的客观条件或位置称为状态。

动态规划的状态具有如下性质：当某阶段状态给定后，在这阶段以后过程的发展不受这阶段以前各

段状态的影响。描述各阶段所处状态的变量成为状态变量。状态变量取值的集合称为状态集合。

（3）决策与决策变量

当各段状态取