《运筹学动态规划.pptx》由会员分享，可在线阅读，更多相关《运筹学动态规划.pptx（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本章重点动态规划的四大要素、一个方程动态规划问题的建模与求解第1页/共65页动态规划概念(1)前面介绍的线性规划研究的是一次性的决策线性规划决策过程可以总结为在给定资源和环境的情况下，决定变量的取值，使某个目标达到最大或最小值这个决策过程可以表示如下图决 策x1x2uZ其中u 表示决策变量x1 表示决策所依赖的资源和环境Z表示目标函数x2 表示决策后的资源和环境状况第2页/共65页动态规划概念(2)例如，前面讲过的生产计划问题就是一次决策某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的日生产计划产品所需原料数量产品所需原料数量（公斤（公斤/件）件）产品产品Q1（件）（件）
2、产品产品Q2（件）（件）产品产品Q3（件）（件）原料可用量原料可用量（公斤（公斤/日）日）原料原料P12301500原料原料P2024800原料原料P33252000产品的利润产品的利润（千元（千元/件）件）354第3页/共65页动态规划概念(3)在这个模型中模型中的A、b和C就是x1模型中的X就是u模型中的f(X)=CX就是ZA、C和剩余的原料为x2n设每天生产三种产品的件数分别为x1、x2、x3n其线性规划模型为决 策x1x2uZ第4页/共65页动态规划概念(4)如果上例中的生产计划不是只在一天里进行，而是连续一周，每天投入一定量的原料，剩余的原料后面可以继续使用，每天只允许生产一种产品并
3、获得相应的利润。问怎样决策才能使一周的总利润最大？解决这样的问题需要将决策过程分为多个阶段，本问题需要分为如下的7个阶段。周日x1x2u1r1周一x3u2r2周六x8u7r7x7第5页/共65页动态规划概念(5)uk（k=1,2,3,4,5,6,7）表示第k天生产三种产品中的哪一种以及生产多少x1=技术环境A、市场环境C和原料bxk+1=技术环境A、市场环境C和原料b+第k天剩余的原料（k=1,2,3,4,5,6,7）rk=第k天生产产品获得的利润总利润=r1+r2+r3+r4+r5+r6+r7动态规划就是解决这种多阶段决策过程的方法动态规划就是解决这种多阶段决策过程的方法第6页/共65页多阶
4、段决策过程(1)其中包含n个决策子问题，每个子问题称为一个阶段，用变量k表示，称为阶段变量xk描述k 阶段初系统的状况，称为状态变量每个阶段有一个输入状态和一个输出状态一般把输入状态称为该阶段的阶段状态TnT1x1x2u1r1T2x3u2r2Tkxk+1ukrkxkxn+1unrnxnn一般的多阶段决策过程表示如下第7页/共65页多阶段决策过程(2)uk 代表k 阶段对第k 子问题进行的决策，称uk为k阶段的决策变量，uk的一组确定的取值称为一个决策rk 表示k 阶段从状态xk 出发做决策uk 之后产生的后果，称为k 阶段的阶段效应若在上述的多阶段决策过程中，系统 k 阶段以后的决策只与 k
5、阶段系统的状态 xk 有关，而与系统以前的决策无关，则称该多阶段决策过程具有无后效性注：动态规划的建模和求解都是针对具有无后效性的多阶段决策过程第8页/共65页多阶段决策过程(3)在具有无后效性的多阶段决策过程中，uk由xk 决定，rk 和xk+1 由xk 和uk 决定，因此决策可以写为 uk(xk)阶段效应可以写为 rk(xk,uk)状态xk+1=Tk(xk,uk)称为状态转移方程，其中Tk 是已知函数多阶段决策过程中，从第k阶段到最终阶段的过程称为k-后部子过程，简称k-子过程第9页/共65页动态规划模型动态规划模型如下n 表示求和或加权求和nopt表示求最优(最大值或最小值)nXk表示k
6、阶段状态可能的取值范围，称为状态可能集合nUk表示k阶段决策可能的取值范围，称为决策允许集合第10页/共65页动态规划建模确定阶段根据实际情况进行阶段划分明确状态变量xk和状态可能集合Xk确定决策变量uk(xk)和决策允许集合Uk确定状态转移方程xk+1=Tk(xk,uk)明确阶段效应rk(xk,uk)和目标R第11页/共65页示例(5.1-1)前面讲过的生产计划问题某工厂用三种原料生产三种产品，已知的条件如下表所示，如连续生产一周，每天投入一定量的原料，剩余的原料后面可以继续使用，每天只允许生产一种产品并获得相应的利润。试制订总利润最大的周生产计划(只建模，不求解)产品所需原料数量产品所需原
7、料数量（公斤（公斤/件）件）产品产品Q1（件）（件）产品产品Q2（件）（件）产品产品Q3（件）（件）原料可用量原料可用量（公斤（公斤/日）日）原料原料P12301500原料原料P2024800原料原料P33252000产品的利润产品的利润（千元（千元/件）件）354第12页/共65页示例(5.1-2)第13页/共65页示例(5.1-3)第14页/共65页动态规划解的概念(1)最优目标值在多阶段决策过程中，从起始状态x1开始，进行一系列的决策，使得目标R达到最优，我们把这种目标的值称为最优目标值，记为R*最优策略把使目标达到最优的决策序列称为最优策略，记为 u1*,u2*,un*最优路线在采用最
8、优策略时，系统从x1开始所经过的状态序列称为最优路线，记为x1*,x2*,xn+1*第15页/共65页动态规划解的概念(2)求解动态规划问题就是要找到最优策略、最优路线和最优目标值第16页/共65页动态规划最优性原理(1)一个多阶段决策过程的最优策略具有这样的性质无论其初始状态及其初始决策如何，对于前面决策所形成的某一状态而言，下余的决策序列必定构成最优策略最优性原理的含义是最优策略的任何一个k-后部子策略(uk*,uk+1*,un*)，是以xk*为初始状态的k-后部子过程的最优策略第17页/共65页动态规划最优性原理(2)如上图A到B之间的蓝线是由状态A到状态B的最优策略在线上任取一点M，M
9、到B之间的蓝线就是由状态M到状态B的最优策略ABM第18页/共65页贝尔曼函数(1)在k阶段从初始状态xk 出发，执行最优决策序列，到达过程终点时，整个k-后部子过程中的目标函数取值，称为条件最优目标函数，也称为贝尔曼函数，记为fk(xk)，则n为了将多阶段决策过程的任一阶段状态xk 的最优策略和最终的最优策略相区别，称前者为条件最优策略条件最优策略不一定等于最优路线中的k阶段状态系统从xk出发，在k-后部子过程中的最优策略第19页/共65页贝尔曼函数(2)构成条件最优策略的决策称为条件最优决策将k阶段状态xk的条件最优决策表示为uk(xk)，简记为uk，相应的条件最优策略表示为 uk,uk+
10、1,unn执行条件最优策略时的阶段状态序列称为条条件最优路线件最优路线，表示为xk,xk+1,xn,xn+1第20页/共65页贝尔曼函数(3)动态规划方法的原理就是建立起fk(xk)与fk+1(xk+1)之间的递推关系，然后逐步求出所有的fk(xk)第21页/共65页贝尔曼方程对于无后效性的多阶段决策过程，根据最优性原理和贝尔曼函数定义，可得第22页/共65页动态规划问题求解步骤(1)通过贝尔曼方程逆序求出条件最优目标函数值集合和条件最优决策集合uk=n时，不存在n+1阶段必须就阶段n的所有可能状态 计算 和第23页/共65页动态规划问题求解步骤(2)uk=n-1时，根据 ，就阶段n-1的所有
11、可能状态 计算 和u余者类推，直到阶段1第24页/共65页动态规划问题求解步骤(3)通过状态转移方程顺序求出最优决策序列和最优路线阶段1的状态x1唯一确定时，x1*=x1，可得唯一确定的u1(x1*)和f1(x1*)，则R*=f1(x1*)，u1*(x1*)=u1(x1*)u当阶段1的状态x1不唯一时，u由 求得 ，求出u余者类推，直至阶段n，求出 、和第25页/共65页动态规划的四大要素、一个方程在动态规划的建模和求解过程中，有五个方面起着极其重要的作用四大要素(模型里的)状态变量及其可能集合决策变量及其可能集合状态转移方程xk+1=Tk(xk,uk)阶段效应rk(xk,uk)贝尔曼方程第2
12、6页/共65页动态规划应用举例(1)最短路线问题：从某地出发，途径若干个中间点最后到达目的地，试求距离最短或费用最省的路线用动态规划求解该问题分为三种情况考虑定步数问题不定步数问题(有限步=无循环)不定步数问题(无限步=有循环)第27页/共65页示例(5.2-1)路线图如下所示，箭头表示通行方向，线上数字表示道路长度，试求s到t的最短路线sabcdeft9877456456754第28页/共65页示例(5.2-2)该问题是一个定步数问题，分为3个阶段阶段1：决定由s 到a、b 还是c阶段2：决定是到d、e 或是f阶段3：到t状态变量xk 设为k 阶段初始所在地x1s，x2a,b,c，x3d,e
13、,f，x4tk阶段决策uk是决定下一步走到哪里，有u1a,b,cu2(a)d,f，u2(b)d,e，u2(c)d,e,f u3t第29页/共65页示例(5.2-3)状态转移方程xk+1=uk阶段效应rk(xk,uk)取为从xk 走到uk 的路线长度，如r1(s,a)=9贝尔曼函数 fk(xk)定义为从xk 走到 t 的最短路线贝尔曼方程第30页/共65页示例(5.2-4)通过贝尔曼方程逆序求出条件最优目标函数值集合和条件最优决策集合 u3/x4x3t/tf3()u3()defr3(x3,u3)+f4(x4)f3()计算表+0+0+0ttt574574第31页/共65页示例(5.2-5)u2/x
14、3x2d/de/ef/ff2()u2()abcr2(x2,u2)+f3(x3)f2()计算表+5+5+5+7+7+4+474564568109fdd第32页/共65页示例(5.2-6)u1/x2x1a/ab/bc/cf1()u1()sr1(x1,u1)+f2(x2)f1()计算表+8+10+998716c第33页/共65页示例(5.2-7)通过状态转移方程顺序求出最优决策序列和最优路线R*=f1(s)=16，x1*=su1*(x1*)=u1(s)=c，x2*=cu2*(x2*)=u2(c)=d，x3*=du3*(x3*)=u3(d)=t，x4*=t第34页/共65页示例(5.2-8)sabcd
15、eft9877456456754x1x2x3x4f4()u3,f3()u2,f2()u1,f1()End,0t,5t,7t,4f,8d,10d,9c,16第35页/共65页示例(5.3-1)路线图如下所示，箭头表示通行方向，线上数字表示道路长度，试求s到t的最短路线sabcdt9865242443第36页/共65页示例(5.3-2)该问题是一个无循环的不定步数问题，从s到t 的路线最少可以经过3步，最多可以经过5步这样的问题，可以划分为5个(或3个)阶段来处理，其中允许某个阶段原地不动阶段1：决定由s 到a 或是b阶段2：决定是到a、c或是d阶段3：决定是到c、d或是t阶段4：决定是到d或是t
16、阶段5：到t第37页/共65页示例(5.3-3)状态变量xk 设为k 阶段初始所在地x1s，x2a,b，x3a,c,d，x4c,d,t，x5d,t，x6tk阶段决策uk是决定下一步走到哪里，有u1a,bu2(a)c,d，u2(b)a,c,du3(a)c,d，u3(c)d,t，u3(d)tu4(c)d,t，u4(d)t，u4(t)tu5(d)t，u5(t)tu6t第38页/共65页示例(5.3-4)状态转移方程xk+1=uk阶段效应rk(xk,uk)取为从xk 走到uk 的路线长度，如r1(s,a)=9贝尔曼函数 fk(xk)定义为从xk 走到 t 的最短路线贝尔曼方程第39页/共65页示例(5
17、.3-5)通过贝尔曼方程逆序求出条件最优目标函数值集合和条件最优决策集合 u5/x6x5t/tf5()u5()dtr5(x5,u5)+f6(x6)f5()计算表+0+0tt4040第40页/共65页示例(5.3-6)u4/x5x4d/dt/tf4()u4()cdtr4(x4,u4)+f5(x5)f4()计算表+4+4+0+03040240td/tt+02第41页/共65页示例(5.3-7)u3/x4x3c/cd/dt/tf3()u3()acdr3(x3,u3)+f4(x4)f3()计算表+2+2+4+4+4+0+06203504824cc/td/t第42页/共65页示例(5.3-8)u2/x3
18、x2a/ac/cd/df2()u2()abr2(x2,u2)+f3(x3)f2()计算表+8+8+2+4054284a/cc+2+464第43页/共65页示例(5.3-9)u1/x2x1a/ab/bf1()u1()sr1(x1,u1)+f2(x2)f1()计算表+4+49812b第44页/共65页示例(5.3-10)通过状态转移方程顺序求出最优决策序列和最优路线R*=f1(s)=12，x1*=su1*(x1*)=u1(s)=b，x2*=bu2*(x2*)=u2(b)=c，x3*=cu3*(x3*)=u3(c)=c/t，x4*=c/tu4*(x4*)=u4(c/t)=t，x5*=tu5*(x5*
19、)=u5(t)=t，x6*=t第45页/共65页示例(5.3-11)sabcdt9865242443End,0t,4t,2c,8c,4b,12第46页/共65页示例(5.4-1)路线图如下所示，箭头表示通行方向，线上数字表示道路长度，试求s到t的最短路线sabcdt5839149543第47页/共65页示例(5.4-2)该问题是一个有循环的不定步数问题，循环一圈的路线长度为8若有一条从起点到终点经过循环上顶点或边但无循环的路线只要该循环的路线长度为非负值，只走该路线必定比走该路线且循环几圈的路线总长度要小或等若该循环的路线长度为负值，只要走一圈循环其路线总长度就减少一些，这种情况下无最短路线不
20、算循环，从s到t 的路线最少可以经过3步，最多可以经过5步第48页/共65页示例(5.4-3)这样的问题，可以划分为3个阶段来处理，其中允许第2个阶段走2或3条边阶段1：决定由s 到a 或是b阶段2：决定由a 或b 经过某条路线到c 或d阶段3：由c 或d 到t状态变量xk 设为k 阶段初始所在地x1s，x2a,b，x3c,d，x4t第49页/共65页示例(5.4-4)k阶段决策uk是决定下面要走的路线以及下一步走到哪里，有u1a,bu2(a)c,d,cd,cbd，u2(b)d,ad,ac,acdu3t第50页/共65页示例(5.4-5)状态转移方程xk+1=k阶段的目的地阶段效应rk(xk,
21、uk)取为从uk 中所走路线的长度，如r2(b,ac)=7贝尔曼函数 fk(xk)定义为从xk 走到 t 的最短路线贝尔曼方程第51页/共65页示例(5.4-6)通过贝尔曼方程逆序求出条件最优目标函数值集合和条件最优决策集合x4x3t/tf3()u3()cdr3(x3,u3)+f4(x4)f3()计算表+0+0tt9595第52页/共65页示例(5.4-7)x3x2cdf2()u2()abr2(x2,u2)+f3(x3)f2()计算表+9+9+5+53674119cdd第53页/共65页示例(5.4-8)x2x1abf1()u1()sr1(x1,u1)+f2(x2)f1()计算表+11+958
22、16a第54页/共65页示例(5.4-9)通过状态转移方程顺序求出最优决策序列和最优路线R*=f1(s)=16，x1*=su1*(x1*)=u1(s)=a，x2*=au2*(x2*)=u2(a)=cd，x3*=du3*(x3*)=u3(d)=t，x4*=t第55页/共65页示例(5.4-10)sabcdt5839149543End,0t,5d,8d,9cd,11a,16第56页/共65页动态规划应用举例(2)资源分配问题：设有某种资源，总量为M，可以投入 n 种生产活动。已知用于生产活动 k 的资源为 uk 时的收益是 gk(uk)，问应如何分配资源才能使 n 种生产活动的总收益最大？该问题用
23、分为两种情况uk 连续变化，gk(uk)是线性函数时，该问题是线性规划问题gk(uk)不是线性函数时，该问题是非线性规划问题，可以利用动态规划方法求解第57页/共65页示例(5.5-1)某公司拟将50万元资金投放下属的A、B、C三个部门，各部门在获得资金后的收益如下表所示，试求总收益最大的投资分配方案投放资金(十万元)012345收益(万元)A01520252830B0010254570C01020304050第58页/共65页示例(5.5-2)该问题可以作为三阶段决策过程，对A、B、C三个部门的资金分配形成3个阶段决策变量uk 设为给部门k 分配的资金量，状态变量xk 设为给部门k 分配资金
24、之前的资金拥有量，则x1=5，xk+1=xk-uk，xk0，uk0，k=1,2,3用gk(uk)表示给部门k 分配资金uk 时从部门k 获得的收益第59页/共65页示例(5.5-3)f3()计算表x4 x30f3()u3()012345r3(x3,u3)+f4(x4)+0+0+0+0+0+00001010202030301324040450505第60页/共65页示例(5.5-4)x3 x2012345f2()u2()012345r2(x2,u2)+f3(x3)f2()计算表+0+10+0+0+10+20+0+10+20+30+0+10+20+30+40+0+10+20+30+40+50000
25、001010002025100030000452510045470452510007050第61页/共65页示例(5.5-5)x2 x1012345f1()u1()5r1(x1,u1)+f2(x2)f1()计算表+0+10+20+30+45+7030282520150700第62页/共65页示例(5.5-6)通过状态转移方程顺序求出最优决策序列和最优路线R*=f1(5)=70，x1*=5u1*(x1*)=u1(5)=0，x2*=5u2*(x2*)=u2(5)=5，x3*=0u3*(x3*)=u3(0)=0，x4*=0第63页/共65页作业(16)书上175页的4-1、177页的4-64-1的问题(最后一句话)改为试求A到E的最短路线及其长度第64页/共65页感谢您的观看！第65页/共65页