1、数学建模 数学建模 6 动态规划模型举例 以上讨论的优化问题属于静态的，即不必考虑时间的变化，建立的模型线性规划、非线 性规划、整数规划等，都属于静态规划。多阶段决策属于动态优化问题，即在每个阶段（通常以 时间或空间为标志）根据过程的演变情况确定一个决策，使全过程的某个指标达到最优。例如： （1）化工生产过程中包含一系列的过程设备，如反应器、蒸馏塔、吸收器等，前一设备的输出 为后一设备的输入。因此，应该如何控制生产过程中各个设备的输入和输出，使总产量最大。 （2）发射一枚导弹去击中运动的目标，由于目标的行动是不断改变的，因此应当如何根据目标 运动的情况，不断地决定导弹飞行的方向和速度，使之最快
2、地命中目标。 （3）汽车刚买来时故障少、耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增 加则变得故障多，油耗高，维修费用增加，经济效益差。使用时间俞长，处理价值也俞低。另外， 每次更新都要付出更新费用。因此，应当如何决定它每年的使用时间，使总的效益最佳。 动态规划模型是解决这类问题的有力工具，下面介绍相关的基本概念及其数学描述。 （1）阶段 整个问题的解决可分为若干个相互联系的阶段依次进行。通常按时间或空间划分阶 段，描述阶段的变量称为阶段变量，记为 。k （2）状态 状态表示每个阶段开始时所处的自然状况或客观条件，它描述了研究过程的状况。 各阶段的状态通常用状态变量描述。常用 表
3、示第 阶段的状态变量。 个阶段的决策过程有kxn 个状态。用动态规划方法解决多阶段决策问题时，要求整个过程具有无后效性。即：如果1n 某阶段的状态给定，则此阶段以后过程的发展不受以前状态的影响，未来状态只依赖于当前状态。 （3）决策 某一阶段的状态确定后，可以作出各种选择从而演变到下一阶段某一状态，这种选 择手段称为决策。描述决策的变量称为决策变量。决策变量限制的取值范围称为允许决策集合。 用 表示第 阶段处于状态 时的决策变量，它是 的函数，用 表示 的允许)(kxukxkx)(kxDk 决策集合。 （4）策略 一个由每个阶段的决策按顺序排列组成的集合称为策略。由第 阶段的状态 开始kx 到
4、终止状态的后部子过程的策略记为 。在实际问题中，)(,)(),()(1nkkk xuxuxp 可供选择的策略有一定范围，称为允许策略集合。其中达到最优效果的策略称为最优策略。 （5）状态转移方程 如果第 个阶段状态变量为 ，作出的决策为 ，那么第 阶段的状kk1 态变量 也被完全确定。用状态转移方程表示这种演变规律，写作 ，1kx (1Txk)u （6）最优值函数 指标函数是系统执行某一策略所产生结果的数量表示，是用来衡量策略优劣 的数量指标，它定义在全过程和所有后部子过程上。指标函数的最优值称为最优值函数。 数学建模 数学建模 下面的方程在动态规划逆序求解中起着本质的作用。 1,),(,0)
5、( ),(,min11 1)( nkuxTxf xfvf kn kkkxDukk 称此为动态规划逆序求解的基本方程（贝尔曼方程） 。 可以把建立动态规划模型归纳成以下几个步骤： （1）将问题恰当地划分为若干个阶段； （2）正确选择状态变量，使它既能描述过程的演变，又满足无后效性； （3）规定决策变量，确定每个阶段的允许决策集合； （4）写出状态转移方程； （5）确定各阶段各种决策的阶段指标，列出计算各阶段最优后部策略指标的基本方程。 下面结合具体例子阐述建立动态规划模型的思路。 例13 生产计划问题。公司要对某产品制定 n周的生产计划，产品每周的需求量、生产和贮存 费用、生产能力的限制、初始库
6、存量等都是已知的，试在满足需求的条件下，确定每周的生产量， 使 n周的总费用最少。 决策变量是第 周的生产量，记作 。已知下列数据及函数关系：第 周的k),21(kuk 需求量 ：第 周产量为 时的生产费为 ；第 周初贮存量为 kx时这一周的贮存费kdkkc 为 )(xh；第 周的生产能力限制为 ；初始（ ）及终结（ ）时贮存量均为零。kU0n 按照最短路问题的思路，设从第 周初贮存量为 到（ 周末）过程结束的最小费用函数为kxn ，则下列逆向递推公式成立。)(kxf 0)( 1,2,)()(min1 1n kkkkUukxf nXxfxhck ， (1) 而 kx与 满足1 (2)012,1
7、nkkxndu， 这里贮存量 是状态变量， （2）式给出了相邻阶段的状态在决策变量作用下的转移规律，k 称为状态转移规律。在用（1）式计算时， 的取值范围允许状态集合 由（2）式及允kxkX 许决策集合 决定。)0(kUu 在实际问题中，为简单起见，生产费用常取 ， ； ，)(kuc0k kkcuac)( 数学建模 数学建模 ，其中 是单位产品生产费，而 是生产准备费。贮存费用常取 ， 是单0kuca kkhx)( 位产品（一周的）贮存费。 最优方程（1）和状态转移方程（2）构成了这个多阶段决策问题的动态规划模型。实际上， 多阶段决策问题有时也可用静态规划方法求解，如例2的生产计划问题。 例1
8、4 资源分配问题。总量为 的资源A 和总量为 的资源B同时分配给 n个用户，已知第1m2m 用户利用数量 的资源A和数量 的资源B 时，产生的效益为 ，问如何分配现有资kkukv ),(kvug 源使总效益最大。 这本来是个典型的静态规划问题： (1) nkkvugZMax1),( nkkmts110,. （2） nkkvv120, （3） 但是当 比较复杂及 n较大时，用非线性规划求解是困难的，特别是，若 是用表格或图形给kg kg 出而无解析表达式时，则难以求解。而这种情况下，将其转化为动态规划，是一种可行的方法。 资源A，B每分配给一个用户划分为一个阶段，分配给第 用户的数量是二维决策变
9、量k ，而把向第 用户分配之前，分配者手中掌握的资源数量作为二维状态变量，记作),(kvuk ，这样，状态转移方程应为yx kkvyux1 （4） 最优值函数 定义为将数量 的资源分配给第 至第 n用户时能获得的最大效益，),(kxf ),(kxk 它满足最优方程 0),( 1,2,0,),(),(ma1 2111n kkkkkyvxukf nmyxyfgk 数学建模 数学建模 （5） 对于由（4） ， （5）式构成的动态规划模型，不需要 , 的解析表达式，完全)(kvug),(kyxf 可以求数值解。 例15 系统可靠性问题。一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常 运
10、行。为提高系统的可靠性，每个部件都装置备用件，一旦原部件故障，备用件就自动进入系统。 显然，备用件越多，系统可靠性越高，但费用也越大，那么在一定的总费用限制下，如何配置各 部件的备用件，使系统的可靠性最高呢？ 设系统有 n个部件，当部件 装置 个备用件时，这个部件正常工作的概率为 。而kku )(kup 每个备用件的费用为 ，另外设总费用不应超过 。kcC 这个优化问题的目标函数是系统正常运行的概率，它等于 n个串联部件正常工作的概率的乘 积。约束条件是备用件费用之和不应超过 ，决策变量是各部件的备用件数量，于是问题归结 为 nkkupZMax1)( （1） 为非负整数 nkkuCcts1,.
11、 （2） 这个非线性规划转化为动态规划求解比较方便。 按照对 n个部件装置备用件的次序划分阶段，决策变量仍为部件 的备用件数量 ，而状kku 态变量选取装配部件 之前所容许使用的费用，记作 ，于是状态转移方程为kkx kkucx1 （3） 最优值函数 定义为状态 下，由部件 到部件 n组成的子系统的最大正常工作概率，它)(kfkk 满足 )()()( 1)( kkxUuk xfpMafk （4） 且为正整数, ,/c,0)(kkk 12,0， nkCx 数学建模 数学建模 1)(1nxf （5） 注意，这个动态规划模型的最优方程（4）中，阶段指标 与最优值函数 之)(kup)(1kxf 间的关
12、系是相乘，而不是例1315中的相加，这是由“两事件之交的概率等于两事件概率之积”这 一性质决定的。与此相应，最优值函数的初始条件 等于1。)(1nxf 例16 任务均衡问题。一批任务由若干设备完成，问题是如何均衡地向每个设备分配各项任务， 使这批任务尽早地完成。例如一高层（设 层）办公大楼有 部性能相同的电梯，为了在早高N 峰期间尽快地将乘客送到各层的办公室，决定各部电梯分段运行，即每部电梯服务一定的层段。 假定根据统计资料，已知一部电梯从第 层次开始服务 层所需要的时间为 ，问如何安排这些ijijt 电梯服务的层段，使送完全部乘客的时间最短。 按照由下而上安排电梯服务层次的序号划分阶段 。第
13、 部电梯（即第 阶段）nk,21kk 开始服务的层次为状态 ，它服务的层数为决策 ，满足kxku ku1 （1） 当 ， 时，已知第 部电梯服务的时间为 。因为对于第 两部电梯ixkjuk ijktuxv),( lk, 而言，总的服务时间为 ，所以最优值函数 （即从第 部到第),(),(llkxvuMax )(kxfn 部电梯总的最短服务时间）满足 )(),(min)( 1)( kkxUuk fvfk ,21| nxNkk 1,2,32 nkNxk （2） 0)(1nf （3） 这里我们假定每部电梯至少服务1层，且从第2层起开始服务。 应用动态规划方法求解多阶段决策问题分为两个步骤。第一是应用
14、动态规划基本方程，逆序 地求出条件最优目标函数值集合和条件最优决策集合。第二是顺序地求出最优决策序列。下面以 一个例子加以说明。 例17 机器负荷分配问题。某种机器可以在高低两种不同的负荷下进行生产。在高负荷下生产时， 每台机器生产产品的年产量为7吨，年折损率 （即若年初完好的机器有 台，则年终完7.0au 数学建模 数学建模 好的机器数为 台） ，在低负荷下生产时，每台机器生产产品的年产量为5吨，年折损率au 。若开始时完好的机器数有 台，要求制定一个三年计划，在每年开始时，决9.0b10x 定如何重新分配在两种不同的负荷下生产的完好机器数，使在三年内产品的总产量达到最大。 设第 年初完好的
15、机器数为 ，分配给高负荷下生产的机器数为 ，即在低负荷下生产的kk ku 机器数为 - 。这里 、 可取非负实数，如 表示第 年度一台机器正常工作时间kxukx7.0kx 只占 。于是第 年初完好的机器数7.01 kkkkk uuu2.9.)(9.07. 第 年度的产量k kkkk xxxv5)(),( 设三年总产量为 ，则问题即求解下面的线性规划问题：V31)25(kkuxMax 0.ts 3,21,0,2.9.1 kxuxkkkk 现用动态规划来解。本题要求的是已知第一年度初拥有的完好机器数 台，用最优方案0 到第三年度末这段期间的产品产量，将它记为 。为此先求：已知第 年度初拥有的完好机
16、)(1xf j 器数 ，用最优方案到第三年末这段期间的产品产量，将它记为 ，列出动态jx 3,2),(xfj 规划的基本方程 0)( 3,21,.09.)(),(41xf kuxxfvMafkkuk 求解过程如下： )(),()( 43033xfuxvMaxfu （1） 即 ，得最优解 ，从而 。)52()(3033xuMaxfx 3*xu337)(f )(,(202fvfxu （2） 数学建模 数学建模 即 ，)2.09.(752)(202 uxuMaxf )3.16.0(222xuMaxu 得最优解 ，从而 。2* 2.1)f )(,()(011xfvxfu （3） 即 ，)2.09.(52)( 11011 uMaxfu )71.538.0(1 xuMaxu 得最优解 ，从而 。* 7.)xf 已知 ，则原问题的最优值为 。1x 570)(1f 顺序求出原问题的最优解为 ， ，0*1u902.9.012*ux 6302.9.3*ux 即第一年度应把年初全部完好机器投入低负荷生产，后两年每年应把年初全部完好机器投入高负 荷生产，这样所得的三年总产量最高，为15710吨。
