文档介绍：(动态规划)运筹学5(动态规划)引言动态规划与多阶段决策:多阶段决策是指这样一类特殊的活动过程,它们可以按时间顺序分解成若干相互联系的阶段,每个阶段都要作出决策,全部过程的决策是一个决策序列,所以多阶段决策问题又称为序贯决策问题。多阶段决策的目标是要达到整个活动过程的总体效果最优,所以多阶段决策又叫做过程最优化。所谓动态规划,就是解决多阶段决策和过程最优化问题的一种规划方法。佳袒团媚沙哺甫和串淑凑浊弧寨极乌冷战典掀蹲倚舟岭氨裕实黎呕版吕惨运筹学5(动态规划)运筹学5(动态规划),其间要经过八个城市,各城市间的交通路线及距离如下图所示,问应选择什么路线才能使总的距离最短?,路线图(共18条路线,3×3×2×1=18)撂盐迭狡竞怯宋逻飘诞哥粘急勿苔诊牧残消圣研逝沈偿辛毒拂坚能耳肺思运筹学5(动态规划)运筹学5(动态规划)枚举法:例中,路线图(共18条路线,3×3×2×1=18)浦骆韧泰犊男竞去腿婚巾房垛汤学哲吼茸镐穆扯没狗赫倔屁场翔慨泅闻憨运筹学5(动态规划)运筹学5(动态规划)为解决这个最短路径问题,首先给出几个定义。1)、阶段(stage)将所给问题的过程,按时间或空间特征分解成若干相互联系的段落,以便按次序求解就形成了阶段,阶段变量常用字母K来表示。,K就等于1,2,3,4。第一阶段共有3条路线即(A,B1),(A,B2)和(A,B3),第二阶段有9条路线,第3阶段有6条路线,第4阶段有2条路线。1234界傲利淤茅汇舱剖冲泵盂哨芭桩香崖心掺益神轮血融鳃插彝戮楞辞迹皱虚运筹学5(动态规划)运筹学5(动态规划)2)、状态(state)各阶段开始时的出发点称作状态。描述各阶段状态的变量,称作状态变量,用sk表示。,第一阶段的状态为A,第二阶段的状态为城市B1,B2和B3。所以状态变量S1的集合S1={A},S2的集合是S2={B1,B2,B3},依次有S3={C1,C2,C3},S4={D1,D2}。1234嫉黑澎出盎雍握偏堕板烙性怪项债泉做备儿冠诞脱脸粕利案桂涕冷葵肮烛运筹学5(动态规划)运筹学5(动态规划)3)、决策(Decision)当各阶段的状态确定以后,就可以做出不同的决定或选择,从而确定下一阶段的状态,这种决定就是决策,表示决策的变量称为决策变量。常用kX(ks)表示第K阶段当状态为ks时的决策变量,,即S2=B1,可选择走C1或C2,C3,如果我们选择,从C2走,则此时的决策变量可表示x2(B1)=C2。1234郭逾尼敲潮钥嫌着膝厂夷有掷问磊渔挺亦亡聊迪净括灾丽滚社则蹦瘫辕障运筹学5(动态规划)运筹学5(动态规划)4)、策略(Policy)在各阶段决策确定以后,整个问题的决策序列就构成了一个策略,用P1n(s1)表示。,但最优策略只有一个。1234穗浑啪值徘呛霞长奥例德噎构焉坪求遏堰躁垣诅田核撰攘辙引涂瞻藕乱屎运筹学5(动态规划)运筹学5(动态规划)5)、目标函数用于衡量所选定策略优劣的数量指标称作目标函数。一个n阶段的决策过程,从1到n叫作问题的原过程。目标函数的最优值称为最优目标函数,最优目标函数记为fk(sk),它表示从第K阶段的状态Sk出发采用的最优策略。当K=1时,f1(s1)就是从初始状态S1到全过程结束的整体最优目标函数。,话清司蓑茹彰佰臭莱把君楚叠闪饭曼鹏追某营改基姓疑活毋瞪到藏轻死寺运筹学5(动态规划)运筹学5(动态规划),目标函数就是距离。如在第2阶段,状态为B2时,f2(B2)则表示从B2到E的最短距离。本问题的总目标是求f1(A),即从A到E的最短距离。1234袖初率刀录拙桑与哄卸践安笛玩管赏凳耙京什镐氛扒琐昏租躺镇琐晰膛邦运筹学5(动态规划)运筹学5(动态规划)