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

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

1、第十章动态规划Dynamicprogramming动态规划是运筹学的一个重要分支，它是解决多阶段决策过程问题的一种数学方法，大约产生于50年代，1951年，美国数学家贝尔曼等人，根据多阶段决策问题的特点，把多阶段决策问题转换为一系列互相联系的单阶段决策问题，然后逐一加以解决。与此同时，他提出了这类问题的“最优化原理”，研究了许多实际问题，从而创建了解决最优化问题的一类新方法－－动态规划。他的名著《动态规划》于1957年出版，该书为动态规划的第一部著作。动态规划所解决的问题：多阶段问题动态规划的核心:动态规

2、划的优缺点:在于将问题公式化，也可以说，动态规划是将多阶段决策问题进行公式化的一种技术。适用范围广，模型算法一体化，方便编程。由于没有统一的标准模型，使得动态规划的应用难度增加。动态规划根据多阶段决策过程的时间参量类型可以分为离散型决策过程和连续型决策过程；根据决策过程的演变性态又可以分为确定型决策过程和随机型过程。组合起来有下列类型：离散确定型、离散随机型、连续确定型、连续随机型。本章主要介绍离散确定型决策过程。§1多阶段决策过程最优化问题举例§2基本概念、基本方程与最优化原理§3动态规划的应用(1)§

3、4动态规划的应用(2)§1多阶段决策过程最优化问题举例在生产和科学实验中，有一类活动的过程，由于它的特殊性，可以将它分为若干个相互联系的阶段，在它的每一个阶段都需要决策，从而使得整个过程达到最好的活动效果。状态状态状态状态状态1决策2决策n决策……因此，各个阶段的决策选择都不是随意的，它依赖于当前面临的状态，又会影响以后的发展。当各个阶段决策都确定以后就组成了一个决策序列，因而就决定了整个过程的一个活动路线。这种把一个问题可以看成是一个前后关联的具有链状结构的多阶段过程称为多阶段决策过程，也称为序惯决策过

4、程。这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策一般来说是与时间有关的，决策依赖于当前面临的状态，又随即引起状态的转移。一个决策过程是在变化的状态中产生出来的，故有“动态”的含义，因此把处理这类问题的方法称为动态规划方法。但是一些与时间无关的静态规划问题（如线性规划、非线性规划等），只要人为的引入“时间因素”，也可以把它视为多阶段决策问题，用动态规划的方法加以处理.多阶段决策问题的例子很多，现举例如下：例1.(最短路径问题)下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。

5、BACBDBCDEC412312312322164724838675611063751B4用穷举法的计算量:如果从A到E的站点有k个，除A、E之外每站有3个位置则总共有3k-1×2条路径；计算各路径长度总共要进行(k+1)3k-1×2次加法以及3k-1×2-1次比较。随着k的值增加时，需要进行的加法和比较的次数将迅速增加；例如当k=20时，加法次数为4.2550833966227×1015次，比较1.3726075472977×1014次。若用1亿次/秒的计算机计算需要约508天。讨论：1、以上求从A到E

6、的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路径问题。也就是说，我们可以把它分为四个阶段，转化为多阶段决策问题用动态规划的方法来处理。这样问题即要求：在各个阶段选取一个恰当的决策，使得由这些决策组成的决策序列决定一条路线，且为A点到E点的路程最短。根据最优化原理在最短路问题上的阐述，我们可以从最后一个阶段开始，从终点向始点方向逐点逆推，找出各点到终点的最短路，当逆推到始点时，也即找到全过程的最短路。第四阶段：两个始点D1和D2，终点只有一个；表10

7、-1阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)ED1D210*6106EE分析得知：从D1和D2到E的最短路径唯一。第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2的最短路径问题（见表10－2）：表10-2阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111

8、D2D2D1第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论,分别求B1,B2,B3,B4到C1,C2,C3的最短路径问题（见表10－3）：分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。阶段2本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)C1C2C3B1B2B3B42