1、第七章 动态规划规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果
2、。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（dynamic programming）同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划） 。当然，由于动态规划不是一种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman
3、） 。20世纪 40 年代末 50 年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957 年贝尔曼发表了数篇研究论文，并出版了他的第一部著作动态规划 。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961 年贝尔曼出版了他的第二部著作，并于 1962 年同杜瑞佛思（Dreyfus）合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten） 。爱尔思先后于 1961 年和 1964 年出版了两部关于动态
4、规划的著作，并于 1964 年同尼母霍思尔（Nemhauser） 、威尔德（ Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献。动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离散的问题，由
5、于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。7.1 动态规划的基本理论1.1 多阶段决策过程的数学描述有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。任何一个阶段（ stage，即决策点）都是由输入（ input） 、决策（ decision） 、状态转移律（ transformati
6、on function）和输出（ output）构成的，如图 7-1（a）所示。其中输入和输出也称为状态（ state） ，输入称为输入状态，输出称为输出状态。图 7-1由于每一阶段都有一个决策，所以每一阶段都应存在一个衡量决策效益大小的指标函数，这一指标函数称为阶段指标函数，用 gn表示。显然 gn是状态变量 Sn和决策变量 dn的函数，即 gn = r（ Sn， dn） ，如图 7-1（b）所示。显然，输出是输入和决策的函数，即：（7-1）),(1ndSf式（7-1）即为状态转移律。在由 N 个阶段构成的过程里，前一个阶段的输出即为后一个阶段的输入。1.2 动态规划的基本概念动态规划的数学
7、描述离不开它的一些基本概念与符号，因此有必要在介绍多阶段决策过程的数学描述的基础上，系统地介绍动态规划的一些基本概念。1 阶段（ stage）阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，常用 k 来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，但要便于将问题的过程转化为多阶段决策的过程。对于具有 N 个阶段的决策过程，其阶段变量 k1，2， N。2 状态（ state）状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。状态既反映前面各阶段系列决策的结局，又是本阶段决策的一个出发点和依据；它是各阶段信息的传递点和结合点。各阶段的状态通常用状态变
8、量 Sk来加以描述。作为状态应具有这样的性质：如果某阶段状态给定后，则该阶段以后过程的发展不受此阶段以前各阶段状态的影响。换句话说，过程的历史只能通过当前的状态来影响未来，当前的状态是以往历史的一个总结。这个性质称为无后效性（ the future is independent of the past）或健忘性（ the process is forgetful） 。3 决策（ decision）决策是指决策者在所面临的若干个方案中做出的选择。决策变量 dk表示第 k 阶段的决策。决策变量 dk的取值会受到状态 Sk的某种限制，用 Dk（ Sk）表示第 k 阶段状态为 Sk时决策变量允许的取值
9、范围，称为允许决策集合，因而有 dk（ Sk） Dk（ Sk） 。4 状态转移律（ transformation function）状态转移律是确定由一个状态到另一状态演变过程的方程，这种演变的对应关系记为Sk+1 = Tk（ Sk , dk） 。输 出输 入决 策阶 段状态转移（a）Sn+1SndnStage ngn = r(Sn,dn)（b）5 策略（ policy）与子策略（ sub-policy）由所有阶段决策所组成的一个决策序列称为一个策略，具有 N 个阶段的动态规划问题的策略可表示为： )(,)(,21NSdSd从某一阶段开始到过程终点为止的一个决策子序列，称为过程子策略或子策略。
10、从第k 个阶段起的一个子策略可表示为： )(,)(),(1Nkk6 指标函数指标函数有阶段指标函数和过程指标函数之分。阶段指标函数是对应某一阶段决策的效率度量，用 gk = r（ Sk， dk）来表示；过程指标函数是用来衡量所实现过程优劣的数量指标，是定义在全过程（策略）或后续子过程（子策略）上的一个数量函数，从第 k 个阶段起的一个子策略所对应的过程指标函数常用 Gk,N 来表示，即： ),(1, NkkNk dSRG构成动态规划的过程指标函数，应具有可分性并满足递推关系；即： kkg,1, 这里的 表示某种运算，最常见的运算关系有如下二种：（1） 过程指标函数是其所包含的各阶段指标函数的“
11、和” ，即：NkjjkgG,于是 NkNk,1, （2） 过程指标函数是其所包含的各阶段指标函数的“积” ，即：kjjNkgG,于是 NkNk,1, 7 最优指标函数从第 个阶段起的最优子策略所对应的过程指标函数称为最优指标函数，可以用式k（7-2）加以表示：（7-2）)(1 Nkdk ggoptSfNk 其中“ opt”是最优化“ optimization”的缩写，可根据题意取最大“ max”或最小“ min”。在不同的问题中，指标函数的含义可能是不同的，它可能是距离、利润、成本、产量或资源量等。1.3 动态规划的数学模型动态规划的数学模型除包括式（7-2）外，还包括阶段的划分、各阶段的状态
12、变量和决策变量的选取、允许决策集合和状态转移律的确定等。如何获得最优指标函数呢？一个 阶段的决策过程，具有如下一些特性：N（1） 刚好有 个决策点；（2） 对阶段 而言，除了其所处的状态 和所选择的决策 外，再没有任何其它kkSkd因素影响决策的最优性了；（3） 阶段 仅影响阶段 的决策，这一影响是通过 来实现的；11S（4） 贝尔曼（ Bellman）最优化原理：在最优策略的任意一阶段上，无论过去的状态和决策如何，对过去决策所形成的当前状态而言，余下的诸决策必须构成最优子策略。根据贝尔曼（ Bellman）最优化原理，可以将式（7-2）表示为递推最优指标函数关系式（7-3）或式（7-4）：（
13、7-3）)()( 11 kkdNkdk SfgoptgoptSfNk （7-4） kk 利用式（7-3）和式（7-4）可表示出最后一个阶段（第 N 个阶段，即 k=N）的最优指标函数：（7-5）)()(1NNdNSfgoptSf（7-6）N其中 称为边界条件。一般情况下，第 阶段的输出状态 已经不再影响本)(1Nf 1NS过程的策略，即式（7-5）中的边界条件 ，式（7-6）中的边界条件0)(1NSf；但当问题第 阶段的输出状态 对本过程的策略产生某种影响时，边1Sf界条件 就要根据问题的具体情况取适当的值，这一情况将在后续例题中加以反)(1N映。已知边界条件 ，利用式（7-3）或式（7-4）
14、即可求得最后一个阶段的最优)(1NSf指标函数 ；有了 ，继续利用式（7-3）或式（7-4）即可求得最后两个阶)(Nf段的最优指标函数 ；有了 ，进一步又可以求得最后三个阶段的最优f )(1NSf指标函数 ；反复递推下去，最终即可求得全过程 个阶段的最优指标函数2f，从而使问题得到解决。由于上述最优指标函数的构建是按阶段的逆序从后向前进)(1Sf行的，所以也称为动态规划的逆序算法。通过上述分析可以看出，任何一个多阶段决策过程的最优化问题，都可以用非线性规划（特殊的可以用线性规划）模型来描述；因此，从原则上讲，一般也可以用非线性规划（或线性规划）的方法来求解。那么利用动态规划求解多阶段决策过程有
15、什么优越性、又有什么局限性呢？动态规划的优点：第一，求解更容易、效率更高。动态规划方法是一种逐步改善法，它把原问题化成一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少得多，约束集合也简单得多，故较易于确定最优解。第二，解的信息更丰富。非线性规划（或线性规划）的方法是对问题的整体进行一次性求解的，因此只能得到全过程的解；而动态规划方法是将过程分解成多个阶段进行求解的，因此不仅可以得到全过程的解，同时还可以得到所有子过程的解。动态规划的缺点：第一，没有一个统一的标准模型。由于实际问题不同，其动态规划模型也就各有差异，模型构建存在一定困难。第二，应用条件苛刻。由于构造动态规划模型状态变
16、量必须满足“无后效性”条件，这一条件不仅依赖于状态转移律，还依赖于允许决策集合和指标函数的结构，不少实际问题在取其自然特征作为状态变量时并不满足这一条件，这就降低了动态规划的通用性。第三，状态变量存在“维数障碍” 。最优指标函数是状态变量的函数，当状态变量的维数增加时，最优指标函数的计算量将成指数倍)(kSf增长；因此，无论是手工计算还是电算“维数障碍”都是无法完全克服的。7.2 确定性动态规划问题确定性动态规划问题即阶段的输出状态完全由其输入状态和决策所决定的动态规划问题。确定性动态规划解决的问题可能包含经济管理的方方面面，可以是最短路线问题，可以是资源配置问题，也可以是其他的规划优化问题。
17、最短路线问题直观、具体地演示了动态规划的基本概念和基本步骤；因此，让我们首先来分析一下最短路线问题。2-1 最短路线问题例 7-1 美国黑金石油公司（ The Black Gold Petroleum Company）最近在阿拉斯加（ Alaska）的北斯洛波（ North Slope）发现了大的石油储量。为了大规模开发这一油田，首先必须建立相应的输运网络，使北斯洛波生产的原油能运至美国的 3 个装运港之一。在油田的集输站（结点 C）与装运港（结点 P1、 P2、 P3）之间需要若干个中间站，中间站之间的联通情况如图 7-2 所示，图中线段上的数字代表两站之间的距离（单位：10 千米） 。试确
18、定一最佳的输运线路，使原油的输送距离最短。解：最短路线有一个重要性质，即如果由起点 A 经过 B 点和 C 点到达终点 D 是一条最短路线，则由 B 点经 C 点到达终点 D 一定是 B 到 D 的最短路（贝尔曼最优化原理） 。此性质用反证法很容易证明，因为如果不是这样，则从 B 点到 D 点有另一条距离更短的路线存在，不妨假设为 BPD；从而可知路线 ABPD 比原路线 ABCD 距离短，这与原路线 ABCD 是最短路线相矛盾，性质得证。根据最短路线的这一性质，寻找最短路线的方法就是从最后阶段开始，由后向前逐步递推求出各点到终点的最短路线，最后求得由始点到终点的最短路；即动态规划的方法是从终
19、点逐段向始点方向寻找最短路线的一种方法。按照动态规划的方法，将此过程划分为4 个阶段，即阶段变量 ；取过程在各阶段所处的位置为状态变量 ，按逆序算4,321k kS法求解。CP3P2P1M11M12M21M22M23M31M32M33M3410128691110769751146864377 6534k=1 k=2 k=3 k=4图 7-2当 时：4k由结点 M31到达目的地有两条路线可以选择，即选择 P1或 P2；故：选择 P268min)(314Sf由结点 M32到达目的地有三条路线可以选择，即选择 P1、 P2或 P3；故：选择 P2374in)(324Sf由结点 M33到达目的地也有三
20、条路线可以选择，即选择 P1、 P2或 P3；故：选择 P356min)(34Sf由结点 M34到达目的地有两条路线可以选择，即选择 P2或 P3；故：选择 P24in)(344Sf当 时：3k由结点 M21到达下一阶段有三条路线可以选择，即选择 M31、 M32或 M33；故：选择 M32105637min)(213 Sf由结点 M22到达下一阶段也有三条路线可以选择，即选择 M31、 M32或 M33；故：选择 M32或 M33105379in)(23Sf由结点 M23到达下一阶段也有三条路线可以选择，即选择 M32、 M33或 M34；故：选择 M33或 M34936541min)(23
21、3 MSf当 时：2k由结点 M11到达下一阶段有两条路线可以选择，即选择 M21或 M22；故：选择 M221608in)(12 Sf由结点 M12到达下一阶段也有两条路线可以选择，即选择 M22或 M23；故：选择 M2291mi)(122f当 时：1k由结点 C 到达下一阶段有两条路线可以选择，即选择 M11或 M12；故：选择 M11281906in)(1CSf从而通过顺序（计算的反顺序）追踪（黑体标示）可以得到两条最佳的输运线路： CM11M22M32P2； CM11M22M33P3。最短的输送距离是 280 千米。2-2 资源分配问题所谓资源分配问题，就是将一定数量的一种或若干种资
22、源（如原材料、机器设备、资金、劳动力等）恰当地分配给若干个使用者，以使资源得到最有效地利用。设有 m 种资源，总量分别为 bi（ i = 1,2, m） ，用于生产 n 种产品，若用 xij代表用于生产第 j 种产品的第 i 种资源的数量（ j = 1,2, n） ，则生产第 j 种产品的收益是其所获得的各种资源数量的函数，即 gj = f（ x1j,x2j, xmj） 。由于总收益是 n 种产品收益的和，此问题可用如下静态模型加以描述： njjgz1maxinjib1 ),2(m0ijx ),1;,nji 若 xij是连续变量，当 gj = f（ x1j,x2j, xmj）是线性函数时，该模
23、型是线性规划模型；当 gj = f（ x1j,x2j, xmj）是非线性函数时，该模型是非线性规划模型。若 xij是离散变量或（和） gj = f（ x1j,x2j, xmj）是离散函数时，此模型用线性规划或非线性规划来求解都将是非常麻烦的。然而在此情况下，由于这类问题的特殊结构，可以将它看成为一个多阶段决策问题，并利用动态规划的递推关系来求解。本教材只考虑一维资源的分配问题，设状态变量 Sk表示分配于从第 k 个阶段至过程最终（第 N 个阶段）的资源数量，即第 k 个阶段初资源的拥有量；决策变量 xk表示第 k 个阶段资源的分配量。于是有状态转移律： kkxS1允许决策集合： 0|)(kkk
24、D最优指标函数（动态规划的逆序递推关系式）：)()(max)( 10kkSk Sfgfk )1,2,(N1N利用这一递推关系式，最后求得的 即为所求问题的最大总收益，下面来看一个)(1Sf具体的例子。例 7-2 某公司拟将 500 万元的资本投入所属的甲、乙、丙三个工厂进行技术改造，各工厂获得投资后年利润将有相应的增长，增长额如表 7-1 所示。试确定 500 万元资本的分配方案，以使公司总的年利润增长额最大。表 7-1投资额 100 万元 200 万元 300 万元 400 万元 500 万元甲 30 70 90 120 130乙 50 100 110 110 110丙 40 60 110
25、120 120解：将问题按工厂分为三个阶段 ，设状态变量 （ ）代表从第3,21kkS3,21个工厂到第 3 个工厂的投资额，决策变量 代表第 个工厂的投资额。于是有状态转移k kx率 、允许决策集合 和递推关系式：kxS1 0|)(kkSD)(ma)(10kxfgfk ),(4当 时：3k )(max0)(ax)( 3303 33 ggSf SS于是有表 7-2，表中 表示第三个阶段的最优决策。x表 7-2 （单位：百万元）3S0 1 2 3 4 5x0 1 2 3 4 5)(3Sf0 0.4 0.6 1.1 1.2 1.2当 时：2k )()(max)( 232022 xSfgSfS于是有
26、表 7-3。表 7-3 （单位：百万元）g2（ x2） +f3（ s2 - x2）x2S2 0 1 2 3 4 5)(2Sfx0 0+0 0 01 0+0.4 0.5+0 0.5 12 0+0.6 0.5+0.4 1.0+0 1.0 23 0+1.1 0.5+0.6 1.0+0.4 1.1+0 1.4 24 0+1.2 0.5+1.1 1.0+0.6 1.1+0.4 1.1+0 1.6 1，25 0+1.2 0.5+1.2 1.0+1.1 1.1+0.6 1.1+0.4 1.1+0 2.1 2当 时：1k )()max)( 121011 xSfgSfS于是有表 7-4。表 7-4g1（ x1）
27、 +f2（ s1 x1）x1S1 0 1 2 3 4 5)(1Sfx5 0+2.1 0.3+1.6 0.7+1.4 0.9+1.0 1.2+0.5 1.3+0 2.1 0，2然后按计算表格的顺序反推算，可知最优分配方案有两个：（1）甲工厂投资 200 万元，乙工厂投资 200 万元，丙工厂投资 100 万元；（2）甲工厂没有投资，乙工厂投资 200 万元，丙工厂投资 300 万元。按最优分配方案分配投资（资源） ，年利润将增长 210 万元。这个例于是决策变量取离散值的一类分配问题，在实际问题中，相类似的问题还有销售店的布局（分配）问题、设备或人力资源的分配问题等。在资源分配问题中，还有一种决
28、策变量为连续变量的资源分配问题，请见例 7-3。例 7-3 机器负荷分配问题。某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量（件）函数为 ，其中 为投入高负荷生产的机器数量，年xg81度完好率 （年底的完好设备数等于年初完好设备数的 70%） ；在低负荷下生产的产7.0量（件）函数为 ，其中 为投入低负荷生产的机器数量，年度完好率 。yg52 9.0假定开始生产时完好的机器数量为 1000 台，试问每年应如何安排机器在高、低负荷下的生产，才能使 5 年生产的产品总量最多？解：设阶段 表示年度（ ） ；状态变量 为第 年度初拥有的完好机器k5,4321kkS数量（同时也是第
29、 年度末时的完好机器数量） 。决策变量 为第 年度分配高负荷下x生产的机器数量，于是 为该年度分配在低负荷下生产的机器数量。这里的 和kxS kS均为连续变量，它们的非整数值可以这样理解：如 就表示一台机器在第 年度kx 6.0kSk中正常工作时间只占全部时间的 60%； 就表示一台机器在第 年度中只有 30%的工3.0kxk作时间在高负荷下运转。状态转移方程为： kkkkkk xxSxS 2.9.)(97)(1 允许决策集合： |kSxD设阶段指标 为第 年度的产量，则：),(kQkkkk xS35)(8),( 过程指标是阶段指标的和，即： 5kjjkQ令最优值函数 表示从资源量 出发，采取
30、最优子策略所生产的产品总量，因而有)(kSfS逆推关系式： )2.09.(35max1)( kkkkSDxSfkk 边界条件 。0)(6f当 时：5k 35ma)(5065055fSSxSx 因 是关于 的单调递增函数，故取 ，相应有 。)(5f x 8)(f当 时：4k 2.9.(3ma)( 4454044ffSx )0854 xS.12.a404xSx因 是关于 的单调递增函数，故取 ，相应有 ；依次类推，)(4Sf4 446.13)(Sf可求得：当 时： ，3k3 335.7)(f当 时： ，20x2280S当 时： ，1 70.11f计算结果表明最优策略为： ， ， ， ， ；即前x3Sx45Sx两年将全部设备都投入低负荷生产，后三年将全部设备都投入高负荷生产，这样可以使 5年的总产量最大，最大产量是 23700 件。有了上述最优策略，各阶段的状态也就随之确定了，即按阶段顺序计算出各年年初的完好设备数量。 10S902.9.2.9.012 xS 813 567.8.34 35670445 29.9.2.9.0556 xS
