第八章动态规划ppt课件.ppt

第八章 动态规划,第一节 动态规划原理和模型第二节 一维动态规划求解方法第三节 动态规划在经济和管理中的应用,第一节 动态规划原理和模型,一、引例与动态规划的基本概念二、动态规划的原理三、动态规划模型的建立,动态规划是50年初由美国数学家R.Bellman等人提出的解决多阶段决策过程优化问题的“最优化原理”基础上建立起来的。动态规划是将一个较复杂的多阶段决策问题分解为若干相互关联的较容易求解的子决策问题，而每一个子决策问题都有多种选择，并且当一个子决策问题确定以后，将影响另一个子决策问题，从而影响到整个问题的决策。,一、动态规划的基本概念,动态规划模型分为（1）离散模型；（2）连续模型。本章只讨论与离散模型有关原理和方法。这对连续模型也适用。下面通过一个多阶段决策过程的例子引入动态规划的基本概念、原理和方法。,例8.1（最短路问题）某运输公司拟将一批货物从A地运往E地，其间的交通系统网络如图8-1所示。图上节点表示地点，边表示两地之间的道路，边上的数字表示两地间的运输费用，求运输费用最低的运输路线。,相关的概念:,A,B1,B2,B3,C1,C2,C3,D1,D2,E,第2阶段,第3阶段,第4阶段,第1阶段,5,4,12,3,3,11,3,6,4,4,4,1,6,5,7,9,8,(1) 阶段 将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，按次序去求每阶段的解，用字母k表示阶段变量。,A,B1,B2,B3,C1,C2,C3,D1,D2,E,第2阶段,第3阶段,第4阶段,第1阶段的状态,第2阶段的状态,第1阶段,5,4,12,3,3,11,3,6,4,4,4,1,6,5,7,9,s1状态A ，s2?,S1=A，S2=B1、B2、B3，S3=C1、C2、C3，S4=D1、D2。,8,(2)状态 状态就是阶段的起始位置。通常一个阶段包含若干个状态。第k阶段的状态就是该阶段所有始点的集合。描述各阶段状态的变量称为状态变量。常用sk表示第k阶段的状态变量。状态变量的取值集合称为状态集合，用Sk表示。,3）决策决策是某阶段状态给定之后，从该状态演变到下一阶段某一状态的选择。表示决策的变量称为决策变量，用uk(sk)表示第阶段，状态为sk时的决策变量，它是状态变量的函数。实际问题中，决策变量的选取往往受到某些条件的影响而限制于某一范围，此范围称为允许决策集合。,A,B1,B2,B3,C1,C2,C3,D1,D2,E,第2阶段,第3阶段,第4阶段,第1阶段的状态,第2阶段的状态,第1阶段,5,4,12,3,3,11,3,6,4,4,4,1,6,5,7,9,在例8.1中，u2(B1)就表示第2阶段状态为B1时的决策变量（它或等于C1或等于C3），即，从第2阶段的状态B1出发，可到达下一阶段的C1或者C3，所以这一阶段的允许决策集D2(B1)=C1,C3。,8,4）策略各阶段决策确定后，组成的一个有序的决策序列就构成了一个策略。 称为全过程的一个策略，简称策略。 称为由第k阶段开始到最后阶段止的一个子策略，简称后部子策略。 使整个问题到达最优效果的策略称为最优策略。 动态规划方法就是要从允许策略集中找出最优策略。,A,B1,B2,B3,C1,C2,C3,D1,D2,E,第2阶段,第3阶段,第4阶段,第1阶段的状态,第2阶段的状态,第1阶段,5,4,12,3,3,11,3,6,4,4,4,1,6,5,7,9,A,EA,B2,C3,D2,E就是一个策略。,8,B2,EB2,C3,D2,E就是一个子策略。,A,B1,B2,B3,C1,C2,C3,D1,D2,E,第2阶段,第3阶段,第4阶段,第1阶段的状态,第2阶段的状态,第1阶段,5,4,12,3,3,11,3,6,4,4,4,1,6,5,7,9,状态转移方程为 sk+1=uk(sk),8,5）状态转移方程 它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程，用sk+1=Tk(sk,uk)表示。该方程描述了由第k阶段到第k+1阶段的状态转移规律。因此又称其为状态转移函数。,指标函数是用来衡量多阶段决策过程优劣的一种数量指标。 一个n 阶段决策过程，从1到n 称为问题的原过程，对于任意一个给定的k（1kn），从第k 阶段到第n 阶段的过程称为原过程的一个后部子过程。 用 V1,n(s1,p1,n)表示初始状态为s1 采用策略p1,n 时，原过程的指标函数值。 Vk,n(sk,pk,n)表示在第k 阶段，状态为sk采用策略pk,n 时，后部子过程的指标函数值。 从第k 阶段状态 sk采用最优策略 p*k,n 到过程终止时的最佳效益值，称为最优指标函数。记为fk(sk)。,6）指标函数,A,B1,B2,B3,C1,C2,C3,D1,D2,E,第2阶段,第3阶段,第4阶段,第1阶段的状态,第2阶段的状态,第1阶段,5,4,12,3,3,11,3,6,4,4,4,1,6,5,7,9,V2,4(B1)：表示在第2阶段，状态为B1时，从B1到E的距离。f2(B1)则表示从B1到E的最短距离。,8,二、动态规划的原理,在例8.1中，整个运输路程分为四个阶段，见图8.2。下面给出求解的全过程。这里我们采用倒推的方法，即从终点（E）到起点（A）。,1第4阶段，即从E到D，从E出发倒推到下一站D，它可通过D1，也可通过D2，所需费用分别为5和3。如果现处于状态D1，到终点E的最佳路线费用：f4(D1)=5，最优策略：u4(D1)=E。如果现处于状态D2，到终点E的最佳路线费用：f4(D2)=3，最优策略：u4(D2)=E。,第3阶段，当从E到达D后，有两个状态D1和D2； 若处于状态D1，则可到达C1或C2，则费用分别为9或7。 若处于状态D2，则可到达C1或C2或C3，费用分别为8或12或5。从E经D1到达C1或C2 的费用，应加上E到达D1这段的费用，所以费用分别为5+9=14、5+7=12；从E经D2到达C2或C2或C3 的费用，应加上E到达D2这段的费用，所以费用分别为3+8=11、3+12=15、3+5=8。,如果现在处于C1，则到达终点E的最小费用为：最小费用路线为 相应的最优决策u3(C1)=D2。如果现在处于C2，则到达终点E的最小费用为：最小费用路线为 。相应的最优决策:,如果现在处于C3，到达终点E的最小费用为：最小费用路线为 相应的最优决策,3第2阶段，同上。如果现处于B1，到达终点E的最小费用为：最小费用路线为 相应的最优决策如果现处于B2，则到达终点E的最小费用为：最小费用路线为 相应的最优决策如果现处于B3，则到达终点E的最小费用为：最小费用路线为 相应的最优决策,4在第1阶段A处，则到达终点E的最小费用为：最小费用路线为： 相应的最优决策：所以，整个问题的最小费用路线为：最优策略为： ， ， ， 。,在每一阶段的求解，都利用了第k阶段和第k+1 阶段的如下关系：,这种关系称为动态规划的基本方程。,所谓最优化原理是：一个过程的最优决策具有这样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。,三、动态规划模型的建立,用动态规划解决实际问题，就要建立动态规划模型，为此需要解决如下问题：1. 划分阶段2. 确定状态变量和决策变量以及相应的取值范围3. 建立状态转移方程4. 确定指标函数，建立动态规划的基本方程5. 确定边界条件,1. 划分阶段 按照时间、空间、变量划分为若干阶段。 建立动态规划模型要求每个阶段问题具有同一模式。2. 确定状态变量和决策变量以及相应的取值范围 决策过程可用状态演变描述。状态必须包含表示系统情况和确定决策所需要的全部信息，反映过程的演变特征。无后效性。找出状态变量在各阶段的取值范围。决策变量由系统最优化的目的所决定。3. 建立状态转移方程 根据状态变量和决策变量的含义，写出状态转移方程。4. 确定指标函数，建立动态规划的基本方程 选取指标函数，根据指标函数建立最优指标函数递推关系,即基本方程5. 确定边界条件,例8.2. 有一工厂研制甲、乙、丙三种新产品，估计这三种新产品研制成功的概率分别为：0.6、0.4、0.3。由于工厂急于推出新产品，决定再加拨2万元研制费，以提高新产品研制成功的概率。据估计，把增加的研制费用于各种新产品研制时，研制成功的概率见下表。现把这批研制费分配给各新产品（不分配、分配给1万元或分配给2万元），使这三种新产品都研制成功的概率最大。应怎样分配。,划分阶段 把对某一种新产品增加研制费用作为一个阶段，将整个过程分为三个阶段。对甲产品增加研制费用记为第1阶段、对乙产品增加研制费用记为第2阶段、对丙产品增加研制费用记为第3阶段。K=1,2,3。状态变量 把有可能提供的研制费用作为状态变量，记为sk，它的取值范围是：0、1、2 决策变量 把给第k种新产品的研制费用的数量作为决策变量 uk，它由决策者决定，不能超过当时拥有的金额 sk建立状态转移方程 sk+1=sk-uk 确定指标函数 确定边界条件 由于开始时可用的金额为2万元，而最后将全部用完，所以 s1=2， s4=0,第二节 一维动态规划求解方法,一、逆推法二、顺推法,逆推法是从最后一个阶段开始，逐阶段向前，直至第一阶段，即可求出全过程最优策略和指标函数的最优值。例8.3用逆推法求解例8.2。,一、逆推法,s2=s1-0=2,s3=s2-1=1,最优解0-1-1,从最后一个阶段开始，逐阶段向前，直至第一阶段，即可求出全过程最优策略和指标函数的最优值。,二、顺推法,逆推法是从最后一个阶段开始，逐阶段向前，直至第一阶段，即可求出全过程最优策略和指标函数的最优值。如果过程是可逆的，即对每一状态，都可从状态转移方程 得到 ，则可用顺推法，由第一阶段开始，逐阶段向后，直至最后一个阶段。,下面再用顺推法求解例8.2。,例8.4用顺推法求解例8.2,基本方程为：,第1阶段 ：最优策略是 ：第2阶段：最优策略是：第3阶段：最优策略是：,第2阶段：,最优策略是：,最优策略是：,最优策略是：,第3阶段：,最优策略是：,故，最优策略是：,第三节 动态规划在经济和管理中的应用,一、背包问题二、生产计划问题三、货物存储问题四、设备更新问题五、资源分配问题六、复合系统可靠性问题,一、背包问题,第一阶段：只装第一种物品,允许装入前1种物品的总重量s2,允许装入前2种物品的总重量s3,第二阶段：只装第二种物品,该段可装入x1w1,该段可装入x2w2,s2=s3-x1w1,价值：p1(x1)+p2(x2)+,一位旅行者携带背包旅游，已知他的背包所能承受的重量为w千克，现有n种物品可供他选择装入包中，第i种物品的单件重量为wi 千克，其价值是携带数量 xi 的函数 pi (xi )。问旅行者应如何选择携带物品的件数，使总价值最大？,划分阶段 将可装入物品按1,2,n 排序，每段装一种物品，共划分为n个阶段，k=1,2,n. 状态变量 在第k阶段开始时，背包中允许装入前k种物品的总重量，记为sk+1决策变量 装入第k 种物品的件数，记为xk建立状态转移方程 sk=sk+1-wkxk允许决策集合 确定指标函数 fk(sk+1)表示在背包中允许装入物品的总重量不超过sk+1千克，并采用最优策略只装前k种物品时的最大使用价值。 确定边界条件 背包所能承受的重量为w千克,例8.5：有一最大载重量为5吨的船，将装载3种货物，每种货物的单件重量和单件价值见表，怎样装载才能使装载的总价值最大？,设第k 种货物装载的件数为xk (k=1,2,3)，划分为3个阶段，每一阶段装一种物品。Sk+1表示在第k 阶段开始时，允许装入前k 种物品的总重量。则 sk=sk+1-wkxk,K=1,K=2,K=3,s4=5,X*3=2,所以最优策略是：,第1种货物装载1件，第2种货物不装，第3种货物装载2件。最优价值是,s4=5,二、生产计划问题,已知企业产品的生产费用、存储费用和市场的需求量，在其生产能力和存储能力许可的前提下，怎样制定各个时期的生产计划，既能完成交货任务，又使总支出最小。某中转仓库要按月在月初供应一定数量的某种部件给总装车间，由于生产条件的变化，生产车间在各月份中生产每单位这种部件所需耗费的工时不同，各月份的生产量于当月的月底前，全部要存入仓库以备后用。已知总装车间的各个月份的需求量以及在加工车间生产该部件每单位数量所需工时见表,设仓库容量为H = 9，开始库存量为2，最终库存量为0，要制定一个半年的逐月生产计划，既满足需要和仓库容量的限制，又使生产这种部件的总耗费工时数最少。,第k月,库存量为sk,生产量为uk,库存量为sk+1,需求量为dk,sk+1=sk+uk-dk,当月生产当月入库,sk为第k月需求送出之前，上阶段产品送入之后,划分阶段 按月份划分阶段，每个月为一个阶段，k=1,2,6. 状态变量 第k阶段开始时（即本阶段需求送出之前，上阶段产品送入之后）部件库存量，记为sk决策变量 第k阶段内的部件生产量，记为uk建立状态转移方程 sk+1=sk+uk-dk，最优指标函数 fk(sk)表示在第k阶段开始的库存量为sk时，从第k阶段到最后一阶段生产部件的最小累计工时数。 基本方程 确定边界条件 so=开始库存量2，s7=0，u6=0,K=6,K=5,最优决策为：,最小累计工时数为：,K=4,第4阶段的最优决策为：,最小累计工时数为：,sk+1=sk+uk-dk , so=2，s7=0，u6=0,第6阶段不生产，故u6=0,K=3,u3的允许集合：,K=2,sk+1=sk+uk-dk ,u0,s9,d4=2,d3=3,K=1,sk+1=sk+uk-dk,K=0,故各月最优生产计划为：7，4，9，3，0，4。,sk+1=sk+uk-dk,d1=8, H=9,s0=2,三、货物存储问题,例8.7考虑下面三个月的库存问题，在每月初，公司必须决定在本月内，应生产多少产品。在一个月内生产x 单位的产品，所需成本为，其中，当时，。每月最多生产4个单位，每月的需求是随机的，或为1或为2单位。如果生产的数量大于需求，就出现库存。每个月末检查库存，1个单位的库存费用是1元。因为库存能力有限，每月末的库存量不能超过3单位。但同时要求必须及时满足需求。在第3个月末要把现有的库存以每单位2元的价格售出。在第1月的月初，公司有1单位的库存。如何制定生产策略使三个月内的期望费用最小。,解：划分阶段：将三个月份为三个阶段，每个月为一个阶段状态变量：sk表示第k 个月初的库存数。则s1=1。决策变量：xk表示第k月生产的单位数。显然有状态转移方程：sk+1=sk+ xk - ak，其中ak为一随机需求量或为1或为2。fk ( sk )表示第k个月初的库存是sk 时，第k 个月至第3个月内的最小期望费用。则第3个月的期望费用是：,其中当k=1，2时，有动态规划的基本方程：其中,用逆序法求解得最优策略是 即第一个月生产3个单位，第二、第三个月不生产。最小成本是 元。,四、设备更新问题,现有一台效益函数为r(t)的设备，其维修费用为u(t)、更新费用为c(t)，需要在n 年内的每年年初做出决策，是继续使用旧设备还是更换一台新设备，使n年总效益最大。设r(t)：在第k年设备已使用过t年，再使用1年时的效益。uk(t)：在第k年设备已使用过t年，再使用1年时的维修费用。ck(t)：在第k年卖掉一台已使用t年的设备，买进一台新设备的更新净费用。a：折扣因子（0a 1），表示一年以后的单位收入价值相当于现年的a单位。,如果年初决定把使用t年的旧设备再继续使用1年，则在这一年内所得回收额为：如果年初决定把使用t年的旧设备卖掉购买一台新设备，则在这一年内所得回收额为：,建立动态规划模型,划分阶段：k（k=1,n）表示计划使用该设备的年限数。状态变量sk：第k年初，设备已使用过的年数。决策变量xk：第 k 年初更新，还是继续使用旧设备，分别用R 和 K 表示。状态转移方程为：动态规划的基本方程为：,五、资源分配问题,设有一原料，总量为a，用于生产n种产品。若分配数量xi 用于生产第i种产品，其产生的效益为ri(xi)。问如何分配，才能使生产n种产品的总收入最大？ 建立动态规划划分阶段：将n 种产品按的序号排列，每种产品为一个阶段，分为n个阶段，k=1, , n。状态变量：sk表示分配给第k个产品至第n 种产品的资源数。决策变量：xk表示分配给第k个产品的资源数。,状态转移方程：sk+1 = sk - xkfk (sk )表示在拥有资源sk，分配给第k种产品至第n 种产品所得到的最大总收入。则有动态规划的基本方程：边界条件：因为在第1阶段时的资源为总资源，到第n+1阶段时资源已分配完毕，所以s1=a，sn+1=0，fn+1(sn+1)=0。,六、复合系统可靠性问题,例8.9某厂设计一种电子设备，由三种元件D1，D2，D3组成，已知这三种元件的价格和可靠性如表8-8所示。要求在设计中所使用元件的费用不超过105元，试问应如何设计使设备的可靠性达到最大(不考虑重量的限制)。,表 8-8,解：按元件种类划分为三个阶段，设状态变量sk(k=1,2,3)表示能容许用在Dk元件至D3元件的总费用；决策变量xk表示在Dk元件上的并联个数；Pk表示一个元件正常工作的概率，则 为xk个Dk元件不正常工作的概率，令最优值函数fk (sk)表示由状态sk开始从Dk元件至D3元件组成的系统的最大可靠性，因而有,由于s1=105，故此问题求只要出f1(105)即可.,同理从而求得最优方案： ，即D1元件用1个，D2元件用2个，D3元件用2个，其总费用为100元，可靠性为0.648。,第四节 Lingo软件对几类特殊动态规划问题的实现,略,谢 谢！,