《数学建模》课程教学资源（教材讲义）第四章动态规划 dynamic programming.doc_大学文库

第四章动态规划 §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)，用

-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 递归方程如下方程称为递归方程

-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 计算。基本方程可以表为

动态规划可以看作求决策a13u2…Lun使指标函数Vn(x1,u1,l2…un)达到最优最大或最小)的极值问题,状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件,原则上可以用非线性规划方法求解些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解下面用例子说明例3用动态规划解下列非线性规划 8r(ur: lk=a,u≥0. 其中g4(l4)为任意的已知函数。解按变量u的序号划分阶段,看作n段决策过程。设状态为x1,x2,…,xn,取问题中的变量1,l2 为决策。状态转移方程为 x=dx=x ,k=1,2,…,n 取gA(uk)为阶段指标,最优值函数的基本方程为(注意到xn+1=0) f(xk=max [g, (xk)+fr () 0≤xk≤a,k=n,n-1…2,1 fn+1(0)=0 按照逆序解法求出对应于x每个取值的最优决策u4(xk),计算至f1(a)后即可利用状态转移方程得到最优状态序列{x}和最优决策序列{u4(x)} 与静态规划相比,动态规划的优越性在于: (i)能够得到全局最优解。由于约束条件确定的约束集合往往很复杂,即使指标函数较简单,用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为系列结构相似的子问题,每个子问题的变量个数大大减少,约束集合也简单得多,易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题,可以对每个子过程用枚举法求解,而约束条件越多,决策的搜索范围越小, 求解也越容易。对于这类问题,动态规划通常是求全局最优解的唯一方法 (i)可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同,动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要这样的解族,即使不需要,它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时,这样的解族可以用来寻找次优策略 (ⅲi)能够利用经验提高求解效率。如果实际问题本身就是动态的,由于动态规划方法反映了过程逐段演变的前后联系和动态特征,在计算中可以利用实际知识和经验提髙求解效率。如在策略迭代法中,实际经验能够帮助选择较好的初始策略,提高收敛速动态规划的主要缺点是: (ⅱ)没有统一的标准模型,也没有构造模型的通用方法,甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析,构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力 -40

-40- 动态规划可以看作求决策 u u un , , , 1 2  使指标函数 ( , , , ) 1n 1 u1 u2 un V x ，  达到最优（最大或最小）的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件，原则上可以用非线性规划方法求解。一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。下面用例子说明。例 3 用动态规划解下列非线性规划 = n k gk uk 1 max ( ) ； s.t. = =  n k uk a uk 1 , 0 . 其中 ( ) gk uk 为任意的已知函数。解按变量 k u 的序号划分阶段，看作 n 段决策过程。设状态为 n x , x , , x 1 2  ，取问题中的变量 u u un , , , 1 2  为决策。状态转移方程为 , , 1,2, , . x1 = a xk +1 = xk −uk k =  n 取 ( ) gk uk 为阶段指标，最优值函数的基本方程为（注意到 xn+1 = 0 ） ( ) max [ ( ) ( )] 1 1 0 + +   = k k + k k u x k k f x g x f x k k ； 0  xk  a, k = n,n −1,  ,2,1 ； f n+1 (0) = 0. 按照逆序解法求出对应于 k x 每个取值的最优决策 ( ) * k k u x ，计算至 ( ) f 1 a 后即可利用状态转移方程得到最优状态序列 { } * k x 和最优决策序列 { ( )} * * k k u x 。与静态规划相比，动态规划的优越性在于：（i）能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。（ii）可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。（iii）能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提高求解效率。如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速度速度。动态规划的主要缺点是：（i）没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力

和灵活的技巧性,这就带来了应用上的局限性 (i)用数值方法求解时存在维数灾( curse of dimensionality)。若一维状态变量有m 个取值,那么对于n维问题,状态x就有m”个值,对于每个状态值都要计算、存储函数f(x),对于n稍大(即使n=3)的实际问题的计算往往是不现实的。日前还没有克服维数灾的有效的一般方法 §5若干典型问题的动态规划模型 5.1最短路线问题寸于例1一类最短路线问题( shortest Path Problem),阶段按过程的演变划分,状态由各段的初始位置确定,决策为从各个状态出发的走向,即有xk+1=u4(xk),阶段指标为相邻两段状态间的距离d4(xk2u4(x),指标函数为阶段指标之和,最优值函数 f4(xk)是由x出发到终点的最短距离(或最小费用),基本方程为 f(xr=mn [d (k, u,(xr))+f, (xkDlk=n,, 1; fn+1(xn+1)=0 利用这个模型可以算出例1的最短路线为ABC2DE2F2G,相应的最短距离为 52生产计划问题对于例2一类生产计划问题( Production planning problem),阶段按计划时间自然划分,状态定义为每阶段开始时的储存量x,决策为每个阶段的产量u,记每个阶段的需求量(已知量)为dk,则状态转移方程为 xk+1=xk+l4-dk,x≥0.k=1,2,…,n (5) 设每阶段开工的固定成本费为a,生产单位数量产品的成本费为b,每阶段单位数量产品的储存费为C,阶段指标为阶段的生产成本和储存费之和,即 (4)=+{+,“4>0 指标函数V为v4之和。最优值函数f(x)为从第k段的状态x出发到过程终结的最小费用,满足 f4(x)=m[v4(xk,uk)+fk+1(xk+1),k=n,…1 其中允许决策集合U由每阶段的最大生产能力决定。若设过程终结时允许存储量为 x21,则终端条件是 (7) (5)~(7)构成该问题的动态规划模型 53资源分配问题种或几种资源(包括资金)分配给若干用户,或投资于几家企业,以获得最大的效益。资源分配问题( resource allocating Problem)可以是多阶段决策过程,也可以是静态规划问题,都能构造动态规划模型求解。下面举例说明。例4机器可以在高、低两种负荷下生产。u台机器在高负荷下的年产量是g(u)

-41- 和灵活的技巧性，这就带来了应用上的局限性。（ii）用数值方法求解时存在维数灾（curse of dimensionality）。若一维状态变量有 m 个取值，那么对于 n 维问题，状态 k x 就有 n m 个值，对于每个状态值都要计算、存储函数 ( ) k k f x ，对于 n 稍大（即使 n = 3 ）的实际问题的计算往往是不现实的。目前还没有克服维数灾的有效的一般方法。 §5 若干典型问题的动态规划模型 5.1 最短路线问题对于例 1 一类最短路线问题（shortest Path Problem），阶段按过程的演变划分，状态由各段的初始位置确定，决策为从各个状态出发的走向，即有 ( ) k 1 k k x = u x + ，阶段指标为相邻两段状态间的距离 ( , ( )) k k k k d x u x ，指标函数为阶段指标之和，最优值函数 ( ) k k f x 是由 k x 出发到终点的最短距离（或最小费用），基本方程为 ( ) min [ ( , ( )) ( )], , ,1; 1 1 ( ) f x dk xk uk xk f k xk k n  u x k k k k = + + + = ( ) 0. f n+1 xn+1 = 利用这个模型可以算出例 l 的最短路线为 AB1C2D1E2F2G ，相应的最短距离为 18。 5.2 生产计划问题对于例 2 一类生产计划问题（Production planning problem），阶段按计划时间自然划分，状态定义为每阶段开始时的储存量 k x ，决策为每个阶段的产量 k u ，记每个阶段的需求量（已知量）为 k d ，则状态转移方程为 , 0, 1,2, , . xk +1 = xk + uk − dk xk  k =  n (5) 设每阶段开工的固定成本费为 a ，生产单位数量产品的成本费为 b ，每阶段单位数量产品的储存费为 c ，阶段指标为阶段的生产成本和储存费之和，即    +  = + 0 , 0 ( , ) k k k k k k a bu u v x u cx (6) 指标函数 Vkn 为 k v 之和。最优值函数 ( ) k k f x 为从第 k 段的状态 k x 出发到过程终结的最小费用，满足 ( ) min [ ( , ) ( )], , ,1. f x vk xk uk f k 1 xk 1 k n  u U k k k k = + + + =  其中允许决策集合 Uk 由每阶段的最大生产能力决定。若设过程终结时允许存储量为 0 n+1 x ，则终端条件是 ( ) 0. 0 f n+1 xn+1 = （7）（5）~（7）构成该问题的动态规划模型。 5.3 资源分配问题一种或几种资源（包括资金）分配给若干用户，或投资于几家企业，以获得最大的效益。资源分配问题（resource allocating Problem）可以是多阶段决策过程，也可以是静态规划问题，都能构造动态规划模型求解。下面举例说明。例 4 机器可以在高、低两种负荷下生产。 u 台机器在高负荷下的年产量是 g(u)

-42- 在低负荷下的年产量是 h(u) ，高、低负荷下机器的年损耗率分别是 1 a 和 1 b （ 0  b1  a1  1 ）。现有 m 台机器，要安排一个 n 年的负荷分配计划，即每年初决定多少台机器投入高、低负荷运行，使 n 年的总产量最大。如果进一步假设 g(u) = u ， h(u) = u （     0 ），即高、低负荷下每台机器的年产量分别为  和  ，结果将有什么特点。解年度为阶段变量 k = 1,2,  ,n 。状态 k x 为第 k 年初完好的机器数，决策 k u 为第 k 年投入高负荷运行的台数。当 k x 或 k u 不是整数时，将小数部分理解为一年中正常工作时间或投入高负荷运行时间的比例。机器在高、低负荷下的年完好率分别记为 a 和 b ，则 a =1− a1 ， b =1− b1 ，有 a  b 。因为第 k 年投入低负荷运行的机器台数为 k uk x − ，所以状态转移方程是 ( ) k 1 k k uk x + = au + b x − （8）阶段指标 k v 是第 k 年的产量，有 ( , ) ( ) ( ) k k k k k uk v x u = g u + h x − （9）指标函数是阶段指标之和，最优值函数 ( ) k k f x 满足 0 , , ,2,1. ( ) max [ ( , ) ( )], 1 1 0 x m k n  f x v x u f x k k k k k k u x k k k k   = = + + +   (10) 及自由终端条件 ( ) 0, 0 . f n+1 xn+1 =  xn+1  m （11）当 k v 中的 g, h 用较简单的函数表达式给出时，对于每个 k 可以用解析方法求解极值问题。特别，若 g(u) = u ，h(u) = u ，（10）中的 [ ( , ) ( )] k k k k 1 k v x u f x + + 将是 k u 的线性函数，最大值点必在区间 k k 0  u  x 的左端点 uk = 0 或右端点 k k u = x 取得，即每年初将完好的机器全部投入低负荷或高负荷运行。习题四 1. 设某工厂有 1000 台机器，生产两种产品 A、B ，若投入 y 台机器生产 A 产品，则纯收入为 5y ，若投入 y 台机器生产 B 种产品，则纯收入为 4 y ，又知：生产 A 种产品机器的年折损率为 20%，生产 B 产品机器的年折损率为 10%，问在 5 年内如何安排各年度的生产计划，才能使总收入最高？(最好给出 Matlab 的求解程序)。 2. 有四个工人，要指派他们分别完成 4 项工作，每人做各项工作所消耗的时间如下表：工作工人 A B C D 甲乙丙丁 15 19 26 19 18 23 17 21 21 22 16 23 24 18 19 17 问指派哪个人去完成哪项工作，可使总的消耗时间为最小？试对此问题用动态规划方法求解

《数学建模》课程教学资源（教材讲义）第四章 动态规划 dynamic programming

《数学建模》课程教学资源（教材讲义）第四章动态规划 dynamic programming