《动态规划完整》PPT课件.ppt
《《动态规划完整》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《动态规划完整》PPT课件.ppt(104页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、主要内容主要内容:7.17.1多阶段决策问题多阶段决策问题多阶段决策问题多阶段决策问题7.2 7.2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理动态规划的基本概念和基本原理动态规划的基本概念和基本原理7.3 7.3 动态规划应用举例动态规划应用举例动态规划应用举例动态规划应用举例第第 七七 章章 动动 态态 规规 划划例例 求解最短路问题求解最短路问题 分阶段的最短路径:C1T 3-:B1C1T 4-:A2B1C1T 7-:QA2B1C1T 11 Q-A3B1C1T 11 Q-A3B2C2T 11最短路径最短路径34476117811最短路径解的特点1、可以将全过程求解分为若干阶
2、段求解;-多阶段决策问题多阶段决策问题多阶段决策问题多阶段决策问题2、在全过程最短路径中,将会出现阶段的最优路径;-递推性递推性递推性递推性3、前面的终点确定,后面的路径也就确定了,且与前面的路径(如何找到的这个终点)无关;-无后效性无后效性无后效性无后效性3、逐段地求解最优路径,势必会找到一个全过程最优路径。-动态规划动态规划动态规划动态规划7.17.1多阶段决策问题多阶段决策问题 动态规划是解决多阶段最优决策的方法动态规划是解决多阶段最优决策的方法,由美国数学家贝尔曼由美国数学家贝尔曼(R.Bellman)于于 1951年首先提出年首先提出;1957年贝尔曼发表动态规划方面的第一部年贝尔曼
3、发表动态规划方面的第一部专著专著“动态规划动态规划”,标志着运筹学的一标志着运筹学的一 个个新分支的创立。新分支的创立。动态规划将复杂的多阶段决策问题分解为动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题一系列简单的、离散的单阶段决策问题,采用顺序求解方法采用顺序求解方法,通过解一系列小问题通过解一系列小问题达到求解整个问题目的达到求解整个问题目的;动态规划的各个决策阶段不但要考虑本阶动态规划的各个决策阶段不但要考虑本阶段的决策目标段的决策目标,还要兼顾整个决策过程的还要兼顾整个决策过程的整体目标整体目标,从而实现整体最优决策从而实现整体最优决策.动态规划的分类动态规划的
4、分类:离散确定型离散确定型离散随机型离散随机型连续确定型连续确定型连续随机型连续随机型动态规划的特点动态规划的特点:动态规划动态规划没有准确的数学表达式和定义没有准确的数学表达式和定义精确的算法精确的算法,它强调它强调具体问题具体分析具体问题具体分析,依赖分析者的经验和技巧依赖分析者的经验和技巧。与运筹学其他方法有很好的互补关系与运筹学其他方法有很好的互补关系,尤尤其在处理非线性、离散性问题时有其独其在处理非线性、离散性问题时有其独到的特点。到的特点。通通常常多多阶阶段段决决策策过过程程的的发发展展是是通通过过状状态态的的一一系系列列变变换换来来实实现现的的。一一般般情情况况下下,系系统统在在
5、某某个个阶阶段段的的状状态态转转移移除除与与本本阶阶段段的的状状态态和和决决策策有有关关外外,还还可可能能与与系系统统过过去去经经历历的的状状态态和和决决策策有有关关。因因此此,问问题题的的求求解解就就比比较较困困难难复复杂杂。而而适适合合于于用用动动态态规规划划方方法法求求解解的的只只是是一一类类特特殊殊的的多多阶阶段段决决策策问问题题,即即具具有有“无后效性无后效性”的多阶段决策过程。的多阶段决策过程。所所所所谓谓谓谓无无无无后后后后效效效效性性性性,又又又又称称称称马马马马尔尔尔尔柯柯柯柯夫夫夫夫性性性性,是是是是指指指指系系系系统统统统从从从从某某某某个个个个阶阶阶阶段段段段往往往往后
6、后后后的的的的发发发发展展展展,仅仅仅仅由由由由本本本本阶阶阶阶段段段段所所所所处处处处的的的的状状状状态态态态及及及及其其其其往往往往后后后后的的的的决决决决策策策策所所所所决决决决定定定定,与与与与系统以前经历的状态和决策系统以前经历的状态和决策系统以前经历的状态和决策系统以前经历的状态和决策(历史历史历史历史)无关。无关。无关。无关。具具有有无无后后效效性性的的多多阶阶段段决决策策过过程程的的特特点点是是系系统统过过去去的的历历史史,只只能能通通过过现现阶阶段段的的状状态态去去影影响响系系统统的的未未来来,当当前前的的状状态态就就是是后过程发展的初始条件。后过程发展的初始条件。动态规划的
7、应用动态规划的应用动态规划在工程技术动态规划在工程技术,企业管理企业管理,军事部军事部门有广泛的应用门有广泛的应用;可解决资源分配可解决资源分配,生产生产调度调度,库存管理库存管理,路径优化路径优化,设备更新设备更新,投资规划投资规划,排序问题和生产过程的最优控排序问题和生产过程的最优控制等问题制等问题;使用动态规划方法求解决策问题首先要将使用动态规划方法求解决策问题首先要将问题改造成符合动态规划求解要求的形式问题改造成符合动态规划求解要求的形式,要涉及以下概念要涉及以下概念:(1)(1)阶段阶段(2)(2)状态状态(3)(3)决策与策略决策与策略 (4)(4)状态转移方程状态转移方程 (5)
8、(5)指标函数指标函数 (6)(6)基本方程基本方程7.2 7.2 动态规划的基本概念和基本思想动态规划的基本概念和基本思想一、基本概念一、基本概念(1)划分阶段划分阶段 把一个复杂决策问题按时间或空间特把一个复杂决策问题按时间或空间特征分解为若干征分解为若干(n)(n)个相互联系的阶段个相互联系的阶段(stage),(stage),以便按顺序求解以便按顺序求解;阶段变量描述当前所处的阶段位置,一阶段变量描述当前所处的阶段位置,一般用下标般用下标 k 表示表示;每阶段有若干状态每阶段有若干状态(state),表示某一阶段决表示某一阶段决策面临的条件或所处位置及运动特征的量策面临的条件或所处位置
9、及运动特征的量,称称为状态。反映状态变化的量叫作状态变量。为状态。反映状态变化的量叫作状态变量。k 阶段的状态特征可用状态变量阶段的状态特征可用状态变量 sk 描述描述;每一阶段的全部状态构成该阶段的状态集合每一阶段的全部状态构成该阶段的状态集合Sk,并有,并有sk Sk。每个阶段的状态可分为初始状。每个阶段的状态可分为初始状态和终止状态,或称输入状态和输出状态,态和终止状态,或称输入状态和输出状态,阶段的初始状态记作阶段的初始状态记作sk,终止状态记为,终止状态记为sk+1,也是下个阶段的初始状态。也是下个阶段的初始状态。(2)确定状态确定状态(3)(3)决策、决策变量决策、决策变量 所谓决
10、策就是确定系统过程发展的方案,所谓决策就是确定系统过程发展的方案,决策的实质是关于状态的选择,是决策者从决策的实质是关于状态的选择,是决策者从给定阶段状态出发对下一阶段状态作出的选给定阶段状态出发对下一阶段状态作出的选择。择。用以描述决策变化的量称之决策变量,用以描述决策变化的量称之决策变量,和状态变量一样,决策变量可以用一个数,和状态变量一样,决策变量可以用一个数,一组数或一向量来描述也可以是状态变量一组数或一向量来描述也可以是状态变量的函数,记以的函数,记以 ,表示于,表示于 k 阶段状阶段状态态 sk 时的决策变量时的决策变量 决策变量的取值往往也有一定的容许范围,决策变量的取值往往也有
11、一定的容许范围,称之允许决策集合决策变量称之允许决策集合决策变量 xk(sk)的允许的允许决策集用决策集用 XK(SK)表示,表示,xk(sk)XK(SK),允允许决策集合实际是决策的约束条件。许决策集合实际是决策的约束条件。(4)(4)策略和允许策略集合策略和允许策略集合 策略策略(Policy)也叫决策序列策略有全过程也叫决策序列策略有全过程策略和策略和 k 部子策略之分,全过程策略是指具部子策略之分,全过程策略是指具有有n 个阶段的全部过程,由依次进行的个阶段的全部过程,由依次进行的 n 个个阶段决策构成的决策序列,简称策略,表示阶段决策构成的决策序列,简称策略,表示为为 。从。从 k
12、阶段到第阶段到第 n 阶段,阶段,依次进行的阶段决策构成的决策序列称为依次进行的阶段决策构成的决策序列称为 k 部子策略部子策略,表示为表示为 ,显然,显然当当 k=1时的时的 k 部子策略就是全过程策略。部子策略就是全过程策略。(5)状态转移方程状态转移方程 状态转移确定从一个状态到另一个状态的转状态转移确定从一个状态到另一个状态的转移过程移过程,由状态转移方程描述由状态转移方程描述:sk+1=T(sk,xk);状态转移方程在大多数情况下可以由数学公状态转移方程在大多数情况下可以由数学公式表达式表达,如如:sk+1=sk+xk;(6)指标函数指标函数 用来衡量策略或子策略或决策的效果的用来衡
13、量策略或子策略或决策的效果的某种数量指标,就称为指标函数。它是定义某种数量指标,就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量在全过程或各子过程或各阶段上的确定数量函数。对不同问题,指标函数可以是诸如费函数。对不同问题,指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、用、成本、产值、利润、产量、耗量、距离、时间、效用,等等。时间、效用,等等。用用vk(sk,xk)表示第表示第 k 段处于状态段处于状态 sk且所且所作决策为作决策为 xk 时的指标,则它就是第时的指标,则它就是第 k 段指标段指标函数,简记为函数,简记为vk。用用f(sk,xk)表示第表示第k k子过
14、程的指标函数。表子过程的指标函数。表示处于第示处于第 k 段段 sk 状态且所作决策为状态且所作决策为xk时,时,从从 sk 点到终点的距离。由此可见,点到终点的距离。由此可见,f(sk,xk)不仅跟当前状态不仅跟当前状态 sk 有关,有关,(2 2)过程指标函数)过程指标函数(也称目标函数)(也称目标函数)(1)阶段指标函数)阶段指标函数(也称阶段效应)(也称阶段效应)还跟该子过程策略还跟该子过程策略 pk(sk)有关有关,严格说来,严格说来,应表示为应表示为 fk(sk,pk(sk)。它是由各阶段的。它是由各阶段的阶段指标函数阶段指标函数 vk(sk,xk)累积形成的,对于累积形成的,对于
15、 k 部子过程的指标函数可以表示为:部子过程的指标函数可以表示为:式式中中,表表示示某某种种运运算算,可可以以是是加加、减减、乘、除、开方等乘、除、开方等 多阶段决策问题中,常见的目标函数形式多阶段决策问题中,常见的目标函数形式之一是取各阶段效应之和的形式,即之一是取各阶段效应之和的形式,即:有些问题,如系统可靠性问题,其目标函有些问题,如系统可靠性问题,其目标函数是取各阶段效应的连乘积形式,数是取各阶段效应的连乘积形式,(7)最优解最优解 用用 fk*(sk)表示第表示第 k 子过程指标函数子过程指标函数Fk(sk,pk(sk)在状态在状态 sk 下的最优值,即下的最优值,即:称称 fk(s
16、k)为第为第 k 子过程上的最优指标函数;子过程上的最优指标函数;与它相应的子策略与它相应的子策略 pk(sk)称为状态称为状态 sk 下的最下的最优子策略,记为优子策略,记为 pk*(sk)例例例例 用动态规划求解最短路问题用动态规划求解最短路问题 最短路的求解最短路的求解最短路的求解最短路的求解:阶段阶段:可分为可分为4个阶段个阶段,k=1,.,4。状态状态:可用城市编号可用城市编号,S1=Q,S2=A1,A2,A3,S3=B1,B2,B3,S4=C1,C2,S5=T 决策决策:决策变量也可用城市编号决策变量也可用城市编号;状态转移方程状态转移方程:sk+1=xk;阶段指标函数:阶段指标函
17、数:过程指标(阶段递推)函数过程指标(阶段递推)函数:k=4f4(C1)=3,f4(C2)=4 k=3f3(B1)=min1+f4(C1)=4*,4+f4(C2)=8=4 f3(B2)=min6+f4(C1)=9,3+f4(C2)=7*=7 f3(B3)=min3+f4(C1)=6*,3+f4(C2)=7=6 k=2 f2(A1)=min7+f3(B1),4+f3(B2),6+f3(B3)=min11*,11*,12=11f2(A2)=min3+f3(B1),2+f3(B2),4+f3(B3)=min7*,9,10 =7 f2(A3)=min4+f3(B1),1+f3(B2),5+f3(B3)
18、=min8*,8*,11 =8 k=1 f1(Q)=min2+f2(A1),4+f2(A2),3+f2(A3)=min13,11*,11*=11 最短路是:最短路是:Q A2 B1 C1 T,p=A2,B1,C1,T Q A3 B1 C1 T,p=A3,B1,C1,T Q A3 B2 C2 T,p=A3,B2,C2,T整个过程的最优策略应具有这样的性质整个过程的最优策略应具有这样的性质:无论过去的状态和决策如何无论过去的状态和决策如何,对前面的决策对前面的决策所形成的状态而言所形成的状态而言,后续的诸决策必须构成后续的诸决策必须构成最优策略;最优策略;上一条成立的条件是阶段递推函数严格单上一条
19、成立的条件是阶段递推函数严格单调。调。二、动态规划的最优性原理二、动态规划的最优性原理在在例例题题中中,求求解解最最短短路路线线的的计计算算公公式式可可以以概概括写成:括写成:其其中中,vk 在在这这里里表表示示从从状状态态 sk 到到由由决决策策 xk 所所决决定定的的状状态态 sk+1 之之间间的的距距离离。f5(s5)=0 是是边边界条件,表示全过程到第四阶段终点结束。界条件,表示全过程到第四阶段终点结束。一般地,对于一般地,对于 n 个阶段的决策过程,假设只个阶段的决策过程,假设只考虑指标函数是考虑指标函数是“和和”与与“积积”的形式,第的形式,第 k 阶段和第阶段和第 k+1 阶段间
20、的递推公式可表示如下:阶段间的递推公式可表示如下:当过程指标函数为下列当过程指标函数为下列“和和”的形式时的形式时 相应的函数基本方程为相应的函数基本方程为:当过程指标函数为下列当过程指标函数为下列“积积”的形式时的形式时相应的函数基本方程为相应的函数基本方程为:动态规划的优缺点动态规划的优点动态规划的优点动态规划的优点动态规划的优点可以解决线性可以解决线性,非线性非线性,整整数规划无法有效求解的复数规划无法有效求解的复杂问题杂问题;容易找到全局最优解容易找到全局最优解;可以得到一组解可以得到一组解;动态规划的缺点:动态规划的缺点:动态规划的缺点:动态规划的缺点:没有标准的模型可供应用没有标准
21、的模型可供应用,构构模依赖于个人的经验和技巧模依赖于个人的经验和技巧;状态变量需满足无后效性状态变量需满足无后效性,有有较大的局限性较大的局限性;动态规划的维数灾难限制了动态规划的维数灾难限制了对规模较大问题的求解效率对规模较大问题的求解效率;7.3 7.3 动态规划方法应用动态规划方法应用动态规划的步骤:动态规划的步骤:1.将问题按时间或空间划分为满足递推关系的将问题按时间或空间划分为满足递推关系的若干阶段若干阶段,对非时序问题可人为地引入对非时序问题可人为地引入“时时段段”概念概念;2.正确选择状态变量正确选择状态变量 sk,满足满足:可知性可知性:正确描述动态过程演变正确描述动态过程演变
22、,可直接可直接或间接确定状态变量的值或间接确定状态变量的值;无后效性无后效性:后面的决策与前面的决策无关后面的决策与前面的决策无关;3.确定决策变量确定决策变量 xk以及允许决策集合以及允许决策集合Xk;4.写出状态转移方程写出状态转移方程 sk+1=T(sk,xk);5.决策变量的取值范围决策变量的取值范围 6.写出过程指标函数(阶段函数)的递推写出过程指标函数(阶段函数)的递推关系关系,应满足应满足:a)是定义在所有阶段上的数量函数;是定义在所有阶段上的数量函数;b)具有可分离性,并满足递推关系;具有可分离性,并满足递推关系;c)阶段函数应严格单调。阶段函数应严格单调。动态规划应用举例:动
23、态规划应用举例:1.最优路径问题最优路径问题2.资源配置问题资源配置问题3.生产与库存问题生产与库存问题4.机器负荷分配问题机器负荷分配问题5.复合系统工作可靠性问题复合系统工作可靠性问题6.二维背包问题二维背包问题7.设备更新问题设备更新问题8.货郎担问题货郎担问题9.非线性规划的求解非线性规划的求解1.最优路径问题最优路径问题 某厂要确定一种新产品在今后五年内的价格,并已拟定只在5、6、7、8元这四种单价中进行选择。据预测,今后五年不同价格下每年盈利(万元)见下表,但是各相邻年度价格增减不得超过1元。问今后五年内每年定价各为多少,可逾七五年总利润最大。价格/元盈利/万元第一年第二年第三年第
24、四年第五年592458675864765973887664价格/元盈利/万元第一年第二年第三年第四年第五年592458675864765973887664131411843410182223172428283037353638解:1、建立动态规划模型:阶段:以年划分阶段,k=5,4,3,2,1;状态变量sk为每个阶段初的价格,则Sk=5,6,7,8;决策变量xk为每年所确定的价格,则Xk=5,6,7,8;状态转移方程:阶段指标函数vk(sk,xk)为每个阶段选择xk所取得的盈利;例如v(sk,)过程指标函数为第k阶段状态为sk时到最后一个阶段的总利润。基本函数方程为:、逆序求解:k=5f5(s
25、5,x5)v5(s5,x5)+f6*(s6)f5*(s5)x5*s x 5 6 7 8 5 8+0 8 5 6 4+0 4 6 7 3+0 3 7 8 4+0 4 8k=4f4(s4,x4)v4(s4,x4)+f5*(s5)f4*(s4)x4*s x 5 6 7 8 5 5+8 5+4 13 5 6 6+8 6+4 6+3 14 5 7 7+4 7+3 7+4 11 6,8 8 6+3 6+4 10 7k=3f3(s3,x3)v3(s3,x3)+f4*(s4)f3*(s3)x3*s x 5 6 7 8 5 4+13 4+14 18 6 6 8+13 8+14 8+11 22 7 7 9+14
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态规划完整 动态 规划 完整 PPT 课件
限制150内