第六章 动态规划第六章 动态规划动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法大约产生于50年代1951年美国数学家贝尔曼（R3>．Bellman）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相联系单阶段问题，然后逐个加以解决与此同时，他提出了解决这类问题的“最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新的方法——动态规划他的名著“动态规划”于1957年出版，该书是动态规划的第一本著作动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中都有广泛的应用，并且获得了显著的效果在企业管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等，所以它是现代企业管理中的一种重要的决策方法许多问题用动态规划的方法去处理，常比线性规划或非线性规划更有成效特别对于离散性的问题，由于解析数学无法施展其术，而动态规划的方法就成为非常有用的工具应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。
因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理因此，读者在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解动态规划模型的分类，根据多阶段决策过程的时间参量是离散的还是连续的变量，过程分为离散决策过程和连续决策过程根据决策过程的演变是确定性的还是随机性的，过程又可分为确定性决策过程和随机性决策过程组合起来就有离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型本部分主要研究离散决策过程，介绍动态规划的基本概念、理论和方法，并通过几个典型的问题来说明它的应用，这些都是整个动态规划的基本内容 第一节 动态规划的基本原理一、引例 ——最短路问题例1 图5.1为一道路网，各路段的长度如图中所示，某人欲从A到J，试为他选择一条最短线为解决这一问题，显然可用直接枚举法，即列出从A到J（沿图中箭头方向前进）的所有路线，分别计算出这些路线的长度，经比较选出其中最短者本问题从A到各个节点的路线数示于图5.1中各节点旁的小圆圈中，可知共有8条路线为清楚起见，将这8条路线分离划出于图5.2中由图5.2右侧标出的各条路线的总长度可知，A—B—E—H—J为最短路，其长度等于9。
由于每条路线均由4段组成，故计算一条路线的长度要做3次加法运算，8条路线共需24次加法运算此外，为决定最短路长还要进行7次比较为减少计算工作量，我们考虑另一种算法用表示从起点A到终点J的最短路长，类似地，用表示从某一节点K到J的最短路长，并用表示节点K到某节点Y的路段长度由于各路段长度已给，故知取决于和，取决于和，取决于和，……，、和则仅取决于，而J为终点，可令=0如此，可按以下顺序逐步进行计算3+0=3=5+0=5=6+0=6=2+3=5算出的最短路线长度等于9，与枚举法结果相同由=9知B在最短路上线，由知E在最短路线上，如此追踪可找出最短路径（在有关数据下加有横线）为A—B—E—H—J该算法仅需14次加法，5次比较，比枚举法计算量少；问题规模越大，计算量的节约越显著可以认为，随问题规模的增加，枚举法的计算量按指数增加，而该方法则按线性增加上述第二种算法采用了由后向前逐阶段递推的方法，它包含了动态规划的基本思想二、动态规划的主要术语为便于下面讨论，先解释动态规划的主要术语，并说明一些有关概念1．阶段（stage）多阶段决策过程包含若干个组成阶段，整个过程是由各个阶段按一定顺序联系起来的统一整体，它由开始阶段出发，按过程进行的方向，由前向后一个阶段一个阶段地推移，直至最后一个阶段结束为止。
若决策者在某一阶段作出了一个决策，则系统此后的发展就要受到这一决策的影响，这个决策的好坏，将影响到此后的决策序列及其效果因此，在作阶段决策时不能不考虑到对后面各阶段的影响而将它单独“最优化”由于最后一个阶段对其它阶段不产生影响，因而可以把它看作是整个系统的一个子问题，而将它子最优化，从而得出这一阶段的相应决策然后，把最后两个阶段看成第二个子问题，利用已得前一子问题子最优化的结果，对其进行子最优化，并得出倒数第二个阶段的相应决策如此继续，直至第一阶段，即可求出全过程的最优决策序列用上述方法，通过由后向前逐阶段求解由后部各阶段（或称后部子过程）构成的子问题，就把求解原来的n阶段问题，简化成了求解n个单阶段子问题图5.3表明了这种求解过程，并且虚线框代表由后部子过程构成的子问题基于以上分析，在用动态规划的方法解决实际问题时，通常都先将原来的问题划分成若干个阶段，并从最后一个阶段开始，由后向前逆向递推寻优求解例1时将整个过程划时代发为四个阶段，第一阶段包括路段AB和AC，第二阶段包括路段BD、BE、CE和CF，第三阶段包括路段DG、EG、EH、EI和FI，第四阶段由路段GJ、HJ和IJ组成（图5.4）。
求最短路时由第四阶段开始，沿与过程行进方向相反的方向逆向递推进行 图5.32．状态（State）状态表示过程（系统）的状况或所处的位置，进行到某一阶段的系统可处于若干个不同的状态在例1中，可把某阶段所含路段的起点（也是前一阶段中路段的终点）定义为该阶段的状态，这样一来，其第一阶段有一个状态：A点；第二阶段有二个状态：B点和C点；……选择的状态构成该阶段的状态集合在例1中，=｛A｝，=｛B，C｝，=｛D，E，F｝，=｛G，H，I｝3．决策（Decision）对于处于某一状态的系统，决策者可以作出不同的决策，而使系统沿着不同的方向演变，结果达到下一阶段的某个状态描述采取不同决策的变量称为决策变量在进行决策时，决策变量的选取要受到某些条件的影响而只能限于某种范围，这一范围构成允许决策集合常用表示阶段的决策变量，表示阶段的允许决策集合，显然，它们都是状态变量的函数若系统在阶段处于状态，则有从n阶段决策过程第一阶段的某一状态出发，逐阶段作出决策构成的策略，称为全过程策略，简称策略，记为 （5.1）而与阶段到最终阶段的后部子过程相对应的策略称为予策略，记为 （5.1）4．指标函数和阶段收益（Return）指标函数是用以衡量多阶段决策过程实现效果的一种数量指标，是定义在全过程和所有后部子过程上的数量函数，显然，它和起始状况以及以后各阶段的决策有关，可表示为=1，2，…，n阶段收益是系统通过某一阶段对于指标函数的贡献，它与所处的状态和决策者的决策有关，若用表示阶段的阶段收益，则可写成 （5.3）在上述最短路问题中，阶段收益是旅行者通过该阶段中某一路段所走的距离，而指标函数则是他从某节点起到达终点所走的距离之和。
对于阶段的某一状态来说，若从它出发并选定了一确定的策略（或后部子策略），则状态就得到了一确定的指标函数值，这个值也称为该状态的值策略不同，得出的状态的值也不同在最优策略下状态的值，是状态的最优值，记为（以后常简记为） 在例1中，节点E的状态的值有三个：7、6、8；节点A的状况的值有八个，而其最优值为9由以上讨论可知，指标函数由阶段收益构成，其间的关系主要有以下两种：（1）指标函数为阶段收益之和 （5.4）（2）指标函数为阶段收益之积 （5.5）三、动态规划的基本原理1．最优性原理（Principle of Optimality）现再看例1的最短路问题，已求出最短路线是A—B—E—H—J我们指出：在最短路线上的任一点，它到终点的最短路也在这条路线上例如点E到终点J的最短路线是E—H—J，而不会是别的，如若不然，A—B—E—H—J就不会是A到J的最短路线，也是其上任一点到终点的最短路线根据以上说明，即可了解下面陈述的最优性原理：在多阶段决策过程中，最优决策序列具有这种性质，即不管该序列上某状态以前的状态和决策如何，余下的决策序列必构成该状态的最优决策序列。
最优性原理是动态规划理论的核心，它是由R．Bellman首先提出的这个原理说明，最优策略的任一后部子策略也是最优的根据这个原理，在用动态规划的方法求解多阶段决策问题时，各状态前面的状态和决策，对其后面的子问题来说，只不过相当于其初始条件而已，并不影响后面过程的最优决策2．动态规划的函数方程由以上说明可知，在用动态规划的方法逐阶段求解n阶段决策问题时，要利用第阶段与第+1阶段之间的如下关系：上述方程为动态规划的函数方程，或称为动态规划的基本方程它反映了一种递推关系，动态规划就是借助于这种递推关系来求解的根据问题的性质，Opt可用max，也可用min对应于式（5.4）和（5.5）这两种情况，有若已知第阶段的状态，则当该阶段的决策确定之后，就完全确定了下一阶段（+1阶段）的状态，故和的函数，即 （5.9）上式称为状态转移方程，或变换方程它给出了状态转移规律四、建立动态规划的数学模型为了用动态规划的方法解决实际问题，首先必须建立动态规划的数学模型这主要指的是解决好以下几个问题1．划分阶段划分阶段是用多阶段决策过程描述一个实际问题的第一步，通常可根据问题的性质，按照时间、空间、变量等进行划分。
2．确定状态变量及状态集合多阶段决策过程的进展，可用各阶段的状态演变来描述因而，先取的状态变量应能反映过程的演变特征，并要满足无后效性的要求所谓无后效性指的是：若已知过程已处于某阶段的某一状态，则该阶段以后过程的演变，就不再受以前各阶段状态的影响这就是说，过程的过去历史只能通过当前的状态去影响它未来的发展，当前状态是未来过程的初始状态在建立实际问题的动态规划模型时，若选取的状态变量不能使它描述的过程具有无后效性，就不能把它作为动态规划模型中的状态变量这时，需要适当改变状态的规定方法，以实现无后效性的要求决定了状态变量之后，还需对实际问题的情况进行分析，以确定状态集合，即各个阶段状态变量的可能取值范围确定决策变量及允许决策集合决策变量是决策者对系统实施控制的手段，它应能体现决策者对系统发展的能控作用在确定允许决策集合时，应考虑到一切可能情况，它通常是由系统状态和最优化的目的所决定的4．建立状态转移方程状态转移方程如式（5.9）所示，它给出了状态转移的规律当阶段的状态变量和决策变量的数值取定时，如果第+1阶段的状态变量的值也随之确定，则称这种多阶段决策过程为确定性多阶段决策过程，；如果对于确定的和，相应的不确定，而是具有某种概论分布的随机变量，则这种多阶段决策过程就是随机性的。
5．确定各阶段的阶段收益。