最新动态规划ppt课件.ppt

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

1、动态规划§7.1多阶段决策过程的最优化动态规划是解决多阶段最优决策的方法,由美国数学家贝尔曼(R.Bellman)于1951年首先提出;1957年贝尔曼发表动态规划方面的第一部专著“动态规划”,标志着运筹学的一个新分支的创立。多阶段决策决策一些经营活动的过程可以划分为若干个相互联系的阶段。策略——各阶段的决策构成的序列。多阶段决策问题动态规划的特点:动态规划没有准确的数学表达式和定义精确的算法,它强调具体问题具体分析,依赖分析者的经验和技巧。与运筹学其他方法有很好的互补关系,尤其在处理非线性、离散性问题时有其独

2、到的特点。通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。具有无后效性的多阶段决策过程的特点是系统过去的历史，只能通过现阶段的状态去影响

3、系统的未来，当前的状态就是后过程发展的初始条件。最优化原理已知A到T的最短路径是：Q→A2→B1→C1→T那么这条路线上的任一点到T的最短路线，必包含在其中。例如：A2→B1→C1→T；B1→C1→T；C1→T动态规划方法的基本思路根据多阶段决策问题的特性，提出一种求解这类问题的一般方法，逆序递推法。以例1为例进行说明。基本思路：把寻求最优策略看做连续递推的过程，从最终阶段开始，逆着实际过程的进展方向逐段求解，在每一段求解中都要利用刚求解完那段的结果，直到初始阶段求出结果，返回始点为止。标号法适用于例1这类最优

4、路线问题；标号法是借助网路图通过分段标号来求出最优路线的一种简便、直观的方法。使用动态规划方法求解决策问题首先要将问题改造成符合动态规划求解要求的形式,要涉及以下概念:(1)阶段(2)状态(3)决策(4)状态转移(5)策略(6)指标函数(7)最优解§7.2动态规划的基本概念和基本思想一、基本概念(1)阶段把一个复杂决策问题按时间或空间特征分解为若干(n)个相互联系的阶段(stage),以便按顺序求解;阶段变量k:描述当前所处的阶段位置状态表示某一阶段起始条件。每阶段有若干状态(state),反映状态变化的量叫作

5、状态变量。k阶段的状态特征可用状态变量sk描述;每一阶段的全部状态构成该阶段的状态集合Sk，并有skSk。(2)状态(3)决策、决策变量所谓决策就是确定系统过程发展的方案，决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。用以描述决策变化的量称之决策变量xk，和状态变量一样，决策变量可以用一个数，一组数或一向量来描述．它是状态变量的函数，记以，表示于k阶段状态sk时的决策变量．决策变量的取值往往也有一定的容许范围，称之允许决策集合．决策变量xk(sk)的允许决策集用XK(SK)表

6、示，xk(sk)XK(SK),允许决策集合实际是决策的约束条件。(4)状态转移方程状态转移确定从一个状态到另一个状态的转移过程,由状态转移方程描述:sk+1=T(sk,xk);即：sk和xk一旦确定下来，下一阶段状态sk＋1变量也随之确定。例1：sk＋1＝xk(sk)状态转移方程在大多数情况下可以由数学公式表达,如:sk+1=sk+xk(sk)；(5)策略和允许策略集合策略(Policy)也叫决策序列．策略有全过程策略和第k子过程策略之分，全过程策略是n个阶段的全部过程，由依次进行的n个阶段决策构成的决策序列

7、，简称策略，表示为。从k阶段到第n阶段，依次的阶段决策构成的决策序列称为第k子过程策略,表示为，显然当k=1时的第k子过程策略就是全过程策略。(6)指标函数用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。用vk(sk,xk)表示第k段处于状态sk且所作决策为xk时的指标，则它就是第k段指标函数，简记为vk。用fK(sk,xk)表示第k子过程的指标函数。表示

8、处于第k段sk状态且所作决策为xk时，从sk点到终点的运费。由此可见，fK(sk,xk)不仅跟当前状态sk有关，还跟该子过程策略（2）过程指标函数（也称目标函数）（1）阶段指标函数（也称阶段效应）pk(sk)有关,严格说来，应表示为fk(sk,pk(sk))。它是由各阶段的阶段指标函数vk(sk,xk)累积形成的，对于第k子过程的指标函数可以表示为：式中，表示某种运算，可以是加、减、