运筹学课件 第五章动态规划.ppt

第五章 动 态 规 划 一、综 述 动态规划解决多阶段决策过程最优化的一种数学方法，大约产生于50年代。 1951年美国数学家贝尔曼 (R. Bellman)等人根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。与此同时，他提出了解决这类问题的 “最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新的方法——动态规划。他的名著 《动态规划》于 1957年出版，该书是动态规划的第一本著作。 动态规划的方法在工程技术 、企业管理 、工农业生产及军事部门中都有广泛的应用 ，并且获得了显著的效果。 在企业管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等，所以它是现代企业管理中的一种重要的决策方法。 许多问题用动态规划的方法处理，常常比线性规划或非线性规划更有效，特别是对于离散性的问题。应当指出，动态规划是求解问题的一种方法，是考察问题的一种途径，而不是一种特殊的算法 (如线性规划是一种算法)。 动态规划它不像线性规划那样有一个标准的数学表达式和明确的一组规则，而必须对具体的问题进行具体的分析和处理。因此，在学习动态规划时，除了要对动态规划的基本概念和方法正确理解外，还应该以丰富的想象力去建立模型，用创造性的技巧去求解。 动态规划所研究的对象是多阶段决策问题。 多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。 每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。 二、 多阶段决策问题 1、多阶段决策问题的描述 一个决策问题常与时间联系，将时间作为变量的决策问题称为动态决策问题。在动态决策问题中，研究对象——系统所处的状态和时点都是进行决策的重要因素。决策者要在系统发展的不同时点，根据系统的当前状态，不断地作出决策。因此，多次决策是动态决策的一个基本特点。 在多阶段决策过程中，系统的动态过程可以按照时间的进程分为若干个相互联系的阶段，而在每一个阶段中，具有一个或多个状态，在每一个阶段中都要针对每一个状态作出决策。 在各个阶段的决策确定以后，就顺序构成了一个决策序列，称为一个策略。 由于每个阶段有多种决策，因此，形成有多种策略可供选择，策略不同经济效果也不一定相同。 多阶段决策问题，就是在允许选择的策略集内选择一个最优策略，使在预定的标准下，达到最好的经济效果。 2、多阶段决策案例 介绍一个经典的多阶段决策问题— 最短路线问题的求解。 例 1 如下图所示，要从 A地出发到达 B地，如何走，使总路程最短，最短路是多少? 生活中的常识告诉我们 ，最短路有一个重要的特性：如果由起点 A经过 P点和 H点而到达终点 G是一条最短路线，则由点P出发经过 H点到达终点 G的这条子路线，对于从点 P出发到达终点的所有可能选择的不同路线来说，必定也是最短路。此特性用反证法易证 。 因为如果不是这样 ，则从点 P到 G点有另外一条距离更短的路线存在，把它和原来最短路线由 A点到达 P点的那部分连接起来，就会得到一条由 A点到 G点的新路线，它比原来那条最短路线的距离还要短些。这与假设相矛盾，是不可能的。 根据最短路线这一特性，寻找最短路线的方法，就是从最后一段开始，用由后向前逐步递推的方法，求出各点到终点的最短路线，最终求得由起点至终点的最短路线。所以，可以利用动态规划的方法从终点逐段向始点方向寻找最短的路线。 首先，将这一问题看成是四个阶段的问题，由①到 (②，③，④)中的点是第一阶段;由 (② 、③、④)中的点到 (⑤、⑥、⑦)中的一点是第二阶段;由 (⑤、⑥ 、⑦)中的点到(⑧、⑨)中的一点是第三阶段;由 (⑧ 、⑨)中的一点到⑩是第四阶段。 具体计算前，先引进几个符号: K— 阶段变量 sk— 状态变量，表示第 k阶段所处的位置。 Xk— 决策变量，表示当状态为 sk时，可选择的下一状态 (这里有Xk =sk十1) d (sk, Xk)— 从 sk到sk+1= Xk的距离。 fk(sk)— 由sk到终点的