运筹学-动态规划ppt课件.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《运筹学-动态规划ppt课件.ppt》由会员分享,可在线阅读,更多相关《运筹学-动态规划ppt课件.ppt(81页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、清华大学出版社管理运筹学教程管理运筹学教程第三章第三章 动态规划动态规划清华大学出版社图3-1清华大学出版社名词解释n阶段,用k表示。n状态、状态变量,用Sk表示,通常是集合n决策、决策变量,通常用uk或xk表示。n状态转移及其方程:n过程与子过程n策略与子策略:n指标函数与最优值函数:nkp,),(,nkknkpSV),(1kkkkuSTS),()(,nkknkPpkkpSVSfoptnknk),()(,nkknkPpkkpSVSfoptnknk清华大学出版社二、最优化原理与动态规划的基本方法nBellman原理n动态规划的基本方法n逆向顺序法n前向顺序法清华大学出版社Bellman原理示意
2、图清华大学出版社逆向顺序法求解例3-2清华大学出版社第二节 动态规划建模与求解步骤n建立动态规划模型的基本要求n动态规划的求解步骤清华大学出版社一、建立动态规划模型的基本要求n将问题划分成若干阶段。有的问题的阶段性很明显,有的则不明显,需要分析后人为假设。n确定各阶段的状态变量,并给出状态转移方程,状态转移方程的形式应当与递推顺序一致。n状态变量应当满足无后效性要求。n明确指标函数,给出最优函数递推方程,递推方程的形式应当与递推顺序一致。清华大学出版社二、动态规划的求解步骤n正确划分阶段。n确定状态变量和决策变量,并给出状态变量和决策变量的可行集合。n确定求解的递推顺序,给出状态转移方程。n确
3、定阶段、子过程(子策略)的指标函数,确定最优值函数的递推方程和边界条件。n递推求解。n与递推过程反向求出最优策略(最优决策变量值系列)和最优状态变化路线。清华大学出版社第三节 动态规划的应用举例n定价问题n资源分配问题n生产存储问题清华大学出版社一、定价问题n某公司考虑为某新产品定价,该产品的单价拟从每件5元、6元、7元和8元这四个中选取一个,每年允许价格有1元幅度的变动,该产品预计畅销五年,据预测不同价格下各年的利润如表3-1所示。 清华大学出版社表3-2 每年预计利润额单价第一年第二年第三年第四年第五年5元6元7元8元101214161213141515161615202018142524
4、1814清华大学出版社建立数学模型n按年划分阶段,k=1,2,.,5n每阶段的状态变量为本年(上一年已确定)的价格,状态变量的可行集合Sk=(5,6,7,8)。n决策变量为每年依据当年价格为下一年度决定价格,根据题意决策变量的可行集合是:n采用逆序算法,因此状态转移方程是n最优值函数递推方程为)1, 1(kkkkSSSu)(1kkkSuS)()(max)(11kkkkukkSfudSfk清华大学出版社进行各阶段的计算n采用逆序法,设 n当k=5时,S5=(5,6,7,8),由表3-1得到n当k=4时, S4=(5,6,7,8),由递推方程n得0)(66Sf14)8(,18)7(,24)6(,2
5、5)5(5555ffff)()(max)(5544444SfudSfu5)5(,4524202520max)6()6()5()5(max)5(454544ufdfdf清华大学出版社继续求解8) 8 (,92) 8 (, 8) 7(,90) 7(, 7) 6(,87) 6(6) 5 (,84) 5 (,17) 8 (,76) 8 (, 7 , 6) 7(,75) 7(, 7 , 6) 6(,74) 6(6) 5 (,73) 5 (,27) 8 (,57) 8 (, 6) 7(,61) 7(, 6 , 5) 6(,61) 6(6 , 5) 5 (,60) 5 (,37) 8 (,32) 8 (,
6、6) 7(,42) 7(, 5) 6(,45) 6(111111112222222233333333444444ufufufufkufufufufkufufufufkufufuf时当时当时当清华大学出版社反推得最优路线n按照与求最优值函数方向相反的顺序求最优状态路线:最优决策变量。即从第一年单价应为8元开始,向后推算。n得第二年定价8元,第三年定价7元,第四年定价6元,第五年定价5元。n最大利润值为92万元。清华大学出版社用决策图求解清华大学出版社二、资源分配问题n某公司将5台加工中心分配给甲、乙、丙、丁四个工厂,各工厂或设备后可产生如表3-2所示的利润,应怎么分配设备可使公司总利润最大?清华
7、大学出版社 工厂设备数甲乙丙丁012345067101215037912130510111111046111212清华大学出版社建立数学模型n按工厂次序划分阶段,k=1,2,3,4n状态变量为各阶段可用于分配的设备总台数n决策变量是分配给第k工厂的设备数n采用逆序算法,状态转移方程n最优值函数递推方程kkkxSS10)()()(max)(5511SfSfudSfkkkkukkk清华大学出版社第4阶段的最优解n当k=4时,S4=(0,1,2,3,4,5)0123450123450461112120461112120123454S4u),(444Sud)(44Sf)(4*4Su清华大学出版社第3阶
8、段的最优解n当k=3时,S3=(0,1,2)0000000101054045512012051064069101023S3u),(333Sud)(334uSf*3u33fd )(33Sf清华大学出版社第3阶段的最优解(续)n当k=3时,S3=33012305101111640111114111423S3u),(333Sud)(334uSf*3u33fd )(33Sf清华大学出版社第3阶段的最优解(续)n当k=3时,S3=44012340510111112116401216161511161,23S3u),(333Sud)(334uSf*3u33fd )(33Sf清华大学出版社第3阶段的最优解(
9、续)n当k=3时,S3=5501234505101111111212116401217211715112123S3u),(333Sud)(334uSf*3u33fd )(33Sf清华大学出版社第2阶段的最优解n当k=2时,S2=(0,1,2)0000000101035053502012037105010871002S2u),(222Sud)(223uSf*2u22fd )(22Sf清华大学出版社第2阶段的最优解(续)当k=2时,S2=330123037914105014131291402S2u),(222Sud)(223uSf*2u22fd )(22Sf清华大学出版社第2阶段的最优解(续)当k
10、=2时,S2=4401234037912161410501617171412171,22S2u),(222Sud)(223uSf*2u22fd )(22Sf清华大学出版社第2阶段的最优解(续)当k=2时,S2=55012345037912132116141050211921191715210,22S2u),(222Sud)(223uSf*2u22fd )(22Sf清华大学出版社第1阶段的最优解(续)当k=1时,S1=5 50123450671012152117141050212321201715231 1S1u),(111Sud)(112uSf*1u11fd )(11Sf清华大学出版社第4阶段
11、的最优解n当k=4时,S4=(0,1,2,3,4,5)012345012345046111212046111212012345清华大学出版社反向求最佳状态路线0 , 10 , 122 , 32 , 141*44*33*22*1uSuSuSu由方案一方案二工厂名分配设备数工厂名分配设备数甲乙丙丁1121甲乙丙丁1220清华大学出版社三、生产存储问题n某公司生产并销售某产品。根据市场预测,今后四个月的市场需求量如表3-7所示。时期(月)需求量(dk)12342324清华大学出版社已知的其它条件n已知生产一件产品的成本是1千元,每批产品的生产准备成本是3千元,每月仅能生产一批,每批6件。每件存储成本
12、为0.5千元,且第一个月初无存货,第四个月末的存货要求为零。求最优(最低成本)生产与存储计划。n设第k月的生产量uk,存储量为Sk,则总成本为kkkkkSuuSC5 . 003),(清华大学出版社建立数学模型n以月划分阶段,k=1,2,3,4n各阶段决策变量为该阶段生产量uk,状态变量为该阶段存储量Sk。n采用逆序算法,则状态转移方程为n最低成本递推公式是kkkkduSS10)()(),(min)(551160SfSfuSCSfkkkkkduSukkkkkk清华大学出版社第四阶段的最优解n当k=4时,d4=4,因地四阶段末无存货,因此S4=(0,1,2,3,4)S4u4本期成本C4S5f5(S
13、5)f4(S4)生产存储01234432107654000.511.5276.565.52000000000076.565.52清华大学出版社第三阶段最优解n当k=3时,由于 ,且第三阶段需求量d3=2,S3=(0,1,2,3,4,5,6)44SS3u3本期成本C3S4f4(S4)f3(S3)生产存储0234565678900000567890123476.565.521212.51313.511清华大学出版社第三阶段最优解:S3=1S3u3本期成本C3S4f4(S4)f3(S3)生产存储112345456780.50.50.50.50.54.55.56.57.58.50123476.565.
14、5211.512.012.513.010.5清华大学出版社第三阶段最优解:S3=2S3u3本期成本C3S4f4(S4)f3(S3)生产存储2012340456711111156780123476.565.52811.512.012.510.0清华大学出版社第三阶段最优解:S3=3,4S3u3本期成本C3S4f4(S4)f3(S3)生产存储3012304561.51.51.51.51.55.56.57.512346.565.52811.512.09.5401204522226723465.52811.59清华大学出版社第三阶段最优解:S3=5,6S3u3本期成本C3S4f4(S4)f3(S3)生
15、产存储501042.52.52.56.5345.5288.560033425清华大学出版社第二阶段最优解n当k=2时,d2=3,由于最生产能力为6,而d1=2,因此S2=(0,1,2,3,4)S2u2本期成本C2S3f3(S3)f2(S2)生产存储03456678900006789012311.010.58.08.01717.51617清华大学出版社第二阶段最优解:S2=1S2u2本期成本C2S3f3(S3)f2(S2)生产存储123456567890.50.50.50.50.55.56.57.58.59.50123411.010.58.08.08.016.51715.516.517.5清华大
16、学出版社第二阶段最优解:S2=2S2u2本期成本C2S3f3(S3)f2(S2)生产存储2123456456789111111567891001234511.010.58.08.08.08.016.016.515.016.017.018.0清华大学出版社第二阶段最优解:S2=3S2u2本期成本C2S3f3(S3)f2(S2)生产存储3012345604567891.51.51.51.51.51.51.51.55.56.57.58.59.510.5012345611.010.58.08.08.08.05.012.516.014.515.516.517.515.5清华大学出版社第二阶段最优解:S2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 动态 规划 ppt 课件
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内