第四章动态规划 §1引言 1.1动态规划的发展及研究内容 动态规划( dynamic programming)是运筹学的一个分支,是求解多阶段决策问题 的最优化方法。20世纪50年代初R.E. Bellman等人在研究多阶段决策过程 multistep decision process)的优化问题时,提出了著名的最优性原理( principle of optimality),把 多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方 法一动态规划。1957年出版了他的名著《 Dynamic Programming》,这是该领域的第 本著作。 动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了 泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动 态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时 间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为 多阶段决策过程,也可以用动态规划方法方便地求解 应指出,动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是 种特殊算法(如线性规划是一种算法)。因而,它不象线性规划那样有一个标准的数 学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。因此,在学习 时,除了要对基本概念和方法正确理解外,应以丰富的想象力去建立模型,用创造性的 技巧去求解 例1最短路线问题 下面是一个线路网,连线上的数字表示两点之间的距离(或费用)。试寻求一条由A 到G距离最短(或费用最省)的路线 ,Lc 例2生产计划问题 工厂生产某种产品,每单位(千件)的成本为1(千元),每次开工的固定成本为3 (千元),工厂每季度的最大生产能力为6(千件)。经调查,市场对该产品的需求量第 二、三、四季度分别为2,3,2,4(千件)。如果工厂在第一、二季度将全年的需 求都生产出来,自然可以降低成本(少付固定成本费),但是对于第三、四季度才能上 市的产品需付存储费,每季每千件的存储费为0.5(千元)。还规定年初和年末这种产品 均无库存。试制定一个生产计划,即安排每个季度的产量,使一年的总费用(生产成本 和存储费)最少 12决策过程的分类 根据过程的时间变量是离散的还是连续的,分为离散时间决策过程( discrete-time decision process)和连续时间决策过程( continuous-time decision process);根据过程的 演变是确定的还是随机的,分为确定性决策过程( deterministic decision process)和随
-35- 第四章 动态规划 §1 引言 1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解多阶段决策问题 的最优化方法。20 世纪 50 年代初 R. E. Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把 多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方 法—动态规划。1957 年出版了他的名著《Dynamic Programming》，这是该领域的第一 本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广 泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动 态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时 间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为 多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是 一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数 学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习 时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的 技巧去求解。 例 1 最短路线问题 下面是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由 A 到 G 距离最短（或费用最省）的路线。 例 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)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶 段,以便按阶段的次序解优化问题。阶段变量一般用k=1,2…,n表示。在例1中由A 出发为k=1,由B(=1,2)出发为k=2,依此下去从F(=1,2)出发为k=6,共 n=6个阶段。在例2中按照第一、二、三、四季度分为k=1,2,3,4,共四个阶段。 2.1.2状态 状态( state)表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并 且无后效性,即当某阶段的状态变量给定时,这个阶段以后过程的演变与该阶段以前各 阶段的状态无关。通常还要求状态是直接或间接可以观测的。 描述状态的变量称状态变量( state variable)。变量允许取值的范围称允许状态集合 ( set of admissible states)。用xk表示第k阶段的状态变量,它可以是一个数或一个向量 用Xk表示第k阶段的允许状态集合。在例1中x2可取B2B2,或将B定义为 i(=1.2),则x2=1或2,而X2={,2} n个阶段的决策过程有n+1个状态变量,xn+表示xn演变的结果。在例1中x,取 G,或定义为1,即x2=1 根据过程演变的具体情况,状态变量可以是离散的或连续的。为了计算的方便有时 将连续变量离散化;为了分析的方便有时又将离散变量视为连续的。 状态变量简称为状态 2.1.3决策 当一个阶段的状态确定后,可以作出各种选择从而演变到下一阶段的某个状态,这 种选择手段称为决策( decision),在最优控制问题中也称为控制( control)。 描述决策的变量称决策变量( decision variable),变量允许取值的范围称允许决策 集合( set of admissible decisions)。用lk(xk)表示第k阶段处于状态x时的决策变量, 它是xk的函数,用Uk(xk)表示xk的允许决策集合。在例1中2(B)可取C1,C2或C3, 可记作u2()=1,2,3,而U2(1)={12,3} 决策变量简称决策 策略 决策组成的序列称为策略( policy)。由初始状态x;开始的全过程的策略记作 P1n(x1),即 Pn(x1)={1(x1),u2(x2),…,ln(xn)} 由第k阶段的状态xk开始到终止状态的后部子过程的策略记作Pn(xk),即 P(x)={u(x),…un(xn)},k=1,2,…,n-1 类似地,由第k到第j阶段的子过程的策略记作 P(xk)={4(xk)…,(x,) 可供选择的策略有一定的范围,称为允许策略集合( set of admissible policies),用
-36- 机性决策过程（stochastic decision process），其中应用最广的是确定性多阶段决策过程。 §2 基本概念、基本方程和计算方法 2.1 动态规划的基本概念和基本方程 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。 2.1.1 阶段 阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶 段，以便按阶段的次序解优化问题。阶段变量一般用 k =1,2, ,n 表示。在例 1 中由 A 出发为 k =1 ，由 B (i = 1,2) i 出发为 k = 2 ，依此下去从 F (i =1,2) i 出发为 k = 6 ，共 n = 6 个阶段。在例 2 中按照第一、二、三、四季度分为 k =1,2,3,4 ，共四个阶段。 2.1.2 状态 状态（state）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并 且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各 阶段的状态无关。通常还要求状态是直接或间接可以观测的。 描述状态的变量称状态变量（state variable）。变量允许取值的范围称允许状态集合 (set of admissible states)。用 k x 表示第 k 阶段的状态变量，它可以是一个数或一个向量。 用 Xk 表示第 k 阶段的允许状态集合。在例 1 中 2 x 可取 1 2 B ,B ，或将 Bi 定义为 i(i = 1,2) ，则 x2 =1 或 2 ，而 {1,2} X2 = 。 n 个阶段的决策过程有 n +1 个状态变量， n+1 x 表示 n x 演变的结果。在例 1 中 7 x 取 G ，或定义为 1 ，即 x7 = 1。 根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时 将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。 状态变量简称为状态。 2.1.3 决策 当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这 种选择手段称为决策（decision），在最优控制问题中也称为控制（control）。 描述决策的变量称决策变量（decision variable），变量允许取值的范围称允许决策 集合（set of admissible decisions）。用 ( ) k k u x 表示第 k 阶段处于状态 k x 时的决策变量， 它是 k x 的函数，用 ( ) k k U x 表示 k x 的允许决策集合。在例 1 中 ( ) u2 B1 可取 1 2 C ,C 或 C3 ， 可记作 u2 (1) =1,2,3 ，而 (1) {1,2,3} U2 = 。 决策变量简称决策。 2.1.4 策略 决策组成的序列称为策略（policy）。由初始状态 1 x 开始的全过程的策略记作 ( ) 1 1 p x n ，即 ( ) { ( ), ( ), , ( )} 1n 1 1 1 2 2 n n p x = u x u x u x . 由第 k 阶段的状态 k x 开始到终止状态的后部子过程的策略记作 ( ) kn k p x ，即 ( ) { ( ), , ( )} kn k k k n n p x = u x u x ， k = 1,2, ,n −1. 类似地，由第 k 到第 j 阶段的子过程的策略记作 ( ) { ( ), , ( )} kj k k k j j p x = u x u x . 可供选择的策略有一定的范围，称为允许策略集合(set of admissible policies)，用
Pn(x1),P(xk)B(x)表示 21.5.状态转移方程 在确定性过程中,一旦某阶段的状态和决策为已知,下阶段的状态便完全确定。用 状态转移方程( equation of state transition)表示这种演变规律,写作 xk+I=T(k, uk),k=1, 2,...,n (1) 在例1中状态转移方程为xk1=l4(x) 21.6.指标函数和最优值函数 指标函数( objective function)是衡量过程优劣的数量指标,它是定义在全过程和所有 后部子过程上的数量函数,用V(x,l,x1,…,xn+1)表示,k=1,2,…,n。指标函数 应具有可分离性,即V可表为x2,u1,Fk+1n的函数,记为 m(xk,lk2xk+1,…,xm+1)=94(xk,u4k,Vk+m(x+1,Lk+1,xk+2…,xn+1)并且函数9k对于 变量k+1n是严格单调的 过程在第j阶段的阶段指标取决于状态x,和决策u1,用v(x,u1)表示。指标函 数由v,(j=12,…,n)组成,常见的形式有: 阶段指标之和,即 阶段指标之积,即 如(x442x+…,xn)=∏v(x,u1) j=k 阶段指标之极大(或极小),即 (xk,4,xk+13…,xn+1)=mx(mmv,(x,4) 这些形式下第k到第j阶段子过程的指标函数为V(xk,k,xk+1…,x:)。 根据状态转移方程指标函数V还可以表示为状态xk和策略P的函数,即 Vn(xk,Pbn)。在xk给定时指标函数V对p的最优值称为最优值函数( optimal value function),记为fk(xk),即 f4(xk)=opt(xk2P如), 其中opt可根据具体情况取max或min。 2.1.7最优策略和最优轨线 使指标函数J达到最优值的策略是从k开始的后部子过程的最优策略,记作 υωn={u3…,Ln}。Pυ是全过程的最优策略,简称最优策略( optimal policy)。从初始 状态x(=x)出发,过程按照pn和状态转移方程演变所经历的状态序列 {x1,x2…,xn+1}称最优轨线( optimal trajectory)。 21.8递归方程 如下方程称为递归方程
-37- ( ), ( ), ( ) 1n 1 kn k kj k P x P x P x 表示。 2.1.5. 状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用 状态转移方程（equation of state transition）表示这种演变规律，写作 ( , ), 1,2, , . xk +1 = Tk xk uk k = n （1） 在例 1 中状态转移方程为 ( ) k 1 k k x = u x + 。 2.1.6. 指标函数和最优值函数 指标函数(objective function)是衡量过程优劣的数量指标，它是定义在全过程和所有 后部子过程上的数量函数，用 ( , , , , ) kn k k k +1 n+1 V x u x x 表示， k =1,2, ,n 。指标函数 应具有可分离性，即 Vkn 可表为 k uk Vk n x 1 , , + 的函数，记为 ( , , , , ) ( , , ( , , , )) kn k k k+1 n+1 = k k k k+1n k+1 k+1 k+2 n+1 V x u x x x u V x u x x 并且函数 k 对于 变量 Vk +1n 是严格单调的。 过程在第 j 阶段的阶段指标取决于状态 j x 和决策 j u ，用 ( , ) j j u j v x 表示。指标函 数由 v ( j 1,2, ,n) j = 组成，常见的形式有： 阶段指标之和，即 = + + = n j k kn k k k n j j u j V (x ,u , x , , x ) v (x , ) 1 1 ， 阶段指标之积，即 = + + = n j k kn k k k n j j u j V (x ,u , x , , x ) v (x , ) 1 1 ， 阶段指标之极大（或极小），即 ( , , , , ) max(min) ( , ) 1 1 j j j k j n Vkn xk uk xk xn v x u + + = . 这些形式下第 k 到第 j 阶段子过程的指标函数为 ( , , , ) kj k k k+1 j+1 V x u x x 。 根据状态转移方程指标函数 Vkn 还可以表示为状态 k x 和策略 pkn 的函数，即 ( , ) kn k pkn V x 。在 k x 给定时指标函数 Vkn 对 pkn 的最优值称为最优值函数（optimal value function），记为 ( ) k k f x ，即 ( ) opt ( , ) ( ) kn k kn p P x f k xk V x p kn kn k = ， 其中 opt 可根据具体情况取 max 或 min 。 2.1.7 最优策略和最优轨线 使指标函数 Vkn 达到最优值的策略是从 k 开始的后部子过程的最优策略，记作 { , , } * * * pkn = uk un 。 * 1n p 是全过程的最优策略，简称最优策略（optimal policy）。从初始 状 态 ( ) * 1 1 x = x 出发，过程按照 * 1n p 和状态转移方程演变所经历的状态序列 { , , , } * 1 * 2 * 1 n+ x x x 称最优轨线（optimal trajectory）。 2.1.8 递归方程 如下方程称为递归方程
fn+(xn+1)=0或 f4(x)=opt{vk(xk,uk)②fk41(xk+1)}k=n,…1 (2) 在上述方程中,当⑧为加法时取fn1(xk+1)=0:当②为乘法时,取fn+1(x+)=1。 动态规划递归方程是动态规划的最优性原理的基础,即:最优策略的子策略,构成最优 子策略。用状态转移方程(1)和递归方程(2)求解动态规划的过程,是由k=η+1逆 推至k=1,故这种解法称为逆序解法。当然,对某些动态规划问题,也可采用顺序解 法。这时,状态转移方程和递归方程分别为: k=Tk+(xk+1,uk+1),k=1,…,H f(x1)=0或1 fk+1(xk+1)=opt{vk+1(xk+1,uk+1)②f(x)},k=1,…, +∈Uk(xk) 纵上所述,如果一个问题能用动态规划方法求解,那么,我们可以按下列步骤,首 先建立起动态规划的数学模型: (i)将过程划分成恰当的阶段 (ⅱi)正确选择状态变量xk’使它既能描述过程的状态,又满足无后效性,同时确 定允许状态集合Xk (ⅲi)选择决策变量u’确定允许决策集合Uk(x)。 (ⅳv)写出状态转移方程。 (v)确定阶段指标vk(xk,lk)及指标函数的形式(阶段指标之和,阶段指标之 积,阶段指标之极大或极小等)。 (ⅵi)写出基本方程即最优值函数满足的递归方程,以及端点条件 §3逆序解法的计算框图 以自由终端、固定始端、指标函数取和的形式的逆序解法为例给出计算框图,其它 情况容易在这个基础上修改得到。 般化的自由终端条件为 fn+1(xn+;)=q(xn+1),i=1,2,…,nt1 (3) 其中φ为已知。固定始端条件可表示为X1={x1}={x1}。 如果状态κ和决策以是连续变量,用数值方法求解时需按照精度要求进行离散 化。设状态x的允许集合为 Xk={xh|i=1,2,…,nk},k=12,…,n 决策l5(x)的允许集合为 U={u|j=1,2,…,n},=12.…n,k=1,2 状态转移方程和阶段指标应对xk的每个取值x和u的每个取值u计算,即 T=T4(x,u),v=v(x,u)。最优值函数应对x的每个取值x计算。基本方 程可以表为
-38- = = = + + + + ( ) opt { ( , ) ( )}, , ,1 ( ) 0 1 1 1 ( ) 1 1 f x v x u f x k n f x k k k k k u U x k k n n k k k 或 （2） 在上述方程中，当 为加法时取 f n+1 (xk +1 ) = 0 ；当 为乘法时，取 f n+1 (xk +1 ) =1。 动态规划递归方程是动态规划的最优性原理的基础，即：最优策略的子策略，构成最优 子策略。用状态转移方程（1）和递归方程（2）求解动态规划的过程，是由 k = n +1 逆 推至 k =1 ，故这种解法称为逆序解法。当然，对某些动态规划问题，也可采用顺序解 法。这时，状态转移方程和递归方程分别为： xk = Tk+1 (xk+1 ,uk+1 ), k = 1, ,n ， = = = + + + + + + + + f x v x u f x k n f x k k k k k u U x k k k k k ( ) opt { ( , ) ( )}, 1, , ( 0 1 1 1 1 ( ) 1 1 1 1 1 1 1 ） 或 纵上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列步骤，首 先建立起动态规划的数学模型： （i）将过程划分成恰当的阶段。 （ii）正确选择状态变量 k x ，使它既能描述过程的状态，又满足无后效性，同时确 定允许状态集合 Xk 。 （iii）选择决策变量 k u ，确定允许决策集合 ( ) k k U x 。 （iv）写出状态转移方程。 （v）确定阶段指标 ( , ) k k uk v x 及指标函数 Vkn 的形式（阶段指标之和，阶段指标之 积，阶段指标之极大或极小等）。 （vi）写出基本方程即最优值函数满足的递归方程，以及端点条件。 §3 逆序解法的计算框图 以自由终端、固定始端、指标函数取和的形式的逆序解法为例给出计算框图，其它 情况容易在这个基础上修改得到。 一般化的自由终端条件为 1 1 1 1 ( ) ( ), 1,2, , n+ n+ i = n+ i = nn+ f x x i (3) 其中 为已知。固定始端条件可表示为 { } { } * 1 1 1 X = x = x 。 如果状态 k x 和决策 k u 是连续变量，用数值方法求解时需按照精度要求进行离散 化。设状态 k x 的允许集合为 Xk = {xki | i =1,2, ,nk }, k =1,2, ,n . 决策 ( ) ki ki u x 的允许集合为 U u j nki i nk k n j ki ki { | 1,2, , }, 1,2, , , 1,2, , = ( ) = = = . 状态转移方程和阶段指标应对 k x 的每个取值 ki x 和 ki u 的每个取值 ( j) uki 计算，即 ( , ) ( j) k k ki uki T = T x ， ( , ) ( j) k ki uki v = v x 。最优值函数应对 k x 的每个取值 ki x 计算。基本方 程可以表为
f(x2)=v4(x,u4)+f4(T4(x,l) f (xk)=opt(xk), (4) n2;,l k 按照(3),(4)逆向计算出f(x1),为全过程的最优值。记状态x的最优决策为 (xk),由x和6(x)按照状态转移方程计算出最优状态,记作x。并得到相应的 最优决策,记作(x)。于是最优策略为{un1(x1),n2(x2),…,u2(x 算法程序的框图如下 fF(xn)=v,(rk,u) 虞a:(x:) +f+1(T(x+ x+=7x;,a(x) 是 fa Cru ) opt fuGEn) 存/(x),an 否 Lk+1 i ti+l 输出k,x,M(x) 是==k-1 图的左边部分是函数序列的递推计算,可输出全过程最优值f(x1),如果需要还 可以输出后部子过程最优值函数序列f(xk)和最优决策序列u(x)。计算过程中存 f4(x)是备计算∫-1之用,在∫1算完后可用f1将f替换掉;存u4(xk)是备右边 部分读u4(x)之用 图的右边部分是最优状态和最优决策序列的正向计算,可输出最优策略 {x2(x2),u2(x2)…,un(x}和最优轨线{x1,x2,…,x}。 §4动态规划与静态规划的关系 动态规划与静态规划(线性和非线性规划等)研究的对象本质上都是在若干约束条 件下的函数极值问题。两种规划在很多情况下原则上可以相互转换
-39- 1,2, , , 1,2, , , , ,2,1. ( ) opt ( ), ( ) ( , ) ( ( , )), ( ) ( ) 1 ( ) ( ) j n i n k n f x f x f x v x u f T x u ki k ki j k j k ki j k k ki ki j ki k ki ki j k = = = = = + + （4） 按照（3），（4）逆向计算出 ( ) * 1 1 f x ，为全过程的最优值。记状态 ki x 的最优决策为 ( ) * ki ki u x ，由 * 1 x 和 ( ) * ki ki u x 按照状态转移方程计算出最优状态，记作 * k x 。并得到相应的 最优决策，记作 ( ) * * k k u x 。于是最优策略为 { ( ), ( ), , ( )} * * * 2 * 2 * 1 * 1 n n u x u x u x 。 算法程序的框图如下。 图的左边部分是函数序列的递推计算，可输出全过程最优值 ( ) * 1 1 f x ，如果需要还 可以输出后部子过程最优值函数序列 ( ) k ki f x 和最优决策序列 ( ) * k ki u x 。计算过程中存 ( ) k ki f x 是备计算 k −1 f 之用，在 k −1 f 算完后可用 k −1 f 将 k f 替换掉；存 ( ) * k ki u x 是备右边 部分读 ( ) * * k k u x 之用。 图的右边部分是最优状态和最优决策序列的正向计算，可输出最优策略 { ( ), ( ), , ( )} * * * 2 * 2 * 1 * 1 n n u x u x u x 和最优轨线 { , , , } * * 2 * 1 n x x x 。 §4 动态规划与静态规划的关系 动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条 件下的函数极值问题。两种规划在很多情况下原则上可以相互转换