第六章 动态规划ppt课件.ppt

《第六章 动态规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章动态规划第六章动态规划数据、模型与决策(第二版)工商管理硕士（MBA）系列教材《数据、模型与决策》相关教学课件免财富值！！免费下载学习目标动态规划是解决多阶段决策过程最优化问题的一种方法。明确什么是多阶段的决策问题；理解动态规划的基本思想和基本方程；理解动态规划的最优性原理和最优性定理。掌握动态规划在资源分配问题、生产和存贮问题、采购问题中的应用，并学会使用动态规划方法分析和解决实际的问题。第六章动态规划数据、模型与决策(第二版)第六章动态规划动态规划（DynamicProgramming，简称DP）是运筹学的重要分支之一，

2、它是一种研究多阶段决策问题的最优化理论和方法。大约产生于50年代。1951年美国数学家贝尔曼（R.Bellman）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变为一系列互相联系单阶段问题，然后逐个加以解决。动态规划的方法，在工程技术中、企业管理、工农业生产及军事等部门都有广泛的应用，并且获得了显著的效果。动态规划模型的分类，根据多阶段决策过程的时间变量是离散的还是连续的变量，过程分为离散决策过程和连续决策过程。第六章动态规划数据、模型与决策(第二版)第六章动态规划6.1动态规划的基本概念和基本方程6.2动态规划应用举例第六

3、章动态规划数据、模型与决策(第二版)6.1动态规划的基本概念和基本方程6.1.1多阶段决策6.1.2动态规划的基本概念6.1.3动态规划的基本方程6.1.4动态规划的基本思想归纳6.1.5动态规划的最优性原理和最优性定理第六章动态规划数据、模型与决策(第二版)6.1.1多阶段决策多阶段决策问题：把一个问题可看作一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，也称序贯决策过程。第六章动态规划数据、模型与决策(第二版)最短路问题下图是一个线路网络图，代表待定的输油管可行路线，A，B，C代表经过的三个地区，每个地区都有若干个转

4、运点，构成许多不同的输油路线，转运点间的数字表示点间距离，问应选择那些路线，使总路线最短？第六章动态规划数据、模型与决策(第二版)6.1.2动态规划的基本概念阶段状态决策策略状态转移方程指标函数和最优值函数第六章动态规划数据、模型与决策(第二版)6.1.3动态规划的基本方程动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。当k=4时，由D1到终点E只有一条路线，故f4（D1）=4，同理，f4（D2）=3。当k=3时，出发点有C1，C2，C3三个。若从C1出发，则有两个选择，一是至D1，一是至D2，则f3（C1）=min=

5、min=7其相应的决策为u3（C1）=D1，这说明，由C1至终点E的最短距离为7，其最短路线是C1D1E。同理，从C2和C3出发，则有f3（C2）=6其相应的决策为u3（C2）=D2f3（C3）=10其相应的决策为u3（C3）=D1第六章动态规划数据、模型与决策(第二版)当k=2时，有f2（B1）=12u2（B1）=C2f2（B2）=11u2（B2）=C2f2（B3）=9u2（B2）=C2当k=1时，出发点只有一个A点，则有f1（A）=15u1（A）=B1于是，我们找到从起点A到终点E点的最短距离为15。为了找出最短路线，再按计算

6、的顺序反推之，可求出最优决策函数序列{uk}，即由u1（A）=B1，u2（B1）=C2，u3（C2）=D2，u4（D2）=E组成一个最优策略。因而，找出相应的最短路线为AB1C2D2E。第六章动态规划数据、模型与决策(第二版)第六章动态规划数据、模型与决策(第二版)一般情况下，k阶段与k+1阶段的递推关系可写为（6-1）k=n，n-1，，1边界条件为fn+1（sn+1）=0这种递推关系式（x.1）称为动态规划的基本方程。第六章动态规划数据、模型与决策(第二版)6.1.4动态规划方法的基本思想归纳（1）动态方法关键在于正确的归纳出基

7、本的递推关系式和恰当的边界条件（即基本方程）。要做到这一点，必须先将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后的一个子问题所得到的最优解，就是整个问题的最优解。（2）在多阶段决策过程中，动态规划方法是既将当前一阶段和未来各阶段分开，又将当前效益和未来效益结合起来考虑的一种最优化方法。因此，每阶段决策的选取是从全局来考虑的，与该段的最优选择

8、答案一般是不同的。（3）在求整个问题的最优策略时，由于初始状态是已知的，而每阶段的决策都是该阶段状态的函数，故最优决策所进过的各阶段状态便可逐次变换得到，从而确定了最优路线。第六章动态规划数据、模型与决策(第二版)步骤：（1）将系统分为恰当的阶段，