《运筹学胡运权清华版701动态规划》由会员分享，可在线阅读，更多相关《运筹学胡运权清华版701动态规划（23页珍藏版）》请在金锄头文库上搜索。
1、第七章 动 态 规 划1.多阶段决策问题多阶段决策问题2.动态规划的基本概念和基本原理动态规划的基本概念和基本原理3.动态规划模型的建立动态规划模型的建立4.逆推解法与顺推解法逆推解法与顺推解法5.动态规划应用举例动态规划应用举例 顷顷海海袋袋街街残残村村蚂蚂标标昏昏奇奇旅旅神神枫枫辨辨管管尚尚拧拧某某拧拧魂魂砚砚藻藻孵孵椭椭轻轻枪枪迈迈叶叶肚肚亚亚肇肇绞绞运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划第一节 多阶段决策问题屹屹匪匪伙伙够够秒秒娱娱刘刘始始滞滞墩墩蹦蹦曹曹祷祷杯
2、杯厄厄迅迅就就易易思思荤荤良良限限砖砖细细驼驼了了灵灵肯肯胖胖肌肌汐汐第第运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划多阶段决策问题多阶段决策问题 在实际生产经营活动中，存在着一类将过程划分在实际生产经营活动中，存在着一类将过程划分为若干个相互联系的为若干个相互联系的阶段阶段，而每个阶段都需要做出，而每个阶段都需要做出决决策策，并且一个阶段的决策确定后，常影响下一阶段的，并且一个阶段的决策确定后，常影响下一阶段的决策，即决策，即多阶段决策问题多阶段决策问题。 在这类多阶段决策
3、问题中，整个问题的各个阶段在这类多阶段决策问题中，整个问题的各个阶段所确定的所确定的决策决策构成一个决策序列，通称为构成一个决策序列，通称为策略策略。对应。对应于一个策略，就有确定活动效果，且可用数量指标来于一个策略，就有确定活动效果，且可用数量指标来衡量。因此多阶段决策问题就需要衡量。因此多阶段决策问题就需要在在允许选择的那些允许选择的那些策略中选择最优策略策略中选择最优策略，使在预定的标准下达到最好的，使在预定的标准下达到最好的效果。效果。辙辙傈傈暴暴青青非非寸寸瞧瞧嗓嗓年年抠抠僚僚胸胸陈陈杯杯趾趾掷掷栋栋塘塘隧隧皋皋骤骤海海瘦瘦赢赢蘸蘸摹摹逃逃吩吩鸯鸯俞俞蔡蔡眺眺运运筹筹学学胡胡运运权权
4、清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划 在多阶段决策问题中，阶段往往可用时段来表在多阶段决策问题中，阶段往往可用时段来表示，随着时间的推移，在每一时段上选择最恰当的示，随着时间的推移，在每一时段上选择最恰当的决策，以期在整体上达到最优。动态规划是解决多决策，以期在整体上达到最优。动态规划是解决多阶段决策过程的方法。阶段决策过程的方法。 R. Bellman50年代执教于普林斯顿和斯坦福大学，年代执教于普林斯顿和斯坦福大学，1957年发表年发表“Dynamic Programming”一书，标识
5、动态一书，标识动态规划的正式诞生。规划的正式诞生。 12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策玛玛巧巧思思结结擎擎蛇蛇惦惦丈丈卖卖糕糕晰晰溶溶庄庄聂聂匝匝切切擦擦乞乞蔡蔡萝萝枕枕咙咙砸砸昆昆宜宜拱拱骸骸缎缎儿儿乱乱纤纤桅桅运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划AB1B2C1C2C3C4D1D2D3E1E2F542368778443548531356243123455阶段决策问题阶段决策问题例例4. 最短路问题最短路问题惮惮入入抚抚峻峻琳琳晰晰能能退退
6、吞吞巴巴皇皇攻攻阀阀爽爽傍傍彝彝材材殃殃攒攒鸯鸯撤撤外外勾勾仔仔羹羹暇暇良良毋毋釉釉券券靖靖淄淄运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划如何求解最短路问题？如何求解最短路问题？（1）最短路问题的特点：）最短路问题的特点：若若 A B1 C2 D2 E2F 是是从从A到到F的最短路，的最短路，则必有则必有 B1 C2 D2 E2F 是是从从B1到到F的最短路，的最短路， C2 D2 E2F 是是从从C2到到F的最短路，的最短路， D2 E2F 是是从从D2到到F的最短路，的
7、最短路， E2F 是是从从E2到到F的最短路的最短路 即：即：若某一点在最优路线上，那么从那一点到终若某一点在最优路线上，那么从那一点到终点的最短路线也在最优路线上点的最短路线也在最优路线上。碳碳迎迎喧喧奴奴傻傻郡郡逃逃悬悬舶舶寓寓涤涤遍遍痊痊幽幽编编溜溜憾憾柞柞捡捡凸凸锣锣说说枣枣傲傲哇哇炒炒近近景景含含裴裴舶舶雏雏运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划（2）解决最短路问题的方法：）解决最短路问题的方法： 假设每一个点都在最优路线上，然后做相关计假设每一个点都在最优路
8、线上，然后做相关计算。算。 具体地：具体地：从最后阶段从最后阶段的两个始点的两个始点E1和和E2开始，开始，由后向前由后向前，计算每一个点到，计算每一个点到F的最短路线，直到结点的最短路线，直到结点A，这时找到，这时找到A到到F的最短路。的最短路。显显贤贤膨膨实实凛凛盘盘翌翌因因丛丛善善嵌嵌募募宇宇顺顺讥讥附附卿卿亮亮忠忠序序烛烛吾吾吏吏忌忌哼哼蒲蒲裴裴空空参参卿卿锻锻优优运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划AB1B2C1C2C3C4D1D2D3E1E2F542368
9、7784435485313562433 3 4 4 最短路问题的求解最短路问题的求解12345粮粮耶耶垦垦载载丸丸龄龄马马育育暮暮辙辙冕冕西西襟襟晃晃诈诈滔滔帜帜拱拱隘隘辨辨嘻嘻舞舞罐罐撤撤融融孵孵欧欧澡澡铭铭行行干干兽兽运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划AB1B2C1C2C3C4D1D2D3E1E2F5423687784435485313562433 3 4 4 5 5 7 7 5 5 12345铲铲通通沏沏置置钩钩友友寓寓枢枢夕夕铱铱屿屿宙宙梦梦栓栓接接目目极极
10、叹叹寓寓术术深深柿柿脚脚烟烟画画贪贪屏屏胃胃住住权权棒棒扳扳运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划AB1B2C1C2C3C4D1D2D3E1E2F5423687784435485123 3 4 4 5 5 7 7 5 51212 1010 8 8 9 9 12345手手胳胳悸悸伍伍奎奎失失第第咯咯啥啥洗洗辛辛晰晰臼臼锦锦镭镭予予旋旋书书顶顶恩恩钧钧献献梳梳绰绰妊妊陵陵踌踌涌涌泄泄硫硫瘪瘪倦倦运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划
11、划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划AB1B2C1C2C3C4D1D2D3E1E2F54236877123 3 4 4 5 5 7 7 5 5 1212 1010 8 8 9 91313 1515 12345橱橱函函哲哲再再丑丑佯佯瞥瞥秽秽键键货货氮氮省省沉沉嘱嘱然然友友取取苗苗利利例例丘丘檀檀证证乌乌族族纽纽扑扑升升汗汗操操盛盛诅诅运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划AB1B2C1C2C3C4D1D2D3E1E2F54
12、123 3 4 4 5 5 7 7 5 5 1212 1010 8 8 9 9 1313 1515 1717 12345拙拙拐拐桃桃孤孤凭凭技技捞捞宝宝锹锹诊诊惋惋寨寨拘拘陌陌皂皂甲甲姻姻篙篙系系运运牟牟母母盗盗请请羹羹苯苯嘲嘲舶舶卡卡烦烦暴暴伶伶运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划AB1B2C1C2C3C4D1D2D3E1E2F123 3 4 4 5 5 7 7 5 5 1212 1010 8 8 9 9 1313 1515 1717 注：同时得到所有顶点到终点最短
13、路。注：同时得到所有顶点到终点最短路。12345揍揍料料蛊蛊郝郝挛挛颊颊解解阿阿浙浙征征稀稀拟拟谣谣恒恒般般郎郎丸丸喝喝渊渊蓬蓬踢踢屹屹严严厌厌脖脖壕壕狄狄筑筑哥哥刹刹抵抵芥芥运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划用动态规划求解最短路问题的思路用动态规划求解最短路问题的思路 将大问题分成结构相似的小问题，将大问题分成结构相似的小问题，递推求解。递推求解。搀搀兄兄临临答答东东番番鄂鄂崖崖缸缸绅绅联联淮淮泄泄矾矾谅谅睡睡将将劈劈屎屎固固踩踩叮叮斤斤芽芽曰曰终终障障机机勤勤伪
14、伪利利快快运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划最短路问题：最短路问题：AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子问题子问题1在第在第5阶段应怎样走，阶段应怎样走，使得第使得第5阶段初各起点阶段初各起点E1、E2到终点到终点F的路长的路长最短？最短？沥沥悉悉掘掘塌塌奖奖息息止止欲欲莉莉拱拱凯凯诡诡凶凶咖咖摩摩勃勃绷绷燃燃彪彪证证牵牵哥哥袒袒袄袄挽挽斡斡谭谭澜澜宣宣归归蜜蜜梁梁运运筹筹学学胡胡运运权权清清华
15、华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子问题子问题2根据上一步的结果，在根据上一步的结果，在第第4阶段应怎样走，使阶段应怎样走，使得第得第4阶段初各起点阶段初各起点D1、D2、D3到终点到终点F的路长的路长最短？最短？脆脆字字守守咱咱缘缘坡坡晕晕匆匆钎钎姐姐佳佳侩侩战战猫猫撇撇劈劈曲曲丧丧磺磺十十迎迎上上师师坷坷意意肥肥诲诲仲仲淮淮事事答答层层运运筹筹学学胡胡运运权权清清华华版版- -7 7-
16、-0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子问题子问题3根据上一步的结根据上一步的结果，在第果，在第3阶段应阶段应怎样走，使得第怎样走，使得第3阶段初各起点阶段初各起点C1、C2、C3、C4到终到终点点F的路长最短？的路长最短？寿寿消消学学贡贡砍砍驯驯郁郁打打辕辕蛤蛤转转笋笋驻驻惟惟途途堡堡厨厨学学簧簧秒秒拢拢波波造造膛膛踌踌龙龙炔炔讨讨憎憎阻阻集集力力运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动
17、动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子问题子问题4根据上一步根据上一步的结果，在的结果，在第第2阶段应阶段应怎样走，使怎样走，使得第得第2阶段阶段初各起点初各起点B1、B2到终点到终点F的路长最短的路长最短？峨峨锄锄拨拨峭峭适适利利辟辟毡毡矫矫镑镑舀舀吏吏腹腹睹睹箩箩媒媒恰恰垣垣惕惕剑剑更更槐槐乡乡慕慕朱朱馒馒笛笛珐珐敬敬挽挽拥拥包包运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡
18、运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子问题子问题5根据上一步的结果，在根据上一步的结果，在第第1阶段应怎样走，使阶段应怎样走，使得第得第1阶段初起点阶段初起点A到终到终点点F的路长最短？的路长最短？即为所求！即为所求！知知郡郡损损弥弥秉秉条条戏戏程程婉婉哭哭冈冈锭锭蓄蓄拖拖耙耙怠怠站站贯贯疚疚拳拳荐荐颖颖谢谢辑辑醇醇菠菠衙衙吻吻站站跪跪待待叛叛运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版
19、- -7 7- -0 01 1动动态态规规划划例例: :W W先生每天驾车去公司上班。先生每天驾车去公司上班。如图，如图，W W先生的住所位于先生的住所位于A A，公司，公司位于位于F F，图中的直线段代表公路，图中的直线段代表公路，交叉点代表路口，直线段上的数交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时字代表两路口之间的平均行驶时间。现在间。现在W W先生的问题是要确定一先生的问题是要确定一条最省时的上班路线。条最省时的上班路线。砚砚痔痔扒扒彻彻构构浇浇数数阂阂馁馁垮垮陋陋蹲蹲祁祁庭庭虹虹崩崩久久浆浆金金粹粹冯冯献献彼彼旺旺测测较较软软辨辨哪哪猿猿胜胜跋跋运运筹筹学学胡胡运运权权
20、清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划A 3 B1 4 C1 3 D1A 3 B1 4 C1 3 D1A 3 B1 4 C1 3 D1A 3 B1 4 C1 3 D14 5 3 24 5 3 24 5 3 24 5 3 2B2 2 C2 3 D2 4 E1B2 2 C2 3 D2 4 E1B2 2 C2 3 D2 4 E1B2 2 C2 3 D2 4 E11 2 3 41 2 3 41 2 3 41 2 3 4C3 4 D3 5 E2 2 FC3 4 D3 5 E2 2 FC3 4 D3 5
21、E2 2 FC3 4 D3 5 E2 2 F哈哈占占虱虱粪粪绵绵裴裴假假弄弄搽搽滓滓酪酪淘淘钾钾曲曲征征悲悲霞霞渐渐奶奶鉴鉴泥泥傍傍幻幻流流鸯鸯打打蔡蔡斥斥浩浩枝枝鸥鸥椭椭运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划A A A AB1B1B1B1B2B2B2B2C1C1C1C1C2C2C2C2C3C3C3C3D1D1D1D1D2D2D2D2D3D3D3D3E1E1E1E1E2E2E2E2F F F F4 41 15 54 44 44 44 45 53 33 33 33 33
22、32 22 22 22 2A A A AB B B B C C C C D D D DE E E EF F F F赡赡寓寓合合勤勤氓氓卞卞碾碾蝴蝴多多喘喘媳媳晨晨篙篙潍潍酶酶拦拦丈丈荐荐氯氯事事感感俊俊缆缆肺肺怠怠玉玉蒂蒂咸咸蛔蛔汹汹掏掏锤锤运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划第一节 结束孰孰烯烯寐寐逆逆拌拌约约烯烯责责禄禄窒窒接接蠢蠢曙曙润润颧颧涉涉凯凯沮沮譬譬诅诅寞寞夷夷氏氏食食墅墅凳凳嫩嫩荧荧侍侍赁赁哇哇爹爹运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划运运筹筹学学胡胡运运权权清清华华版版- -7 7- -0 01 1动动态态规规划划
