刘凤鸣

（浙江海洋学院 数理与信息学院，浙江 舟山 316000）

1 动态规划的基本概念

多阶段决策过程，是指一类特殊的过程，它们可以按时间顺序分解成若干个相互联系的阶段，称为“时段”，在每个时段都要做决策，全部过程的决策是一个决策序列。多阶段决策问题也称为序贯决策问题。

多阶段决策问题的目标是要达到整个活动过程的总体最优。在每个阶段进行决策时不应仅考虑本阶段最优，尤其应考虑对最终目标的影响，从而做出对全局来说最优的决策。动态规划是符合这种要求的一种决策方法。

动态规划开始只是应用于多阶段决策性问题，后来渐渐被发展为解决离散最优化问题的有效手段，进一步应用于一些连续性问题上。然而，动态规划更像是一种思想而非算法，它没有固定的数学模型，没有固定的实现方法，其正确性也缺乏严格的理论证明。因此，一直以来动态规划的数学理论模型是一个研究的热点。一个多阶段决策过程最优化问题的动态规划模型通常包含以下基本要素：阶段、状态、决策、策略、状态转移方程、指标函数和最优值函数，在建立动态规划数学模型时，主要是确定这些动态规划的基本要素。

2 动态规划算法的基本步骤

2.1 划分阶段

应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。

2.2 选择状态

正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性.动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的。

2.3 确定决策并写出状态转移方程

之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。

2.4 写出规划方程（包括边界条件）

动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。

3 动态规划应用问题

3.1 资源分配问题

例：某物流公司每天要给3家公司运送6车货物，如果各公司获得这些货物之后获得的盈利如表1所示，则这车货物如何分配给各工厂才能使盈利最大。

表1

解：将问题按公司分为3个阶段，甲、乙、丙三个公司分别编号为1、2、3

设sk表示为分配给第k个公司至第n个公司的货物车数

xk表示为分配给第k个公司的货物数量

则sk+1=sk-xk为分配给第k+1个公司至第n个公司的货物车数

pk（xk）表示为xk车货物分配到第k个公司所得的盈利值

fk（sk）表示为sk车货物分配给第k个公司至第n个公司时所得到的最大盈利值

根据逆推关系式

fk（sk）=max｛pk（xk）+fk+1（sk-xk）｝，k=3，2，1

0≤xk≤sk

f4（s4）=0

所以从最后一个阶段开始向前逆推计算

第三阶段：

设将 s3 车货物（s3=0，1，2，3，4，5，6）全部分配给公司丙时，最大盈利值为

f3（s3）=max［p3（x3）］

其中 x3=s3=0，1，2，3，4，5，6

因为此时只有一个公司，有多少车货物就全部分配给公司丙，故它的盈利值就是该段的最大盈利值，其数值计算如表2所示。

第二阶段：

k=2 时，设把 s2 车货物（s2=0，1，2，3，4，5，6）分配给公司乙和丙时，对每个s2值有一种最优分配方案，使最大盈利值为

表2

表中，x3*表示使f3（x3）为最大值时的最优决策。

表3

f2（s2）=max［p2（x2）+f3（s2-x2）］

其中 s2=0，1，2，3，4，5，6

因为乙公司x2车，其盈利为p2（x2），余下的s2-x2车就给丙公司，则它的盈利最大值为 f3（s2-x2）。 现在选择x2的值，使 p2（x2）+f3（s2-x2）取最大值，其数值计算如表3所示。

第一阶段：

k=1时，设把s1车（这里只有s1=6的情况）货物分配给甲、乙、丙三个公司时，最大盈利值为

f1（6）=max［p1（x1）+f2（6-x1）］

其中 x1=0，1，2，3，4，5，6

因为给甲公司x1车，其盈利为p1（x1），剩下的6-x1车就分给乙和丙两个公司，则它的盈利最大值为f2（6-x1），现选择 x1值，使p1（x1）+f2（6-x1）取最大值，它就是所求的总盈利最大值，其数值计算如表4所示。

表4

根据计算表格的顺序反推算，可知最优分配方案为：

x1*=1，由于s2=s1-x1*=6-1=5，查第二个表可知x2*=5，s3=s2-x2*=5-5=0

即得甲公司分配1车，乙公司分配5车，丙公司不分配，总盈利为17。

3.2 设备更新问题

现以一台机器设备为例，在使用过程中，每年都面临继续使用或更新的决策，要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年内总效益最大。

n为设备计划使用年数。

Ik（t）为第k年（阶段）机器役龄为t年的一台机器运行（在使用一年）所得的收入。

Ok（t）为第k年机器役龄为t年的一台机器运行（再使用一年）时所需运行的费用（或维修费用）。

Ck（t）为第k年机器役龄为t年的一台机器更新时所需的净费用（处理一台役龄为t的旧设备，买进一台新设备的更新净费用）。

a为折扣因子，表示一年以后的收入是上一年的a单位。

T为在第一年开始正在使用的机器的役龄。

最优指标函数gk（t）：表示第k年初，使用一台已用了t年的设备，到第n年末的最大收益。

xk（t）表示给出 gk（t）时，在第 k 年开始时的决策（保留或更新）建立动态规划模型如下：

阶段k（k=1，2，…，n）表示计划使用该设备的年限数。

决策变量xk：是第k年初更新，还是保留使用旧设备，分别用R，K表示。

状态转移方程为：

例：假设n=5，a=1，T=1，某台新设备的年收入及运行费用、更新费用如表5，试确定五年内的更新策略，使总效益达到最大。

表5

解：因第k年开始机龄为t年的机器，其制造年序应为k-t年，因此，I5（0）为第五年新产品的收入，即 I5（0）=43，I3（2）为第一年的产品其机龄为 2年的收入，即I3（2）=30，C5（1）是第五年机龄为1年的机器（应为第四年的产品）的更新费用，即C5（1）=41，其余同理类推。

当k=1时，由于设T=1，所以从第五年开始计算时，机器使用了1、2、3、4、5 年，根据递推关系式

最后根据上面的结果反推之，可求得最优策略为

第一年机龄为1，最佳策略为K

第二年机龄为2，最佳策略为R

第三年机龄为1，最佳策略为K

第四年机龄为2，最佳策略为K

第五年机龄为3，最佳策略为K

最大收益为99。

4 总结

动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，在动态规划的设计过程中，阶段的划分和状态的表示是非常重要的两步，这两步会直接影响该问题的计算复杂性，有时候阶段划分或状态表示的不合理还会使得动态规划法不适用。动态规划的优点是最优解是全局最优解，能得到一系列（包括子过程）的最优解，不需要对系统状态转移方程、阶段效应函数等的解析性质作任何假设。缺点是没有统一的标准模型和标准的算法可供使用，应用有局限性。

［1］运筹学[M].3版.清华大学出版社

［2］动态规划案例[OL].百度文库.

［3］运筹学动态规划[OL].百度文库.