【5A文】动态规划完整版.ppt

《【5A文】动态规划完整版.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、主要内容:§7.1多阶段决策问题§7.2动态规划的基本概念和基本原理§7.3动态规划应用举例【5A文】动态规划完整版例求解最短路问题ⅠⅡⅢⅣ分阶段的最短路径Ⅳ：C1—T3Ⅲ--Ⅳ:B1—C1—T4Ⅱ--Ⅲ--Ⅳ：A2—B1—C1—T7Ⅰ--Ⅱ--Ⅲ--Ⅳ：Q—A2—B1—C1—T11Q--A3—B1—C1—T11Q--A3—B2—C2—T11最短路径ⅠⅡⅢⅣ34476117811最短路径解的特点1、可以将全过程求解分为若干阶段求解；------多阶段决策问题2、在全过程最短路径中，将会出现阶段的最优路径；-----递推性3、前面的终点确

2、定，后面的路径也就确定了，且与前面的路径（如何找到的这个终点）无关；-----无后效性3、逐段地求解最优路径，势必会找到一个全过程最优路径。-----动态规划§7.1多阶段决策问题动态规划是解决多阶段最优决策的方法,由美国数学家贝尔曼(R.Bellman)于1951年首先提出;1957年贝尔曼发表动态规划方面的第一部专著“动态规划”,标志着运筹学的一个新分支的创立。动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题,采用顺序求解方法,通过解一系列小问题达到求解整个问题目的;动态规划的各个决策阶段不但要考虑本阶段的决策

3、目标,还要兼顾整个决策过程的整体目标,从而实现整体最优决策.动态规划的分类:离散确定型离散随机型连续确定型连续随机型动态规划的特点:动态规划没有准确的数学表达式和定义精确的算法,它强调具体问题具体分析,依赖分析者的经验和技巧。与运筹学其他方法有很好的互补关系,尤其在处理非线性、离散性问题时有其独到的特点。通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多

4、阶段决策问题，即具有“无后效性”的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。具有无后效性的多阶段决策过程的特点是系统过去的历史，只能通过现阶段的状态去影响系统的未来，当前的状态就是后过程发展的初始条件。动态规划的应用动态规划在工程技术,企业管理,军事部门有广泛的应用;可解决资源分配,生产调度,库存管理,路径优化,设备更新,投资规划,排序问题和生产过程的最优控制等问题;§7.2动态规划的基本概念和基本思想使用动态规划方法求解

5、决策问题首先要将问题改造成符合动态规划求解要求的形式,要涉及以下概念:(1)阶段(2)状态(3)决策与策略(4)状态转移方程(5)指标函数(6)基本方程一、基本概念(1)划分阶段把一个复杂决策问题按时间或空间特征分解为若干(n)个相互联系的阶段(stage),以便按顺序求解;阶段变量描述当前所处的阶段位置，一般用下标k表示;每阶段有若干状态(state),表示某一阶段决策面临的条件或所处位置及运动特征的量,称为状态。反映状态变化的量叫作状态变量。k阶段的状态特征可用状态变量sk描述;每一阶段的全部状态构成该阶段的状态集合Sk，并有sk

6、Sk。每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段的初始状态记作sk，终止状态记为sk+1，也是下个阶段的初始状态。(2)确定状态(3)决策、决策变量所谓决策就是确定系统过程发展的方案，决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。用以描述决策变化的量称之决策变量，和状态变量一样，决策变量可以用一个数，一组数或一向量来描述．也可以是状态变量的函数，记以，表示于k阶段状态sk时的决策变量．决策变量的取值往往也有一定的容许范围，称之允许决策集合．决策变量xk(sk)的允许决策集用XK

7、(SK)表示，xk(sk)XK(SK),允许决策集合实际是决策的约束条件。(4)策略和允许策略集合策略(Policy)也叫决策序列．策略有全过程策略和k部子策略之分，全过程策略是指具有n个阶段的全部过程，由依次进行的n个阶段决策构成的决策序列，简称策略，表示为。从k阶段到第n阶段，依次进行的阶段决策构成的决策序列称为k部子策略,表示为，显然当k=1时的k部子策略就是全过程策略。(5)状态转移方程状态转移确定从一个状态到另一个状态的转移过程,由状态转移方程描述:sk+1=T(sk,xk);状态转移方程在大多数情况下可以由数学公式表达,如

8、:sk+1=sk+xk；(6)指标函数用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润