运筹学 动态规划.ppt

《运筹学 动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章动态规划——DynamicProgramming（DP）动态规划是运筹学的一个重要分支，是解决多阶段决策过程最优化问题的一种非常有效的方法。1951年，美国数学家贝尔曼（R.Bellman）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。动态规划是分析某一类问题的一种途径。它不像LP那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。本章主要研究离散决策

2、过程，介绍动态规划的基本概念、理论和方法，并通过一些典型的应用问题说明它的应用。4.1多阶段决策过程的最优化4.2动态规划的基本概念及原理4.3动态规划模型的建立和求解4.1多阶段决策过程的最优化一、多阶段决策过程整个决策过程可按时间或空间顺序分解成若干相互联系的阶段（“时段”），在每一阶段都要作出决策，全部过程的决策是一个决策的序列。某厂有1000台机器，现需作一个五年计划，以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大，如图4-1所示。例4-1时间阶段示例（机器负荷问题）图4-1机器负荷问题B1AC3F2F1E3E2E1D3

3、D2D1C4C2C1B2G531368766835342138223335526643例4-2空间阶段示例（最短路线问题）给定线路网络图如下，各点间连线上的数字表示距离，现要从A地向G地铺设一条输油管道，问应选择什么路线，使总距离最短？图4-2第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段二、多阶段决策过程最优化的目标生产存储问题投资决策问题设备更新问题三、示例达到整个活动过程的总体效果的最优，而非各单个阶段最优的简单总和。4.2动态规划的基本概念和基本原理一、基本概念1、阶段2、状态3、决策和策略4、状态转移方程5、指标函数B1AC3F2F1E3E2E1D

4、3D2D1C4C2C1B2G531368766835342138223335526643例4-2最短路线问题给定线路网络图如下，各点间连线上的数字表示距离，现要从A地向G地铺设一条输油管道，问应选择什么路线，使总距离最短？图4-21、阶段（stage）将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，用k表示。如例4-2中，问题分为A→B、B→C…共6个阶段，k=6。2、状态（state）指各阶段开始时过程所处的自然状况或客观条件。状态应具有“无后效性”，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。如：S1={A}，S2

5、={B1,B2}，…3、决策（decision）与策略（policy）当某一阶段的状态确定后，可以作出不同的决定或选择，从而确定下一阶段的状态，这种决定或选择称为决策。如：从第二阶段的状态B1出发，可以选择下一阶段的C1～C3，即D2(B1)={C1,C2,C3}若决定选择C3，则d2(B1)=C3一组有序的决策序列构成一个策略，从第k阶段至第n阶段的一个策略称为后部子策略，记为Pkn→（dk，dk+1，…，dn）。例4-24、状态转移方程系统由一个阶段的一个状态转变到下一个阶段的另一个状态称为状态转移。其对应状态和决策的关系称为状态转移方程。记为5、阶段指标

6、衡量在一个阶段某个状态下各决策所对应的某种数量指标或效果，记为6、指标函数衡量所选策略优劣的数量指标或效果。最优指标函数表示从第k个阶段采用最优策略到过程终止时的最佳效益值，记为例4-2最短路线问题穷举法动态规划法得最优线路为：B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G537633412332643437597681310912131618该点到G点的最短距离图4-3上述最短路线的计算过程可用图直观表示(标号法)，如图4-3所示，结点上方矩形内的数字表示该点到终点的最短距离。标号法过程B1AC3F2F1E3E2E1D3D2D1C4C2C1B2

7、G第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段531368766835342138223335526643437597681310912131618图4-4二、最优化原理Bellman最优化原理：“一个过程的最优策略具有这样的性质，即无论开始的状态及初始的决策如何，对先前决策所形成的状态而言，其以后所有的决策必构成最优决策——后部子过程最优”三、动态规划基本思路1、将问题划分多个阶段。恰当选择状态变量、决策变量及定义最优指标函数2、从边界条件开始，逆向或正向逐段递推求解。3、各个阶段的最优决策是从全局考虑的，并非仅考虑本阶段。其基本方程为建立动态规划的模型

8、，就是分析问题并建立问题的动态规划基本