第七章动态规划.ppt

1、第七章 动态规划,动态规划是解决多阶段策划过程最优化问题的一种方法。该方法是有美国数学家贝尔曼（R Bellman）等人在20世纪50年代初提出的。1957年，R Bellman发表了该分支领域的第一本专著动态规划（Dynamic Programming）。,动态规划模型的分类：离散确定型；离散随机型；连续确定型；连续随即型。其中离散确定型是最基本的，本章主要针对这种类型的问题，介绍动态规划的基本思想、原理和方法.,第1节 多阶段决策过程的最优化,多阶段决策过程，本意是指这样一类特殊的活动过程，它们可以按时间顺序分解成若干相互联系的阶段，称为“时段”，在每一个时段都要做出决策，全部过程的决策是

2、一个决策序列，所以多阶段决策问题属序贯决策问题。 多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。,生产与存贮问题 投资决策问题 设备更新问题,第2节 动态规划的基本概念和基本原理,动态规划的基本概念 阶段； 状态； 决策和策略； 状态转移； 指标函数。,动态规划的基本思想与基本原理 (1) 将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指函数，从而问题化成一族同类型的子问题，然后逐个求解。 （2）求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解

3、。 （3）动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。,第2节 动态规划模型的建立与求解,建立动态规划模型，就是分析问题并建立问题的动态规划基本方程。成功地应用动态规划方法的关键，在于识别问题的多阶段特征，将问题分解成为可用递推关系式联系起来的若干子问题，而正确建立基本关系方程的关键又在于正确选择状态变量，保证各阶段的状态变量具有递推的状态转移关系.,两种求解方法：逆序解法（后向动态规划方法）、顺序解法（前向动态规划法）。 寻优的方向与多阶段决策过程的实际行进方向相反，从最一段

4、开始逐段前推，求得全过程的最优策略，称为逆序解法。与之相反，顺序解法的寻优方向与过程的行进方向相同，计算时从第一段开始逐段向后递推，计算后一阶段要用到前一阶段的求优结果，最后一段计算的结果就是全过程的最优结果。,在建模时要注意以下区别： 状态转移方式不同 指标函数的定义不同 基本方程形式不同,基本方程分段求解时的几种常用算法 离散变量的分散穷举算法 连续变量的解法 连续变量的离散化解法 高维问题的降维法及疏密格子点法,第4节 动态规划在经济管理中的应用,二、生产经营问题,生产与贮存问题 采购与销售问题,设备更新问题,复合系统工作可靠性问题,某种机器的工作系统由n个部件组成，只要有一个部件失灵，

5、整个系统就不能正常工作。为提高系统工作可靠性，在每个部件上均装有方框方要的备用件，并地备用元件自动投入装置。显然，备用元件越多，整个系统工作的可靠性越大，但备用元件增多也会导致系统的成本、重量、体积相应增大，工作精度降低。因此，在考虑上述限制限制条件下，如何选择各种部件和备用元件数，使整个系统的工作可靠性最大。,货郎担问题,货郎担问题一般提法为：一个货郎从某城出发，经过若干个城镇一次，且仅一次，最后仍回到原出发的城镇，问应如何选择行走路线可使总行程最短，这是运筹学的一个著名问题，实际中有很多问题可以归结为这类问题。,第5节 马氏决策规划简介,本节简单介绍处理随机系统多阶段决策的马尔可夫决策规划（Markov decision programming，简称马氏决策规划）。,一、马尔可夫过程 一类动态随机系统，其系统状态的转移规律具有无后效性，即已知现时系统所处的状态，采取决策后虽不能预知下次系统将转移到哪个状态，但下次转移到的状态所服从的概率规律是已知的，且与系统以前的历史无关，我们称这种系统状态的转移规律具有马尔可夫性质，称这种过程为马尔可夫过程。,马氏决策规划 在赋值马氏过程中，如果在某状态选用不同的决策能够改变相应的状态转移矩阵及报酬矩阵，就产生了动态随机系统求最优策略的问题，马氏决策规划就是研究这类问题的。,马氏决策规划的基本概念于20世纪60年代建立，几十年来，无