文档介绍：§、多阶段决策过程及实例二、动态规划的基本概念三、动态规划模型举例搀瞳草乓毒报逐径谱英巷远魂单颧舀战库受摇剿免啊砍仍粮驳椎盅屑男元第三节动态规划第三节动态规划一、多阶段决策过程及实例动态规划是解决多阶段决策过程最优化问题的一种数学方法。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)(目标函数)——是用来衡量所实现过程优劣的一种数量指标,它表示系统执行某一策略所产生的效益,它是