第三节动态规划ppt课件.ppt

4.3 动态规划模型,一、多阶段决策过程及实例二、动态规划的基本概念三、动态规划模型举例,一、多阶段决策过程及实例动态规划是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家Bellman(贝尔曼）等人，根据一类多阶段决策问题的特性，提出了解决这类问题的“最优化原理”，并研究了许多实际问题，从而创建了最优化问题的一种新方法动态规划。多阶段决策问题是指这样一类活动的过程，由于他的特殊性，可将其分为若干个互相联系的阶段，在它的每一个阶段都需作出决策，并且一个阶段的决策决定后，常常影响下一个阶段的决策，从而使整个过程达到最好的活动效果。,这样一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，也称为序贯决策过程。例1（最短路线问题）如图，给出一个线路网络，A为始点，G为终点，两点之间的连线可以表示道路、管道等，连线上的数字表示两点间的距离（或费用），试选择一条由A到G的线路，使总距离（或费用）为最小。,例2 （生产存贮问题）某工厂根据市场调研情况，需制定今后四个月的生产计划，据估计，在这四个月内，市场对该产品的需求量如下表所示：假定市场每批产品的固定成本费用为3千元，每单位产品成本费用为1千元，库存费用每月为0.5千元.并且规定1月月初和4月月底均无产品库存.试问该厂如何安排各个月的生产与库存，使总费用最小.,二、动态规划的基本概念和基本方程动态规划的基本概念1、阶段(stage)k： 把所给问题的过程，恰当地分成若干个相互联系的阶段（步骤）.描述阶段的变量称为阶段变量，常用k表示.k = 1、2、3、2、状态(state)sk：状态表示每个阶段开始所处的状况，即是每一阶段的出发位置（阶段的起点）.通常一个阶段有多个状态.描述状态的变量称为状态变量.第k阶段的状态变量记为sk,该阶段所有可能的状态的全体称为状态集合，记为Sk.如例1：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、状态转移方程：状态转移方程描述由一个状态到另一个状态的演变过程.因为某一阶段的状态变量及决策变量取定后，下一阶段的状态就随之而定.用 sk+1=T(sk,uk) 表示k阶段与k+1阶段的变化规律.5、策略由过程的第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).,或者说全过程中各个阶段的决策uk组成的有序总体就称为策略.允许策略集合可供选择的策略范围，用P表示.最优策略从允许策略集合中找出的使问题达到最有效果的策略称为最优策略.6、指标函数和最优指标函数值阶段效益（指标）是衡量该阶段决策效果的数量指标，它是阶段状态和阶段决策的函数.用dk(sk,uk)表示在第k阶段由状态sk和执行决策uk(sk)所得的效益.,指标函数（目标函数）是用来衡量所实现过程优劣的一种数量指标，它表示系统执行某一策略所产生的效益，它是定义在过程（可以是全过程，也可以是后部子过程）上的数量函数.用fk,n表示：当初始状态确定后，过程的策略就确定了，因而指标函数也就确定了，故指标函数是初始状态和策略的函数，即：最优指标函数值指标函数的最优值称为最优指标函数值，记为fk(sk).,动态规划的基本思想和基本方程最短路线的特性如果从起点到终点的最短路线在第k阶段通过点Pk，则最短路线上由点Pk出发到达终点的这一段子路线，对于从Pk到达终点的所有可能选择的不同路线来说，必定是最短的。动态规划的基本思想由后向前逐步推移计算.即从最后一段开始，由后向前逐步递推，求出各点到终点的最短路线.下面我们利用动态规划基本思想来解决如下问题：,例3 、求由A到D的最短路线.,再按计算顺序反推之，可得最优决策函数序列uk,即：u1(A)=B1,u2(B1)=C1,u3(C1)=D.从最短路线问题的例子的计算过程，可以看到，用动态规划方法解决问题的关键是正确写出k阶段与k+1阶段之间的递推关系式（基本方程）：由此得动态规划的一般模型为：,按照上述方法我们来求例1图中的最短路线解：,三、动态规划模型举例动态规划建模的一般步骤（1）划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。（2）正确选择状态变量选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。,（3）确定决策变量及允许决策集合通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。（4）确定状态转移方程根据k 阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。（5）确定阶段效益（指标）函数和最优指标函数，建立动态规划基本方程阶段（效益）指标函数是指第k 阶段的收益，最优指标函数是指从第k 阶段状态出发到第n 阶段末所获得收益的最优值，最后写出动态规划基本方程。,以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。,例4（生产库存管理系统）设某公司全年计划生产某种产品A，其四个季度的订货量分别为600件，700件，500件，1200件.已知生产产品A的生产费用与产品数量的平方成正比，其比例系数为0.005，厂内有仓库可以存放未销售出的产品，其存贮费为每件每季度1元，问如何安排各季度的产量，可以满足各季度的订货量需求，又使全年的总费用最小？,模型建立： 1、划分阶段：每一季度为一个阶段；2、设出状态变量：令sk（k=1,2,3,4)表示第k个季度初的产品数量（库存数量）, s1=0,s5表示年终剩余的产品数量；3、设出决策变量：令uk(k=1,2,3,4)表示第k季度的产量,ukAk- sk，Ak表示第k季度的订货量；4、状态转移方程：sk+1=sk+uk-Ak,5、阶段效益：表示该季度的生产费用与库存费用之和dk(sk,uk)=1*sk+0.005uk2;,6、基本方程：模型求解：,例5（生产管理问题）设某生产企业有数量为A的某种机器，可在高低两种负荷下生产某种产品.假设在高负荷下生产时，产品的年产量s1和投入生产的机器数量y的关系为s1=g(y)，到年终的机器完好率为a(0a1);在低负荷下生产时，产品的产量s2和投入生产的机器数z的关系为s2=h(z),其机器的完好率为b(0b1).现在要制定一个n年的生产计划，在每年的年初，问如何重新分配完好的机器在两种负荷下工作的数量，可使得n年内的总产量最高？如果要求在第n年必须保证仍有一定数量B的完好机器，又如何制定生产计划？,模型建立（1）设出状态变量：令sk表示第k年年初具有完好的机器数量，s1=A,sn+1表示第n年末的完好机器数量；（2）设出决策变量：令uk表示第k年初分配给高负荷生产的机器数量，则分配给低负荷的机器数量为sk-uk；（3）状态转移方程： Sk+1=auk+b(sk-uk)=(a-b)uk+bsk；（4）阶段效益：表示第k年底产品的产量，即：dk(sk,uk)=g(uk)+h(sk-uk),(5)基本方程：fk(sk)表示从状态sk出发，采用后部最优子策略，到第n年底年终的最高产量，则的动态规划模型为：,模型求解:设s1=1000台，n=5年，a=0.7, b=0.9, g(y)=8y,h(z)=5z.则状态转移方程为:sk+1=0.7uk+0.9(sk-uk)=0.9sk-0.2uk阶段效益为dk=8uk+5(sk-uk)=3uk+5sk；动态规划模型为：求解如下：,如果要求终端s6=500,这时如何安排生产，才能在满足这一要求的条件下产量最高？解：由状态转移方程得： s6=-0.2u5+0.9s5=500u5=4.5s5-2500,即u5*=4.5s5-2500,由状态转移方程可得：,例6、（设备更新问题）在工农业生产和交通运输业中，经常遇到因设备陈旧或损坏而需要更新的问题.从经济观点出发，一台设备使用多少年更新，才能使总的效益最大，这就是设备更新问题.设备更新的一般提法为：在已知一台设备已使用过t年再使用一年的效益函数为r(t)，维修费用函数为u(t)及更新费用函数为c(t)条件下，要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年总效益最大。,模型建立（1）划分阶段：将问题划分为n个阶段，阶段变量k为营运年数；（2）状态变量：设sk表示第k年年初设备的役龄，若开始时役龄为0，则sk的可达状态为0，1，2，k;若开始时役龄为m，则sk可达的状态为m,m+1,m+k-1;（3）决策变量：设uk=K表示第k年年初继续使用旧设备,uk=R表示第k年年初更新旧设备； （4）状态转移方程：,（5）阶段效益函数：（6）设fk(sk)表示从第k年年初开始，使用一台役龄为sk的设备，到第n年年末的最大效益，从而得动态规划模型为：,模型求解：设买一台同种型号的新设备价格为5千元；每台设备的年均效益、维修费用、旧设备的折旧费及更新费用如下表所示：,例、已知网络计划各工序的正常工作、特定工时及相应费用如下表所示，网络图如1所示.,按正常工作,则从图1中计算出总工期为74天. 关键路线为 . 由上表可得正常工作条件下，总费用为47800元.设正常工作条件下，任务总间接费用8000元. 工期每缩短一天则间接费用减少330元，求最低成本日程.,