数学建模案例分析--最优化方法建模6动态规划模型举例

1、数学建模§ 6动态规划模型举例以上讨论的优化问题属于静态的，即不必考虑时间的变化，建立的模型一一线性规划、非线性规划、整数规划等，都属于静态规划。多阶段决策属于动态优化问题，即在每个阶段（通常以 时间或空间为标志）根据过程的演变情况确定一个决策，使全过程的某个指标达到最优。例如：（1）化工生产过程中包含一系列的过程设备，如反应器、蒸馏塔、吸收器等，前一设备的输出为 后一设备的输入。因此，应该如何控制生产过程中各个设备的输入和输出，使总产量最大。（2） 发射一枚导弹去击中运动的目标，由于目标的行动是不断改变的，因此应当如何根据目标运动的情况，不断地决定导弹飞行的方向和速度，使之最快地命

2、中目标。（3）汽车刚买来时故障少、耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加则变得故障多，油耗高，维修费用增加，经济效益差。使用时间俞长，处理价值也俞低。另外，每次更新都要付出更新费用。因此，应当如何决定它每年的使用时间，使总的效益最佳。动态规划模型是解决这类问题的有力工具，下面介绍相关的基本概念及其数学描述。（1） 阶段 整个问题的解决可分为若干个相互联系的阶段依次进行。通常按时间或空间划分阶段， 描述阶段的变量称为 阶段变量，记为k。（2） 状态状态表示每个阶段开始时所处的自然状况或客观条件，它描述了研究过程的状况。各阶段的状态通常用 状态变量描述。常用xk表示第k阶段的

3、状态变量。n个阶段的决策过程有n T 个状态。用动态规划方法解决多阶段决策问题时，要求整个过程具有无后效性。即：如果某阶段的状态给定，则此阶段以后过程的发展不受以前状态的影响，未来状态只依赖于当前状态。（3） 决策 某一阶段的状态确定后， 可以作出各种选择从而演变到下一阶段某一状态，这种选择 手段称为决策。描述决策的变量称为 决策变量。决策变量限制的取值范围称为 允许决策集合。用 Uk （xQ表示第k阶段处于状态Xk时的决策变量，它是 Xk的函数，用Dk（xJ表示Xk的允许决策 集合。（4） 策略 一个由每个阶段的决策按顺序排列组成的集合称为策略。由第k阶段的状态xk开始到终止状态的后部子过程

4、的策略记为Pk（Xk）二Uk（Xk）,Uk ,Xk 1）,，Un（Xn）。在实际问题中，可供选择的策略有一定范围，称为允许策略集合。其中达到最优效果的策略称为最优策略。（5）状态转移方程如果第k个阶段状态变量为Xk，作出的决策为uk，那么第k 1阶段的状态变量Xk i也被完全确定。用状态转移方程表示这种演变规律，写作Xk i =Tk（ Xk，Uk）（6）最优值函数指标函数是系统执行某一策略所产生结果的数量表示，是用来衡量策略优劣的数量指标，它定义在全过程和所有后部子过程上。指标函数的最优值称为最优值函数。下面的方程在动态规划逆序求解中起着本质的作用。fk(Xk)= mD、Vk(Xk,Uk(Xk

5、) + fz(Xk4i)，uk 电Dk (xk )*f“(XnG =0,=Tk(Xk,uQ,k = n,n 1,1称此为动态规划逆序求解的基本方程(贝尔曼方程)。可以把建立动态规划模型归纳成以下几个步骤：(1) 将问题恰当地划分为若干个阶段；(2) 正确选择状态变量，使它既能描述过程的演变，又满足无后效性；(3) 规定决策变量，确定每个阶段的允许决策集合；(4) 写出状态转移方程；(5) 确定各阶段各种决策的阶段指标，列出计算各阶段最优后部策略指标的基本方程。下面结合具体例子阐述建立动态规划模型的思路。例13生产计划问题。公司要对某产品制定n周的生产计划，产品每周的需求量、生产和贮存费用、生产

6、能力的限制、初始库存量等都是已知的，试在满足需求的条件下，确定每周的生产量，使n周的总费用最少。决策变量是第k周的生产量，记作Uk (k =1,2,n)。已知下列数据及函数关系：第k周的需求量dk :第k周产量为Uk时的生产费为Ck(Uk );第k周初贮存量为Xk时这一周的贮存费为 hk(xQ ;第k周的生产能力限制为 Uk ;初始(k = 0)及终结(k = n)时贮存量均为零。按照最短路问题的思路，设从第k周初贮存量为xk到(n周末)过程结束的最小费用函数为 fk(xk)，则下列逆向递推公式成立。fk(Xk) =0卵2 Ck(Uk) +hk(Xk) + fk+(Xk+)Xk 芒 Xk,k=

7、 n,2,1(1)0勺k$kfn +( Xn + ) 0而Xk与Xk 1满足Xk4t =Xk +Uk dk, k = n，2,，X1 = Xn+ = 0这里贮存量Xk是状态变量，(2)式给出了相邻阶段的状态在决策变量作用下的转移规律，称 为状态转移规律。在用(1)式计算时，xk的取值范围一一允许状态集合 Xk由(2)式及允许决策集合(0 uk <Uk )决定。在实际问题中，为简单起见，生产费用常取ck(uk )，uk = 0 ； ck(uk)=a，cuk，uk 0，其中c是单位产品生产费，而 a是生产准备费。贮存费用常取hk(xk)二hxk，h是单位产品(一周的)贮存费。最优方程(1)和

8、状态转移方程(2 )构成了这个多阶段决策问题的动态规划模型。实际上，多阶段决策问题有时也可用静态规划方法求解，如例2的生产计划问题。例14 资源分配问题。总量为mi的资源A和总量为m2的资源B同时分配给n个用户，已知第k用 户利用数量uk的资源A和数量Vk的资源B时，产生的效益为 gk (uk ,Vk)，问如何分配现有资源使 总效益最大。这本来是个典型的静态规划问题：nMax L=為 gk(Uk,Vk)(1)k 4ns.t. ' uk = m1,uk 丄0(2)k 4n' Vk 二 m)2,Vk -0(3)k吕但是当gk比较复杂及n较大时，用非线性规划求解是困难的，特别是，若g

9、k是用表格或图形给出而无解析表达式时，则难以求解。而这种情况下，将其转化为动态规划，是一种可行的方法。资源A，B每分配给一个用户划分为一个阶段，分配给第k用户的数量是二维决策变量(Uk,Vk)，而把向第k用户分配之前，分配者手中掌握的资源数量作为二维状态变量，记作(xk,yk)，这样，状态转移方程应为m =Xk _Uk/、丿(4)jk+ =yVk最优值函数fk (Xk, yk)定义为将数量(Xk, yk)的资源分配给第 k至第n用户时能获得的最大效益，它满足最优方程fk(Xk, yk) =0maXkgk(Uk,Vk) fk 1(Xk 1, yk 1), o -Xk - m1,0_ yk -=

10、n, . ,2,10莖莖,fn 1(0,0) =0(5) 对于由(4),( 5)式构成的动态规划模型，不需要gk(uk,vk), fk(xk,yk)的解析表达式，完全可以求数值解。例15系统可靠性问题。一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行。为提高系统的可靠性， 每个部件都装置备用件，一旦原部件故障，备用件就自动进入系统。显然，备用件越多，系统可靠性越高，但费用也越大，那么在一定的总费用限制下，如何配置各 部件的备用件，使系统的可靠性最高呢？设系统有n个部件，当部件k装置uk个备用件时，这个部件正常工作的概率为Pk（uJ。而每个备用件的费用为 ck，另外设总费用不应

11、超过 C。这个优化问题的目标函数是系统正常运行的概率，它等于n个串联部件正常工作的概率的乘积。约束条件是备用件费用之和不应超过C ,决策变量是各部件的备用件数量，于是问题归结为nMax Z = U Pk （山）（1）k 4ns.t.ckuk 二 C,uk 为非负整数（2）k 4这个非线性规划转化为动态规划求解比较方便。按照对n个部件装置备用件的次序划分阶段，决策变量仍为部件k的备用件数量uk，而状态变量选取装配部件 k之前所容许使用的费用，记作xk，于是状态转移方程为Xki 二 Xk-CkUk（ 3）最优值函数fk（Xk）定义为状态Xk下，由部件k到部件n组成的子系统的最大正常工作概率，它满足

12、fk（xj 二 Max Pk（Uk） fk i（Xk i）（4）UkP k （Xk）5（兀）=山 u 0,Xk/Ck ,且为正整数,0 兰 Xk 兰 C,k = n,，2，fn 1（Xn 1）-1（ 5）注意，这个动态规划模型的最优方程（4）中，阶段指标pk （uk）与最优值函数fk.jXk*）之间的关系是相乘，而不是例1315中的相加，这是由 两事件之交的概率等于两事件概率之积”这一性质决定的。与此相应，最优值函数的初始条件fn 1（xn1等于1。例16任务均衡问题。一批任务由若干设备完成，问题是如何均衡地向每个设备分配各项任务，使这批任务尽早地完成。例如一高层（设N层）办公大楼有n部性能相

13、同的电梯，为了在早高峰期间尽快地将乘客送到各层的办公室，决定各部电梯分段运行，即每部电梯服务一定的层段。假定根据统计资料，已知一部电梯从第i层次开始服务j层所需要的时间为 h，问如何安排这些电梯服务的层段，使送完全部乘客的时间最短。按照由下而上安排电梯服务层次的序号划分阶段k =1,2 - , n。第k部电梯(即第k阶段)开始服务的层次为状态xk，它服务的层数为决策 uk，满足xk 1 =Xk Uk( 1)当Xk二i，Uk = j时，已知第k部电梯服务的时间为 Vk (Xk,Uk)二tij。因为对于第k,l两部电梯 而言，总的服务时间为 Maxvk(xk,uk),V|(X|,U|)，所以最优值

14、函数fk (xk)(即从第k部到第n 部电梯总的最短服务时间)满足fk(xQ 二“ minx、max Vk(Xk,uQ, fk i(Xk 1)uk Hk (Xk )Uk(xQ =山 |Uk =1,2,，N - 兀 -(n - k) 1 Xk =2,3, , N k = n, ,2,1(2)fn 1 (n *= 0( 3)这里我们假定每部电梯至少服务 1层，且从第2层起开始服务。应用动态规划方法求解多阶段决策问题分为两个步骤。第一是应用动态规划基本方程，逆序地求出条件最优目标函数值集合和条件最优决策集合。第二是顺序地求出最优决策序列。下面以 一个例子加以说明。例17 机器负荷分配问题。 某种机器

15、可以在高低两种不同的负荷下进行生产。在高负荷下生产时，每台机器生产产品的年产量为7吨，年折损率a =0.7 (即若年初完好的机器有U台，则年终完好的机器数为au台)，在低负荷下生产时，每台机器生产产品的年产量为5吨，年折损率b =0.9。若开始时完好的机器数有X1 =1000台，要求制定一个三年计划，在每年开始时，决定如何重新分配在两种不同的负荷下生产的完好机器数，使在三年内产品的总产量达到最大。设第k年初完好的机器数为 Xk，分配给高负荷下生产的机器数为 Uk，即在低负荷下生产的 机器数为Xk - Uk。这里Uk、Xk可取非负实数，如 Xk =0.7表示第k年度一台机器正常工作时间 只占0.

16、7。于是第k 1年初完好的机器数xk j = 0.7uk 0.9(xk -uk)二 0.9xk -0.2uk第k年度的产量Vk(Xk,Uk) =7Uk 5(Xk -Uk) =5Xk 2Uk设三年总产量为 V，则问题即求解下面的线性规划问题：3Max V 八（5xk 2uk）k 4S.t. X- =1000xk 1 二 0.9xk0.2uk, 0 乞 uk 乞 xk, k = 1,2,3现用动态规划来解。本题要求的是已知第一年度初拥有的完好机器数x1 =1000台，用最优方案到第三年度末这段期间的产品产量，将它记为f/x）。为此先求：已知第j年度初拥有的完好机器数，用最优方案到第三年末这段期间的

17、产品产量，将它记为fj（Xj）, j = 2,3，列出动态规划的基本方程'fk（xQ =用8冬皿区,山）+ f k* （xkG0虫k空k=xk 十=0.9x 0.2uk, k = 1,2,3i f4（X4） = 0求解过程如下：f3（X3）=0MaA【V3（X3,U3）+ f4（X4）（ 1）03盏即 f3（X3）Max （2u3 5x3），得最优解 u3 = X3，从而 f3（X3）=7x3。0直3咚f2（X2）= MaXV2（X2,u2） f3（X3）（ 2）0 <2 <2即 f2（x2） = °Max 2u2 5x2 7（0.9x2 -0.2u2） = &#

18、176;Max （0.6u2 11.3x2），得最优解 u； = x2，从而 f2 （x2） = 11.9x2。f/xj Maxv1（X1,u1） f2（X2）（ 3）0色巻即 f1 （x1）Max2u1 5x1 11.9（0.9x1 -0.2u1）Max 0.38u1 15.71x1），0屯圭0勺1童得最优解 u-i =0，从而 f1（x1） = 15.71x1。已知X1 =1000,则原问题的最优值为仏（为）=15710。顺序求出原问题的最优解为u1 =0，u2 = x2 = 0.9x1 -0.2“ =900， u3 = x3 = 0.9x2 - 0.2u2 = 630即第一年度应把年初全部完好机器投入低负荷生产，后两年每年应把年初全部完好机器投入高负荷生产，这样所得的三年总产量最高，为15710吨。 物业安保培训方案为规范保安工作，使保安工作系统化/规范化，最终使保安具备满足工作需要的知识和技能，特制定本教学教材大纲。一、课程设置及内容全部课程分为专业理论知识和技能训练两大科目。其中专业理论知识内容包括：保安理论知识、消防业务知识、职业道德、法律常识、保