管理运筹学课件第9章-动态规划讲解学习.ppt
《管理运筹学课件第9章-动态规划讲解学习.ppt》由会员分享,可在线阅读,更多相关《管理运筹学课件第9章-动态规划讲解学习.ppt(25页珍藏版)》请在咨信网上搜索。
管理运筹学课件,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管理运筹学课件第9章-动态规划,引例 马车驿站问题,1,2,4,8,3,3,5,3,8,6,6,7,8,6,3,2,3,5,A,B,2,B,1,D,2,D,1,C,3,C,2,C,4,C,1,E,A B C D E,阶段1,阶段2,阶段3,阶段4,4个阶段,E,E,D1D2,D1D2,D1D2,D1D2,C2C3C4,C1C2C3,1,D1,E,1,D2,E,2,C4,D1,C4,D2,2,C3,D1,C3,D2,2,C2,D1,C2,D2,2,C1,D1,C1,D2,3,B2,C2,B2,C3,B2,C4,3,B1,C1,B1,C2,B1,C3,B1B2,2,A,B1,A,B2,A,B2,B1,C4,C3,C2,C1,D1,D2,4,3,2,1,终点,路线数,可选路线,起点,阶段,一共有2321=12条不同的路线,f(E)=0,f(D1)=2,f(D2)=1,f(C1)=8,f(C2)=5,f(C3)=4,f(C1)=5,f(B1)=8,f(B2)=11,f(A)=13,回顾分析过程:,1.将分析对象划分成4阶段;,2.每阶段始点状态与终点状态有关,而不考虑始终点状态如何形成(无记忆性);,3.每阶段各始点状态为终点状态与始点至终点距离之和的最小值(状态转移),这种最优化方法称为动态规划,由美国数学家贝尔曼等人于20世纪50年代创立.,12/18/2024,2,管理运筹学课件,本章主要内容,9.1 动态规划的概念和原理,9.1.1,动态规划的基本概念,9.1.2,动态规划的最优化原理,9.2 动态规划的模型和求解,9.2.1,动态规划模型的建立,9.2.2,动态规划问题的解法,9.3 应用举例,案例1,资源分配问题,案例2,设备负荷问题,案例3,生产库存问题,案例4,背包问题,本章小结,12/18/2024,3,管理运筹学课件,9.1.1 动态规划的基本概念,1.阶段:,把所给问题的过程,恰当地分为若干个相互联系的阶段,以便能按一定的次序去求解。描述阶段的变量称为阶段变量,常用,k,表示。导入案例中,k,=1,2,3,4,2.状态变量:,每个阶段开始所处的自然状况或客观条件(用点集表示).如引例:第1阶段的状态就是起点,A,记为,s,1,=,A,;第2阶段有2个状态,B,1,B,2,记为,s,2,=,B,1,B,2,;第3阶段有4个状态,C,1,C,2,C,3,C,4,记为,s,3,=,C,1,C,2,C,3,C,4,;第4阶段有2个状态,D,1,D,2,记为,s,4,=,D,1,D,2,;,3.决策变量:,在某一阶段的某个状态时的不同选择,如引例中,B,1,状态下有3种选择:,B,1,C,1,B,1,C,2,B,1,C,3,这3种选择构成了允许决策的集合。不同状态下允许决策的集合也不同,故决策变量是状态变量的函数,即,x,k,(s,k,)D(s,k,),1,2,4,8,3,3,5,3,8,6,6,7,8,6,3,2,3,5,A,B,2,B,1,D,2,D,1,C,3,C,2,C,4,C,1,E,A B C D E,阶段1,阶段2,阶段3,阶段4,4个阶段,4.策略,按顺序排列的决策组成的集合,由过程的第k阶段开始到终止状态为止的过程(或k子过程),k子过程的策略称子策略,记为P,k,n,(s,k,),即,P,k,n,(,s,k,)=,x,k,(,s,k,),x,k+1,(,s,k+1,),x,n,(,s,n,),当,k,=1,时,即为全过程的一个策略。如引例中:,DE,,即4到5过程起始有2个状态,,D,1,和,D,2,,因此有,P,4,5,=,D,1,E,,,D,2,E,5.状态转移方程,确定过程是由一个状态到另一个状态的演变过程。第k阶段状态变量值给定后,如果确定决策变量,第k+1阶段状态变量值就完全确定。即:,s,k+1,=T,(,s,k,x,k,),如引例中:若对,A,B,1,A,B,2,选择了,A,B,1,则,s,2,=5,B,1,到,C,有3种选择:,B,1,C,1,、,B,1,C,2,、,B,1,C,3,,若选择了,B,1,C,2,则,s,3,=,s,2,+,d,(,B,1,C,2,)=8,6.指标函数,用来衡量所实现过程优劣的一种数量指标。其基本方程有加法和乘法两种形式,通常加法形式用的较多,其公式为:,7.边界条件,起始或终止条件。,12/18/2024,4,管理运筹学课件,5.1.2 动态规划的基本原理,1,2,4,8,3,3,5,3,8,6,6,7,8,6,3,2,3,5,A,B,2,B,1,D,2,D,1,C,3,C,2,C,4,C,1,E,A B C D E,阶段1,阶段2,阶段3,阶段4,4个阶段,最优化原理(Optimality principle):,最优策略具备这样的性质:无论初始状态与初始决策如何,以后诸决策对以第一个决策所形成的状态作为初始状态的过程而言,必然构成最优策策略.通俗地说:最优策略的子策略也是最优的.,例如,在导入案例中,最优策略是AB1C2D1E,最短距离为13,其子策略:B1C2D1E,C2D1E,D1E也是最优的。,依据这一原理,从后往前推各阶段最优子过程,从而得到全程最优过程。,设,f(i),表示从点,i到终点E的最短距离,d(i,j),表示点,i,j之间的距离.,显然,f,(,E,)=0,为该问题的边界条件.,k=4,决策:D1,E,k=3,决策:D2,E,决策:C1,D1,决策:C2,D1,k=2,决策:C3,D2,决策:C4,D2,决策:B1,C2,决策:B2,C3,k=1,决策:A,B1,最短路线:A,B1C2D1E,最短路长:13,12/18/2024,5,管理运筹学课件,5.1.2 动态规划的最优化原理,12/18/2024,6,管理运筹学课件,9.2.1 动态规划模型的建立,解 把生产第,k,种产品看成是第,k,阶段,划分为,n,个阶段.,设,s,k,表示第,k,阶段初资源可用量(状态变量),x,k,表示分配给第,k,阶段资源的数量(决策变量),显然有:,允许决策集合,s,k+,1,=s,k,-x,k,(状态转移方程),s,1,=a,(边界条件),指标函数:,若,fk,(,sk,),表示数量为,sk,资源分配给第,k,种产品时,从第k阶段到第n阶段总收益,则有:,12/18/2024,7,管理运筹学课件,9.2.1 动态规划模型的建立,指标函数通常有两种形式:加法形式和乘法形式。,12/18/2024,8,管理运筹学课件,9.2.2 动态规划问题的解法:逆序法,最优值函数f(k):从k阶段到E的最短距离;阶段指标函数,即该阶段选择不同路线的距离。从后向前推。,S,1,=,A,S,2,=,B,1,B,2,S,3,=,C,1,C,2,C,3,C,4,S,4,=,D,1,D,2,S,5,=,E,f,5,(,E,),=,0,同理,f,4,(,D,1,),=2,f,4,(,D,2,),=,1,同理,f,3,(,C,2,),=,5,f,3,(,C,3,),=,4,f,3,(,c,4,),=,5,同理,f,2,(,B,2,),=,11,1,2,4,8,3,3,5,3,8,6,6,7,8,6,3,2,3,5,A,B,2,B,1,D,2,D,1,C,3,C,2,C,4,C,1,E,A B C D E,阶段1,阶段2,阶段3,阶段4,12/18/2024,9,管理运筹学课件,9.2.2 动态规划问题的解法:顺序法,1,2,4,8,3,3,5,3,8,6,6,7,8,6,3,2,3,5,A,B,2,B,1,D,2,D,1,C,3,C,2,C,4,C,1,E,A B C D E,阶段1,阶段2,阶段3,阶段4,最优值函数f(k):从A到k阶段的最短距离;阶段指标函数,即该阶段选择不同路线的距离。从前向后推。,S,0,=,A,S,1,=,B,1,B,2,S,2,=,C,1,C,2,C,3,C,4,S,3,=,D,1,D,2,S,4,=,E,最优值函数:,f,0,(,A,),=,0,f,1,(,B,1,),=,5,f,2,(,B,2,)=3,f,2,(,C,1,),=,7,f,3,(,C,2,),=,8,f,3,(,C,3,),=,10,f,3,(,c,4,),=,9,f,3,(,D,1,),=,11,f,4,(,D,2,),=,13,12/18/2024,10,管理运筹学课件,案例1 资源分配问题,5台设备分配给3个工厂,盈利表如下,如何分配可使获利最大?,台数,工厂,0,1,2,3,4,5,甲,乙,丙,0,0,0,4,5,3,8,9,7,11,11,9,11,12,11,11,12,12,分析 3个工厂看成3个阶段.,阶段变量,k,(,k=1,2,3,),;,状态变量,s,k,表示为分配给第,k,个工厂至第,n,个工厂的设备台数;,决策变量,x,k,表示分配给第,k,个工厂的设备台数;,则有,s,k+1,=,s,k,-x,k,;,P,k,(,x,k,)表示为,xk,台设备分配到第,k,个工厂所得赢利值;,f,k,(s,k,)表示为 台设备分配给第,k,个工厂至第,n,个工厂所得到的最大赢利值。则有:,12/18/2024,11,管理运筹学课件,k,=3,x,3,s,3,P,3,(,x,3,),f,3,(,s,3,),x,3,*,0,1,2,3,4,5,0,1,2,3,4,5,0,3,7,9,11,12,0,3,7,9,11,12,0,1,2,3,4,5,k,=2,x,2,s,2,P,2,(,x,2,)+f,3,(s,2,-x,2,),f,2,(,s,2,),x,2,*,0,1,2,3,4,5,0,1,2,3,4,5,0,0+3,0+7,0+9,0+11,0+12,5+0,5+3,5+7,5+9,5+11,9+0,9+3,9+7,9+9,11+0,11+3,11+7,12+0,12+3,12+0,0,5,9,12,16,18,0,1,2,1,2,2,2,3,k,=1,x,1,s,1,P,1,(,x,1,)+f,2,(s,1,-x,1,),f,1,(,s,1,),x,1,*,0,1,2,3,4,5,5,0+18,4+16,8+12,11+9,11+5,11+0,20,1,2,3,0,1,2,3,4,5,甲,乙,丙,0,0,0,4,5,3,8,9,7,11,11,9,11,12,11,11,12,12,方案一:1,2,2,方案二:2,1,2,方案三:2,2,1,方案四:3,2,0,12/18/2024,12,管理运筹学课件,案例2 设备负荷问题,某种机器可在高低两种不同的负荷下进行生产,设机器在高负荷下生产的产量函数为,g=,9,x,,其中,x,为投入生产的机器数量,季度完好率为,a=,0.65,,在低负荷下生产的产量函数为,h=,4,y,,其中,y,为投入生产的机器数量,季度完好率为,b=,0.95,。设资源拥有量100.,解 4季度看成4阶段,sk,第,k,季初拥有完好机器数,xk,第,k,季分配给高负荷机器数,则低负荷分配数,s,k,-x,k,下季度初完好机器数,s,k+1,=0.65,x,k,+0.95(,s,k,-,x,k,),第,k,季产量,v,k,=6,x,k,+4(,s,k,-x,k,),12/18/2024,13,管理运筹学课件,k,=4,f,4,是,x,4,的增函数,故最大值解为,x,4,*,=,s,4,相应地有,f,4,(,s,4,)=9,s,4,k,=3,f,3,是,x,3,的增函数,故最大值解为,x,3,*,=,s,3,相应地有,f,3,(,s,3,)=14.85,s,3,12/18/2024,14,k,=2,f,2,是,x,2,的增函数,故最大值解为,x,2,*,=,s,2,相应地有,f,2,(,s,2,)=18.6525,s,2,k,=1,f,1,是,x,1,的减函数,故最大值解为,x,1,*,=,0,相应地有,f,1,(,s,1,)=21.719875,s,1,=2172,反向推算,由,s,1,=100,,x,1,=0,知,s,2,=95,,x,2,=95,,s,3,=61.75,,x,3,=61.75,,s,4,=40.14,,x,4,=40.14,,s,5,=26.09。,即第1季度设备100%全部分配给低负荷,第2季度初完好设备为95%,全部分配给高负荷第3季度完好设备为61.75%,全部分配给高负荷第4季度完好设备为40.14%,全部分配给高负荷。全年结束后,设备完好率为26.09%.最大产量2172。,12/18/2024,15,Lingo程序,model,:,sets,:,JD/1.4/:s,x,v;,!,定义状态变量、决策变量和指标函数,;,ZB/1.5/:f;,!,定义最优值函数,;,endsets,f(5)=0;,!,初始化最优值函数,;,s(1)=100;,!,初始化状态变量,;,for,(jd:x=s);,!,决策变量取值限制,;,for,(jd(k)|k#lt#4:s(k+1)=0.65*x(k)+0.95*(s(k)-x(k););,!,状态转移方程,;,for,(jd(k):v(k)=9*x(k)+4*(s(k)-x(k);,!,指标函数表达式,;,for,(zb(k)|k#lt#5:f(k)=v(k)+f(k+1););,!,基本方程,;,max,=f(1);,!,目标,;,end,12/18/2024,16,管理运筹学课件,案例3 生产库存问题,12/18/2024,17,管理运筹学课件,案例3 生产库存问题,12/18/2024,18,管理运筹学课件,案例3 生产库存问题,12/18/2024,19,管理运筹学课件,案例3 生产库存问题,阶段,1,2,3,4,5,需求/dk,2,3,2,4,3,逆推:,f,5,=26.5,s,5,=0,x,5,*,=0 或 3,s,4,=3,x,4,*,=6,s,4,=0,x,4,*,=0,s,3,=1,s,3,=4,x,3,*,=0 或 3,x,3,*,=6,s,2,=3,s,2,=0,s,2,=0,x,2,*,=6,x,2,*,=0,x,2,*,=0,s,1,=0,x,1,*,=2,s,1,=3,x,1,*,=5,s,1,=3,x,1,*,=5,12/18/2024,20,管理运筹学课件,案例4 背包问题,12/18/2024,21,管理运筹学课件,案例4 背包问题,12/18/2024,22,管理运筹学课件,案例4 背包问题,背包重,3,4,5,价值,4,5,6,最优方案:依次装2,1,0个,最大价值:13,12/18/2024,23,管理运筹学课件,本章小结,本章介绍了动态规划的基本概念、基本原理和几种典型的应用问题。要求,1)理解动态规划的核心概念,状态与状态变量、决策与决策变量、策略、状态转移方程、指标函数和最优值函数。,2)理解动态规划的最优化原理:一个最优策略的子策略总是最优的。,3)动态规划模型的建立和求解,一般的,给一个实际问题建立动态规划模型时,必须做到下面五点。,(1)将问题的过程划分成适当的阶段。,(2)正确选择状态变量,使它既能描述过程的演变,又满足无后效性。,(3)确定决策变量及每阶段的允许决策集合。,(4)正确写出状态转移方程即。,(5)正确写出指标函数的关系。,动态规划模型的求解有两种方法:逆序解法和顺序解法。,4)动态规划的应用,掌握动态规划在最短路线问题、资源分配问题、生产库存问题、背包问题求法。,12/18/2024,24,管理运筹学课件,此课件下载可自行编辑修改,仅供参考!感谢您的支持,我们努力做得更好!谢谢,- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 管理 运筹学 课件 动态 规划 讲解 学习
咨信网温馨提示:
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
关于本文