动态规划算法原理与的应用

动态规划算法原理及其应用讨论系 别: ｘ ｘ ｘ 姓 名: x x x指导教员： ｘ x ｘ 2 ０ 1 ２年 5 月２ 0 日摘要:动态规划就是解决最优化问题得基本方法,本文介绍了动态规划得基本思想与基本步骤,并通过几个实例得分析,讨论了利用动态规划设计算法得具体途径。关键词:动态规划 多阶段决策１、引言 规划问题得最终目得就就是确定各决策变量得取值，以使目标函数达到极大或微小。在线性规划与非线性规划中,决策变量都就是以集合得形式被一次性处理得;然而,有时我们也会面对决策变量需分期、分批处理得多阶段决策问题。所谓多阶段决策问题就是指这样一类活动过程:它可以分解为若干个互相联系得阶段，在每一阶段分别对应着一组可供选取得决策集合;即构成过程得每个阶段都需要进行一次决策得决策问题。将各个阶段得决策综合起来构成一个决策序列,称为一个策略。显然，由于各个阶段选取得决策不同,对应整个过程可以有一系列不同得策略。当过程实行某个具体策略时,相应可以得到一个确定得效果,实行不同得策略,就会得到不同得效果。多阶段得决策问题，就就是要在所有可能实行得策略中选取一个最优得策略,以便得到最佳得效果。动态规划就是一种求解多阶段决策问题得系统技术,可以说它横跨整个规划领域(线性规划与非线性规划)。在多阶段决策问题中,有些问题对阶段得划分具有明显得时序性,动态规划得“动态”二字也由此而得名。动态规划得主要创始人就是美国数学家贝尔曼(Ｂ ell ｍ an)。２ 0 世纪４０年代末 50 年代初，当时在兰德公司(Ran ｄ Corporati ｏ n）从事讨论工作得贝尔曼首先提出了动态规划得概念。1957 年贝尔曼发表了数篇讨论论文，并出版了她得第一部著作《动态规划》。该著作成为了当时唯一得进一步讨论与应用动态规划得理论源泉。在贝尔曼及其助手们致力于进展与推广这一技术得同时，其她一些学者也对动态规划得进展做出了重大得贡献,其中最值得一提得就是爱尔思(A ｒ i ｓ)与梅特顿（Mitt ｅ n)。爱尔思先后于 1961 年与１ 9 ６４年出版了两部关于动态规划得著作,并于 196 ４年同尼母霍思尔(Ｎ e ｍ hauser)、威尔德(W ｉｌ d）一道创建了处理分枝、循环性多阶段决策系统得一般性理论。梅特顿提出了许多对动态规划后来进展有着重要意义得基础性观点,并且对明晰动态规划路径得数学性质做出了巨大得贡献。动态规划问世以来，在工程技术、经济管理等社会各个领域都有着广泛得应用,并且获得了显...