第七章动态规划

《第七章动态规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第七章动态规划规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会而对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具休策略时，相应可以得到一个确定

2、的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略屮选取一个最优的策略，以便得到最佳的效果。动态规划(dy/m/mEprogramming)同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域(线性规划和非线性规划)。当然，由于动态规划不是一•种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，冇些问题对阶段的划分具冇明显的时序性，动态规

3、划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼(％/加期)。20世纪40年代末50年代初，当时在兰德公司(RcmdCgpomion)从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思Eg合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同吋，其他一些学者也对动态规划的发展做出了重大的贡献，其屮最值得一提的是爱尔思(Aris)和梅

4、特顿(Mi伽)。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔ZmhauE、威尔徳(W〃d)—道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划示来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨犬的贡献。动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用來解决授优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及牛产过程最优控制问题等，是经济管理屮—•种重要的决策技术

5、。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更冇效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也对以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要介绍动态规划的基木概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。§7.1动态规划的基本理论1.1多阶段决策过程的数学描述有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作岀相应的决策，以使整个过程达到最佳的活动效果。

6、任何一个阶段(stage,即决策点)都是由输入(inpul)、决策(decision)、状态转移律JIr&nsformationfunction)和输Hl(output)构成的，如图7-1(a)所示。其中输入和输出也称为状态(state),输入称为输入状态，输出称为输出状态。状态转移&=r(SnM(b)图7・1由于每一阶段都有一个决策，所以每--阶段都应存在一个衡量决策效益大小的指标函数，这一-指标函数称为阶段指标函数，用和表示。显然幻是状态变量S和决策变量况的函数，即的二厂(S,4),如图7-1(b)所示。显然,输出是输入和决策的函数,即：S”+】

7、=/(S”,d〃)(7-1)式(7-1)即为状态转移律。在由用个阶段构成的过程里，前一个阶段的输出即为后一个阶段的输入。1・2动态规划的基本概念动态规划的数学描述离不开它的一些基木概念与符号，因此有必要在介绍多阶段决策过程的数学描述的基础上，系统地介绍动态规划的一些基本概念。1.阶段(.stage}阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，常用/來表示。阶段的划分一•般是根据吋间和空间的自然特征來进行的，但要便于将问题的过程转化为多阶段决策的过程。对于具冇”个阶段的决策过程，其阶段变虽斤=1,2,・・•，N。2.状态(state)

8、状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。状态既反映前面各阶段系列决策的结局