第三节动态规划.pptx

一、多阶段决策过程及实例动态规划是解决多阶段决策过程最优化问题的一种数学方法。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)(目标函数)——是用来衡量所实现过程优劣的一种数量指标,它表示系统执行某一策略所产生的效益,它是定义在过程(可以是全过程,也可以是后部子过程),n表示:当初始状态确定后,过程的策略就确定了,因而指标函数也就确定了,故指标函数是初始状态和策略的函数,即:最优指标函数值——指标函数的最优值称为最优指标函数值,记为fk(sk).动态规划的基本思想和基本方程最短路线的特性——如果从起点到终点的最短路线在第k阶段通过点Pk,则最短路线上由点Pk出发到达终点的这一段子路线,对于从Pk到达终点的所有可能选择的不同路线来说,必定是最短的。动态规划的基本思想——,由后向前逐步递推,: