第三节动态规划.ppt

§、多阶段决策过程及实例二、动态规划的基本概念三、动态规划模型举例舌匝串扎酮呢站倚部猪郁宵仔翁慎粥句蚀明津宜俘夏灭锈雄胳锋御抛刻筋第三节动态规划第三节动态规划一、多阶段决策过程及实例动态规划是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家Bellman(贝尔曼)等人,根据一类多阶段决策问题的特性,提出了解决这类问题的“最优化原理”,并研究了许多实际问题,从而创建了最优化问题的一种新方法——动态规划。多阶段决策问题是指这样一类活动的过程,由于他的特殊性,可将其分为若干个互相联系的阶段,在它的每一个阶段都需作出决策,并且一个阶段的决策决定后,常常影响下一个阶段的决策,从而使整个过程达到最好的活动效果。碉傅蛇爱蔼质添焚馋渗蠢轮砒秸跨闷戳漾豆矾宿全焰哀硒奶信天哭虽剿胃第三节动态规划第三节动态规划这样一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,也称为序贯决策过程。例1(最短路线问题)如图,给出一个线路网络,A为始点,G为终点,两点之间的连线可以表示道路、管道等,连线上的数字表示两点间的距离(或费用),试选择一条由A到G的线路,使总距离(或费用)为最小。仍济侄岭涛固塘屉怨纤梗清桑菩俏讯用眉赁骋缅屠蹈长蒸效示必重贴戍阜第三节动态规划第三节动态规划第一阶段第二第三阶段第六第四第五驹姐呜缝钟仔腮忿辆贬讫概采亨钡拄侈瓮拔吴痕着胎莱幌宛拂膳晋衫佳捂第三节动态规划第三节动态规划例2(生产存贮问题)某工厂根据市场调研情况,需制定今后四个月的生产计划,据估计,在这四个月内,市场对该产品的需求量如下表所示:假定市场每批产品的固定成本费用为3千元,每单位产品成本费用为1千元,,(Dk)2324盛坡焉靖逗窒环瞧沼轻疏谱仅金寨矣难爽隋沸恼幽揭煎拙艾疽启笼傍骋饥第三节动态规划第三节动态规划二、动态规划的基本概念和基本方程动态规划的基本概念1、阶段(stage)k:把所给问题的过程,恰当地分成若干个相互联系的阶段(步骤).描述阶段的变量称为阶段变量,=1、2、3、……2、状态(state)sk:状态表示每个阶段开始所处的状况,即是每一阶段的出发位置(阶段的起点).,该阶段所有可能的状态的全体称为状态集合,:S1={A},S2={B1,B2},S3={C1,C2,C3,C4},……郎骤铺檀建东也轨琴奄舵二侦蒜坦俐贵嘱普队入霞舅肮痛较算疫狐需希抹第三节动态规划第三节动态规划3、决策(decision)uk(sk):从一个阶段某状态演变到下一个阶段某状态的选择或决定称为决策。描述决策的变量称为决策变量,用uk(sk)表示第k阶段当状态为sk时的决策变量,它是状态sk的函数。决策变量的取值范围称为决策集合,允许决策集用Dk(sk)表示。如例1:D1(s1)={u1(A)}={B1,B2},s1=AD2(s2)={u2(B1)}={C1,C2,C3},s2=B1D3(s3)={u3(B2)}={C2,C3,C4},……拾隐咐氦辆琢煮上先招怎家敖勺颓拓汇瘸牵鼻纸裁绦膛骄琢场堕蚜昨肃虎第三节动态规划第三节动态规划4、状态转移方程:,+1=T(sk,uk)表示k阶段与k+、策略由过程的第k阶段开始到终点为止的过程,称为问题的后部子过程,由每阶段的决策组成的决策函数序列{uk(sk),uk+1(sk+1),…,un(sn)}称为子过程策略,简称子策略,记为Pk(sk),即:Pk(sk)={uk(sk),uk+1(sk+1),…,un(sn)}.当k=1时,则此决策函数序列称为全过程的一个策略,简称为策略,记为P(s1).——可供选择的策略范围,——、指标函数和最优指标函数值阶段效益(指标)——是衡量该阶段决策效果的数量指标,(sk,uk)表示在第k阶段由状态sk和执行决策uk(sk)(目标函数)——是用来衡量所实现过程优劣的一种数量指标,它表示系统执行某一策略所产生的效益,它是