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

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

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

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

4、始到终止状态的后部子过程的策略记为pk ( xk ) uk (xk ), uk 1 ( xk 1 ),un (xn ) 。在实际问题中，可供选择的策略有一定范围，称为允许策略集合 。其中达到最优效果的策略称为最优策略 。（5）状态转移方程如果第 k 个阶段状态变量为 xk ，作出的决策为 uk ，那么第 k 1阶段的状态变量 xk 1 也被完全确定。用状态转移方程表示这种演变规律，写作xk 1Tk ( xk ， u k )（6）最优值函数指标函数是系统执行某一策略所产生结果的数量表示，是用来衡量策略优劣的数量指标，它定义在全过程和所有后部子过程上。指标函数的最优值称为最优值函数 。下面的方程在

5、动态规划逆序求解中起着本质的作用。f k (xk )min vk ( xk , uk ( xk ) f k 1 ( xk 1 ),u kDk ( xk )fn 1 ( xn 1 )0,xk 1Tk (xk , uk ), kn, n1,1称此为动态规划逆序求解的基本方程（贝尔曼方程）。可以把建立动态规划模型归纳成以下几个步骤：（ 1）将问题恰当地划分为若干个阶段；（ 2）正确选择状态变量，使它既能描述过程的演变，又满足无后效性；（ 3）规定决策变量，确定每个阶段的允许决策集合；（ 4）写出状态转移方程；（ 5）确定各阶段各种决策的阶段指标，列出计算各阶段最优后部策略指标的基本方程。下面结合具体

6、例子阐述建立动态规划模型的思路。例 13生产计划问题。公司要对某产品制定n 周的生产计划，产品每周的需求量、生产和贮存费用、 生产能力的限制、 初始库存量等都是已知的，试在满足需求的条件下， 确定每周的生产量，使 n 周的总费用最少。决策变量是第k 周的生产量，记作uk (k1,2, n) 。已知下列数据及函数关系：第k 周的需求量 dk ：第 k 周产量为 u k 时的生产费为 ck (uk) ；第 k 周初贮存量为xk 时这一周的贮存费为hk (xk ) ；第 k 周的生产能力限制为 U k；初始（ k0 ）及终结（ kn ）时贮存量均为零。按照最短路问题的思路， 设从第 k 周初贮存量为

7、xk 到（ n 周末）过程结束的最小费用函数为f k ( xk ) ，则下列逆向递推公式成立。fk (xk )min ck (uk ) hk (xk )f k 1 (xk 1 )xk X k ,k，n, 2,10 ukUk(1)fn1( xn 1 ) 0而 xk 与 xk 1 满足xk 1xkuk d k ,k n, ，2，1(2)x1xn 10这里贮存量 xk是状态变量，（ 2）式给出了相邻阶段的状态在决策变量作用下的转移规律，称为状态转移规律。在用（1）式计算时，xk 的取值范围 允许状态集合X k 由（ 2）式及允许决策集合 (0 ukU k ) 决定。在实际问题中，为简单起见， 生产费

8、用常取 ck (uk ) ， uk0 ； ck (uk ) a cuk ， uk0 ，其中 c 是单位产品生产费，而 a 是生产准备费。贮存费用常取hk (xk )hxk ， h 是单位产品（一周的）贮存费。最优方程（ 1）和状态转移方程（2）构成了这个多阶段决策问题的动态规划模型。实际上，多阶段决策问题有时也可用静态规划方法求解，如例2的生产计划问题。例 14 资源分配问题。 总量为 m1的资源 A 和总量为 m2 的资源 B同时分配给 n 个用户， 已知第 k 用户利用数量 uk 的资源 A 和数量 vk的资源 B 时，产生的效益为 gk (uk ,vk ) ，问如何分配现有资源使总效益最

9、大。这本来是个典型的静态规划问题：nMaxZg k(uk, vk )(1)k 1ns.t .ukm1,uk0（2）k 1nvkm2 ,vk0（3）k 1但是当gk 比较复杂及n 较大时，用非线性规划求解是困难的，特别是，若g k 是用表格或图形给出而无解析表达式时，则难以求解。而这种情况下，将其转化为动态规划，是一种可行的方法。资源A ， B 每分配给一个用户划分为一个阶段，分配给第k用户的数量是二维决策变量(uk , vk ) ，而把向第k 用户分配之前，分配者手中掌握的资源数量作为二维状态变量，记作( xk , yk ) ，这样，状态转移方程应为xk 1xku k（ 4）yk 1ykvk最

10、优值函数f k ( xk , yk ) 定义为将数量( xk , yk ) 的资源分配给第k 至第 n 用户时能获得的最大效益，它满足最优方程f k (xk , yk )max gk (uk , vk ) f k 1 ( xk 1 , yk 1 ),0 xk m1 ,0 yk m2 , k n, ,2,10ukxk0vkykf n 1 (0,0)0（5）对于由（ 4），（ 5）式构成的动态规划模型，不需要g k (uk , vk ) , f k (xk , yk ) 的解析表达式，完全可以求数值解。例 15系统可靠性问题。一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行。 为

11、提高系统的可靠性，每个部件都装置备用件，一旦原部件故障，备用件就自动进入系统。显然，备用件越多，系统可靠性越高，但费用也越大，那么在一定的总费用限制下，如何配置各部件的备用件，使系统的可靠性最高呢？设系统有 n 个部件，当部件k 装置 uk 个备用件时，这个部件正常工作的概率为pk (uk ) 。而每个备用件的费用为ck ，另外设总费用不应超过C 。这个优化问题的目标函数是系统正常运行的概率，它等于n 个串联部件正常工作的概率的乘积。约束条件是备用件费用之和不应超过C ，决策变量是各部件的备用件数量，于是问题归结为nMaxZpk (uk )（1）k 1ns.t.ck uk C , uk 为非负

12、整数（2）k 1这个非线性规划转化为动态规划求解比较方便。按照对 n 个部件装置备用件的次序划分阶段，决策变量仍为部件k 的备用件数量 uk，而状态变量选取装配部件k 之前所容许使用的费用，记作xk ，于是状态转移方程为xk 1xkck uk（3）最优值函数f k (xk ) 定义为状态xk 下，由部件 k 到部件 n 组成的子系统的最大正常工作概率，它满足f k (xk )Max pk (uk ) f k 1 ( xk 1 )（4）u k U k ( xk )U k ( xk ) uk uk 0, xk /c k, 且为正整数 ,0 xk C, k n， ，2，1f n 1 ( xn 1 )

13、 1（5）注意，这个动态规划模型的最优方程（4）中，阶段指标pk (uk ) 与最优值函数 f k1 ( xk 1 ) 之间的关系是相乘， 而不是例 1315中的相加， 这是由 “两事件之交的概率等于两事件概率之积”这一性质决定的。与此相应，最优值函数的初始条件f n 1 ( xn 1 )1等于 1。例 16 任务均衡问题。一批任务由若干设备完成，问题是如何均衡地向每个设备分配各项任务，使这批任务尽早地完成。例如一高层（设 N 层）办公大楼有 n 部性能相同的电梯，为了在早高峰期间尽快地将乘客送到各层的办公室，决定各部电梯分段运行，即每部电梯服务一定的层段。假定根据统计资料，已知一部电梯从第i

14、 层次开始服务j 层所需要的时间为tij ，问如何安排这些电梯服务的层段，使送完全部乘客的时间最短。按照由下而上安排电梯服务层次的序号划分阶段k 1,2, , n 。第 k 部电梯（即第k 阶段）开始服务的层次为状态xk ，它服务的层数为决策uk ，满足xk 1xkuk（1）当 xki ， ukj 时，已知第 k 部电梯服务的时间为 vk (xk , uk )tij 。因为对于第 k ,l 两部电梯而言，总的服务时间为Maxvkxkuk),vl(xlul) ，所以最优值函数fk ( xk )n(,（即从第 k 部到第部电梯总的最短服务时间）满足fk (xk )ukmin max vk (xk

15、, uk ), f k 1 (xk1 )U k ( xk )U k ( xk )uk | uk 1,2, , N xk ( nk) 1 xk 2,3, , N k n, ,2,1（ 2）fn 1 (n1)0（3）这里我们假定每部电梯至少服务1层，且从第 2层起开始服务。应用动态规划方法求解多阶段决策问题分为两个步骤。第一是应用动态规划基本方程，逆序地求出条件最优目标函数值集合和条件最优决策集合。第二是顺序地求出最优决策序列。下面以一个例子加以说明。例17机器负荷分配问题。某种机器可以在高低两种不同的负荷下进行生产。在高负荷下生产时，每台机器生产产品的年产量为7吨，年折损率a0.7 （即若年初完

16、好的机器有u 台，则年终完好的机器数为 au 台），在低负荷下生产时，每台机器生产产品的年产量为5吨，年折损率b0.9。若开始时完好的机器数有x11000台，要求制定一个三年计划，在每年开始时，决定如何重新分配在两种不同的负荷下生产的完好机器数，使在三年内产品的总产量达到最大。设第 k 年初完好的机器数为xk ，分配给高负荷下生产的机器数为uk ，即在低负荷下生产的机器数为 xk - uk 。这里 uk 、 xk 可取非负实数，如xk0.7 表示第 k 年度一台机器正常工作时间只占 0.7 。于是第 k1年初完好的机器数xk 10.7uk0.9( xkuk )0.9xk0.2uk第 k 年度的

17、产量vk (xk , uk )7uk 5(xk uk ) 5xk2uk设三年总产量为V ，则问题即求解下面的线性规划问题：3MaxV(5xk2uk )k1s.t .x11000xk 10.9xk0.2uk ,0ukxk , k1,2,3现用动态规划来解。本题要求的是已知第一年度初拥有的完好机器数x11000台，用最优方案到第三年度末这段期间的产品产量，将它记为f1( x1) 。为此先求：已知第j 年度初拥有的完好机器数 xj ，用最优方案到第三年末这段期间的产品产量，将它记为f j ( xj ),j2,3 ，列出动态规划的基本方程f k(xk )Max vk ( xk , u k ) f k 1 ( xk 1 )0 u kxkxk 10.9xk0.2uk , k 1,2,3f 4 (x4 )0求解过程如下：f 3 ( x3 )Max v3 ( x3 , u3 )f 4 ( x4 )0 u3x3即 f 3 ( x3 ) Max ( 2u35x3 ) ，得最优解 u 3*x 3 ，从而 f 3 ( x3 ) 7x3 。0 u 3 x3f2 (x2 )Maxv2 (x2,u2 )f3(x3 )0 u2 x2即 f 2 (x2 )Max 2u25x27(0.9x20.2u2 )Max ( 0.6u2 11.3x2 ) ，0 u2 x20 u