第七章 动态规划.ppt

文档介绍：第七章动态规划
动态规划是解决多阶段策划过程最优化问题的一种方法。该方法是有美国数学家贝尔曼(R Bellman)等人在20世纪50年代初提出的。1957年,R Bellman发表了该分支领域的第一本专著《动态规划》(Dynamic Programming)。
动态规划模型的分类:①离散确定型;②离散随机型;③连续确定型;④连续随即型。其中离散确定型是最基本的,本章主要针对这种类型的问题,介绍动态规划的基本思想、原理和方法.
第1节多阶段决策过程的最优化
多阶段决策过程,本意是指这样一类特殊的活动过程,它们可以按时间顺序分解成若干相互联系的阶段,称为“时段”,在每一个时段都要做出决策,全部过程的决策是一个决策序列,所以多阶段决策问题属序贯决策问题。
多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。
生产与存贮问题
投资决策问题
设备更新问题
第2节动态规划的基本概念和基本原理
动态规划的基本概念
⑴阶段;
⑵状态;
⑶决策和策略;
⑷状态转移;
⑸指标函数。
动态规划的基本思想与基本原理
(1) 将多阶段决策过程划分阶段,恰当地选取状态变量、决策变量及定义最优指函数,从而问题化成一族同类型的子问题,然后逐个求解。
(2)求解时从边界条件开始,逆(或顺)过程行进方向,逐段递推寻优。在每一个子问题求解时,都要使用它前面已求出的子问题的最优结果,最后一个子问题的最优解,就是整个问题的最优解。
(3)动态规划方法是既把当前一段与未来各段分开,又把当前效益和未来效益结合起来考虑的一种最优化方法,因此每段的最优决策选取是从全局考虑的,与该段的最优选择一般是不同的。
第2节动态规划模型的建立与求解
建立动态规划模型,就是分析问题并建立问题的动态规划基本方程。成功地应用动态规划方法的关键,在于识别问题的多阶段特征,将问题分解成为可用递推关系式联系起来的若干子问题,而正确建立基本关系方程的关键又在于正确选择状态变量,保证各阶段的状态变量具有递推的状态转移关系.
两种求解方法:逆序解法(后向动态规划方法)、顺序解法(前向动态规划法)。
寻优的方向与多阶段决策过程的实际行进方向相反,从最一段开始逐段前推,求得全过程的最优策略,称为逆序解法。与之相反,顺序解法的寻优方向与过程的行进方向相同,计算时从第一段开始逐段向后递推,计算后一阶段要用到前一阶段的求优结果,最后一段计算的结果就是全过程的最优结果。