《动态规划教学》PPT课件.ppt
《《动态规划教学》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《动态规划教学》PPT课件.ppt(76页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、管管 理理 运运 筹筹 学学第十章第十章 动态规划动态规划1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理3动态规划的应用动态规划的应用(1)4动态规划的应用动态规划的应用(2)1管管 理理 运运 筹筹 学学11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例例例1 最短路径问题最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC4123123123221647248386756110637512管管 理理 运运 筹筹 学学11多阶段决策过程最优化问题举例多阶段决策过程最优
2、化问题举例(一)用穷举法的计算量(一)用穷举法的计算量:l如果从A到E的站点有k=4个,除A、E之外每站有3个位置则总共有3k-1条路径;l计算各路径长度总共要进行3k-1次加法以及3k-1-1次比较。随着k的值增加时,需要进行的加法和比较的次数将迅速增加。3管管 理理 运运 筹筹 学学11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例(二)用动态规划解法(二)用动态规划解法以上求从A到E的最短路径问题,可以转化为四个性质完全相同,但规模较小的子问题,即分别从Di、Ci、Bi、A到E的最短路径问题。第四阶段:两个始点D1和D2,终点只有一个;表10-1分析得知:从D1和D2到E的最短
3、路径唯一。阶段4本阶段始点(状态)本阶段各终点(决策)到E的最短距离本阶段最优终点(最优决策)ED1D210*6106EE4管管 理理 运运 筹筹 学学第三阶段:有三个始点C1,C2,C3,终点有D1,D2,对始点和终点进行分析和讨论分别求C1,C2,C3到D1,D2的最短路径问题:表10-2分析得知:如果经过C1,则最短路为C1-D2-E;如果经过C2,则最短路为C2-D2-E;如果经过C3,则最短路为C3-D1-E。11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例阶段3本阶段始点(状态)本阶段各终点(决策)到E的最短距离本阶段最优终点(最优决策)D1D2C1C2C38+10=1
4、87+10=171+10=116+6=125+6=116+6=12121111D2D2D15管管 理理 运运 筹筹 学学第二阶段:有4个始点B1,B2,B3,B4,终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3的最短路径问题:表10-3分析得知:如果经过B1,则走B1-C2-D2-E;如果经过B2,则走B2-C3-D1-E;如果经过B3,则走B3-C3-D1-E;如果经过B4,则走B4-C3-D1-E。11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例阶段2本阶段始点(状态)本阶段各终点(决策)到E的最短距离本阶段最优终点(最优决策)
5、C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C36管管 理理 运运 筹筹 学学第一阶段:只有1个始点A,终点有B1,B2,B3,B4。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题:表10-4最后,可以得到:从A到E的最短路径为AB4C3D1E11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例阶段1本阶段始点(状态)本阶段各终点(决策)到E的最短距离本阶段最优终点(最优决策)B1B
6、2B3B4A4+12=16 3+13=163+14=172+12=1412C27管管 理理 运运 筹筹 学学 以上计算过程及结果,可用图2表示,可以看到,以上方法不仅得到了从A到D的最短路径,同时,也得到了从图中任一点到E的最短路径。以上过程,仅用了22次加法,计算效率远高于穷举法。BCBBCDC413ADE2123123321647248386751610601061211111213141412751211多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例8管管 理理 运运 筹筹 学学一、基本概念:1、阶段k:表示决策顺序的离散的量,阶段可以按时间或空间划分。2、状态sk:能确定地表
7、示决策过程当前特征的量。状态可以是数量,也可以是字符,数量状态可以是连续的,也可以是离散的。3、决策xk:从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数,记为xk(sk)。决策允许集合Dk(sk):在状态sk下,允许采取决策的全体。4、策略Pk,n(sk):从第k阶段开始到最后第n阶段的决策序列,称k子策略。P1,n(s1)即为全过程策略。5、状态转移方程sk+1=Tk(sk,xk):某一状态以及该状态下的决策,与下一状态之间的函数关系。22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理9管管 理理 运运 筹筹 学学 6、阶段指标函数vk(sk,xk):从状态sk出发
8、,选择决策xk所产生的第k阶段指标。过程指标函数Vk,n(sk,xk,xk+1,xn):从状态sk出发,选择决策xk,xk+1,xn所产生的过程指标。动态规划要求过程指标具有可分离性,即Vk,n(sk,xk,xk+1,xn)=vk(sk,xk)+Vk+1(sk+1,xk+1,xn)称指标具有可加性,或 Vk,n(sk,xk,xk+1,xn)=vk(sk,xk)Vk+1(sk+1,xk+1,xn)称指标具有可乘性。二、基本方程:最优指标函数fk(sk):从状态sk出发,对所有的策略Pk,n,过程指标Vk,n的最优值,即22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理10管管 理理
9、 运运 筹筹 学学 对于可加性指标函数,上式可以写为上式中“opt”表示“max”或“min”。对于可乘性指标函数,上式可以写为以上式子称为动态规划最优指标的递推方程,是动态规划的基本方程。终端条件:为了使以上的递推方程有递推的起点,必须要设定最优指标的终端条件,一般最后一个状态n+1下最优指标fn+1(sn+1)=0。22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理11管管 理理 运运 筹筹 学学三、最优化原理三、最优化原理作为整个过程的最优策略具有如下性质:不管在此最优策略上的某个状态以前的状态和决策如何,对该状态来说,以后的所有决策必定构成最优子策略。就是说,最优策略的任
10、意子策略都是最优的。22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理12管管 理理 运运 筹筹 学学一、资源分配问题一、资源分配问题例2.某公司拟将某种设备5台,分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后,预测可创造的利润如表10-5所示,问这5台设备应如何分配给这3个工厂,使得所创造的总利润为最大?表10-5盈利工厂设备台数甲厂乙厂丙厂0000135427106391111412111251311123 3 动态规划的应用动态规划的应用(1)(1)13管管 理理 运运 筹筹 学学解:将问题按工厂分为三个阶段,甲、乙、丙三个厂分别编号为1、2、3厂。设sk=分配给第k个
11、厂至第3个厂的设备台数(k=1、2、3)。xk=分配给第k个设备台数。已知s1=5,并有从与的定义,可知以下我们从第三阶段开始计算。3 3 动态规划的应用动态规划的应用(1)14管管 理理 运运 筹筹 学学 第三阶段:显然将台设备都分配给第3工厂时,也就是时,第3阶段的指标值(即第3厂的盈利)为最大,即由于第3阶段是最后的阶段,故有其中可取值为0,1,2,3,4,5。其数值计算见表106。3 3 动态规划的应用动态规划的应用(1)15管管 理理 运运 筹筹 学学 表表106 012345000014 4126623111134121245121253 3 动态规划的应用动态规划的应用(1)16
12、管管 理理 运运 筹筹 学学其中表示取3子过程上最优指标值时的决策,例如在表10-6中可知当=4时,有有此时,即当时,此时取(把4台设备分配给第3厂)是最优决策,此时阶段指标值(盈利)为12,最优3子过程最优指标值也为12。第二阶段:当把台设备分配给第2工厂和第3工厂时,则对每个值,有一种最优分配方案,使最大盈利即最优2子过程最优指标函数值为 3 3 动态规划的应用动态规划的应用(1)17管管 理理 运运 筹筹 学学因为上式也可写成其数值计算如表107所示。表107 0123450001045120654102301156110 1424012114110 161,25012512116114
13、1102123 3 动态规划的应用动态规划的应用(1)18管管 理理 运运 筹筹 学学其中在的这一行里,当时,这里从表105中可知,把1台设备交给乙厂所得盈利数即可,知,这里从表106查即可知=11。同样可知当时,可知;当时,;当时,;当时,;由于,不可能分2厂5台设备,故时,栏空着不填。从这些数值中取得最大即得,即有=16。在此行中我们在取最大值的上面加一横以示区别,也可知这时的最优决策为1或2。3 3 动态规划的应用动态规划的应用(1)19管管 理理 运运 筹筹 学学第一阶段:把台设备分配给第1,第2,第3厂时,最大盈利为其中可取值0,1,2,3,4,5.数值计算见表108表10-8然后按
14、计算表格的顺序推算,可知最优分配方案有两个:1.由于,根据,查表107可知,再由,求得。即分配给甲厂0台,乙厂2台,丙厂3台。2.由于,根据,查表107可01234553169+1012+513+0210,23 3 动态规划的应用动态规划的应用(1)20管管 理理 运运 筹筹 学学知,再由,求得,即分配给甲厂2台,乙厂2台,丙厂1台。这两种分配方案都能得到最高的总盈利21万元。3 3 动态规划的应用动态规划的应用(1)21管管 理理 运运 筹筹 学学二、背包问题二、背包问题设有n种物品,每一种物品数量无限。第i种物品每件重量为wi公斤,每件价值ci元。现有一只可装载重量为W公斤的背包,求各种物
15、品应各取多少件放入背包,使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数(i=1,2,n),背包中物品的总价值为z,则Maxz=c1x1+c2x2+cnxns.t.w1x1+w2x2+wnxnWx1,x2,xn0且为整数。3 3 动态规划的应用动态规划的应用(1)22管管 理理 运运 筹筹 学学下面用动态规划逆序解法求解它。设阶段变量k:第k次装载第k种物品(k=1,2,n)状态变量sk:第k次装载时背包还可以装载的重量;决策变量uk=xk:第k次装载第k种物品的件数;决策允许集合:Dk(sk)=xk|0 xksk/wk,xk为整数;状态转移方程:sk
16、+1=skwkxk;阶段指标:vk=ckxk;最优过程指标函数fk(sk):第k到n阶段容许装入物品的最大使用价值;递推方程:fk(sk)=maxckxk+fk+1(sk+1)=maxckxk+fk+1(skwkxk);xDk(sk)终端条件:fn+1(sn+1)=0。3 3 动态规划的应用动态规划的应用(1)23管管 理理 运运 筹筹 学学例3.某咨询公司有10个工作日可以去处理四种类型的咨询项目,每种类型的咨询项目中待处理的客户数量、处理每个客户所需工作日数以及所获得的利润如表109所示。显然该公司在10天内不能处理完所有的客户,它可以自己挑选一些客户,其余的请其他咨询公司去做,应如何选择
17、客户使得在这10个工作日中获利最大?表109咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润1234432213472811203 3 动态规划的应用动态规划的应用(1)24管管 理理 运运 筹筹 学学解:用动态规划来求解此题。我们把此问题分成四个阶段,第一阶段我们决策将处理多少个第一种咨询项目类型中的客户,第二阶段决策将处理多少个第二种咨询项目类型中的客户,第三阶段、第四阶段我们也将作出类似的决策。我们设分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日(第k阶段的状态变量)。=在第k种咨询项目中处理客户的数量(第k阶段的决策变量)。已知10并有3 3 动态规划的应
18、用动态规划的应用(1)25管管 理理 运运 筹筹 学学 并从与的定义可知从第四阶段开始计算:显然将个工作日尽可能分配给第四类咨询项目,即时,第四阶段的指标值为最大,其中,表示取不大于的最大整数,符号为取整符号,故有由于第四阶段是最后的阶段,故有3 3 动态规划的应用动态规划的应用(1)26管管 理理 运运 筹筹 学学因为至多为10,其数值计算见表1010。表表101001000100200300400500600702018020190201100113 3 动态规划的应用动态规划的应用(1)27管管 理理 运运 筹筹 学学第三阶段:当把个工作日分配给第四类和第三类咨询项目时,则对每个值,都有
19、一种最优分配方案,使其最大盈利即最优3子过程最优指标函数值为因为因为至多为10,所以的取值可为0,1,2。其数值计算见表1011。3 3 动态规划的应用动态规划的应用(1)28管管 理理 运运 筹筹 学学 表表1011012000100200300400111500111600111711+0200802011+0222902011+02221002011+02223 3 动态规划的应用动态规划的应用(1)29管管 理理 运运 筹筹 学学 第二阶段:同样以每个值都有一种最优分配方案,使其最大盈利即最优2子过程最优指标函数值为:因为,故有因为至多为10,所以的取值为0,1,2,3。其数值计算见表
20、1012。33动态规划的应用动态规划的应用(1)30管管 理理 运运 筹筹 学学33动态规划的应用动态规划的应用(1)表表10-1231管管 理理 运运 筹筹 学学 第一阶段:我们已知,又因为,同样有因为,故可取值为0,1,2,10。其数值计算见表1013。表101333动态规划的应用动态规划的应用(1)32管管 理理 运运 筹筹 学学从表1013可知,从而得10010,在表1012的的这一行可知,由,查表1011的的这一行可知,最后由,查表10-10的的这一行得,综上所述得最优解为:此时最大盈利为28。现在我们不妨假设该咨询公司的工作计划有所改变,只有8个工作日来处理这四类咨询项目,那么该咨
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态规划教学 动态 规划 教学 PPT 课件
限制150内