第四章 动态规划 §1 引言 1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解多阶段决策问题的最优化方法。20世纪50年代初R. E. Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。 例1 最短路线问题 下面是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由到距离最短（或费用最省）的路线。  例2 生产计划问题 工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3（千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。 1.2 决策过程的分类 根据过程的时间变量是离散的还是连续的，分为离散时间决策过程（discrete-time decision process）和连续时间决策过程（continuous-time decision process）；根据过程的演变是确定的还是随机的，分为确定性决策过程（deterministic decision process）和随机性决策过程（stochastic decision process），其中应用最广的是确定性多阶段决策过程。 §2 基本概念、基本方程和计算方法 2.1 动态规划的基本概念和基本方程 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。 2.1.1 阶段 阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用表示。在例1中由出发为，由出发为，依此下去从出发为，共个阶段。在例2中按照第一、二、三、四季度分为，共四个阶段。 2.1.2 状态 状态（state）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。 描述状态的变量称状态变量（state variable）。变量允许取值的范围称允许状态集合(set of admissible states)。用表示第阶段的状态变量，它可以是一个数或一个向量。用表示第阶段的允许状态集合。在例1中可取，或将定义为，则或，而。  个阶段的决策过程有个状态变量，表示演变的结果。在例1中取，或定义为，即。 根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。 状态变量简称为状态。 2.1.3 决策 当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）。 描述决策的变量称决策变量（decision variable），变量允许取值的范围称允许决策集合（set of admissible decisions）。用表示第阶段处于状态时的决策变量，它是的函数，用表示的允许决策集合。在例1中可取或，可记作，而。 决策变量简称决策。 2.1.4 策略 决策组成的序列称为策略（policy）。由初始状态开始的全过程的策略记作，即 . 由第阶段的状态开始到终止状态的后部子过程的策略记作，即 ，. 类似地，由第到第阶段的子过程的策略记作 . 可供选择的策略有一定的范围，称为允许策略集合(set of admissible policies)，用表示。 2.1.5. 状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程（equation of state transition）表示这种演变规律，写作  （1） 在例1中状态转移方程为。 2.1.6. 指标函数和最优值函数 指标函数(objective function)是衡量过程优劣的数量指标，它是定义在全过程和所有后部子过程上的数量函数，用表示，。指标函数应具有可分离性，即可表为的函数，记为 并且函数对于变量是严格单调的。 过程在第阶段的阶段指标取决于状态和决策，用表示。指标函数由组成，常见的形式有： 阶段指标之和，即 ， 阶段指标之积，即 ， 阶段指标之极大（或极小），即 . 这些形式下第到第阶段子过程的指标函数为。 根据状态转移方程指标函数还可以表示为状态和策略的函数，即。在给定时指标函数对的最优值称为最优值函数（optimal value function），记为，即 ， 其中可根据具体情况取或。 2.1.7 最优策略和最优轨线 使指标函数达到最优值的策略是从开始的后部子过程的最优策略，记作。是全过程的最优策略，简称最优策略（optimal policy）。从初始状态出发，过程按照和状态转移方程演变所经历的状态序列称最优轨线（optimal trajectory）。 2.1.8 递归方程 如下方程称为递归方程  （2） 在上述方程中，当为加法时取；当为乘法时，取。动态规划递归方程是动态规划的最优性原理的基础，即：最优策略的子策略，构成最优子策略。用状态转移方程（1）和递归方程（2）求解动态规划的过程，是由逆推至，故这种解法称为逆序解法。当然，对某些动态规划问题，也可采用顺序解法。这时，状态转移方程和递归方程分别为： ， 纵上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列步骤，首先建立起动态规划的数学模型： （i）将过程划分成恰当的阶段。 （ii）正确选择状态变量，使它既能描述过程的状态，又满足无后效性，同时确定允许状态集合。 （iii）选择决策变量，确定允许决策集合。 （iv）写出状态转移方程。 （v）确定阶段指标及指标函数的形式（阶段指标之和，阶段指标之积，阶段指标之极大或极小等）。 （vi）写出基本方程即最优值函数满足的递归方程，以及端点条件。 §3 逆序解法的计算框图 以自由终端、固定始端、指标函数取和的形式的逆序解法为例给出计算框图，其它情况容易在这个基础上修改得到。 一般化的自由终端条件为  (3) 其中为已知。固定始端条件可表示为。 如果状态和决策是连续变量，用数值方法求解时需按照精度要求进行离散化。设状态的允许集合为 . 决策的允许集合为 . 状态转移方程和阶段指标应对的每个取值和的每个取值计算，即，。最优值函数应对的每个取值计算。基本方程可以表为  （4） 按照（3），（4）逆向计算出，为全过程的最优值。记状态的最优决策为，由和按照状态转移方程计算出最优状态，记作。并得到相应的最优决策，记作。于是最优策略为。 算法程序的框图如下。  图的左边部分是函数序列的递推计算，可输出全过程最优值，如果需要还可以输出后部子过程最优值函数序列和最优决策序列。计算过程中存是备计算之用，在算完后可用将替换掉；存是备右边部分读之用。 图的右边部分是最优状态和最优决策序列的正向计算，可输出最优策略和最优轨线。 §4 动态规划与静态规划的关系 动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。 动态规划可以看作求决策使指标函数达到最优（最大或最小）的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件，原则上可以用非线性规划方法求解。 一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。下面用例子说明。 例3 用动态规划解下列非线性规划 ； s.t. . 其中为任意的已知函数。 解 按变量的序号划分阶段，看作段决策过程。设状态为，取问题中的变量为决策。状态转移方程为  取为阶段指标，最优值函数的基本方程为（注意到） ； ； . 按照逆序解法求出对应于每个取值的最优决策，计算至后即可利用状态转移方程得到最优状态序列和最优决策序列。 与静态规划相比，动态规划的优越性在于： （i）能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。 （ii）可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。 （iii）能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提高求解效率。如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速度速度。 动态规划的主要缺点是： （i）没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。 （ii）用数值方法求解时存在维数灾（curse of dimensionality）。若一维状态变量有个取值，那么对于维问题，状态就有个值，对于每个状态值都要计算、存储函数，对于稍大（即使）的实际问题的计算往往是不现实的。目前还没有克服维数灾的有效的一般方法。 §5 若干典型问题的动态规划模型 5.1 最短路线问题 对于例1一类最短路线问题（shortest Path Problem），阶段按过程的演变划分，状态由各段的初始位置确定，决策为从各个状态出发的走向，即有，阶段指标为相邻两段状态间的距离，指标函数为阶段指标之和，最优值函数是由出发到终点的最短距离（或最小费用），基本方程为   利用这个模型可以算出例l的最短路线为， 相应的最短距离为18。 5.2 生产计划问题 对于例 2一类生产计划问题（Production planning problem），阶段按计划时间自然划分，状态定义为每阶段开始时的储存量，决策为每个阶段的产量，记每个阶段的需求量（已知量）为，则状态转移方程为  (5) 设每阶段开工的固定成本费为，生产单位数量产品的成本费为，每阶段单位数量产品的储存费为，阶段指标为阶段的生产成本和储存费之和，即  (6) 指标函数为之和。最优值函数为从第段的状态出发到过程终结的最小费用，满足  其中允许决策集合由每阶段的最大生产能力决定。若设过程终结时允许存储量为，则终端条件是  （7） （5）~（7）构成该问题的动态规划模型。 5.3 资源分配问题 一种或几种资源（包括资金）分配给若干用户，或投资于几家企业，以获得最大的效益。资源分配问题（resource allocating Problem）可以是多阶段决策过程，也可以是静态规划问题，都能构造动态规划模型求解。下面举例说明。 例4 机器可以在高、低两种负荷下生产。台机器在高负荷下的年产量是，在低负荷下的年产量是，高、低负荷下机器的年损耗率分别是和（）。现有台机器，要安排一个年的负荷分配计划，即 每年初决定多少台机器投入高、低负荷运行，使年的总产量最大。如果进一步假设，（），即高、低负荷下每台机器的年产量分别为和，结果将有什么特点。 解 年度为阶段变量。状态为第年初完好的机器数，决策为第年投入高负荷运行的台数。当或不是整数时，将小数部分理解为一年中正常工作时间或投入高负荷运行时间的比例。 机器在高、低负荷下的年完好率分别记为和，则，，有。因为第年投入低负荷运行的机器台数为，所以状态转移方程是  （8） 阶段指标是第年的产量，有  （9） 指标函数是阶段指标之和，最优值函数满足  (10) 及自由终端条件  （11） 当中的用较简单的函数表达式给出时，对于每个可以用解析方法求解极值问题。特别，若，，（10）中的 将是的线性函数，最大值点必在区间的左端点或右端点取得，即每年初将完好的机器全部投入低负荷或高负荷运行。 习 题 四 1. 设某工厂有1000台机器，生产两种产品，若投入台机器生产产品，则纯收入为，若投入台机器生产种产品，则纯收入为，又知：生产种产品机器的年折损率为20%，生产产品机器的年折损率为10%，问在5年内如何安排各年度的生产计划，才能使总收入最高？(最好给出Matlab的求解程序)。 2. 有四个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表： 工作 工人      甲 乙 丙 丁 15 19 26 19 18 23 17 21 21 22 16 23 24 18 19 17   问指派哪个人去完成哪项工作，可使总的消耗时间为最小？试对此问题用动态规划方法求解。 3. 为保证某一设备的正常运转，需备有三种不同的零件。若增加备用零件的数量，可提高设备正常运转的可靠性，但增加了费用，而投资额仅为8000元。已知备用零件数与它的可靠性和费用的关系如下表所示。 备件数 增加的可靠性 设备的费用（千元）             0.3 0.4 0.5 0.2 0.5 0.9 0.1 0.2 0.7 1 2 3 3 5 6 2 3 4   现要求在既不超出投资额的限制，又能尽量提高设备运转的可靠性的条件下，问各种零件的备件数量应是多少为好？