§6 动态规划模型举例
以上讨论的优化问题属于静态的，即不必考虑时间的变化，建立的模型——线性规划、非线性规划、整数规划等，都属于静态规划。多阶段决策属于动态优化问题，即在每个阶段（通常以时间或空间为标志）根据过程的演变情况确定一个决策，使全过程的某个指标达到最优。例如： （1）化工生产过程中包含一系列的过程设备，如反应器、蒸馏塔、吸收器等，前一设备的输出为后一设备的输入。因此，应该如何控制生产过程中各个设备的输入和输出，使总产量最大。 （2）发射一枚导弹去击中运动的目标，由于目标的行动是不断改变的，因此应当如何根据目标运动的情况，不断地决定导弹飞行的方向和速度，使之最快地命中目标。
（3）汽车刚买来时故障少、耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加则变得故障多，油耗高，维修费用增加，经济效益差。使用时间俞长，处理价值也俞低。另外，每次更新都要付出更新费用。因此，应当如何决定它每年的使用时间，使总的效益最佳。
动态规划模型是解决这类问题的有力工具，下面介绍相关的基本概念及其数学描述。 （1）阶段 整个问题的解决可分为若干个相互联系的阶段依次进行。通常按时间或空间划分阶段，描述阶段的变量称为阶段变量，记为k。
（2）状态 状态表示每个阶段开始时所处的自然状况或客观条件，它描述了研究过程的状况。各阶段的状态通常用状态变量描述。常用xk表示第k阶段的状态变量。n个阶段的决策过程有n?1个状态。用动态规划方法解决多阶段决策问题时，要求整个过程具有无后效性。即：如果某阶段的状态给定，则此阶段以后过程的发展不受以前状态的影响，未来状态只依赖于当前状态。 （3）决策 某一阶段的状态确定后，可以作出各种选择从而演变到下一阶段某一状态，这种选择手段称为决策。描述决策的变量称为决策变量。决策变量限制的取值范围称为允许决策集合。用
uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数，用Dk(xk)表示xk的允许决策
集合。
（4）策略 一个由每个阶段的决策按顺序排列组成的集合称为策略。由第k阶段的状态xk开始到终止状态的后部子过程的策略记为pk(xk)?{uk(xk),uk?1(xk?1),?,un(xn)}。在实际问题中，可供选择的策略有一定范围，称为允许策略集合。其中达到最优效果的策略称为最优策略。 （5）状态转移方程 如果第k个阶段状态变量为xk，作出的决策为uk，那么第k?1阶段的状态变量xk?1也被完全确定。用状态转移方程表示这种演变规律，写作xk?1?Tk(xk，uk) （6）最优值函数 指标函数是系统执行某一策略所产生结果的数量表示，是用来衡量策略优劣的数量指标，它定义在全过程和所有后部子过程上。指标函数的最优值称为最优值函数。 下面的方程在动态规划逆序求解中起着本质的作用。
?fk(xk)?min[vk(xk,uk(xk))?fk?1(xk?1)],uk?Dk(xk)???f(x)?0,x?T(x,u),k?n,n?1,?,1k?1kkk?n?1n?1称此为动态规划逆序求解的基本方程（贝尔曼方程）。 可以把建立动态规划模型归纳成以下几个步骤： （1）将问题恰当地划分为若干个阶段；
（2）正确选择状态变量，使它既能描述过程的演变，又满足无后效性； （3）规定决策变量，确定每个阶段的允许决策集合； （4）写出状态转移方程；
（5）确定各阶段各种决策的阶段指标，列出计算各阶段最优后部策略指标的基本方程。
下面结合具体例子阐述建立动态规划模型的思路。
例13 生产计划问题。公司要对某产品制定n周的生产计划，产品每周的需求量、生产和贮存费用、生产能力的限制、初始库存量等都是已知的，试在满足需求的条件下，确定每周的生产量，使n周的总费用最少。
决策变量是第k周的生产量，记作uk(k?1,2,?,n)。已知下列数据及函数关系：第k周的需求量dk：第k周产量为uk时的生产费为ck(uk)；第k周初贮存量为xk时这一周的贮存费为
hk(xk)；第k周的生产能力限制为Uk；初始（k?0）及终结（k?n）时贮存量均为零。按
照最短路问题的思路，设从第k周初贮存量为xk到（n周末）过程结束的最小费用函数为fk(xk)，则下列逆向递推公式成立。
min[ck(uk)?hk(xk)?fk?1(xk?1)]??fk(xk)?0?uk?Uk???fn?1(xn?1)?0而xk与xk?1满足
xk?Xk,k?n,?，2,1 (1)
?xk?1?xk?uk?dk,??x1?xn?1?0k?n,?，2，1 (2)
这里贮存量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）和状态转移方程（2）构成了这个多阶段决策问题的动态规划模型。实际上，多阶段决策问题有时也可用静态规划方法求解，如例2的生产计划问题。
例14 资源分配问题。总量为m1的资源A和总量为m2的资源B同时分配给n个用户，已知第k用户利用数量uk的资源A和数量vk的资源B时，产生的效益为gk(uk,vk)，问如何分配现有资源使总效益最大。
这本来是个典型的静态规划问题： MaxZ??gk(uk,vk) (1)
k?1n s.t.?uk?1nk?m1,（2） uk?0
?vk?1nk?m2, vk?0 （3）
但是当gk比较复杂及n较大时，用非线性规划求解是困难的，特别是，若gk是用表格或图形给出而无解析表达式时，则难以求解。而这种情况下，将其转化为动态规划，是一种可行的方法。 资源A，B每分配给一个用户划分为一个阶段，分配给第k用户的数量是二维决策变量
(uk,vk)，而把向第k用户分配之前，分配者手中掌握的资源数量作为二维状态变量，记作(xk,yk)，这样，状态转移方程应为
?xk?1?xk?uk （4） ?y?y?vkk?k?1最优值函数fk(xk,yk)定义为将数量(xk,yk)的资源分配给第k至第n用户时能获得的最大效益，它满足最优方程
?fk(xk,yk)?max[gk(uk,vk)?fk?1(xk?1,yk?1)],0?uk?xk?0?vk?yk???fn?1(0,0)?00?xk?m1,0?yk?m2,k?n,?,2,1
（5）
对于由（4），（5）式构成的动态规划模型，不需要gk(uk,vk),fk(xk,yk)的解析表达式，完全可以求数值解。
例15 系统可靠性问题。一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常
运行。为提高系统的可靠性，每个部件都装置备用件，一旦原部件故障，备用件就自动进入系统。显然，备用件越多，系统可靠性越高，但费用也越大，那么在一定的总费用限制下，如何配置各部件的备用件，使系统的可靠性最高呢？
设系统有n个部件，当部件k装置uk个备用件时，这个部件正常工作的概率为pk(uk)。而每个备用件的费用为ck，另外设总费用不应超过C。
这个优化问题的目标函数是系统正常运行的概率，它等于n个串联部件正常工作的概率的乘积。约束条件是备用件费用之和不应超过C，决策变量是各部件的备用件数量，于是问题归结为
MaxZ??pk(uk) （1）
k?1nns.t.?cukk?1k?C, uk为非负整数 （2）
这个非线性规划转化为动态规划求解比较方便。
按照对n个部件装置备用件的次序划分阶段，决策变量仍为部件k的备用件数量uk，而状态变量选取装配部件k之前所容许使用的费用，记作xk，于是状态转移方程为
xk?1?xk?ckuk （3）
最优值函数fk(xk)定义为状态xk下，由部件k到部件n组成的子系统的最大正常工作概率，它满足
fk(xk)?Max[pk(uk)?fk?1(xk?1)] （4）
uk?Uk(xk)?，2，1 Uk(xk)?{ukuk?[0,xk/ck ],且为正整数}, 0?xk?C,k?n， fn?1(xn?1)?1 （5）
注意，这个动态规划模型的最优方程（4）中，阶段指标pk(uk)与最优值函数fk?1(xk?1)之间的关系是相乘，而不是例13~15中的相加，这是由“两事件之交的概率等于两事件概率之积”这一性质决定的。与此相应，最优值函数的初始条件fn?1(xn?1)?1等于1。
例16 任务均衡问题。一批任务由若干设备完成，问题是如何均衡地向每个设备分配各项任务，使这批任务尽早地完成。例如一高层（设N层）办公大楼有n部性能相同的电梯，为了在早高峰期间尽快地将乘客送到各层的办公室，决定各部电梯分段运行，即每部电梯服务一定的层段。假定根据统计资料，已知一部电梯从第i层次开始服务j层所需要的时间为tij，问如何安排这些电
梯服务的层段，使送完全部乘客的时间最短。
按照由下而上安排电梯服务层次的序号划分阶段k?1,2,?,n。第k部电梯（即第k阶段）开始服务的层次为状态xk，它服务的层数为决策uk，满足
xk?1 ?xk?uk （1）
当xk?i，uk?j时，已知第k部电梯服务的时间为vk(xk,uk)?tij。因为对于第k,l两部电梯而言，总的服务时间为Max[vk(xk,uk),vl(xl,ul)]，所以最优值函数fk(xk)（即从第k部到第n部电梯总的最短服务时间）满足
fk(xk)?min{max[vk(xk,uk),fk?1(xk?1)]}
uk?Uk(xk) Uk(xk)?{uk|uk?1,2,?,N?xk?(n?k)?1} xk?2,3,?,Nk?n,?,2,1 （2） fn?1(n?1)?0 （3）这里我们假定每部电梯至少服务1层，且从第2层起开始服务。
应用动态规划方法求解多阶段决策问题分为两个步骤。第一是应用动态规划基本方程，逆序地求出条件最优目标函数值集合和条件最优决策集合。第二是顺序地求出最优决策序列。下面以一个例子加以说明。
例17 机器负荷分配问题。某种机器可以在高低两种不同的负荷下进行生产。在高负荷下生产时，每台机器生产产品的年产量为7吨，年折损率a?0.7（即若年初完好的机器有u台，则年终完好的机器数为au台），在低负荷下生产时，每台机器生产产品的年产量为5吨，年折损率b?0.9。若开始时完好的机器数有x1?1000台，要求制定一个三年计划，在每年开始时，决定如何重新分配在两种不同的负荷下生产的完好机器数，使在三年内产品的总产量达到最大。
设第k年初完好的机器数为xk，分配给高负荷下生产的机器数为uk，即在低负荷下生产的机器数为xk-uk。这里uk、xk可取非负实数，如xk?0.7表示第k年度一台机器正常工作时间只占0.7。于是第k?1年初完好的机器数
xk?1?0.7uk?0.9(xk?uk)?0.9xk?0.2uk
第k年度的产量
vk(xk,uk)?7uk?5(xk?uk)?5xk?2uk
设三年总产量为V，则问题即求解下面的线性规划问题：
数学建模案例分析--最优化方法建模6动态规划模型举例.
