文档介绍：(动态规划)运筹学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(动态规划)