动态规划模型

动态规划是解决多阶段决策过程最优化的一种方法.1951年美国数学家贝尔曼等人，根据一类多阶段决策问题的特性，提出了解决这类问题的“最优化原理”，并研究了许多实际问题，从而创建了最优化问题的一种新方法——动态规划.

多阶段决策问题，是指这样一类活动的过程：由于它的特殊性，可将它划分成若干个相互联系的过程，在它的每个过程都需要做出决策，并且一个阶段的决策确定以后，常影响下一个阶段的决策，从而影响整个决策的结果.多阶段决策问题就是要在允许的决策范围内，选择一个最优决策，使整个系统在预定的标准下达到最佳的效果.研究某一个过程为例，这个过程可以分解为若干个互相联系的阶段.每一阶段都有其初始状态和结束状态，其结束状态即为下一阶段的初始状态.第一阶段的初始状态就是整个过程的初始状态，最后一阶段的结束状态就是整个过程的结束状态.在过程的每一个阶段都需要做出决策，而每一阶段的结束状态依赖于其初始状态和该阶段的决策.动态规划问题就是要找出某种决策方法，使过程达到某种最优效果.动态规划示意如图5-7所示.

图5-7　动态规划示意图

阶段：用动态规划求解多阶段决策问题时，要根据具体的情况将系统适当地分成若干个阶段，以便分阶段求解，描述阶段的变量称为阶段变量.

状态：状态表示系统在某一阶段所处的位置或状态.

决策：某一阶段的状态确定以后，从该状态演变到下一阶段某一状态所作的选择或决定称为决策.描述决策的变量称为决策变量，用u_k（x_k）表示在第k阶段的状态x_k时的决策变量，决策变量限制的范围称为允许决策集合，用D_k（x_k）表示第k阶段从x_k出发的决策集合.

策略：由每阶段的决策u_k（x_k）（k=1，2，…，n）组成的决策函数序列称为全过程策略或简称策略，用P表示，即：

由系统的第k个阶段开始到终点的决策过程称为全过程的后部子过程，相应的策略称为后部子过程策略，用P_k（x_k）表示k子过程策略，即：

对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合，允许策略集合中达到最优效果的策略称为最优策略.

状态转移：某一阶段的状态及决策变量取定后，下一阶段的状态就随之而定.设第k阶段的状态变量为x_k，决策变量为u_k（x_k），第k＋1个阶段的状态为x_k+1，用x_k+1=T_k（x_k，u_k）表示从k阶段到k+1阶段状态转移规律，称之为状态转移方程.

阶段效益：系统某阶段的状态一经确定，执行某一决策所得的效益称为阶段效益，它是整个系统效益的一部分，是阶段状态x_k和阶段决策u_k（x_k）的函数，记为d_k（x_k，u_k）.

指标函数：指标函数是系统执行某一策略所产生效益的数量表示，根据不同的实际情况，效益可以是利润、距离、时间、产量或资源的耗量等.指标函数可以定义在全过程上，也可以定义在后部子过程上，指标函数往往是各阶段效益的某种和式，取最优策略时的指标函数称为最优策略指标.

最后根据动态规划原理得到动态规划的一般模型如下所示：

其中f_k（x_k）表示从状态x_k出发到达终点的最优效益，N表示可将系统分成N个阶段，根据问题的性质，上式中的min有时是max.

动态规划是数学建模中经常被用到的一种优秀方法，接下来就通过两个例题来熟悉动态规划方法.

例5-10　生产计划制订问题

设某厂计划全年生产某种产品A，其四个季度的订货量分别是600件、700件、500件、1200件.已知生产产品A的生产费用与产品数量的平方成正比，其比例系数是0.005，厂内有仓库可存放未销售掉的产品，其存储费为每件每季度1元，问每一季度各应生产多少产品，才能使总费用最少？

【解题思路】

这是一个典型的多阶段决策问题，每一季度为一个阶段.取第k季度初具有的产品数为状态变量x_k；取第k季度需要生产的产品数为决策变量u_k；

由状态x_k采取决策u_k后的状态转移方程显然为：x_k+1=x_k+u_k-A_k.

其中A_k为已知，A₁=600，A₂=700，A₃=500，A₄=1200.

在问题中，效益就是费用，故阶段效益为：d（x_k，u_k）=x_k+0.005u²_k.

若用f_k表示从状态x_k出发，采用最优策略到第四季度结束时产生最小费用，则有如下的动态规划模型：

先从最后一个季度k=4算起，求极值问题：f₄（x₄）=minu₄≥1200-x₄{x₄+0.005u²₄}，显然应取u₄=1200-x₄，于是得：f₄=7200-11x₄+0.005x²₄.

再考虑k=3，求极值问题如下：

利用求极值方法对u₃进行求导得到：0.01u₃-11+0.01（x₃+u₃-500）=0.

得：u₃=800-0.5x₃f₃（x₃）=7550-7x₃+0.0025x²₃.

再考虑k=2，求极值问题如下：

再对u₂进行求导得到：0.01u₂-7+0.005（x₂+u₂-700）=0.

得u₂=700-x₂/3f₂（x₂）=10000-6x₂+0.005x²₃/3.

最后考虑k=1，求极值问题如下：

最后对u₁进行求导得到：0.01u₁-6+0.01（x₁+u₁-600）/3=0.

注意到x₁=0，于是u₁=600，f₁（x₁）=11800.

因而这一生产-库存管理系统各季度的库存量和最优策略序列分别为：

x ₁=0，x₂=0，x₃=0，x₄=300，x₅=0，u₁=600，u₂=700，u₃=800，u₄=900，应用这一策略，才能使总费用最少，为11800元.

例5-11　生产与储存问题

某公司主要为电力公司生产大型变压器，由于电力公司采取预订方式购买，所以该公司可以预测未来几个月的需求量.为确保需求，该公司为新的一年前4个月制订一项生产计划，这4个月的需求如表5-9所示.

生产成本随着生产数量而变化.调试费为4，除了调试费用外，每月生产的头两台各花费为2，后两台各花费为1.最大生产能力为每月4台，生产成本如表5-10所示.

表5-9　四个月需求表

表5-10　成本表

每台变压器在仓库中由这个月存到下个月的储存费为1，仓库的最大储存能力为3台.另外，知道在1月1日时仓库里存着一台变压器，要求在4月30日仓库的库存量为零.试问该公司应如何制订生产计划，使得四个月的生产成本和储存费用最少？

【解题思路】

按月份来划分阶段，第i个月为第i个阶段，设s_k为第k阶段初库存量；x_k为第k阶段的生产量；d_k为第k阶段的需求量；这些数值可以从表5-9得知.

因为下个月的库存量等于上个月的库存量加上上个月的生产量减去上个月的需求量，就得到了如下状态转移方程：

由于必须要满足需求，则有s_k+x_k≥d_k.

另一方面，第k阶段的生产量x_k必不大于同期的生产能力（4台），也不大于第k阶段至第四阶段的需求之和与第k阶段初库存量之差，否则第k阶段的生产量就要超过从第k阶段至第四阶段的总需求，故有.

从以上的状态转移方程0=s₄+x₄-d₄x₄=d₄-s₄=3-s₄，这样就有f₄（s₄）=minr₄（s₄，x₄）=r₄（s₄，3-s₄）.

这里的阶段指标r_n（s_n，x_n）可以分为两部分，即生产成本与储存费，即为r_n（s_n，x_n）=c_n（x_n）+h_n（s_n，x_n）.

由于第四阶段末要求库存为零，即有h₄（s₄，x₄）=1×0=0，这样可得：f₄（s₄）=r₄（s₄，3-s₄）=c₄（3-s₄）+h₄（s₄，3-s₄）=c₄（3-s₄）.

对于每个s₄的可行值，f₄（s₄）的值列于表5-11.

表5-11　可行值表

表中当s₄=0时，可知第四阶段要生产x₄=3-s₄=3台，从表5-11可知总成本为9，同样可以算出当s₄为1，2，3时的情况，结果已列于表5-11中.

第三阶段：此时有r₃（s₃，x₃）=c₃（x₃）+h₃（s₃，x₃）=c₃（x₃）+1×（s₃+x₃-d₃）.

因为s₄=s₃+x₃-d₃，以及d₃=1，所以有如下表达式：

当第三阶段初库存量s₃=1，生产量x₃=2时，则s₃+x₃-d₃=1+2-1=2，所以生产成本为8，第三阶段末库存为2时，储存费为2，而f₄（s₄）=f₄（2），由表5-11可知f₄（2）=6，可知r₃（1，2）+f₄（2）=16，其他结果如表5-12所示.

表5-12　动态规划数据表

第二阶段：因为s₃=s₂+x₂-d₂，以及d₂=4，所以有如下表达式：

计算结果如表5-13所示.

表5-13　动态规划数据表

第一阶段：因为s₂=s₁+x₁-d₁，以及d₁=2，s₁=1，所以有

计算结果如表5-14所示.

表5-14　动态规划数据表

利用递推关系可以得到两组最优解，此时有最低总成本29.如下所示：