第4章 动态规划1 引例和基本概念.ppt

1、第4章 动态规划(Dynamic Programming),动态规划的基本概念和思想 最短路径问题 背包问题 投资分配问题,例 5.1.1 管道设计,最短路问题就是从某地出发，途经若干中间点最后到达目的地，要求找出路程或费用最小的路线。一般的最短路问题将在下一章讨论，这里只讨论分层的最短路问题。下面的管道设计问题(例5.1.1)就是其中之一。,从A点到E点要铺设一条煤气管道， 中间必须经过三个中间站， 第一站可在B1、B2、B3中选择， 第二站可在C1、C2、C3中选择， 第三站可在D1、D2、D3中选择， 要求选择一条由A 到E的铺管路线，使总长度最短。 其中两点连线上的数字表示两点间管线的

2、长度。,从A点到E点铺设管道，可以按其地理特点自然地分成四个阶段：（如下图所示） 从A到B是第一阶段，从B到C是第二阶段， 从C到D是第三阶段，从D到E是第四阶段，,在阶段2，从B3点出发，只有C1、C3两种可选择的点， 如选C1,则C1就是阶段2在B3点的决策结果； C1点既是阶段2铺设管道的终点，又是阶段3铺设管道的起点；,5,4,2,6,3,4,6,5,6,1,2,2,2,3,3,2,3,4,同样的理由，可以递推得其余阶段的铺设路线，如阶段3在C1点的决策是D1，阶段4在D1点的决策只有E点；由于到E点是整个铺设管道的终点，至此，决策过程完成，铺设一条A点到E点的管道是由四个阶段的管道组

3、成的，如A-B3-C1-D1-E，它也称为一个策略。,5,4,2,6,3,4,6,5,6,1,2,2,2,3,3,2,3,4,可以看出，各个阶段的决策不同，铺设的管道也不同，并且当某个阶段的始点给定后，它直接影响着后面各阶段的行进路线和管道的长短，而后面各阶段的路线 的选取不受这点以前各阶段路线的影响。,5,4,2,6,3,4,6,5,6,1,2,2,2,3,3,2,3,4,因此，最短路线问题可简化为四个阶段的决策问题，使由这四个阶段决策组成决策序列，也称为策略所决定的一条路线的总长度最短。,递推关系式为:,例 5.1.2 多阶段资源分配问题,设有数量为x的某种资源，将它投入两种生产方式A和B

4、中：以数量y投入生产方式A，剩下的量投入生产方式B，则可得到收入g(y)+h(x-y)，其中g(y)和h(y)是已知函数，并且g(0)=h(0)=0；同时假设以y与x-y分别投入两种生产方式A，B后可以回收再生产，回收率分别为a与b。试求进行n个阶段后的最大总收入。,若以y与x-y分别投入生产方式A与B，在第一 阶段生产后回收的总资源为x1=ay+b(x-y)，再将x1 投入生产方式A和B，则可得到收入g(y1)+h(x1-y1)， 继续回收资源x2=ay1+b(x1-y1)， 若上面的过程进行n个阶段，我们希望选择n 个变量y,y1,y2,yn-1，使这n个阶段的总收入最大。,因此，问题就变

5、成：求y,y1,y2,yn-1，以使g(y)+h(x-y)+ g(y1)+h(x1-y1)+ +g(yn-1)+h(xn-1-yn-1) 达到最大，且满足条件 x1=ay+b(x-y) x2=ay1+b(x1-y1) xn-1=ayn-2+b(xn-2-yn-2) yi与xi均非负,i=1,2, ,n-1,开始有资源x,再进行k阶段生产并 采取最优分配策略后得到的最大总收入,当k=1时，有 当k=2时，有,x,A,B,y,x-y,第一阶段,回收,x1=ay+b(x-y),A,B,第二阶段,y1,x1-y1,递推关系式为:,例 5.1.3 生产和存储控制问题,某工厂生产某种季节性商品，需要作下一

6、 年度的生产计划，假定这种商品的生产周期需 要两个月，全年共有6个生产周期，需要作出 各个周期中的生产计划。,设已知各周期对该商品的需要量如下表所示：,假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品15个单位，每生产一个单位商品的成本为100元。当开足夜班时，每一生产周期能生产的商品也是15个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为120元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储费用的，假设每单位商品存储一周期需要16元，问应该如何作生产和存储计划，才能使总的生产和

7、存储费用最小？,设第i个周期的生产量为xi，周期末的存储量为uj，那 么这个问题用式子写出来就是：求x1, x2,x6， u1, u2, u3, u4, u5,（ u0, u6 已知）,满足条件：,Sk是这个周期的商品的需要量。,x1+u0=5+u1 x2+u1=5+u2 x3+u2=10+u3 x4+u3=30+u4 x5+u4=50+u5 x6+u5=8+u6,即,1500,3300,15,30,其中,其生产和库存费用为,用 表示开始的库存量为u0, 第k个周期 末库存量为uk的前k个周期的最优生产和库存费 用, 递推关系式为:,多阶段决策问题,一.简介 1.研究对象:用来解决多阶段决策过

8、程最优化的一种数量方法。 2.方法:把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。 3.划分:系统的动态过程可以按照时间或空间进程分为状态相互联系而又相互区别的各个阶段；每个阶段都要进行决策, 4.目的:在多阶段决策过程中目的是使整个过程的决策达到最优效果。,例如生产库存问题,产品仓库容量H=9。期初库存量为2，要求期末（七月底）库存量为0。每个月生产的产品在月末入库。求最优生产计划xk,分析处理方法,静态处理 线性(整数)规划 动态处理 动态规划,生产库存问题的动态结构,按月分7个阶段,8个状态,一般多阶段决策问题的结构,二、基本概念 1、阶段： 把一个问题的过程，恰当

9、地分为若干个相互联系的阶段，以便于按一定的次序去求解。 描述阶段的变量称为阶段变量，常用自然数k表示。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。,2、状态：表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态，描述过程状态的变量称为状态变量，常用sk表示第k阶段的状态变量。,状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合，用表示表示第k阶段的状态。,1,2,3,4,例如,状态变量,状态,分为四个阶段，五个状态,S1=A, S2=B1,B2,B3,S3=C1,C2,C3 S4=E1, E2, E3,S5=F.,S1,S2,S3,

10、S4,S5,3、决策：(从一个阶段的状态到下一个阶段状态 的选择),描述决策的变量，称为决策变量。决策变量是状态变量的函数用xk(sk)表示。 在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合, 用 表示 。,S3,可以在各个阶段进行决策，去控制过程发展的多阶段过程；其发展是通过一系列的状态转移来实现的。,4、多阶段决策过程,5. 状态转移方程：是确定过程由一个状态到另一个状态的演变过程，描述了状态转移规律。,图示如下：,其状态转移方程如下（一般形式）,能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。,动态规划中能 处理的状态

11、转移 方程的形式。,状态具有无后效性的多阶段决策过程的状态转移方程如下,无后效性(马尔可夫性),如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态和决策（历史）的影响；,状态转移方程是确定过程由一个状态到另一个状态的演变过程。如果已知第k阶段状态变量sk的值、该阶段的决策变量一经确定，第k+1阶段状态变量sk+1的值也就确定。,6.策略：从初始阶段到最终阶段，每一阶段的决策所形成的序列,子策略：从k阶段到最终阶段n，每一阶段的决策所形成的序列,最优子策略：最优效果的子策略，记为,7. 指标函数:分为阶段指标函数和过程指标函数。阶段指标函数是指第k阶段，从状态sk出发，采用决策xk时的效益值，用rk(sk,xk)表示。过程指标函数是指过程所包含的各阶段的状态和决策所产生的总的效益值.记为 Rk,nRk,n(sk,xk,sk+1,xk+1,sn,xn),最优指标函数：对应于从状态 sk 出发的最优子策略,的效益。记为,k,n,即从k到最终阶段n过程指标函数的最优值。,Bellman(1951提出)最优性原理,“作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，余下的决策必然形成最优子策略”,即若某一全过程最优策略为,则对上述策略中所隐含的任意状态