第七章 动态规划
规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（dynamic programming）同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献。
动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。
动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。
§7.1 动态规划的基本理论
1.1 多阶段决策过程的数学描述 有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。任何一个阶段（stage，即决策点）都是由输入（input）、决策（decision）、状态转移律（transformation function）和输出（output）构成的，如图7-1（a）所示。其中输入和输出也称为状态（state），输入称为输入状态，输出称为输出状态。
输 入 决 策 dn 阶 段 输 出 Sn Stage n Sn+1 状态转移 （a） 图7-1 gn = r(Sn,dn) （b）
由于每一阶段都有一个决策，所以每一阶段都应存在一个衡量决策效益大小的指标函数，这一指标函数称为阶段指标函数，用gn表示。显然gn是状态变量Sn和决策变量dn的函数，即gn = r（Sn，dn），如图7-1（b）所示。显然，输出是输入和决策的函数，即：
Sn?1?f(Sn,dn) （7-1）
式（7-1）即为状态转移律。在由N个阶段构成的过程里，前一个阶段的输出即为后一个阶段的输入。
1.2 动态规划的基本概念
动态规划的数学描述离不开它的一些基本概念与符号，因此有必要在介绍多阶段决策过程的数学描述的基础上，系统地介绍动态规划的一些基本概念。
1． 阶段（stage）
阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，常用k来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，但要便于将问题的过程转化为多阶段决策的过程。对于具有N个阶段的决策过程，其阶段变量k＝1，2，?，N。 2． 状态（state）
状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。状态既反映前面各阶段系列决策的结局，又是本阶段决策的一个出发点和依据；它是各阶段信息的传递点和结合点。各阶段的状态通常用状态变量Sk来加以描述。作为状态应具有这样的性质：如果某阶段状态给定后，则该阶段以后过程的发展不受此阶段以前各阶段状态的影响。换句话说，过程的历史只能通过当前的状态来影响未来，当前的状态是以往历史的一个总结。这个性质称为无后效性（the future is independent of the past）或健忘性（the process is forgetful）。
3． 决策（decision）
决策是指决策者在所面临的若干个方案中做出的选择。决策变量dk表示第k阶段的决策。决策变量dk的取值会受到状态Sk的某种限制，用Dk（Sk）表示第k阶段状态为Sk时决策变量允许的取值范围，称为允许决策集合，因而有dk（Sk）?Dk（Sk）。
4． 状态转移律（transformation function）
状态转移律是确定由一个状态到另一状态演变过程的方程，这种演变的对应关系记为Sk+1 = Tk（Sk , dk）。
5． 策略（policy）与子策略（sub-policy）
由所有阶段决策所组成的一个决策序列称为一个策略，具有N个阶段的动态规划问题的策略可表示为：
{d1(S1),d2(S2),?,dN(SN)}
从某一阶段开始到过程终点为止的一个决策子序列，称为过程子策略或子策略。从第k个阶段起的一个子策略可表示为：
{dk(Sk),dk?1(Sk?1),?,dN(SN)}
6． 指标函数
指标函数有阶段指标函数和过程指标函数之分。阶段指标函数是对应某一阶段决策的效率度量，用gk = r（Sk，dk）来表示；过程指标函数是用来衡量所实现过程优劣的数量指标，是定义在全过程（策略）或后续子过程（子策略）上的一个数量函数，从第k个阶段起的一个子策略所对应的过程指标函数常用Gk,N 来表示，即：
Gk,N?R(Sk,dk,Sk?1,dk?1,?,SN,dN)
构成动态规划的过程指标函数，应具有可分性并满足递推关系；即：
Gk,N?gk?Gk?1,N
这里的?表示某种运算，最常见的运算关系有如下二种：
（1） 过程指标函数是其所包含的各阶段指标函数的“和”，即：
Gk,N??gj
j?kN于是
Gk,N?gk?Gk?1,N
（2） 过程指标函数是其所包含的各阶段指标函数的“积”，即：
Gk,N??gj
j?kN于是
Gk,N?gk?Gk?1,N
7． 最优指标函数
从第k个阶段起的最优子策略所对应的过程指标函数称为最优指标函数，可以用式（7-2）加以表示：
fk(Sk)?opt{gk?gk?1???gN} （7-2）
dk~N其中“opt”是最优化“optimization”的缩写，可根据题意取最大“max”或最小“min”。在不同的问题中，指标函数的含义可能是不同的，它可能是距离、利润、成本、产量或资源量等。
1.3 动态规划的数学模型
动态规划的数学模型除包括式（7-2）外，还包括阶段的划分、各阶段的状态变量和决策变量的选取、允许决策集合和状态转移律的确定等。
如何获得最优指标函数呢？一个N阶段的决策过程，具有如下一些特性： （1） 刚好有N个决策点；
（2） 对阶段k而言，除了其所处的状态Sk和所选择的决策dk外，再没有任何其它
因素影响决策的最优性了；
（3） 阶段k仅影响阶段k?1的决策，这一影响是通过Sk?1来实现的；
（4） 贝尔曼（Bellman）最优化原理：在最优策略的任意一阶段上，无论过去的状态
和决策如何，对过去决策所形成的当前状态而言，余下的诸决策必须构成最优子策略。
根据贝尔曼（Bellman）最优化原理，可以将式（7-2）表示为递推最优指标函数关系式（7-3）或式（7-4）：
fk(Sk)?opt{gk?gk?1???gN}?opt{gk?fk?1(Sk?1)} （7-3）
dk~Ndkfk(Sk)?opt{gk?gk?1???gN}?opt{gk?fk?1(Sk?1)} （7-4）
dk~Ndk利用式（7-3）和式（7-4）可表示出最后一个阶段（第N个阶段，即k=N）的最优指标函数：
fN(SN)?opt{gN?fN?1(SN?1)} （7-5）
dNfN(SN)?opt{gN?fN?1(SN?1)} （7-6）
dN其中fN?1(SN?1)称为边界条件。一般情况下，第N阶段的输出状态SN?1已经不再影响本过程的策略，即式（7-5）中的边界条件fN?1(SN?1)?0，式（7-6）中的边界条件fN?1(SN?1)?1；但当问题第N阶段的输出状态SN?1对本过程的策略产生某种影响时，边界条件fN?1(SN?1)就要根据问题的具体情况取适当的值，这一情况将在后续例题中加以反映。
已知边界条件fN?1(SN?1)，利用式（7-3）或式（7-4）即可求得最后一个阶段的最优指标函数fN(SN)；有了fN(SN)，继续利用式（7-3）或式（7-4）即可求得最后两个阶段的最优指标函数fN?1(SN?1)；有了fN?1(SN?1)，进一步又可以求得最后三个阶段的最优指标函数fN?2(SN?2)；反复递推下去，最终即可求得全过程N个阶段的最优指标函数f1(S1)，从而使问题得到解决。由于上述最优指标函数的构建是按阶段的逆序从后向前进行的，所以也称为动态规划的逆序算法。
通过上述分析可以看出，任何一个多阶段决策过程的最优化问题，都可以用非线性规划（特殊的可以用线性规划）模型来描述；因此，从原则上讲，一般也可以用非线性规划（或线性规划）的方法来求解。那么利用动态规划求解多阶段决策过程有什么优越性、又有什么局限性呢？
动态规划的优点：第一，求解更容易、效率更高。动态规划方法是一种逐步改善法，它把原问题化成一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少得多，约束集合也简单得多，故较易于确定最优解。第二，解的信息更丰富。非线性规划（或线性规划）的方法是对问题的整体进行一次性求解的，因此只能得到全过程的解；而动态规划方
法是将过程分解成多个阶段进行求解的，因此不仅可以得到全过程的解，同时还可以得到所有子过程的解。
动态规划的缺点：第一，没有一个统一的标准模型。由于实际问题不同，其动态规划模型也就各有差异，模型构建存在一定困难。第二，应用条件苛刻。由于构造动态规划模型状态变量必须满足“无后效性”条件，这一条件不仅依赖于状态转移律，还依赖于允许决策集合和指标函数的结构，不少实际问题在取其自然特征作为状态变量时并不满足这一条件，这就降低了动态规划的通用性。第三，状态变量存在“维数障碍”。最优指标函数fk(Sk)是状态变量的函数，当状态变量的维数增加时，最优指标函数的计算量将成指数倍增长；因此，无论是手工计算还是电算“维数障碍”都是无法完全克服的。
§7.2 确定性动态规划问题
确定性动态规划问题即阶段的输出状态完全由其输入状态和决策所决定的动态规划问题。确定性动态规划解决的问题可能包含经济管理的方方面面，可以是最短路线问题，可以是资源配置问题，也可以是其他的规划优化问题。最短路线问题直观、具体地演示了动态规划的基本概念和基本步骤；因此，让我们首先来分析一下最短路线问题。
2-1最短路线问题
[例7-1] 美国黑金石油公司（The Black Gold Petroleum Company）最近在阿拉斯加（Alaska）的北斯洛波（North Slope）发现了大的石油储量。为了大规模开发这一油田，首先必须建立相应的输运网络，使北斯洛波生产的原油能运至美国的3个装运港之一。在油田的集输站（结点C）与装运港（结点P1、P2、P3）之间需要若干个中间站，中间站之间的联通情况如图7-2所示，图中线段上的数字代表两站之间的距离（单位：10千米）。试确定一最佳的输运线路，使原油的输送距离最短。
解：最短路线有一个重要性质，即如果由起点A经过B点和C点到达终点D是一条最短路线，则由B点经C点到达终点D一定是B到D的最短路（贝尔曼最优化原理）。此性质用反证法很容易证明，因为如果不是这样，则从B点到D点有另一条距离更短的路线存在，不妨假设为B—P—D；从而可知路线A—B—P—D比原路线A—B—C—D距离短，这与原路线A—B—C—D是最短路线相矛盾，性质得证。
根据最短路线的这一性质，寻找最短路线的方法就是从最后阶段开始，由后向前逐步递推求出各点到终点的最短路线，最后求得由始点到终点的最短路；即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。按照动态规划的方法，将此过程划分为4个阶段，即阶段变量k?1,2,3,4；取过程在各阶段所处的位置为状态变量Sk，按逆序算法求解。 C 10 8 M11 12 6 M21 6 9 M22 10 M12 9 11 5 11 4 M23 6 k=3 3 M34 k=1 k=2 4 k=4 7 7 M33 5 P3 M31 6 4 M32 7 6 3 8 P1 7 P2