运筹学概论第6章动态规划.ppt

第6章 动态规划,多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划模型的建立,第一节 多阶段决策过程的最优化,美国数学家贝尔曼(R. Bellman ) 1943年在威斯康星大学获理学硕士学位，1946年在普林斯顿大学获博士学位。19461948年在普林斯顿大学任助理教授,19481952年在斯坦福大学任副教授,19531956年在美国兰德公司任研究员，1956年后在南加利福尼亚大学任数学教授、电气工程教授和医学教授。1957年发表“Dynamic Programming”一书，标志动态规划的正式诞生。,动态规划是解决复杂系统优化问题的一种方法。可用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的最优控制等，是解决动态系统多阶段决策过程的基本方法之一。 动态规划模型的分类：离散确定型；离散随机型；连续确定型；连续随机型。其中离散确定型是最基本的。,例1 最优路径问题离散确定型 给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）,例2 生产与存贮问题离散连续型,某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月生产j单位产品费用为：,每月库存j单位产品的费用为 ，该厂最大库存容量为3单位，每月最大生产能力为6单位，计划开始和计划期末库存量都是零。试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第i+1个月的库存量是第i个月可销售量与该月用户需求量之差；而第i个月的可销售量是本月初库存量与产量之和。,例3 限期采购问题离散随机型,某部门欲采购一批原料，原料价格在五周内可能有所变动，已预测得该种原料今后五周内取不同单价的概率如表所示。试确定该部门在五周内购进这批原料的最优策略，使采购价格的期望值最小。,（1）多阶段决策过程，也称序贯决策。在多阶段决策过程中,总可以按照时间（也可人为引入）进程分为状态相互联系而又相互区别的各个阶段； （2）整个活动过程总体效果最优。各时段决策有机联系，上阶段影响下一阶段决策，进而影响总体。每个阶段都要进行决策,但最终要使整个过程的决策达到最优效果。,动态规划问题的特点：,1、系统所处的阶段和状态是进行决策的重要因素； 2、在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策； 3、找到不同时刻的最优决策以及整个过程的最优策略。,动态规划问题的特点：,例4 生产决策问题 企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。 某工厂每月需供应市场一定数量的产品，并将所余产品存入仓库。一般某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用。要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小。 显然，可以把每个月作为一个阶段，全年分为12个阶段逐次决策。,多阶段决策问题的典型例子,例5 投资决策问题 某公司现有资金Q万元，在今后5年内考虑给A，B，C，D 4个项目投资，这些项目投资的回收期限、回报率均不相同，问该公司应如何确定这些项目每年的投资额，使到第5年末拥有资金的本利总额最大。 这是一个5阶段决策问题。,例 6 设备更新问题 企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用。现某企业要决定一台设备未来8年的更新计划，已预测了第j年购买设备的价格为Kj，设Gj为设备经过j年后的残值，Cj为设备连续使用j-1年后在第j年的维修费(j1，2，8)，问应在哪些年更新设备可使总费用最小。 这是一个8阶段决策问题，每年年初要作出决策，是继续使用旧设备，还是购买新设备。,不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。 线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。,说明,第5章 动态规划,多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划模型的建立与求解,第二节 动态规划的基本概念和基本原理,一、动态规划的基本概念 使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，此时要用到以下概念： (1)阶段； (2)状态； (3)决策和策略； (4)状态转移； (5)指标函数。,1. 阶段、阶段变量,把所给问题的过程，适当地分为若干个相互联系的阶段，以便按次序去求每阶段的解 ;,描述阶段的变量称为阶段变量，常用k表示；,阶段的划分，一般是按时间和空间的自然特征（年、月、路段）来划分 ；,例2中，从A到F可以分成从A到B (B有两种选择B1,B2)，从B到C (C有四种选择C1，C2，C3，C4)，从C到D (D有三种选择D1，D2 ,D3)，从D到E (E有两种选择E1，E2)，再从E到F五个阶段。 k1，2，3，4，5。,状态变量的取值有一定的允许集合或范围，此集合称为状态集合，用Sk表示。 sk Sk,2. 状态、状态变量,每个阶段开始所处的自然状态或客观条件。通常一个阶段有若干个状态。,描述过程状态的变量称为状态变量，常用sk（一个数、一组数、一个向量）表示第k阶段的状态。,在例2中，第一阶段状态为A，第二阶段则有二个状态：Bl，B2。状态变量s1的集合 ，后面各段的状态集合分别是：,动态规划中的状态应具有如下性质：当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各段状态的影响。也就是说，当前的状态是过去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性。如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。 例 2中，当某段的初始状态已选定某个点时，从这个点以后的铺管路线只与该点有关，不受以前的铺管路线影响，所以满足状态的无后效性。,在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。常用 Dk(sk) 表示第 k 阶段从状态sk出发的允许决策集合。,决策变量是状态变量的函数。,3. 决策、决策变量,过程的某一阶段、 某个状态, 可以做出不同的决定(选择), 决定下一阶段的状态，这种决定称为决策。,uk(sk) Dk(sk),描述决策的变量，称为决策变量。常用 表示第 k 阶段当状态为sk 时的决策变量。,在例2中，从第二阶段的状态B1出发，可选择下一段的C1，C2，C3，即其允许决策集合为：,我们决定选择C3，则可表为：,由每段的决策按顺序排列组成的决策函数序列称为k子过程策略，简称子策略，记为pk,n(sk)，即,当k=1时，此决策函数序列成为全过程的一个策略，简称策略，记为p1,n (s1),4. 策略,按顺序排列的决策组成的集合；,可供选择的策略有一定范围，此范围称为允许策略集合，用 表示。从允许策略集合中找出达到最优效果的策略称为最优策略。,由第k阶段第 n阶段（终止状态）为止的过程，称为问题的后部子过程（k 子过程）,状态转移方程是确定过程由一个状态到另一个状态的演变过程。如果第k阶段状态变量 sk 的值、该阶段的决策变量一经确定，按照动态规划的无后效性，第k+1阶段状态变量 sk+1的值也就确定了。,5. 状态转移方程,例2中，状态转移方程为：,费用、成本、利润、路长等 。用 Vk, n 表示之。,6. 指标函数和最优值函数,用于衡量所选定策略优劣的数量指标称为指标函数，包括阶段指标函数和过程指标函数；阶段指标函数是指第k阶段，从状态sk出发，采取决策uk时的效益，用d(sk, uk)或用dk(sk, uk)表示。过程指标函数是定义在全过程或所有后部子过程上确定的数量函数。,一个n段决策过程，从l到n叫作问题的原过程，对于任意一个给定的k(1kn)，从第k段到第n段的过程称为原过程的一个后部子过程。,表示在第k段，状态为sk采用策略 ，后部子过程的指标函数值。,表示初始状态为s1采用策略 时原过程的指标函数值。,最优指标函数记为 ，它表示从第 k 段状态 sk 采用最优策略 到过程终止时的最佳效益值。 与 间的关系为：,opt全称optimum，表示最优化，根据具体问题分别表为max或min。 当k1时， 就是从初始状态 s1 到全过程结束的整体最优函数。,在例2中，指标函数是距离。如第2阶段，状态为B1时， 表示从B1到F的距离，而 则表示从B1到F的最短距离。本问题的总目标是求 ，即从A到终点F的最短距离。,二、动态规划的基本思想与基本原理,下面结合例2最短路线问题介绍动态规划的基本思想。,一种简单的方法，可以求出所有从A至F的可能铺设的路长并加以比较。从A至F共有24条不同路径，要求出最短路线需要做23次比较运算，这种方法称穷举法。当问题的段数很多、各段的状态也很多时，穷举法的计算量会大大增加，甚至使得求优成为不可能。 下面介绍动态规划方法。注意本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点F的最短路线，最后求得A点到F点的最短路线。,用 表示由状态sk点出发，采用决策uk到达下一阶段sk+1点时的两点距离。,第一步，从k5开始，状态变量s5可取两种状态E1，E2，它们到F点的路长分别为4，3。 即：,第二步，k4，状态变量s4可取三个值D1，D2，D3，这是经过一个中途点到达终点F的两级决策问题，从D1到F有两条路线，需加以比较，取其中最短的，即：,由D1到终点F最短距离为7，其路径为D1E1F。相应决策为,即D2到终点最短距离为5，其路径为D2E2F。相应决策为,即D3到终点最短距离为5，其路径为D3E1F。相应决策为,类似的，可算得：,k=3时，有,k=2时，有,k=1时，则,所以最优路线为：,即从A到F的最短距离为17。本段决策为,再按计算顺序反推可得最优决策序列 即,这种递推关系称为动态规划的基本方程，(7.3b)式称为边界条件。,从例2的计算过程中可以看出，在求解的各阶段，都利用了第k段和第k+1段的如下关系：,将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题，然后逐个求解。,(2) 求解时从边界条件开始，逆(或顺)过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解,就是整个问题的最优解。,(3)动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。,现将动态规划方法的基本思想总结如下,动态规划的基本方程是递推逐段求解的根据，一般的动态规划基本方程可以表为：,式中opt可根据题意取min或max， 为状态sk、决策uk 时对应的第k阶段的指标函数值。,从上图可以看出，无论从哪一段的某状态出发到终点F的最短路线，只与此状态有关，而与这点以前的状态、路线无关，即不受从A点是如何到达这点的决策影响。而且从A点到F点的最短路线若经过sk点，则此路线由sk点到F点的后半部，应是由sk点到F的最短路线。,Bellman最优化原理：一个过程的最优策略具有这样的性质：即无论初始状态基初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。,第5章 动态规划,多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划模型的建立与求解,第三节 动态规划模型的建立与求解,一、动态规划模型的建立 建立动态规划的模型，就是分析问题并建立问题的动态规划基本方程。 应用动态规划方法的关键在于:识别问题的多阶段特征，将问题分解成为可用递推关系式联系起来的若干子问题，而正确建立基本递推关系方程的关键又在于正确选择状态变量，保证各阶段的状态变量具有递推的状态转移关系。,下面以资源分配问题为例介绍动态规划的建模条件及解法。资源分配问题是动态规划的典型应用之一，资源可以是资金、原材料、设备、劳力等，资源分配就是将一定数量的一种或几种资源恰当地分配给若干使用者，以获取最大效益。,问如何分配投资数额才能使总效益最大?,例7 某公司有资金10万元，若投资于项目i(i=1,2,3)的投资额为xi时，其效益分别为,解：可列出静态规划问题的模型如下,1. 分阶段：分三个阶段，即 k=1，2，3。 将投资项目排序，首先考虑对项目1投资，然后考虑对项目2投资，最后考虑对项目3投资,即把问题划分为3个阶段，每个阶段只决定对一个项目应投资的金额。这样问题转化为一个3段决策过程。,2. 确定决策变量：通常可以取静态规划中的变量为决策变量。 即设,决策变量 ：决定给第k个项目投资的资金数。,3. 确定状态变量：状态变量与决策变量有密切关系，状态变量一般为累计量或随递推过程变化的量。 可以把每阶段可供使用的资金定为状态变量 ，初始状态 。 为分配于第一种项目的资金数，则当第一阶段(k1)时，有,状态转移方程:,状态变量 ：第k段可以投资于第k项到第3个项目的资金数。,指标函数：,最优指标函数： fk(sk) 当可投资金数为 时，投资第k至第3项所得的最大收益数。,基本方程：,阶段k： k=1,2,3 状态变量sk:第k阶段可以投资于第k项到第3个项目的资金。 决策变量xk:决定给第k个项目的资金。 状态转移方程:sk+1=sk-xk 最优指标函数fk(sk):当可投资金为sk,投资第k项到第3个项目所得的最大收益。 基本方程：,建立动态规划模型的要点为：,1分析题意，识别问题的多阶段特性，按时间或空间的先后顺序适当地划分为满足递推关系的若干阶段，对非时序的静态问题要人为地赋予“时段”概念。,2正确地选择状态变量，使其具备两个必要特征： (1)可知性：即过程演变的各阶段状态变量的取值，能直接或间接地确定； (2)能够确切地描述过程的演变且满足无后效性。即由第k阶段的状态 出发的后部子过程，可以看作是一个以 为初始状态的独立过程。,3根据状态变量与决策变量的含义，正确写出状态转移方程 或转移规则。,4根据题意明确指标函数 , 最优指标函数 以及k阶段指标 的含义，并正确列出最优指标函数的递推关系及边界条件(即基本方程)。,二、 动态规划模型的求解,动态规划的求解有两种方法：逆序解法和顺序解法。 逆序解法：寻优的方向与多阶段决策过程的实际行进方向相反，从最后一段开始计算逐段前推，求得全过程的最优策略。 顺序解法：寻优的方向与过程的实际行进方向相同，从第一段开始逐段向后递推，求得全过程的最优策略。,逆序解法,阶段k： k=1,2,3,4,5 状态变量sk:第k阶段开始所处的位置。 决策变量uk:第k阶段从sk出发到的下一个位置。 状态转移方程:sk+1=uk(sk) 最优指标函数fk(sk):当第k阶段处于sk, 一直到F的最短距离。 基本方程：,当 k=5时：,当 k=4时：,当 k=3时：,当 k=2时：,当 k=1时：,例8 有一辆最大货运量为10t的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值见下表，应如何装载可使总价值最大？,逆序解法： 阶段k： k=1,2,3 状态变量sk:第k阶段可以装载第k种到第3种货物的重量。 决策变量xk:决定装载第k种货物的数量。 状态转移方程:sk+1=sk-akxk 最优指标函数fk(sk):当可装载重量为sk,装载第k种到第3种货物所获得的最大价值。 基本方程：,当阶段k=3时，有,当阶段k=2时，