运筹学--动态规划.pptx

运筹学运筹学 第五章第五章 动态规划划本章重点本章重点n动态规划的四大要素、一个方程n动态规划问题的建模与求解动态规划概念动态规划概念(1)n前面介绍的线性规划研究的是一次性的决策n线性规划决策过程可以总结为u在给定资源和环境的情况下，决定变量的取值，使某个目标达到最大或最小值n这个决策过程可以表示如下图决 策x1x2uZ其中u 表示决策变量x1 表示决策所依赖的资源和环境Z表示目标函数x2 表示决策后的资源和环境状况动态规划概念动态规划概念(2)n例如，前面讲过的生产计划问题就是一次决策u某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的日生产计划产品所需原料数量产品所需原料数量（公斤（公斤/件）件）产品产品Q1（件）（件）产品产品Q2（件）（件）产品产品Q3（件）（件）原料可用量原料可用量（公斤（公斤/日）日）原料原料P12301500原料原料P2024800原料原料P33252000产品的利润产品的利润（千元（千元/件）件）354动态规划概念动态规划概念(3)n在这个模型中u模型中的A、b和C就是x1u模型中的X就是uu模型中的f(X)=CX就是ZuA、C和剩余的原料为x2n设每天生产三种产品的件数分别为x1、x2、x3n其线性规划模型为决 策x1x2uZ动态规划概念动态规划概念(4)n如果上例中的生产计划不是只在一天里进行，而是连续一周，每天投入一定量的原料，剩余的原料后面可以继续使用，每天只允许生产一种产品并获得相应的利润。问怎样决策才能使一周的总利润最大？n解决这样的问题需要将决策过程分为多个阶段，本问题需要分为如下的7个阶段。周日x1x2u1r1周一x3u2r2周六x8u7r7x7动态规划概念动态规划概念(5)nuk（k=1,2,3,4,5,6,7）表示第k天生产三种产品中的哪一种以及生产多少nx1=技术环境A、市场环境C和原料bnxk+1=技术环境A、市场环境C和原料b+第k天剩余的原料（k=1,2,3,4,5,6,7）nrk=第k天生产产品获得的利润n总利润=r1+r2+r3+r4+r5+r6+r7动态规划就是解决这种多阶段决策过程的方法动态规划就是解决这种多阶段决策过程的方法多阶段决策过程多阶段决策过程(1)u其中包含n个决策子问题，每个子问题称为一个阶段，用变量k表示，称为阶段变量uxk描述k 阶段初系统的状况，称为状态变量每个阶段有一个输入状态和一个输出状态一般把输入状态称为该阶段的阶段状态TnT1x1x2u1r1T2x3u2r2Tkxk+1ukrkxkxn+1unrnxnn一般的多阶段决策过程表示如下多阶段决策过程多阶段决策过程(2)uuk 代表k 阶段对第k 子问题进行的决策，称uk为k阶段的决策变量，uk的一组确定的取值称为一个决策urk 表示k 阶段从状态xk 出发做决策uk 之后产生的后果，称为k 阶段的阶段效应n若在上述的多阶段决策过程中，系统 k 阶段以后的决策只与 k 阶段系统的状态 xk 有关，而与系统以前的决策无关，则称该多阶段决策过程具有无后效性n注：注：动态规划的建模和求解都是划的建模和求解都是针对具有无具有无后效性的多后效性的多阶段决策段决策过程程多阶段决策过程多阶段决策过程(3)n在具有无后效性的多阶段决策过程中，uk由xk 决定，rk 和xk+1 由xk 和uk 决定，因此u决策可以写为 uk(xk)u阶段效应可以写为 rk(xk,uk)u状态xk+1=Tk(xk,uk)称为状态转移方程，其中Tk 是已知函数n多阶段决策过程中，从第k阶段到最终阶段的过程称为k-后部子过程，简称k-子过程动态规划模型动态规划模型n动态规划模型如下n 表示求和或加权求和nopt表示求最优(最大值或最小值)nXk表示k阶段状态可能的取值范围，称为状态可能集合nUk表示k阶段决策可能的取值范围，称为决策允许集合动态规划建模动态规划建模n确定阶段u根据实际情况进行阶段划分n明确状态变量xk和状态可能集合Xkn确定决策变量uk(xk)和决策允许集合Ukn确定状态转移方程xk+1=Tk(xk,uk)n明确阶段效应rk(xk,uk)和目标R示例示例(5.1-1)n前面讲过的生产计划问题u某工厂用三种原料生产三种产品，已知的条件如下表所示，如连续生产一周，每天投入一定量的原料，剩余的原料后面可以继续使用，每天只允许生产一种产品并获得相应的利润。试制订总利润最大的周生产计划(只建模，不求解)产品所需原料数量产品所需原料数量（公斤（公斤/件）件）产品产品Q1（件）（件）产品产品Q2（件）（件）产品产品Q3（件）（件）原料可用量原料可用量（公斤（公斤/日）日）原料原料P12301500原料原料P2024800原料原料P33252000产品的利润产品的利润（千元（千元/件）件）354示例示例(5.1-2)示例示例(5.1-3)动态规划解的概念动态规划解的概念(1)n最最优目目标值u在多阶段决策过程中，从起始状态x1开始，进行一系列的决策，使得目标R达到最优，我们把这种目标的值称为最优目标值，记为R*n最最优策略策略u把使目标达到最优的决策序列称为最优策略，记为 u1*,u2*,un*n最最优路路线u在采用最优策略时，系统从x1开始所经过的状态序列称为最优路线，记为x1*,x2*,xn+1*动态规划解的概念动态规划解的概念(2)n求解动态规划问题就是要找到最优策略、最优路线和最优目标值动态规划最优性原理动态规划最优性原理(1)n一个多阶段决策过程的最优策略具有这样的性质u无论其初始状态及其初始决策如何，对于前面决策所形成的某一状态而言，下余的决策序列必定构成最优策略n最优性原理的含义是u最优策略的任何一个k-后部子策略(uk*,uk+1*,un*)，是以xk*为初始状态的k-后部子过程的最优策略动态规划最优性原理动态规划最优性原理(2)n如上图uA到B之间的蓝线是由状态A到状态B的最优策略u在线上任取一点M，M到B之间的蓝线就是由状态M到状态B的最优策略ABM贝尔曼函数贝尔曼函数(1)n在k阶段从初始状态xk 出发，执行最优决策序列，到达过程终点时，整个k-后部子过程中的目标函数取值，称为条件最条件最优目目标函函数数，也称为贝尔曼函数曼函数，记为fk(xk)，则n为了将多阶段决策过程的任一阶段状态xk 的最优策略和最终的最优策略相区别，称前者为条件最优策略条件最优策略不一定等于最优路线中的k阶段状态系统从xk出发，在k-后部子过程中的最优策略贝尔曼函数贝尔曼函数(2)n构成条件最优策略的决策称为条件最条件最优决策决策n将k阶段状态xk的条件最优决策表示为uk(xk)，简记为uk，相应的条件最优策略表示为 uk,uk+1,unn执行条件最优策略时的阶段状态序列称为条条件最优路线件最优路线，表示为xk,xk+1,xn,xn+1贝尔曼函数贝尔曼函数(3)n动态规划方法的原理就是建立起fk(xk)与fk+1(xk+1)之间的递推关系，然后逐步求出所有的fk(xk)贝尔曼方程贝尔曼方程n对于无后效性的多阶段决策过程，根据最优性原理和贝尔曼函数定义，可得动态规划问题求解步骤动态规划问题求解步骤(1)n通过贝尔曼方程逆序求出条件最优目标函数值集合和条件最优决策集合uk=n时，不存在n+1阶段必须就阶段n的所有可能状态 计算 和动态规划问题求解步骤动态规划问题求解步骤(2)uk=n-1时，根据 ，就阶段n-1的所有可能状态 计算 和u余者类推，直到阶段1动态规划问题求解步骤动态规划问题求解步骤(3)n通过状态转移方程顺序求出最优决策序列和最优路线u阶段1的状态x1唯一确定时，x1*=x1，可得唯一确定的u1(x1*)和f1(x1*)，则R*=f1(x1*)，u1*(x1*)=u1(x1*)u当阶段1的状态x1不唯一时，u由 求得 ，求出u余者类推，直至阶段n，求出 、和动态规划的四大要素、一个方程动态规划的四大要素、一个方程n在动态规划的建模和求解过程中，有五个方面起着极其重要的作用u四大要素(模型里的)状态变量及其可能集合决策变量及其可能集合状态转移方程xk+1=Tk(xk,uk)阶段效应rk(xk,uk)u贝尔曼方程动态规划应用举例动态规划应用举例(1)n最短路最短路线问题：从某地出发，途径若干个中间点最后到达目的地，试求距离最短或费用最省的路线n用动态规划求解该问题分为三种情况考虑u定步数问题u不定步数问题(有限步=无循环)u不定步数问题(无限步=有循环)示例示例(5.2-1)n路线图如下所示，箭头表示通行方向，线上数字表示道路长度，试求s到t的最短路线sabcdeft9877456456754示例示例(5.2-2)n该问题是一个定步数问题，分为3个阶段u阶段1：决定由s 到a、b 还是cu阶段2：决定是到d、e 或是fu阶段3：到tn状态变量xk 设为k 阶段初始所在地ux1s，x2a,b,c，x3d,e,f，x4tnk阶段决策uk是决定下一步走到哪里，有uu1a,b,cuu2(a)d,f，u2(b)d,e，u2(c)d,e,f uu3t示例示例(5.2-3)n状态转移方程uxk+1=ukn阶段效应rk(xk,uk)取为从xk 走到uk 的路线长度，如r1(s,a)=9n贝尔曼函数 fk(xk)定义为从xk 走到 t 的最短路线n贝尔曼方程示例示例(5.2-4)n通过贝尔曼方程逆序求出条件最优目标函数值集合和条件最优决策集合 u3/x4x3t/tf3()u3()defr3(x3,u3)+f4(x4)f3()计算表+0+0+0ttt574574示例示例(5.2-5)u2/x3x2d/de/ef/ff2()u2()abcr2(x2,u2)+f3(x3)f2()计算表+5+5+5+7+7+4+474564568109fdd示例示例(5.2-6)u1/x2x1a/ab/bc/cf1()u1()sr1(x1,u1)+f2(x2)f1()计算表+8+10+998716c示例示例(5.2-7)n通过状态转移方程顺序求出最优决策序列和最优路线nR*=f1(s)=16，x1*=snu1*(x1*)=u1(s)=c，x2*=cnu2*(x2*)=u2(c)=d，x3*=dnu3*(x3*)=u3(d)=t，x4*=t示例示例(5.2-8)sabcdeft9877456456754x1x2x3x4f4()u3,f3()u2,f2()u1,f1()End,0t,5t,7t,4f,8d,10d,9c,16示例示例(5.3-1)n路线图如下所示，箭头表示通行方向，线上数字表示道路长度，试求s到t的最短路线sabcdt9865242443示例示例(5.3-2)n该问题是一个无循环的不定步数问题，从s到t 的路线最少可以经过3步，最多可以经过5步n这样的问题，可以划分为5个(或3个)阶段来处理，其中允许某个阶段原地不动u阶段1：决定由s 到a 或是bu阶段2：决定是到a、c或是du阶段3：决定是到c、d或是tu阶段4：决定是到d或是tu阶段5：到t示例示例(5.3-3)n状态变量xk 设为k 阶段初始所在地ux1s，x2a,b，x3a,c,d，x4c,d,t，x5d,t，x6tnk阶段决策uk是决定下一步走到哪里，有uu1a,buu2(a)c,d，u2(b)a,c,duu3(a)c,d，u3(c)d,t，u3(d)tuu4(c)d,t，u4(d)t，u4(t)tuu5(d)t，u5(t)tuu6t示例示例(5.3-4)n状态转移方程uxk+1=ukn阶段效应rk(xk,uk)取为从xk 走到uk 的路线长度，如r1(s,a)=9n贝尔曼函数 fk(xk)定义为从xk 走到 t 的最短路线n贝尔曼方程示例示例(5.3-5)n通过贝尔曼方程逆序求出条件最优目标函数值集合和条件最优决策集合 u5/x6x5t/tf5()u5()dtr5(x5,u5)+f6(x6)f5()计算表+0+0tt4040示例示例(5.3-6)u4/x5x4d/dt/tf4()u4()cdtr4(x4,u4)+f5(x5)f4()计算表+4+4+0+03040240td/tt+02示例示例(5.3-7)u3/x4x3c/cd/dt/tf3()u3()acdr3(x3,u3)+f4(x4)f3()计算表+2+2+4+4+4+0+06203504824cc/td/t示例示例(5.3-8)u2/x3x2a/ac/cd/df2()u2()abr2(x2,u2)+f3(x3)f2()计算表+8+8+2+4054284a/cc+2+464示例示例(5.3-9)u1/x2x1a/ab/bf1()u1()sr1(x1,u1)+f2(x2)f1()计算表+4+49812b示例示例(5.3-10)n通过状态转移方程顺序求出最优决策序列和最优路线nR*=f1(s)=12，x1*=snu1*(x1*)=u1(s)=b，x2*=bnu2*(x2*)=u2(b)=c，x3*=cnu3*(x3*)=u3(c)=c/t，x4*=c/tnu4*(x4*)=u4(c/t)=t，x5*=tnu5*(x5*)=u5(t)=t，x6*=t示例示例(5.3-11)sabcdt9865242443End,0t,4t,2c,8c,4b,12示例示例(5.4-1)n路线图如下所示，箭头表示通行方向，线上数字表示道路长度，试求s到t的最短路线sabcdt5839149543示例示例(5.4-2)n该问题是一个有循环的不定步数问题，循环一圈的路线长度为8n若有一条从起点到终点经过循环上顶点或边但无循环的路线u只要该循环的路线长度为非负值，只走该路线必定比走该路线且循环几圈的路线总长度要小或等u若该循环的路线长度为负值，只要走一圈循环其路线总长度就减少一些，这种情况下无最短路线n不算循环，从s到t 的路线最少可以经过3步，最多可以经过5步示例示例(5.4-3)n这样的问题，可以划分为3个阶段来处理，其中允许第2个阶段走2或3条边u阶段1：决定由s 到a 或是bu阶段2：决定由a 或b 经过某条路线到c 或du阶段3：由c 或d 到tn状态变量xk 设为k 阶段初始所在地ux1s，x2a,b，x3c,d，x4t示例示例(5.4-4)nk阶段决策uk是决定下面要走的路线以及下一步走到哪里，有uu1a,buu2(a)c,d,cd,cbd，u2(b)d,ad,ac,acduu3t示例示例(5.4-5)n状态转移方程uxk+1=k阶段的目的地n阶段效应rk(xk,uk)取为从uk 中所走路线的长度，如r2(b,ac)=7n贝尔曼函数 fk(xk)定义为从xk 走到 t 的最短路线n贝尔曼方程示例示例(5.4-6)n通过贝尔曼方程逆序求出条件最优目标函数值集合和条件最优决策集合x4x3t/tf3()u3()cdr3(x3,u3)+f4(x4)f3()计算表+0+0tt9595示例示例(5.4-7)x3x2cdf2()u2()abr2(x2,u2)+f3(x3)f2()计算表+9+9+5+53674119cdd示例示例(5.4-8)x2x1abf1()u1()sr1(x1,u1)+f2(x2)f1()计算表+11+95816a示例示例(5.4-9)n通过状态转移方程顺序求出最优决策序列和最优路线nR*=f1(s)=16，x1*=snu1*(x1*)=u1(s)=a，x2*=anu2*(x2*)=u2(a)=cd，x3*=dnu3*(x3*)=u3(d)=t，x4*=t示例示例(5.4-10)sabcdt5839149543End,0t,5d,8d,9cd,11a,16动态规划应用举例动态规划应用举例(2)n资源分配源分配问题：设有某种资源，总量为M，可以投入 n 种生产活动。已知用于生产活动 k 的资源为 uk 时的收益是 gk(uk)，问应如何分配资源才能使 n 种生产活动的总收益最大？n该问题用分为两种情况uuk 连续变化，gk(uk)是线性函数时，该问题是线性规划问题ugk(uk)不是线性函数时，该问题是非线性规划问题，可以利用动态规划方法求解示例示例(5.5-1)n某公司拟将50万元资金投放下属的A、B、C三个部门，各部门在获得资金后的收益如下表所示，试求总收益最大的投资分配方案投放资金(十万元)012345收益(万元)A01520252830B0010254570C01020304050示例示例(5.5-2)n该问题可以作为三阶段决策过程，对A、B、C三个部门的资金分配形成3个阶段n决策变量uk 设为给部门k 分配的资金量，状态变量xk 设为给部门k 分配资金之前的资金拥有量，则ux1=5，xk+1=xk-uk，xk0，uk0，k=1,2,3n用gk(uk)表示给部门k 分配资金uk 时从部门k 获得的收益示例示例(5.5-3)f3()计算表x4 x30f3()u3()012345r3(x3,u3)+f4(x4)+0+0+0+0+0+00001010202030301324040450505示例示例(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+50000001010002025100030000452510045470452510007050示例示例(5.5-5)x2 x1012345f1()u1()5r1(x1,u1)+f2(x2)f1()计算表+0+10+20+30+45+7030282520150700示例示例(5.5-6)n通过状态转移方程顺序求出最优决策序列和最优路线nR*=f1(5)=70，x1*=5nu1*(x1*)=u1(5)=0，x2*=5nu2*(x2*)=u2(5)=5，x3*=0nu3*(x3*)=u3(0)=0，x4*=0作业作业(16)n书上175页的4-1、177页的4-6n4-1的问题(最后一句话)改为u试求A到E的最短路线及其长度