1、毕业论文 文客久久 本科 毕业设计 (论文 ) 题 目： 动态规划方法及其在资源分配问题中的应用 学 院： 学生姓名： 专 业： 信息与计算科学 班 级： 指导教师： 起 止 日期： 毕业论文 文客久久 摘要 动态规划问题是一个应用极为广泛的问题 , 它在工程技术、最优控制和生产调度等方面的应用也是相当广泛的 , 动态规划也是计算机科学和运筹学的重要内容 . 20 世纪 50 年代初 , 美国数学家 R. E. Bellman 等人在对多阶段决策过程 (Multistep decision process)的优化问 题研究过程中 , 提出了著名的最优性原理 (Principle of opti
2、mality), 把一类多阶段过程转化为一系列相互联系的单阶段规划问题 . 而最近几十年来关于动态规划在资源分配方面的研究有很大进展 , 研究成果也是层出不穷 , 本文基于以往学者的研究成果上对资源分配问题进行了分析与总结 , 并给出了动态规划及其在资源分配问题的算法的求解过程 , 也涉及在实际生活中的应用 . 最后介绍了现在流行的一些动态规划主要算法和实例 , 并运用 delphi, excel 和 lingo方法解决资源分配问题 . 关键词 : 动态规 划 ;逆推法 ;资源分配问题 ;最优性原理 毕业论文 文客久久 Dynamic programming and its applicati
3、on in resource allocation problems Abstract Dynamic programming is a very extensive application, which is widely used in production scheduling, engineering technology and optimal control. And the dynamic programming is the important content of computer science and operational research. R. E. Bellman
4、 who is the United States mathematician, proposed the famous idea which is the optimum Principle. When he studyed the optimization problem of Multistep decision process in the 1950s, he translated multistep decision process into a series of interconnected single stage programming problems. In recent
5、 decades the research of dynamic programming in the resource allocation problem has the very big progress, and the results of research also emerges in endlessly. This paper analyzes and summes up the results which is based on the previous research of resource allocation problems, and brings forward
6、the process about the solution of the algorithm in the dynamic programming and the resource allocation problems, also involves in the actual life application. At last, the paper introduces some mainly algorithm and practical examples which is often used in dynamic programming, and using Delphi, exce
7、l and lingo methods to solve resource allocation problems. Keywords: Dynamic programming; Inverse push method; The method of Resource allocation problems; Principle of optimality 毕业论文 文客久久 目录 摘要 .I Abstract . II 1 前言 . 1 2 理论基础 . .2 2.1 相关定义 . 3 2.2 动态规划的最优定理 . 5 3 逆推法 . 6 3.1 逆推过程 . 6 3.2 结果计算过程 .
8、7 3.3 逆推法的 delphi实现 .7 3.4 逆推法的 excel实现 .13 3.5 逆推法的 lingo实现 .14 4 资源分配问题的其他算法简要介绍 . .20 5 小结 .22 参考文献 . 23 致谢 . 24 毕业论文 文客久久 1 前言 动态规划 1 应用非常广泛 , 在 生产调度、工程技术和最优控制 中的最优问题 2 . 例如最短路线 3 、生产调度问题 4 、 设备更新、排序、装载 5 等 , 在资源分配问题 6 中尤其重要 . 动态规划问题已经有几十年的研究历史 , 在这几十年 中 , 人们已经建立了动态规划问题比较完善的理论 , 从 R. E. Bellman
9、6 提出的最优性原理至今 , 很多学者都对其进行了研究和改进并提出了很多新的算法 , 根据动态规划问题的计算过程的特殊性 , 其每一阶段求出最优值是都要把相应的状态集合存入内存中去 , 从而造成了计算机使用的内存要成倍增加 . 虽然也有不少方法减少了这种障碍 , 如多项式逼近法 7 , 逐次逼近法 8 , 状态微增法 9 , 拉格朗日乘数法 7 等等 . 所以动态规划在未来的发展空间将会大大提升 , 由于其实用性较强所以其在实际生活中应用还是相当广泛的 . 最近也有很多关于动态规划其他方面问题的研究 , 而且发展迅速 , 但是本文主要讲述的是动态规划方法和其在资源分配问题中的应用 , 并不涉及
10、库存等问题 . 下面简要介绍一下本文的大概内容 : 本文第一部分介绍与动态规划问题有关的定义及定理 , 第二部分介绍最常见的逆推算法 , 第三部分简要介绍有关动态规划问题几种其他算法 , 后面一部分对本文讲述的方法及举例进行总结 , 最后一部分是致谢 . 毕业论文 文客久久 2 理论基础 2.1 相关定义 从文献 6 中我们可以得出所有动态规划问题都必须涉及到以下定义 : 定义 2.1 我们把 在整个动态规划过程的一个自然划分我们称为阶段 , 通常可以根据时间顺序或空间特征来划分阶段 , 以下是按阶段的次序解优化问题 .一般用 k 表示阶段变量 . 例如 : 由 A 出发为 1k , 由 (
11、1,2)iBi 出发为 2k , 依次下去从 ( 1,2)iFi出发为 6k , 共有 6n 个阶段 . 定义 2.2 每个阶段开始时过程所处的自然状况叫作一个状态 . 它应能描述过程的特征并且具有无后效性 , 即 当某阶段状态给定时 , 这个阶段以后过程的演变过程与该阶段以前各阶段的状态没有关联 . 一般来说还要求状态是可以间接或者直接观测到的 . 描述某个状态的变量称为状态变量 (State variable). 变量所允许取值的集合称为允许状态集合 (Set of admissible states). 第 k 阶段的状态变量用 ks 表示 , 它不但可以表示一个实数更可以表示一个向量
12、. 第 k 阶段的允许状态集合用 kS 表示 . 其中 n 阶段的决策过程共有状态变量 1n 个 , 1ns 表示 ns 演变的结果 . 我们根据每个过程演变的具体分析 , 可以把状态变量分为离散的和连续的 . 在分析的过程中有时将离散的变量连续化 ; 有时在计算过程中把变量离散化 . 有时我 们把状态变量简单地叫做状态 . 定义 2.3 当某个阶段的状态被确定后 , 可以作出多种选择变成下一阶段的某个状态 , 这种选择过程称为决策 , 在最优控制问题中把这种选择称为控制 (Control). 我们把描述某一决策的变量称为决策变量 (Dicision variable), 或叫做决策 .同样把
13、变量允许的取值范围称为允许决策集合 (Set of admissible decision). 第 k 个阶段处于第k 个状态 ks 时的决策变量用 ()kkus 表示 , 它是 ks 的函数 , ks 的允许决策集合用毕业论文 文客久久 ()kkDs 表示 . 定义 2.4 所谓策略就是一连串决策共同组成的一个序列 , 我们不妨记 11()nps为从初始状态 1s 开 始的 所有过 程的策 略 , 即 1 1 1 1 2 2( ) ( ) , ( ) , , ( ) n n np s u s u s u s . 记()kn kps为由第 k 阶段的所处的状态 ks 开始到终止状态的后部分子过
14、程的策略 , 即( ) ( ) , , ( ) , 2 , . . . , 1k n k k k n np s u s u s k n ,类似的 , 记 ( ) ( ) , , ( ) kj k k k j jp s u s u s 为由第 k 到第 i 阶段的子过程的策略 . 我们把可供选择的策略一定的范围称为允许策略集合 (Set of admissible policies), 用 11()nps, ()kn kps , ()kj kps表示 . 定义 2.5 在一个确定的过程中 , 如果某阶段的状态和决策已经知道 , 那么下阶段的状态便完全可以由上阶段的状态和决策确定 . 我们这种演变
15、规律为状态转移方程 , 记作 1 ( , ) , 1 , 2 , ,k k k ks T s u k n . 定义 2.6 指标函数是衡量某一过程好坏的数量上的指标 , 它是定义在整个全过程和后部子过程上的数量函数 , 用 11( , , , , )kn k k k nV s u s s表示 , 1,2,.,kn . 指标函数是可分离的 , 即 knV 可表示为 ( 1),k k k ns u V 的函数 , 记为 1 1 ( 1 ) 1 1( , , , , ) , , ( , , ) k n k k k n k k k k n k nV s u s s s u V s s 并且函数 k 关
16、于变量 ( 1)knV 的严格的单调函数 . 状态 js 和决策 ju 决定了第 j 阶段的阶段指标 , 用 ( . )j j jv s u 表示 , 指标函数由( 1, 2,., )jv j n 组成 , 最常见的有以下几种形式 : 所有阶段指标之和 : 11( , , , , ) ( , )nk n k k k n j j jjkV s u s s v s u所有阶段指标之积 : 11( , , , , ) ( , )nk n k k k n j j jjkV s u s s v s u 在这些形式下称 1( , , , )kj k k jV s u s 为第 k 到第 j 阶段的子过程的
17、指标函数 . 毕业论文 文客久久 由其中的状态转移方程 , 我们还可以把指标函数 knV 表示为状态 ks 和策略 knp 的函数 , 即 ( , )kn k knV s p . 在状态 ks 给定的指标函数 knV 对 knp 的最优的值称为最优值函数 , 记作 ()kkfs , 即 ()( ) ( , )kn kn kk k kn kn knp P sf s o p t V s p其中 opt 可依据具体情况取 max 或 min . 因此在不同的问题中 , 指标函数的含义是不同的 , 它可能是距离、时间、利润、成本等 . 定义 2.7 从 k 开始的后部子过程的最优策略就能让指标函数 k
18、nV 达到最优值 , 记作 * * * , , kn k np u u *1np 表示全过 程当中的最优策略 , 简称最优策略 . 从初始状态 *11()ss 出发 , 过程按照 *1np 和状态转移方程演变所经历的状态序列* * *1 2 1 , ,., ns s s 称为最优轨线 . 毕业论文 文客久久 2.2 动态规划的最优定理 最优定理是由 R. E. Bellman 等提出的 , 有时我们也把它叫做最优性原理 . 它在动态规划中是一个非常重要的定理 , 也是所有动态规划问题中的理论基础 . 以下是对最优定理的介绍 : 设阶段 数 n 为的多阶段决策过程 , 其阶段编号为 nu 允许策
19、略 * * *0 , 1 0 1( , , ,np u u *1)nu 为最优策略的充要条件是对任意一个 k 0001S n s S 和 有 0 , 1 0 , 1 0 , 1 , 1*0 , 1 0 0 , 1 0 , 1 0 0 , 1 , 1 , 1() ()( , ) ( , ) ( , ) kkk n k n kn n k k k n k k np p s p p sV s p opt V s p opt V s p 式中0 , 1* 0 , 1 , 1( , )n k k np p p , 1 1 1( , )k k k ks T s u , 它是由给定的初始状态 0s 和子策略0
20、, 1kp 所确定的 k 段状态 . 当 V 是有效函数时 , opt 取 max ;当 V 是损失函数时 , opt取 min . 根据动态规划的前后关联性 , 通过分解成一系列的单阶段决策过程 , 然后逐个加以解决 , 从而求出了整个问题的最优决策序列 . 最为常用的两种方法为逆推法和顺推法 . 由于两种方法计算方法相似 , 故我们就拿逆推法来说明举例 . 毕业论文 文客久久 3 逆推法 逆推法顾名思义就是利用一些关系对整个过程进行逆向推算 , 从而得出最终结果 .它是动态规划最基础的方法 , 后来的方法都是基于此 方法改进的 . 下面就介绍整个逆推法过程 . 3.1 逆推过程 下面就以逆
21、推法为例解决动态规划问题 : 111111 1 1( , ) ( , ) ( , )1 knk k n nk k k n n ns s s ssss x s x s xkn 决 策 x 决 策 x决 策 x状 态效 益 v v v设初始状态为 1s 是已知 , 并假设最优值函数 ()kkfs 表示第 k 阶段的初始状态 ks , 从 k 阶段到 n 阶段所得到的最大效益 , 上图为 n 阶段的决策过程 . 从第 n 阶段开始 , 则有 ()( ) m a x ( , )n n kn n n n nx D sf s v s x其中 ()nnDs 是由状态 ns 所确定的第 n 阶段的允许 决策集
22、合 . 求解这个极值问题 , 就能得到最优的解 ()n n nx x s 和最优值 ()nnfs , 需要我们着重注意的是 , 若集合 ()nnDs有且只有唯一一个决策 , 则 ()n n nx D s 就应写成 ()n n nx x s . 在第 1n 阶段 , 有 111 1 1 1 1()( ) m a x ( , ) ( ) n n nn n n n n n nx D sf s v s x f s 其中 1 1 1( , )n n n ns T s x ;解这个极值问题 , 就能得到此阶段的最优解 11()n n nx x s和对应的最优值 11()nnfs. 在第 k 阶段 , 有 1 1 1 1()( ) m a x ( , ) ( ) k k kk k k k k k kx D sf s v s x f s
