动态规划模型举例

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,6,动态规划模型举例,11/19/2024,1,以上讨论的优化问题大多数属于静态的，即不必考虑时间的变化，建立的模型线性规划、非线性规划、整数规划等，都属于静态规划。多阶段决策属于动态优化问题，即在每个阶段（通常以时间或空间为标志）要根据过程的演变情况确定一个决策，使全过程的某个指标达到最优。,例如：,（1）化工生产过程中包含一系列的过程设备，如反应器、蒸馏塔、吸收器等，前一设备的输出为后一设备的输入。因此，应该如何控制生产过程中各个设备的输入和输出，使总产量最大。,（2）发射一枚导弹去击中运动的目标，由于目标的行动是不断改变的，因此应当如何根据目标运动的情况，不断地决定导弹飞行的方向和速度，使之最快地命中目标。,11/19/2024,2,（3）汽车刚买来时故障少、耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加则变得故障多，油耗高，维修费用增加，经济效益差。使用时间俞长，处理价值也俞低。另外，每次更新都要付出更新费用。因此，应当如何决定它的使用年限，使总的效益最佳。,动态规划模型是解决这类问题的有力工具。下面结合具体例子阐述建立动态规划模型的思路。,例13,最短路问题。图2是一个线路网，连线上的数字表示两点之间的距离（或费用），寻找一条由A到G的路线，使距离最短（或费用最省）。,11/19/2024,3,解：,用穷举法当然可以解决这个问题。不难算出，一共有48条从A到G的路线，用加法得到每条路线的长度后，再作比较即可找出最短路线。显然当路段很多时，计算工作量将是很大的。,A,B,1,B,2,C,1,C,2,C,3,C,4,D,3,D,2,D,1,E,1,E,2,E,3,F,1,F,2,G,5,3,1,3,6,8,7,6,8,4,3,3,5,3,8,6,2,2,1,2,3,3,6,6,2,5,5,3,4,3,图,11/19/2024,4,用动态规划解决问题的思路，来源于生活中这样一个基本常识：如果已经找到由A到G的最短路线是AB,1,C,2,D,1,E,2,F,2,G（图中粗线，记作L），那么当寻求L中的任何一点（如D,1,）到G的最短路时，它必然是L中的子路D,1,E,2,F,2,G（记作L,1,）。因为否则，若D,1,到G的最短路是另一条路线L,2,，则把AB,1,C,2,D,1,与L,2,连接起来，就会得到一条不同于L的从A到G的最短路。根据最短路的这一特性，我们可以从最后一段开始，用逐步向前递推的方法，依次求出路段上各点到G的最短路，最后得到A到G的最短路。,11/19/2024,5,具体实施如下：从A到G要走6个路段，是一个6阶段决策问题，记k=1，2，6。用d,k,（x,k,，x,k+1,）表示第k段的点x,k,与第k+1段的点x,k+1,之间的（已知）距离（视k的不同，x分别代表A，B，F），用u,k,（x,k,）表示在x,k,的决策，即从x,k,向哪一点走，则x,k+1,可以记作x,k+1,=u,k,（x,k,）。设x,k,到终点G的最短距离为f,k,（x,k,），则,k=6时，f (F,1,)=4,f (F,2,)=3,显然u(F,1,)=G,u(F,2,)=G,k=5时，f,5,(E,1,)=min,=min =7,表明E,1,到G的最短路是E,1,F,1,G，即E,1,的最优决策为,u(E1)=,。,11/19/2024,6,表明E,2,到G的最短路是E,2,F,2,G，即E,2,的最优决策为u,5,（E,2,）=F,2,。同法计算出f,5,(E,3,)=9，u,5,（E,3,）=F,2,，,11/19/2024,7,k=3 时，,k=2时,f,2,(B,1,)=13,u,2,(B,1,)=C,2,f,2,(B,2,)=16,u,2,(B,2,)=C,3,k=1时,f,1,(A)=18 ,u,1,(A)=B,1,于是从A到G的最短距离为f,1,(A)=18，而最短路线则由A开始顺次找出最优决策来确定，即u,1,(A)=B,1,，u,2,(B,1,)=C,2,u,3,(C,2,)=D,1,，u,4,(D,1,)=E,2,，u,5,(E,2,)=F,2,，u,6,(F2)=G，最短路线为AB,1,C,2,D,1,E,2,F2G。,11/19/2024,8,不难看出，上述计算过程可以表示为如下的一般形式：,(1),其中D（x）表示在x的允许决策集合，如D,2,（B,1,）=（C,1,，C,2,，C,3,)，X表示第k段的允许状态集合，如X,2,=(B,1,，B,2,）。当按（1）式由k=6逆推至k=1时，就得到了最短距离，而最短路线由顺推的最优决策确定。在动态规划中f（x）称最优值函数，（1）式称最优方程。,11/19/2024,9,需要指出，上例只是最短路问题的一种形式，实际问题中可以有多种形式，如：,1）路线数目不定，如图3，求任一点（如B）到E的最短路线（不论它由几段组成）；,2）有向路网，如图4，求V,1,到V,6,的有向最短路；,3）旅行商问题，如图3，求从A点出发，经每点一次又回到A点的最短路,。,E,D,A,B,C,V,4,V,5,V,6,V,3,V,1,V,2,2,5,3,5,2,6,7,5,1,0.5,2,8,7,2,3,1,1,6,3,10,图图,11/19/2024,10,下面介绍动态规划相关的基本概念及其数学描述,（1）阶段 整个问题的解决可分为若干个相互联系的阶段依次进行。通常按时间或空间划分阶段，描述阶段的变量称为,阶段变量,，记为 。,（2）状态 状态表示每个阶段开始时所处的自然状况或客观条件，它描述了研究过程的状况。各阶段的状态通常用,状态变量,描述。常用 表示第 阶段的状态变量。个阶段的决策过程有 个状态。用动态规划方法解决多阶段决策问题时，要求整个过程具有,无后效性,。即：如果某阶段的状态给定，则此阶段以后过程的发展不受以前状态的影响，未来状态只依赖于当前状态。,11/19/2024,11,（3）决策 某一阶段的状态确定后，可以作出各种选择从而演变到下一阶段某一状态，这种选择手段称为,决策,。描述决策的变量称为,决策变量,。决策变量限制的取值范围称为,允许决策集合,。用 表示第 阶段处于状态 时的决策变量，它是 的函数，用 表示 的允许决策集合。,（4）策略 一个由每个阶段的决策按顺序排列组成的集合称为,策略,。由第 阶段的状态 开始到终止状态的后部子过程的策略记为,在实际问题中，可供选择的策略有一定范围，称为,允许策略集合,。其中达到最优效果的策略称为,最优策略,。,11/19/2024,12,（5）状态转移方程 如果第 个阶段状态变量为 ，作出的决策为 ，那么第 阶段的状态变量 也被完全确定。用状态转移方程表示这种演变规律，写作,（6）最优值函数 指标函数是系统执行某一策略所产生结果的数量表示，是用来衡量策略优劣的数量指标，它定义在全过程和所有后部子过程上。指标函数的最优值称为,最优值函数,。,11/19/2024,13,下面方程在动态规划逆序求解中起着本质的作用。,称此为动态规划逆序求解的基本方程(贝尔曼方程)。,可以把建立动态规划模型归纳成以下几个步骤：,（1）将问题恰当地划分为若干个阶段；,（2）正确选择状态变量，使它既能描述过程的演变，又满足无后效性；,（3）规定决策变量，确定每个阶段的允许决策集合；,（4）写出状态转移方程；,（5）确定各阶段各种决策的阶段指标，列出计算各阶段最优后部策略指标的基本方程。,11/19/2024,14,例14,生产计划问题。公司要对某产品制定n周的生产计划，产品每周的需求量、生产和贮存费用、生产能力的限制、初始库存量等都是已知的，试在满足需求的条件下，确定每周的生产量，使n周的总费用最少。,解：,决策变量是第k周的生产量，记作u,k,（k=1，2，n）。已知下列数据及函数关系：第k周的需求量d,k,：第k周产量为u,k,时的生产费c,k,（u,k,）；第k周初贮存量为x,k,时这一周的贮存费h,k,（x,k,）；第k周的生产能力限制U,k,；初始（k=0）及终结（k=n）时贮存量均为零。按照最短路问题的思路，设从第k周初贮存量为x 到（n周末）过程结,11/19/2024,15,束的最小费用函数为f（x），则下列逆向递推公式成立。,（1）,而x,k,与x,k+1,满足,(2),这里贮存量x是状态变量，（2）式给出了相邻阶段的状态在决策变量作用下的转移规律，称为状态转移规律。在用（1）式计算时，x,k,的取值范围允许状态集合X,k,由（2）式及允许决策集合（0u,k,U,k,）决定。,11/19/2024,16,在实际问题中，为简单起见，生产费用常ck（uk）=0,(u,k,=0)；ck(u,k,)=a+c u,k,(u,k,0)，其中c是单位产品生产费,而a是生产准备费。贮存费用常取h,k,（x,k,）=h x,k,，,h是单位产品（一周的）贮存费。,最优方程（1）和状态转移方程（2）构成了这个多阶段决策问题的动态规划模型。实际上，多阶段决策问题有时也可用静态规划方法求解，如例2的生产计划问题。,例15,资源分配问题。总量为m,1,的资源A和总量为m,2,的资源B同时分配给n个用户，已知第k用户利用数量u,k,的资源A和数量v 的资源B时，产生的效益为g,k,（u,k,v,k,），问,11/19/2024,17,如何分配现有资源使总效益最大。,解,：这本来是个典型的静态规划问题：,Max Z =(1),s.t (2),(3),但是当g,k,比较复杂及n较大时，用非线性规划求解是困难的，特别是，若g,k,是用表格或图形给出而无解析表达式时，则难以求解。而这种情况下，将其转化为,11/19/2024,18,动态规划，是一种可行的方法。,资源A，B每分配给一个用户划分为一个阶段，分配给第k用户的数量是二维决策变量（u,k,v,k,），而把向第k用户分配之前，分配者手中掌握的资源数量作为二维状态变量，记作（x,k,，y,k,），这样，状态转移方程应为,(4),11/19/2024,19,最优值函数f,k,（x,k,，y,k,）定义为将数量x,k,，k,y,的资源分配给第k至第n用户时能获得的最大效益，它满足最优方程,(5),对于由（4），（5）式构成的动态规划模型，不需要g,k,，f,k,的解析表达式，完全可以求数值解。,11/19/2024,20,例16,系统可靠性问题。一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行。为提高系统的可靠性，每个部件都装置备用件，一旦原部件故障，备用件就自动进入系统。显然，备用件越多，系统可靠性越高，但费用也越大，那么在一定的总费用限制下，如何配置各部件的备用件，使系统的可靠性最高呢？,设系统有n个部件，当部件k装置u,k,个备用件时，这个部件正常工作的概率为P,k,（u,k,）。而每个备用件的费用为c,k,，另外设总费用不应超过C。,11/19/2024,21,解：,这个优化问题的目标函数是系统正常运行的概率,它等于n个串联部件正常工作的概率的乘积。约束条件是备用件费用之和不应超过C，决策变量是各部件的备用件数量，于是问题归结为,Max Z =(1),s.t.(2),这个非线性规划转化为动态规划求解比较方便。,11/19/2024,22,按照对n个部件装置备用件的次序划分阶段，决策变量仍为部件k的备用件数量u,k,，而状态变量选取装配部件k之前所容许使用的费用，记作x,k,，于是状态转移方程为,X,k+1,x,k,-c,k,u,k,(3),最优值函数,k,（x,k,）定义为状态x,k,下，由部件到部件组成的子系统的最大正常工作效率，它满足,k,（x,k,）=(4),=u,k,|u,k,0,=1 (5),11/19/2024,23,注意，这个动态规划模型的最优方程（4）中