文档介绍：运筹学 动态规划
*
第1页，本讲稿共67页
1 多阶段决策过程的最优化
概述
多阶段决策过程及其最优化
多阶段决策过程举例
动态规划求解的多阶段决策问题的特点
动态规划方法导引
*
第2页，本讲稿共67页
概，求出最优方案。这里从v1到v10的路程可以分为4个阶段。第一段的走法有三种，第二三两段的走法各有两种，第四段的走法仅一种，因此共有3×2×2×1＝12条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是v1 →v3 → v7 → v9 →v10，最短距离是18。
*
第13页，本讲稿共67页
显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算．
第二种方法：即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是v1→v3→v5→v8→v10，全程长度是20；显然，这种方法的结果常是错误的。
*
第14页，本讲稿共67页
第三种方法：动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为4个阶段，每次的选择总是综合后继过程的最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。
为了找出所有可能状态的最优后继过程，动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。
*
第15页，本讲稿共67页
从v10开始，因为v10是终点，再无后继过程，故可以接着考虑第4阶段上所有可能状态v8,v9的最优后续过程。因为从v8,v9到v10的路线是唯一的，所以v8,v9的最优决策和最优后继过程就是到v10，它们的最短距离分别是5和3。
接着考虑阶段3上可能的状态v5,v6,v7到v10的最优决策和最优后继过程。在状态v5上，虽然到v8是8，到v9是9，但是综合考虑后继过程整体最优，取最优决策是到v9，最优后继过程是v5→v9→v10，最短距离是12。同理，状态v6的最优决策是至v8；v7的最优决策是到v9。
*
第16页，本讲稿共67页
同样，当阶段3上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段2上所有可能状态的最优决策和最优后继过程，如v2的最优决策是到v5，最优路线是v2→v5→v9→v10，最短距离是15。…依此类推，最后可以得到从初始状态v1的最优决策是到v3最优路线是v1→v3→v7→v9→v10，全程最短距离是18。
图中粗实线表示各点到的最优路线，每点上方括号内的数字表示该点到终点的最短路距离。
*
第17页，本讲稿共67页
综上所述，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法较科学有效。
动态规划方法基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。
整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优值，然后再顺序地求出整个问题的最优策略和最优路线。
*
第18页，本讲稿共67页
2 动态规划的基本概念和基本原理
基本概念
阶段和阶段变量
状态、状态变量和可能状态集
决策、决策变量和允许决策集合
策略和允许策略集合
状态转移方程
指标函数
最优解
基本原理
多阶段决策问题的数学模型
动态规划方法的基本思想
*
第19页，本讲稿共67页
阶段和阶段变量
为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段(stage)。一个阶段，就是需要作出一个决策的子问题，通常阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量。阶段数等于多段决策过程从开始到结束所需作出决策的数目。
例5所示的最短路问题就是一个四阶段决策过程。k=1,2,3,4。
*
第20页，本讲稿共67页
状态、状态变量和可能状态集
用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态(state)。反映状态变化的量叫做状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。
按照过程进行的先后，每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终止状态记为sk+1。但为了清楚起见，通常定义阶段的状态即指其初始状态。
*
第21页，本讲稿共67页
一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关于状态的