远程运筹学5动态.ppt

主要内容:5.1多阶段决策过程的最优化 5.2 动态规划的基本概念和基本原理5.3 动态规划方法的基本步骤 5.4 动态规划应用举例,5.1多阶段决策过程的最优化,动态规划是解决多阶段最优决策的方法,由美国数学家贝尔曼(R.Bellman)于 1951年首先提出;1957年贝尔曼发表动态规划方面的第一部专著“动态规划”,标志着运筹学的一 个新分支的创立。,例 5.1 求解最短路问题,动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题,采用顺序求解方法,通过解一系列小问题达到求解整个问题目的;动态规划的各个决策阶段不但要考虑本阶段的决策目标,还要兼顾整个决策过程的整体目标,从而实现整体最优决策.,动态规划的分类:,离散确定型离散随机型连续确定型连续随机型,动态规划的特点:,动态规划没有准确的数学表达式和定义精确的算法,它强调具体问题具体分析,依赖分析者的经验和技巧。与运筹学其他方法有很好的互补关系,尤其在处理非线性、离散性问题时有其独到的特点。,通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，,仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。,具有无后效性的多阶段决策过程的特点是系统过去的历史，只能通过现阶段的状态去影响系统的未来，当前的状态就是后过程发展的初始条件。,动态规划的应用,动态规划在工程技术,企业管理,军事部门有广泛的应用;可解决资源分配,生产调度,库存管理,路径优化,设备更新,投资规划,排序问题和生产过程的最优控制等问题;,拾火柴游戏:桌子上放30根火柴,每人一次可拾起13根,谁拾起最后一根火柴谁输,如果你先选择,如何保证你能赢得游戏？2925211713951,动态规划与倒推求解:,使用动态规划方法求解决策问题首先要将问题改造成符合动态规划求解要求的形式,要涉及以下概念:(1)阶段(2)状态(3)决策与策略(4)状态转移(5)指标函数,5.2 动态规划的基本概念和基本思想,一、基本概念,(1)划分阶段 把一个复杂决策问题按时间或空间特征分解为若干(n)个相互联系的阶段(stage),以便按顺序求解;阶段变量描述当前所处的阶段位置，一般用下标 k 表示;,每阶段有若干状态(state),表示某一阶段决策面临的条件或所处位置及运动特征的量,称为状态。反映状态变化的量叫作状态变量。k 阶段的状态特征可用状态变量 sk 或 xk描述;状态有起始、中间、最终状态之分，每一阶段的全部状态构成该阶段的状态集合Sk，并有skSk或xkSk。每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段的初始状态记作sk，终止状态记为sk+1,(2)确定状态,(3)决策、决策变量,所谓决策就是确定系统过程发展的方案，决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。,用以描述决策变化的量称之决策变量，和状态变量一样，决策变量可以用一个数，一组数或一向量来描述也可以是状态变量的函数，记以，表示于 k 阶段状态 sk 时的决策变量,决策变量的取值往往也有一定的容许范围，称之允许决策集合决策变量 uk(sk)的允许决策集用 UK(SK)表示，uk(sk)UK(SK),允许决策集合实际是决策的约束条件。,(4)策略和允许策略集合,策略(Policy)也叫决策序列策略有全过程策略和 k 部子策略之分，全过程策略是指具有n 个阶段的全部过程，由依次进行的 n 个阶段决策构成的决策序列，简称策略，表示为。从 k 阶段到第 n 阶段，依次进行的阶段决策构成的决策序列称为 k 部子策略,表示为，显然当 k=1时的 k 部子策略就是全过程策略。,(5)状态转移方程,状态转移确定从一个状态到另一个状态的转移过程,由状态转移方程描述:sk+1=T(sk,uk);状态转移方程在大多数情况下可以由数学公式表达,如:sk+1=sk+uk；,(6)指标函数,用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。,用gk(sk,uk)表示第 k 段处于状态 sk且所作决策为 uk 时的指标，则它就是第 k 段指标函数，简记为gk。,用RK(sk,uk)表示第k子过程的指标函数。表示处于第 k 段 sk 状态且所作决策为uk时，从 sk 点到终点的距离。由此可见，RK(sk,uk)不仅跟当前状态 sk 有关，还跟,（2）过程指标函数（也称目标函数）,（1）阶段指标函数（也称阶段效应）,还跟该子过程策略 pk(sk)有关,严格说来，应表示为 Rk(sk,pk(sk)。它是由各阶段的阶段指标函数 gk(sk,uk)累积形成的，对于 k 部子过程的指标函数可以表示为：,式中，表示某种运算，可以是加、减、乘、除、开方等,多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即:,有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，,(7)最优解,用 fk(sk)表示第 k 子过程指标函数Rk(sk,pk(sk)在状态 sk 下的最优值，即:,称 fk(sk)为第 k 子过程上的最优指标函数；与它相应的子策略 pk(sk)称为状态 sk 下的最优子策略，记为 pk*(sk),例 5.2 用动态规划求解最短路问题,最短路的求解:阶段:可分为5个阶段,k=1,.,5。状态:可用城市编号,S1=1,S2=2,3,4,S3=5,6,7,S4=8,9,S5=10 决策:决策变量也可用城市编号;状态转移方程:sk+1=uk;损益递推函数:,k=4f4(8)=10,f4(9)=14 k=3f3(5)=min6+f4(8)=16*,8+f4(9)=22=16 f3(6)=min5+f4(8)=15*,9+f4(9)=23=15 f3(7)=min8+f4(8)=18,3+f4(9)=17*=17 k=2 f2(2)=min6+f3(5),8+f3(6),11+f3(7)=min22*,23,28=22,f2(3)=min6+f3(5),8+f3(6),7+f3(7)=min22*,23,24=22 f2(4)=min5+f3(5),7+f3(6),8+f3(7)=min21*,22,25=21 k=1 f1(1)=min5+f2(2),9+f2(3),7+f2(4)=min27*,31,28=27 最短路是：1 2 5 8 10,计算效率分析:对有 7 个阶段,每个阶段有 5 种状态的最短路径问题,用穷举法计算要进行 56=15625 次加法和 3124 次比较,而动态规划只需105次加法和 84 次比较,计算效率分别提高近150和40倍.,动态规划的无后效性原则,对任何阶段 k,有sk+1=T(sk,uk),sk+1仅取决于当前状态sk和当前决策uk,与 k 阶段前的状态和决策无关,也即,k 阶段以后的发展不受该阶段以前状态的影响,过去的历史只能通过当前状态来影响今后的发展。,整个过程的最优策略应具有这样的性质:无论过去的状态和决策如何,对前面的决策所形成的状态而言,后续的诸决策必须构成最优策略；上一条成立的条件是损益递推函数严格单调。,二、动态规划的最优性原理,在例5.1中，用标号法求解最短路线的计算公式可以概括写成：,其中，gk 在这里表示从状态 sk 到由决策 uk 所决定的状态 sk+1 之间的距离。f5(s5)=0 是边界条件，表示全过程到第四阶段终点结束。,一般地，对于 n 个阶段的决策过程，假设只考虑指标函数是“和”与“积”的形式，第 k 阶段和第 k+1 阶段间的递推公式可表示如下：,当过程指标函数为下列“和”的形式时,相应的函数基本方程为:,当过程指标函数为下列“积”的形式时,相应的函数基本方程为:,5.3 动态规划方法的基本步骤,1.将问题按时间或空间划分为满足递推关系的若干阶段,对非时序问题可人为地引入“时段”概念;2.正确选择状态变量 sk,满足:可知性:正确描述动态过程演变,可直接或间接确定状态变量的值;无后效性:后面的决策与前面的决策无关;,3.确定决策变量uk(或xk)以及允许决策集合Dk;4.写出状态转移方程 sk+1=T(sk,dk);5.决策变量的取值范围 6.写出损益函数的递推关系,应满足:a)是定义在所有阶段上的数量函数；b)具有可分离性，并满足递推关系；c)损益函数应严格单调。,例5.3 有某种机床，可以在高低两种不同的负荷下进行生产，在高负荷下生产时，产品的年产量为 g，与年初投入生产的机床数量 u1 的关系为 g=g(u1)=8u1，这时，年终机床完好台数将为，au1(a为机床完好率，0 a 1，设 a=0.7)。在低负荷下生产时，产品的年产量为 h，和投入生产的机床数量的关系为 h=h(u2)=5u2，相应的机床完好率为 b(0b2，设 b=0.9)，一般情况下(a b)。,假设某厂开始有 x1=1000 台完好的机床，现要制定一个五年生产计划，问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量，以使在5年内产品的总产量为最高。,解：首先构造这个问题的动态规划模型。,1分阶段：设阶段变量 k 表示年度，因此，阶段总数 n=5。,2.状态变量：用 sk 表示第 k 年度初拥有的完好机床台数，同时也是第 k-1 年度末时的完好机床数量。,3.决策变量：用 uk 表示第 k 年度中分配于高负荷下生产的机床台数。于是 sk-uk 便为该年度中分配于低负荷下生产的机床台数。,4状态转移方程为：,决策变量的取值：在第 k 段为,6条件最优目标函数递推方程,令 fk(sk)表示由第 k 年的状态 sk 出发，采取最优分配方案到第5年度结束这段时间的产品产量，根据最优化原理有以下递推关系:,下面采用逆序递推计算法,从第5年度开始递推计算,K=5 时有,显然，当 u5*=s5 时，f5(s5)有最大值，相应的有 f5(s5)=8s5。,K=4 时有：,因此，当 u4*=s4 时，有最大值 f4(s4)=13.6s4,K=3 时有：,可见，当 u3*=s3 时，有最大值 f3(s3)=17.55s3。,K=2 时有：,此时，当 u2*=0 时有最大值，即 f2(s2)=20.8s2,其中 s2=0.7u1+0.9(s1-u1),K=1 时有：,当 u1*=0 时,有最大值，即 f1(s1)=23.7s1,因为 s1=1000,故 f1(s1)=23700 个产品。,按照上述计算顺序寻踪得到下述计算结果：,上面所讨论的最优决策过程是所谓始端状态固定，终端状态自由如果终端也附加上一定的约束条件，那么计算结果将会与之有所差别例如，若规定在第五个年度结束时，完好的机床数量为500台(上面只有278台)，问应该如何安排五年的生产，使之在满足这一终端要求的情况下产量最高？,解：由状态转移方程,有,由此式得,当 k=5 时有,当 k=4 时有,显然，只有取 u4*=0,有最大值 f4(s4)=21.4s4-7500,当 k=3 时有:,显然，只有取 u3*=0,f3(s3)有最大值 f3(s3)=24.5s3-7500。,当 k=2 时有:,显然，只有取 u2*=0,f2(s2)有最大值 f2(s2)=27.1s2-7500。,当 k=1 时有:,显然，只有取 u1*=0,f1(s1)有最大值 f1(s1)=29.4s1-7500。,例5.4 某公司拥有资金 10 万元，若投资于项目 i(i1，2，3)的投资额为 xi 时，其收益分别为 g1(x1)=4x1,g2(x2)=9x2,g3(x3)=2x32,问应如何分配投资数额才能使总收益最大?,这是一个与时间无明显关系的静态最优化问题，可列出其静态模型为：,求 x1,x2,x3 的值使,满足,我们可以人为地赋予它“时段”的概念，用动态规划方法求解,解：（解法1）首先用逆序构造动态规划模型。,1分阶段：设阶段变量 k 表示依次对第 k 个项目投资，因此，阶段总数 n=3。(k=1,2,3),2.状态变量：用 sk 表示已经对第 1 至 第 k-1 个项目投资后的剩余资金；即第 k 段初拥有的可以分配给第 k 到第3个项目的资金额（单位：万元）。,3.决策变量：用 xk 表示对第 k 个项目投资 的资金数量（单位：万元）。,决策变量的取值：0 xk sk,4状态转移方程为：,6.基本方程为：,最优指标函数 fk(sk)表示第 k 阶段，初始状态为 sk 时，从第 k 到第 3 个项目所获最大收益,当 k=3 时：,当 k=2 时：,极大值只可能在 0，s2 端点取得，,当 k=1 时：,矛盾，所以舍去 sk 9/2,故 极大值只能在 0，10 的端点取得，比较0，10两个端点的函数值,即全部资金投于第3个项目,(解法2)用顺序解法,1.阶段划分:（同上）和决策变量,2.状态变量:用 sk 表示可用于第1到第 k-1个项目投资的金额，即对第 k 个项目到第3个项目投资后的剩余资金数量。,3.决策变量:（同上）,4.状态转移方程:,5.决策变量的取值范围：,6.最优指标函数：,令 fk(sk+1)表示第 k 段投资额 sk+1 为时，第1到第 k 项目所获的最大收益，此时顺序解法的基本方程为：,当 k=1 时，有,当 k=2 时，有,当 k3 时，有,x3=9/4 为极小点。,极大值应在0，s4 0，10 端点取得,再由状态转移方程逆推：,动态规划的优点,可以解决线性,非线性,整数规划无法有效求解的复杂问题;容易找到全局最优解;可以得到一组解;,动态规划的缺点,没有标准的模型可供应用,构模依赖于个人的经验和技巧;状态变量需满足无后效性,有较大的局限性;动态规划的维数灾难限制了对规模较大问题的求解效率;,6.3 动态规划应用举例,1.资源配置问题2.生产与库存问题3.复合系统工作可靠性问题4.二维背包问题5.设备更新问题6.货郎担问题,1.资源配置问题,如何将有限的资源分配给若干种生产活动，并使资源利用的收益最大是经济活动中常见的问题，动态规划可以求解一些线性规划无法解决的资源配置问题。,一般的资源分配问题可以描述为如下的规划问题：max:z=g1(x1)+g2(x2)+.+gn(xn)x1+x2+.+xn=axi 0 i=1,.,n,例:某工厂有4台设备要投到三种生产线上，投到不同生产线的预期收入的函数关系如下：g1(x1)=7x1+2(x10);g1(x1)=0(x1=0)g2(x2)=3x2+7(x20);g2(x2)=0(x2=0)g3(x3)=4x3+5(x30);g3(x3)=0(x3=0)设备如何分配可使工厂的收益最大？,分析：1.阶段与生产线相联系,阶段 k 只考虑分配到生产线 k 的设备台数;2.状态变量 sk 表示 k 生产线可分配的设备数;3.决策变量 xk 表示决定在 k 生产线上使用的设备数;4.状态转移方程:sk+1=sk-xk;5.损益函数:fk(sk)=max gk(xk)+fk+1(sk+1),s3 f3(s3)x3*0 f3(0)=maxx3=0 0=0 01 f3(1)=maxx31 4x3+5=9 12 f3(2)=maxx32 4x3+5=13 23 f3(3)=maxx33 4x3+5=17 34 f3(4)=maxx34 4x3+5=21 4,求解：k=3:g3(x3)=4x3+5,k=2:g2(x2)=3x2+7 s3=s2-x2,k=1:g1(x1)=7x1+2 s2=s1-x1,因此得到：x1=2,x2=1,x3=1,离散的时间段内如何安排生产与库存。生产成本为:C(xt)=k+cxt(xt 0)或 C(xt)=0(xt=0),k为开工所需费用,c 是变动成本,xt为 t 期的生产数量;库存成本为：H(yt)=hyt,h为单位库存成本，yt为 t 期期初库存数量。,2.生产与库存问题,例:假定k=250,c=2,h=1,y1=0,T=5,需求数据如下表,如何安排生产才能使总成本最小?,t 1 2 3 4 5需求(dt)220280360140270,分析:阶段可按周期 t 划分,t=1,2,3,4,5每周期期初的库存量为该阶段的状态,状态变量 st 表示 t 周期期初库存；决策变量 xt 表示 t 期的生产数量;状态转移方程为:st+1=st+xt-dt,递推函数:ft(st)=min Ct(xt)+Ht(st)+ft+1(st+1)以库存表示系统状态会大大增加系统状态数量,然而,上述问题的最优决策必须使每一阶段库存或者为零,或者为后续一或几个周期需求之和。,t=5:f5(0)=k+cx5+hs5=250+2270+10=790(x5=270)f5(270)=k+cx5+hs5=0+20+1270=270(x5=0)t=4:f4(0)=min 250+2140+f5(0),250+2410+f5(270)=min 1320*,1340=1320(x4=140)f4(140)=1140+f5(0)=140+790=930(x4=0)f4(410)=1410+f5(270)=410+270=680(x4=0),t=3:f3(0)=min250+2360+f5(0),250+2500+f4(140),250+2770+f4(410)=min 2290,2180*,2470=2180(x3=500)f3(360)=1360+f4(0)=360+1320=1680(x3=0)f3(500)=1500+f4(140)=500+930=1430(x3=0)f3(770)=1770+f4(410)=770+680=1450(x3=0),t=2:f2(0)=min250+2220+f3(0),250+2580+f3(360),250+2720+f3(500),250+2990+f3(770)=min2870*,3090,3120,3680=2870(x2=220)f2(220)=1220+f3(0)=220+2180=2400(x2=0)f2(580)=1580+f3(360)=580+1680=2260(x2=0)f3(720)=1720+f3(500)=720+1430=2150(x2=0),t=1:f1(0)=min250+2280+f2(0),250+2500+f2(220),250+2860+f2(580),250+21000+f2(720)=min3800,3650*,4290,4400=3650(x1=500)最优解为：x1=500,x2=0,x3=500,x4=0,x5=270简单判断方法：只要固定费用大于后面发生的库存费用，就值得一次生产满足一或几个周期的需求。,3.复合系统的工作可靠性问题例:为保证设备可靠运行,一些关键部件往往由多个器件并联运行,如果器件 i 的失效概率为 pi,则 xi 个器件并联工作的可靠性为(1-pixi),假定每个器件的采购费用为 ci,在满足总采购费用不超过预算限制 C 的前提下,使设备可靠性最高的规划问题可以描述为:,该问题为整数非线性规划，可以用动态规划求解，设关键器件数n=3，总费用为120万元。器件的单价与可靠性如下表：,分析：阶段与器件挂钩，第 i 阶段仅考虑器件 i 的采购数量;si 表示 i 阶段可使用的采购费用;xi 表示 i 阶段决定购买 i 器件的数量；状态转移方程:si+1=si-ci xi；递推损益函数:fi(si)=max(1-pixi)fi+1(si+1)。,i=1f1(120)=max1x130.9f2(90),0.99f2(60),0.999f2(30)=max0.90.84*,0.990.4,0.9990=0.756i=2f2(90)=max0.8f3(75),0.96f3(60),0.992f3(45),0.9984f3(30)=max0.80.875,0.960.875*,0.9920.75,0.99840.5=0.84,f2(60)=max 0.8f3(45),0.96f3(30)=max 0.80.75*,0.960.5=0.6f2(30)=max 0.8f3(15),0f3(30)=0 f3(75)=0.875,f3(60)=0.875,f3(45)=0.75,f3(30)=0.5,因此,最优解为:x1=1,x2=2,x3=3,4 二维背包问题,当背包问题中有两个限制条件时(如重量和体积限制),所形成的问题为 二维背包问题,问题的一般形式为:max z=i ci xi s.t.i ai xi b xi 0 且为整数,例:卡车的最大运货重量为 12 吨,容积为 10 立方米,现有A,B 两种货物,重量分别为 3 吨和 4 吨,体积分别为 1 和 5 立方米,运费分别为 2 和 3 元,如何装载使所得运费最大。由资源条件可知最多可装载 4 件 A 或 2 件 B。,分析:阶段可按货物种类划分,k=1,2每阶段剩余的载货能力(重量与容积)为该阶段的状态,状态变量 sk=(s1k,s2k);决策变量 xk 表示 k 阶段资源的占用量;状态转移方程:sk+1=sk-akxk,ak=(a1k,a2k)损益函数为:fk(sk)=maxckxk+fk+1(sk+1),k=2f2(12,10)=maxx2=0,1,2f1(12,10),3+f1(8,5),6+f2(4,0)=max 8,3+4,6+0=8k=1f1(12,10)=maxx14 2x1=8f1(8,5)=maxx12 2x1=4f1(4,0)=0,动态规划的维数增加时,求解的复杂程度也会增加。如果状态变量的维数为 m,离散的决策变量有 n 个取值,则在每个阶段需要存储 nm 个数据,这就是所谓的维数灾难。,5 设备更新问题,设备在使用全过程中会遭受磨损,使用一段时间后就要维修,而且使用的时间越长,维修费用越高,设备使用多少时间在经济上最合算,就是设备更新问题。,分析：阶段 k=1,2,3,4,5;sk 表示 k 年初设备已使用的年限;xk 为 k 年初决定设备是继续使用还是更新的决策变量:xk=1表示继续使用,xk=0表示更新;状态转移方程:sk+1=skxk+1;,k=5 状态变量 s5 可取 1,2,3,4f5(1)=maxx1=0,1r(0)-u(0)-c(1),r(1)-u(1)=max 5-0.5-1.5,4.5-1=3.5(x5*=1)f5(2)=max5-0.5-2.2,4-1.5=2.5(x5*=1)f5(3)=max,3.75-2=2(x5*=0)f5(4)=max5-0.5-3,3-2.5=1.5(x5*=0),k=4状态变量 s4 可取 1,2,3 f4(1)=maxr(0)-u(0)-c(1)+f5(1),r(1)-u(1)+f5(2)=max 5-0.5-1.5+3.5,4.5-1+2.5=6.5(x4*=0)f4(2)=max 5-0.5-2.2+3.5,4-1.5+2=5.8(x4*=0)f4(3)=max 5-0.5-2.5+3.5,3.75-2+1.5=5.5(x4*=0),k=3状态变量 s3 可取 1,2,f3(1)=maxr(0)-u(0)-c(1)+f4(1),r(1)-u(1)+f4(2)=max 5-0.5-1.5+6.5,4.5-1+5.8=9.5(x3*=0)f3(2)=max 5-0.5-2.2+6.5,4-1.5+5.5=8.8(x3*=0),k=2状态变量 s2 可取 1,f2(1)=maxr(0)-u(0)-c(1)+f3(1),r(1)-u(1)+f3(2)=max 5-0.5-1.5+9.5,4.5-1+8.8=12.5(x2*=0)k=1时状态变量 s1 只能取 0 f1(0)=maxr(0)-u(0)-c(0)+f2(1),r(0)-u(0)+f2(1)=max5-0.5-0.5+12.5,5-0.5+12.5=17(x1*=1),最优策略为:k=12345 不更新 更新 更新 更新 不更新,一货郎从某城市出发要经过 n 个城市,每个城市都要经过且只能经过一次,最后还要回到原先出发的城市,问应如何选择旅行路线可使总行程最短。,6 货郎担问题,分析:与最短路径问题不同,由于后面所走的路径与前面所经过的城市相关,状态变量不容易满足无后效性原则;阶段数与要旅行的城市数相关;可以将货郎担问题转化为一个最短路问题,但存在维数灾难。,1,2,3,4,3,4,2,4,2,3,1,4,3,4,2,3,2,6,7,9,9,7,8,8,5,5,8,5,7,5,9,8,6,5,6,8,5,8,14,10,13,13,14,16,17,21,19,23,如果要旅行的城市个数为 n,则最短路等价问题中某一阶段出现的最多节点数是(n-1)!上例中的 n=4,则每阶段最多会有:(4-1)!=3*2*1=6如果有10个城市,会有362880个节点。教科书上介绍的方法与上述方法等价。,