动态规划习题.pdf

学 海 无 涯 第七章 动态规划 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线 性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会 面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动 过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集 合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构 成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以 有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不 同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取 一个最优的策略，以便得到最佳的效果。动态规划 （dynamic programming ）同前面介绍过 的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多 阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然， 由于动态规划不是一种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明 确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中， 有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规 划的主要创始人是美国数学家贝尔曼（Bellman ）。20 世纪40 年代末 50 年代初，当时在兰 德公司（Rand Corporation ）从事研究工作的贝尔曼首先提出了动态规划的概念。1957 年贝 尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一 的进一步研究和应用动态规划的理论源泉。1961 年贝尔曼出版了他的第二部著作，并于1962 年同杜瑞佛思（Dreyfus ）合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广 这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的 是爱尔思（Aris ）和梅特顿（Mitten ）。爱尔思先后于1961 年和1964 年出版了两部关于动态 规划的著作，并于 1964 年同尼母霍思尔（Nemhauser ）、威尔德（Wild）一道创建了处理分 枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要 意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献。 动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的 效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问 题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中 一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划 更有效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常 有用的工具。 动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划； 也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要 介绍动态规划的基本概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。 §7.1 动态规划的基本理论 1.1 多阶段决策过程的数学描述 有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应 的决策，以使整个过程达到最佳的活动效果。任何一个阶段（stage，即决策点）都是由输 入（input）、决策（decision）、状态转移律（transformation function）和输出（output） 构成的，如图 7-1 （a）所示。其中输入和输出也称为状态（state），输入称为输入状态， 输出称为输出状态。 1 学 海 无 涯 决 策 dn 输 入 输 出 Sn Sn+1 阶 段