《数学模型与数学实验》课程书籍文献（数学建模算法大全）第04章 动态规划

第四章动态规划 §1引言 11 动态规划的发展及研究内容 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初RE.Bellman等人在研究多阶段决策过 程(multistep decision 于，提出了著名的最优性 录理（principle o 逐 求解，创立了解决这 是该领城的第万 《Dynamic Programming》, 动态规刻问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广 泛的应用。例如最短路线、床存管理、资源分配、设备更新、排序、 装等问，用动 态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时 间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为 多阶段决策过程，也可以用动态规划方法方便地求解。 ,一中 线性规划 就划 样有 标准 对基 和方法正确理解外 应 用创造 去求 例1层短路线问 图1是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A 到G距离最短（或费用最省）的路线。 s⑧ @&⑧： @ 6©六 04 6 Q406100 图1最短路线问避 例2 十划问 千元).等度分为 单位件)的成本为1千元每次开工的 成本为 34（千 里 年的 求都生产出来，自然可以降低成本（少付 定成本费)，但是对于第三、四季度才能上 市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产显 均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本 和存储费)最少。 1.2决策过程的分类 根据过程的时间变量是离散的还是连续的，分为离散时间决策过程(discrete-time -56

-56- 第四章 动态规划 §1 引言 1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20 世纪 50 年代初 R. E. Bellman 等人在研究多阶段决策过 程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程 优化问题的新方法—动态规划。1957 年出版了他的名著《Dynamic Programming》，这 是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广 泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动 态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时 间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为 多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是 一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数 学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习 时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的 技巧去求解。 例 1 最短路线问题 图 1 是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由 A 到G 距离最短（或费用最省）的路线。 图 1 最短路线问题 例 2 生产计划问题 工厂生产某种产品，每单位（千件）的成本为 1（千元），每次开工的固定成本为 3 （千元），工厂每季度的最大生产能力为 6（千件）。经调查，市场对该产品的需求量第 一、二、三、四季度分别为 2，3，2，4（千件）。如果工厂在第一、二季度将全年的需 求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上 市的产品需付存储费，每季每千件的存储费为 0.5（千元）。还规定年初和年末这种产品 均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本 和存储费）最少。 1.2 决策过程的分类 根据过程的时间变量是离散的还是连续的，分为离散时间决策过程（discrete-time

decision process)和连续时间决策过程(continuous-time decision process):根据过程的 还是随机的，分为确定性决策 机性决策过程 $2基本概念、基本方程和计算方法 21动态规别的基本概今和基木方积 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。 2.1.1阶段 阶段(s©p)是对整个过程的自然划分。通常根据时间顺序或空间硕序特征来划分阶 段，以使按阶段的次序解优化问题。阶段变量一般用k=1,2,.,n表示。在例1中由A 出发为k=1,由B(i=1,2)出发为k=2,依此下去从F0=1,2)出发为k=6,共 n=6个阶段.。 在例2中按照第一、二、三、四季度分为k=12,34,共四个阶段。 且无后效性， 阶段的状态无关。通常还要求状态是直接或间接可以观测的。 描述状态的变量称状态变量(state variable),变量允许取值的范围称允许状态集合 (set of admissible states)。用x.表示第k阶段的状态变量，它可以是一个数或一个向量 用X表示第k阶段的允许状态集合。在例1中x,可取B,B,或将B定义为 i(1=1,2),则x2=1或2，而X2={1,2}。 n个阶段的决策过程有n+1个状态变量，x,表示x,演变的结果。在例1中x,取 G,或定义为1，即x,=1。 状态变量简称为状态。 当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这 种选择手段称为决策(decision),在最优控制问题中也称为控制(control). 描述决策的变量称决策变量(decision variable),变量允许取值的范用称允许决策 集合(set of admissible decisions)。用u,(x,)表示第k阶段处于状态x,时的决策变量， 它是x的函数，用U(x)表示x的允许决策集合在例1中4，(B,)可取C,C2或C, 可记作421)=1,2,3，而U2()={1,2,3}. 决策变量简称决策。 214第略 决策组成的序列称为策略(policy)。由初始状态x,开始的全过程的策略记作 Pn(x),即 由第k阶段的状态x开始到终止状态的后部子过程的策略记作P(x),即 -57

-57- decision process）和连续时间决策过程（continuous-time decision process）；根据过程的 演变是确定的还是随机的，分为确定性决策过程（deterministic decision process）和随 机性决策过程（stochastic decision process），其中应用最广的是确定性多阶段决策过程。 §2 基本概念、基本方程和计算方法 2.1 动态规划的基本概念和基本方程 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。 2.1.1 阶段 阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶 段，以便按阶段的次序解优化问题。阶段变量一般用k = 1,2,L,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) ，则 1 x2 = 或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 中 ( ) 2 B1 u 可取 1 2 C ,C 或C3 ， 可记作 (1) 1,2,3 u2 = ，而 (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 L u x . 由第k 阶段的状态 k x 开始到终止状态的后部子过程的策略记作 ( ) kn k p x ，即 ( ) { ( ), , ( )} kn k k k n n p x = u x L u x ，k = 1,2,L, n −1. 类似地，由第k 到第 j 阶段的子过程的策略记作

D(x)={u.(xe,.,l.(x.)}. 可供选择的策略有 定的范围，称为允许策略集合((set policies)),用 Pn(x),P(x),P(x)表示. 2.1.5.状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用 状态转移方程(equation of state transition)表示这种演变规律，写作 x41=T(x,4,k=l,2,.,n (1) 在例1中状态转移方程为x41=山(x) 2.1.6.指标函数和最优值函数 指标函数(objective function)是衡量过程优劣的数量指标，它是定义在全过程和所有 后部子过程上的数量函数，用'(xk,山，x1,.,x1)表示，k=1,2,n。指标函 数应具有可分离性，即V可表为x,山，Vn的函数，记为 并且函数p,对于变量V。是严格单调的。 过程在第j阶段的阶段指标取决于状态x,和决策4，用v,(x,4,)表示。指标医 数由v(=12,n)组成，常见的形式有： 阶段指标之和，即 Vn(x,4,x1.,xi)=∑y,(,4,力 阶段指标之积，即 V(x,4,x.,xi)=Πy,(x,4,) 阶段指标之极大（或极小），即 'n（xe,4eX4+1.,x+)=max(minp,(g,4） 这些形式下第k到第j阶段子过程的指标函数为'(x,山，x)· 根据状态转移方程指标函数V。还可以表示为状态x和策略P的函数，即 'a(xk,Pn）.在x给定时指标函数Vn对Pn的最优值称为最优值函数(optimal value function),记为f(x:）,即 其中opt可根据具体情祝取max或min。 21.7最优策略和最优轨线 使指标函数V,达到最优值的策略是从k开始的后部子过程的最优策略，记作 po={(,}。pin是全过程的最优策略，简称最优策略(optimal policy)。从初始 状态x(仁x)出发，过程按照P。和状态转移方程演变所经历的状态序列 {x,x,.,x}称最优轨线(optimal trajectory)

-58- ( ) { ( ), , ( )} kj k k k j j p x = u x L u x . 可供选择的策略有一定的范围，称为允许策略集合(set of admissible policies)，用 ( ), ( ), ( ) 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 = L n （1） 在例 1 中状态转移方程为 ( ) k 1 k k x = u x + 。 2.1.6. 指标函数和最优值函数 指标函数(objective function)是衡量过程优劣的数量指标，它是定义在全过程和所有 后部子过程上的数量函数，用 ( , , , , ) k ,n k k k +1 n+1 V x u x L x 表示， k = 1,2,L,n 。指标函 数应具有可分离性，即Vk ,n 可表为 k uk Vk n x 1, , , + 的函数，记为 ( , , , , ) ( , , ( , , , )) k ,n k k k+1 n+1 = k k k k+1,n k +1 k+1 n+1 V x u x L x ϕ x u V x u L x 并且函数ϕk 对于变量Vk+1, n 是严格单调的。 过程在第 j 阶段的阶段指标取决于状态 j x 和决策u j ，用 ( , ) j j u j v x 表示。指标函 数由v ( j 1,2, ,n) j = L 组成，常见的形式有： 阶段指标之和，即 ∑= + + = n j k k n k k k n j j j V (x ,u , x , , x ) v (x ,u ) , 1 L 1 ， 阶段指标之积，即 ∏= + + = n j k k n k k k n j j u j V (x ,u , x , , x ) v (x , ) , 1 L 1 ， 阶段指标之极大（或极小），即 ( , , , , ) max(min) ( , ) , 1 1 j j j k j n k n k k k n V x u x x v x u ≤ ≤ + L + = . 这些形式下第k 到第 j 阶段子过程的指标函数为 ( , , , ) k , j k k j+1 V x u L x 。 根据状态转移方程指标函数Vk ,n 还可以表示为状态 k x 和策略 pkn 的函数，即 ( , ) k ,n k pkn V x 。在 k x 给定时指标函数Vk ,n 对 pkn 的最优值称为最优值函数（optimal value function），记为 ( ) k k f x ，即 ( ) opt ( , ) , ( ) k n k kn p P x k k f x V x p kn∈ kn k = ， 其中opt 可根据具体情况取 max 或 min 。 2.1.7 最优策略和最优轨线 使指标函数Vk ,n 达到最优值的策略是从 k 开始的后部子过程的最优策略，记作 { , , } * * * pkn = uk L un 。 * p1n 是全过程的最优策略，简称最优策略（optimal policy）。从初始 状 态 ( ) * 1 1 x = x 出发，过程按照 * p1n 和状态转移方程演变所经历的状态序列 { , , , } * 1 * 2 * 1 n+ x x L x 称最优轨线（optimal trajectory）

[f(xn)=0或1 (2) 在上述方程中，当⑧为加法时取f(x)=0:当⑧为乘法时，取f(x)=1。动 用状态转移方密规 尤性原理的基础，即： 构成最优 和递归方程 2)求解 是由 划问 也可采用顺 法。这时，状态转移方程和递归方程分别为 xg=T(xk1,4),k=l,.,n 0(x)=0或1 /(xsi）= 0pt{,(x,4)⑧f(x)月，k=l,.,n 例3用lingo求解例1最短路线问题 model: 8te/,1,2cSa2326i,2,828,2c4 2,c3D3,c4D2,c43, E1,E32,F1G,F2G/:D: 92 5526643 eeetex(i)iG1:L (i)-@min (road()(( nd 纵上所述，如果 个问题能用动态规划方法求解，那么，我们可以按下列步骤，首 先建立起动 (i)将过 分成指 的阶段 ()正确选择状态变量x,使它既能描述过程的状态，又满足无后效性，同时确 定允许状态集合X:· ()选择决策变量4，确定允许决策集合U,(x:)。 (v)写出状态转移方程。 (v)确定阶段指标v,(x,4:)及指标函数V的形式（阶段指标之和，阶段指标之 53逆序解法的计算框图

-59- 2.1.8 递归方程 如下方程称为递归方程 ⎪⎩ ⎪ ⎨ ⎧ = ⊗ = = + + ∈ + + ( ) opt { ( , ) ( )}, , ,1 ( ) 0 1 1 1 ( ) 1 1 f x v x u f x k n L f x k k k k k u U x k k n n k k k 或 （2） 在上述方程中，当⊗ 为加法时取 fn+1(xn+1) = 0 ；当⊗ 为乘法时，取 fn+1(xn+1) =1。动 态规划递归方程是动态规划的最优性原理的基础，即：最优策略的子策略，构成最优子 策略。用状态转移方程（1）和递归方程（2）求解动态规划的过程，是由 k = n +1逆 推至 k = 1，故这种解法称为逆序解法。当然，对某些动态规划问题，也可采用顺序解 法。这时，状态转移方程和递归方程分别为： x T xk uk k n r k k ( , ), 1, , = +1 = L ， ⎪⎩ ⎪ ⎨ ⎧ = ⊗ = = + − ∈ + + + f x v x u f x k n f x k k k k k u U x k k k r k k ( ) opt { ( , ) ( )}, 1, , ( 0 1 1 1 ( ) 1 0 1 1 1 L ） 或 例 3 用 lingo 求解例 1 最短路线问题。 model: Title Dynamic Programming; sets: vertex/A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G/:L; road(vertex,vertex)/A B1,A B2,B1 C1,B1 C2,B1 c3,B2 C2,B2 C3,B2 C4, C1 D1,C1 D2,C2 D1,C2 D2,C3 D2,C3 D3,C4 D2,C4 D3, D1 E1,D1 E2,D2 E2,D2 E3,D3 E2,D3 E3, E1 F1,E1 F2,E2 F1,E2 F2,E3 F1,E3 F2,F1 G,F2 G/:D; endsets data: D=5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3; L=0,; enddata @for(vertex(i)|i#GT#1:L(i)=@min(road(j,i):L(j)+D(j,i))); end 纵上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列步骤，首 先建立起动态规划的数学模型： （i）将过程划分成恰当的阶段。 （ii）正确选择状态变量 k x ，使它既能描述过程的状态，又满足无后效性，同时确 定允许状态集合 Xk 。 （iii）选择决策变量uk ，确定允许决策集合 ( ) k k U x 。 （iv）写出状态转移方程。 （v）确定阶段指标 ( , ) k k uk v x 及指标函数Vkn 的形式（阶段指标之和，阶段指标之 积，阶段指标之极大或极小等）。 （vi）写出基本方程即最优值函数满足的递归方程，以及端点条件。 §3 逆序解法的计算框图

特我学店整来图空线数取的形式的莲序州法为险由计短国，英它 般化的自由终端条件为 f(xl)=p(x2i=l,2,.,n 3 其中P为已知。固定始端条件可表示为X,={x}={x)。 如果状态x,和决策山，是连续变量，用数值方法求解时需按照精度要求进行离散 化。设状态x的允许集合为 X。={xli=1,2,.,n,i=1,2.,n,k=12,.,n. 决策山，(x)的允许集合为 U6={g01j=1,2,.,na,i=1,2,.,n,k=1,2,.,n 状态转移方程和阶段指标应对x的每个取值x和山的每个取值计算，即 工=工(，)，=(，)。最优值函数应对x的每个取值x计算。基本方 程可以表为 f(xu）=y(xu,W)+f(T(xu,”), (x)=optf(x). (4) j广=12，.，n6,i=1,2,.,n,k=m,.2l 41 读(x)日 是 图Cai. 是 出】 图2解法框图 -60

-60- 以自由终端、固定始端、指标函数取和的形式的逆序解法为例给出计算框图，其它 情况容易在这个基础上修改得到。 一般化的自由终端条件为 1 1, 1, 1 ( ) ( ), 1,2, , n+ n+ i = n+ i = nn+ f x ϕ x i L (3) 其中ϕ 为已知。固定始端条件可表示为 { } { } * 1 1 1 X = x = x 。 如果状态 k x 和决策 uk 是连续变量，用数值方法求解时需按照精度要求进行离散 化。设状态 k x 的允许集合为 Xk = {xki | i = 1,2,L,nk }, i = 1,2,L,nk ,k = 1,2,L,n . 决策 ( ) ki ki u x 的允许集合为 U u j nki i nk k n j ki ki { | 1,2, , }, 1,2, , , 1,2, , = ( ) = L = L = L . 状态转移方程和阶段指标应对 k x 的每个取值 ki x 和 uki 的每个取值 ( j) uki 计算，即 ( , ) ( j) k k ki uki T = T x ， ( , ) ( j) k ki uki v = v x 。最优值函数应对 k x 的每个取值 ki x 计算。基本方 程可以表为 1,2, , , 1,2, , , , ,2,1. ( ) opt ( ), ( ) ( , ) ( ( , )), ( ) ( ) 1 ( ) ( ) j L n i L n k n L 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） 图 2 解法框图

按照(3)，(4)逆向计算出(x),为全过程的最优值。记状态x的最优决策为 (x。),由x和山(xa)按照状态转移方程计算出最优状态，记作x。并得到相应的 最优决策，记作(x)。于是最优策略为{(x,巧(x),(x)》。 算法程序的框图如图2所示。 图的左边部分是函数序列的递推计算，可输出全过程最优值(x),如果需要还 可以输出后部子过程最优值函数序列∫(x6)和最优决策序列(x方)。计算过程中存 (xa)是备计算f人之用，在-算完后可用-1将人替换掉：存(x)是备右边 部分读山(x)之用。 图的右边部分是最优状态和最优决策序列的正向计算，可输出最优策略 {(),4(x,.,(x)》和最优轨线{ix,.,x} 4 动态却制与静态制的关系 动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条 件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。 动态规划可以看作求决策 ,使指标函数.,4 )达到最优 ,端点条件以及允许状态集、允许决策集等 静态规只要当引天受安法状：决筑等就可以用动态规划方法求解。 下面用例子说明 例4用动态规划解下列非线性规划 s24=a,4≥0 其中g(u:)为任意的已知函数。 解按变量u的序号划分阶段，看作n段决策过程。设状态为x,x2,.,x+1,取 问题中的变量山，山2，.，4。为决策。状态转移方程为 x1=a,x41=x-4,k=1,2,.,n 取g(山，)为阶段指标，最优值函数的基本方程为（注意到x1=0) f)=mx8.x)+f小： 0≤xs≤a,k=n,n-1,.,2,1: fn+1(0)=0. 按照逆序解法求出对应于x每个取值的最优决策山(x:),计算至()后即可利 用状态转移方程得到最优状态序列{x和最优决策序列{4(x)}。 与静态规划相比，动态规划的优越性在于： (1)能多得到全 局最优解。由于约束条件确定的约束集合往往很复杂，即使指标 函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为

-61- 按照（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 L u x 。 算法程序的框图如图 2 所示。 图的左边部分是函数序列的递推计算，可输出全过程最优值 ( ) * 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 L u x 和最优轨线{ , , , } * * 2 * 1 n x x L x 。 §4 动态规划与静态规划的关系 动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条 件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。 动态规划可以看作求决策u u un , , , 1 2 L 使指标函数 ( , , , ) 1n 1 u1 u2 un V x ， L 达到最优 （最大或最小）的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等 是约束条件，原则上可以用非线性规划方法求解。 一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。 下面用例子说明。 例 4 用动态规划解下列非线性规划 ∑= n k gk uk 1 max ( ) ； s.t. ∑= = ≥ n k uk a uk 1 , 0 . 其中 ( ) gk uk 为任意的已知函数。 解 按变量uk 的序号划分阶段，看作n 段决策过程。设状态为 1 2 1 , , , n+ x x L x ，取 问题中的变量u u un , , , 1 2 L 为决策。状态转移方程为 , , 1,2, , . x1 = a xk +1 = xk − uk k = L 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,L,2,1； f n+1 (0) = 0. 按照逆序解法求出对应于 k x 每个取值的最优决策 ( ) * k k u x ，计算至 ( ) 1f a 后即可利 用状态转移方程得到最优状态序列{ } * k x 和最优决策序列{ ( )} * * k k u x 。 与静态规划相比，动态规划的优越性在于： （i）能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标 函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为

一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易 于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式萄 出的 优化 ，可以对每 子过程用枚法求解 求 而约束条 决策的摑 索范用越小， 个最闭 态规划得到的是全过程及所 解不同， 这样的解族，即使不需要，它们]在分析最优策略和最优值对于状态的稳定性时也是很有 用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。 (ⅲ)能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划 方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提 高求解效率。如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速 度。 动态规划的主要缺点是 ,也没有构 模型的通用方法 具体的 和灵活的 定状态转移规律等方面需要丰富的想象 ()用数值方法求解时存在维数灾( of dimensionality)。若维状态变量有n 个取值，那么对于n维问题，状态x就有m”个值，对于每个状态值都要计算、存储函 数∫(x),对于n稍大的实际问题的计算往往是不现实的。目前还没有克服维数灾的 有效的一般方法。 $5若干典型问题的动态规划模型 5.1最短路线间题 对于例1一类最短路线问题(shortest Path Problem),阶段按过程的演变划分，状 态由各段的初始位置确定，决策为从各个状态出发的走向，即有x+1=(x),阶段 指标为相邻两段状态间的距离d,(,“,(x)》,指标函数为阶段指标之和，最优值函数 (x:)是由x,出发到终点的最短距离（或最小费用），基本方程为 f(c)=mind(c,4(x》+f(x小，k=n, fx.)=0 利用这个模型可以算出例1的最短路线为AB,C2D,E,FG,相应的最短距离为18。 52生产计划问题 对于例2一类生产计划问题(Production planning oroblem),阶段按计划时间自然 划分，状态定义为每阶段开始时的储存量：，决策为每个阶段的产量4，记每个阶段 的需求量（己知量）为d:,则状态转移方程为 x1=x+4-dg,xk20,k=1,2,.,n (5) 设每阶段开工的固定成本费为a,生产单位数量产品的成本费为b,每阶段单位数量产 品的储存费为C,阶段指标为阶段的生产成本和储存费之和，即 4)=+ a+b4,山>0 (6) -62

-62- 一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易 于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的 优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小， 求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。 （ii）可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动 态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要 这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有 用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。 （iii）能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划 方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提 高求解效率。如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速 度。 动态规划的主要缺点是： （i）没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问 题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模 型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力 和灵活的技巧性，这就带来了应用上的局限性。 （ii）用数值方法求解时存在维数灾（curse of dimensionality）。若一维状态变量有m 个取值，那么对于n 维问题，状态 k x 就有 n m 个值，对于每个状态值都要计算、存储函 数 ( ) k k f x ，对于n 稍大的实际问题的计算往往是不现实的。目前还没有克服维数灾的 有效的一般方法。 §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 L u x k k k k = + + + = ( ) 0. f n+1 xn+1 = 利用这个模型可以算出例 l 的最短路线为 AB1C2D1E2F2G ，相应的最短距离为 18。 5.2 生产计划问题 对于例 2 一类生产计划问题（Production planning problem），阶段按计划时间自然 划分，状态定义为每阶段开始时的储存量 k x ，决策为每个阶段的产量uk ，记每个阶段 的需求量（已知量）为dk ，则状态转移方程为 , 0, 1,2, , . xk +1 = xk + uk − dk xk ≥ k = L n (5) 设每阶段开工的固定成本费为a ，生产单位数量产品的成本费为b ，每阶段单位数量产 品的储存费为c ，阶段指标为阶段的生产成本和储存费之和，即 ⎩ ⎨ ⎧ + > = + 0 , 0 ( , ) k k k k k k a bu u v x u cx (6)

指标函数'为y之和。最优值函数∫(x)为从第k段的状态x出发到过程终结的最 小费用，满足 f(x)=min[y(x,4)+f(xi，k=n,.,l 其中允许决策集合U。由每阶段的最大生产能力决定。若设过程终结时允许存储量为 x,则终端条件是 fn(x)=0. (7) (5)~(7)构成该问题的动态规划模型 53资源分配间题 一种或几种资源（包括资金）分配给若干用户，或投资于几家企业，以获得最大的 效益。资源分配问题(resource allocating Problem)可以是多阶段决策过程，也可以是 静态规划问题，都能构造动态规划模型求解。下面举例说明。 例5机器可以在高、低两种负荷下生产。台机器在高负荷下的年产量是g(), 在低负荷下的年产量是h(),高、低负荷下机器的年损耗率分别是a,和b (0B>0),即高、低负荷下每台机器的年产最分别为a和B,结果将 有什么特点。 解年度为阶段变量k=1,2,.,n。状态x为第k年初完好的机器数，决策为 第k年投入高负荷运行的台数。当x或山，不是整数时，将小数部分理解为一年中正常 工作时间或投入高负荷运行时间的比例 机器在高、低负荷下的年完好率分别记为a和b,则a=1-a,b=1-b,有 a<b。因为第k年投入低负荷运行的机器台数为x一4：，所以状态转移方程是 =au +b(xx -ug) (8) 阶段指标V,是第k年的产量，有 (x,4)=g(4)+hx-4) (9) 指标函数是阶段指标之和，最优值函数厂(x)满足 f(x)=ma[(x,“:)+f(小 (10 0≤x4≤m,k=n,.,2,1 及自由终端条件 fn1(xni）=0,0≤xn1≤m (11) 当y中的g,h用较简单的函数表达式给出时，对于每个k可以用解析方法求解极 值问题。特别，若g(m)=a,h(0)=u,(10)中的[y,(x,山，)+f(x】将是4 的线性函数，最大值点必在区间0≤山≤x的左端点4=0或右端点4=x取得， 即每年初将完好的机器全部投入低负荷或高负荷运行。 $6具体的应用实例 例6设某工厂有1000台机器，生产两种产品A、B,若投入x台机器生产A产

-63- 指标函数Vkn 为 k v 之和。最优值函数 ( ) k k f x 为从第k 段的状态 k x 出发到过程终结的最 小费用，满足 ( ) min[ ( , ) ( )], , ,1. f x vk xk uk f k 1 xk 1 k n L 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）可以是多阶段决策过程，也可以是 静态规划问题，都能构造动态规划模型求解。下面举例说明。 例 5 机器可以在高、低两种负荷下生产。u 台机器在高负荷下的年产量是 g(u) ， 在低负荷下的年产量是 h(u) ，高、低负荷下机器的年损耗率分别是 1 a 和 1 b （0 1 β > 0），即高、低负荷下每台机器的年产量分别为α 和 β ，结果将 有什么特点。 解 年度为阶段变量k = 1,2,L, n 。状态 k x 为第k 年初完好的机器数，决策uk 为 第k 年投入高负荷运行的台数。当 k x 或uk 不是整数时，将小数部分理解为一年中正常 工作时间或投入高负荷运行时间的比例。 机器在高、低负荷下的年完好率分别记为 a 和 b ，则 1 a = 1− a ， 1 b = 1− b ，有 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 L 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 + + 将是uk 的线性函数，最大值点必在区间 k k 0 ≤ u ≤ x 的左端点uk = 0 或右端点 k k u = x 取得， 即每年初将完好的机器全部投入低负荷或高负荷运行。 §6 具体的应用实例 例 6 设某工厂有 1000 台机器，生产两种产品 A、B ，若投入 x 台机器生产 A 产

品，则纯收入为5x,若投入y台机器生产B种产品，则纯收入为4y,又知：生产A种 产品机器的年折损率为20%，生产B产品机器的年折损率为10%，问在5年内如何安 排各年度的生产计划，才能使总收入最高？ 解年度为阶段变量k=123.45。 令x:表示第年初完好机器数，山：表示第k年安排生产A种产品的机器数，则 x-山为第k年安排生产B种产品的机器数，且0≤山k≤x4 则第k+1年初完好的机器数 x1=-024+1-0.1x4-4)=0.9x-0.1m (12) 令y,(x,山，)表示第k年的纯收入，f(x4)表示第k年初往后各年的最大利润之 和。 显然 6(x6)=0 (13) fx)=maxx,4)+f(x月 =max5s+4x-4)+/(xsn}=max{u:+4x&+f(x)}(14) (1)k=5时，由(13)、(14)式得 /s(x3)=max (us +4xs) 4+4x,关于4求导，知其导数大于零，所以山，+4x,在山，等于x,处取得最大值， 即45=x,时，f,(x)=5x3 (2)k=4时，由(12)、(14)式得 f(x)=max (u+4x+5x) =mxu,+4,+50.9x-0.1,}=m盛0.5u,+8.5} 当山4=x4时，f(x)=9x4 (3)k=3时， )=max仙+4x+9x,} =maxa,+4,+90.9x,-0.1山，》=mx0.14,+12.1x,} 当=时，()=12.2x3 (4)k=2时， 6)=m,+4+122x}=max{-0.224,+14.98x,} 当42=0时，f53(x2)=14.98x2 (5)k=1时， fc,)=max+4+14,98x,=ma-0498,+17.482x} 当4=0时，f(x)=17.482x1。因为 x1=1000(台) -64

-64- 品，则纯收入为5x ，若投入 y 台机器生产 B 种产品，则纯收入为4y ，又知：生产 A 种 产品机器的年折损率为 20%，生产 B 产品机器的年折损率为 10%，问在 5 年内如何安 排各年度的生产计划，才能使总收入最高？ 解 年度为阶段变量 k = 1,2,3,4,5。 令 k x 表示第 k 年初完好机器数，uk 表示第 k 年安排生产 A 种产品的机器数，则 k uk x − 为第k 年安排生产 B 种产品的机器数，且 k k 0 ≤ u ≤ x 。 则第 k +1年初完好的机器数 k k k k k uk x +1 = (1− 0.2)u + (1− 0.1)(x − u ) = 0.9x − 0.1 （12） 令 ( , ) k k uk v x 表示第 k 年的纯收入， ( ) k k f x 表示第 k 年初往后各年的最大利润之 和。 显然 f 6 (x6 ) = 0 （13） 则 ( ) max { ( , ) ( )} 1 1 0 + + ≤ ≤ = k k k + k k u x k k f x v x u f x k k max {5 4( ) ( )} max { 4 ( )} 1 1 0 1 1 0 + + ≤ ≤ + + ≤ ≤ = + − + = k + k + k k u x k k k k k u x u x u f x u x f x k k k k （14） （1）k = 5时，由（13）、（14）式得 ( ) max { 4 } 5 5 0 5 5 5 5 f x u x u x = + ≤ ≤ 5 4 5 u + x 关于u5求导，知其导数大于零，所以 5 4 5 u + x 在u5等于 5 x 处取得最大值， 即 5 5 u = x 时， 5 5 5 5 f (x ) = x 。 （2）k = 4 时，由（12）、（14）式得 ( ) max { 4 5 } 4 4 5 0 4 4 4 4 f x u x x u x = + + ≤ ≤ max { 4 5(0.9 0.1 )} max {0.5 8.5 } 4 4 0 4 4 4 4 0 4 4 4 4 u x x u u x u x u x = + + − = + ≤ ≤ ≤ ≤ 当 4 4 u = x 时， 4 4 4 f (x ) = 9x （3）k = 3时， ( ) max { 4 9 } 3 3 4 0 3 3 3 3 f x u x x u x = + + ≤ ≤ max { 4 9(0.9 0.1 )} max {0.1 12.1 } 3 3 0 3 3 3 3 0 3 3 3 3 u x x u u x u x u x = + + − = + ≤ ≤ ≤ ≤ 当 3 3 u = x 时， 3 3 2 3 f (x ) = 12. x （4）k = 2 时， ( ) max { 4 12.2 } max { 0.22 14.98 } 2 2 0 2 2 3 0 2 2 2 2 2 2 f x u x x u x u x u x = + + = − + ≤ ≤ ≤ ≤ 当 0 u2 = 时， 2 2 2 f (x ) = 14.98x 。 （5）k = 1时， ( ) max{ 4 14.98 } max{ 0.498 17.482 } 1 1 0 1 1 2 0 1 1 1 1 1 1 f x u x x u x u x u x = + + = − + ≤ ≤ ≤ ≤ 当 0 u1 = 时， 1 1 1 f (x ) = 17.482x 。因为 1000 x1 = （台）

所以由(12)式，进行回代得 x2=0.9x1-0.141=900(台) x3=0.9x2-0.l42=810(台) x4=0.9x3-0.11=648(台) x3=0.9x4-0.14=518.4(台) 注：x=518.4台中的0.4台应理解为有一台机器只能使用0.4年将报废。 例7求解下面问题 max [u1+42+43=c(c>0) 4,20i=1,2,3 解：按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量 为x,x2,x,x4,并记，=c:取问题中的变量山，山，山为决策变量：各阶段指标函数 按乘积方式结合。令最优值函数厂(x)表示第k阶段的初始状态为x:,从k阶段到3 阶段所得到的最大值。 设3=，3+山2=x32X2+4=x=C 则 =x,0≤≤2,0≤4≤x 用逆推解法，从后向前依次有 ∫(x)=max4}=x及最优解4=x )=mxf,》=mxu5(3-4,}=maxh,(（仙) 由么=2，-3=0，得4，=号和4=0（合去) du. 验-2-6 dl =-2,<0,故叫，-子x:为极大值点。 所以化)=2方式及最优解店=号 fc)=m,/,}=max仙27年-4P} 同样利用微分法易知)=4，最优解心=： 由于x,已知，因而按计算的顺序反推算，可得各阶段的最优决策和最优值。即

-65- 所以由（12）式，进行回代得 0.9 0.1 900 x2 = x1 − u1 = （台） x3 = 0.9x2 − 0.1u2 = 810（台） x4 = 0.9x3 − 0.1u3 = 648（台） x5 = 0.9x4 − 0.1u4 = 518.4 （台） 注： x5 = 518.4台中的 0.4 台应理解为有一台机器只能使用 0.4 年将报废。 例 7 求解下面问题 3 2 max z = u1u2 u ⎩ ⎨ ⎧ ≥ = + + = > 0 1,2,3 ( 0) 1 2 3 u i u u u c c i 解： 按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量 为 1 2 3 4 x , x , x , x ，并记 x = c 1 ；取问题中的变量 1 2 3 u ,u ,u 为决策变量；各阶段指标函数 按乘积方式结合。令最优值函数 ( ) k k f x 表示第k 阶段的初始状态为 k x ，从k 阶段到 3 阶段所得到的最大值。 设 3 u3 x = ， 3 2 2 x + u = x ， x + u = x = c 2 1 1 则有 3 3 u = x ， 2 2 0 ≤ u ≤ x ， 1 1 0 ≤ u ≤ x 用逆推解法，从后向前依次有 3 3 3 3 ( ) max{ } 3 3 f x u x u x = = = 及最优解 3 * 3 u = x ( ) max { ( )} max { ( )} max ( , ) 2 2 2 0 2 2 2 2 0 3 3 2 2 0 2 2 2 2 2 2 2 2 f x u f x u x u h u x ≤u ≤x ≤u ≤x ≤u ≤x = = − = 由 2 3 0 2 2 2 2 2 2 = u x − u = du dh ，得 2 2 3 2 u = x 和 0 u2 = （舍去） 又 2 2 2 2 2 2 2x 6u du d h = − ，而 2 0 2 3 2 2 2 2 2 2 2 = − < = x du d h u x ，故 2 2 3 2 u = x 为极大值点。 所以 3 2 2 2 27 4 f (x ) = x 及最优解 2 * 2 3 2 u = x 。 ( ) } 27 4 ( ) max{ ( )} max{ 3 1 1 1 0 1 2 2 0 1 1 1 1 1 1 f x u f x u x u u x u x = = − ≤ ≤ ≤ ≤ 同样利用微分法易知 4 1 1 1 64 1 f (x ) = x ，最优解 1 * 1 4 1 u = x 。 由于 1 x 已知，因而按计算的顺序反推算，可得各阶段的最优决策和最优值。即 u c 4 * 1 1 = ， 4 1 1 64 1 f (x ) = c 由 x x u c c c 4 3 4 * 1 2 = 1 − 1 = − =