第四章 动态规划
§1 引言
1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。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）和随
-40-
机性决策过程（stochastic decision process），其中应用最广的是确定性多阶段决策过程。 §2 基本概念、基本方程和计算方法
2.1 动态规划的基本概念和基本方程
一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。 2.1.1 阶段
阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k?1,2,?,n表示。在例1中由A出发为k?1，由Bi(i?1,2)出发为k?2，依此下去从Fi(i?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可取B1,B2，或将Bi定义为
i(i?1,2)，则x2?1或2，而X2?{1,2}。
在例1中x7取xn?1表示xn演变的结果。n 个阶段的决策过程有n?1个状态变量，
G，或定义为1，即x7?1。
根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。
状态变量简称为状态。 2.1.3 决策
当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）。
描述决策的变量称决策变量（decision variable），变量允许取值的范围称允许决策集合（set of admissible decisions）。用uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数，用Uk(xk)表示xk的允许决策集合。在例1中u2(B1)可取C1,C2或C3，可记作u2(1)?1,2,3，而U2(1)?{1,2,3}。
决策变量简称决策。 2.1.4 策略
决策组成的序列称为策略（policy）。由初始状态x1开始的全过程的策略记作
p1n(x1)，即
p1n(x1)?{u1(x1),u2(x2),?,un(xn)}.
由第k阶段的状态xk开始到终止状态的后部子过程的策略记作pkn(xk)，即
pkn(xk)?{uk(xk),?,un(xn)}，k?1,2,?,n?1. 类似地，由第k到第j阶段的子过程的策略记作
pkj(xk)?{uk(xk),?,uj(xj)}.
可供选择的策略有一定的范围，称为允许策略集合(set of admissible policies)，用
-41-
P1n(x1),Pkn(xk),Pkj(xk)表示。
2.1.5. 状态转移方程
在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程（equation of state transition）表示这种演变规律，写作
xk?1?Tk(xk,uk),k?1,2,?,n. （1） 在例1中状态转移方程为xk?1?uk(xk)。
2.1.6. 指标函数和最优值函数
指标函数(objective function)是衡量过程优劣的数量指标，它是定义在全过程和所有后部子过程上的数量函数，用Vk,n(xk,uk,xk?1,?,xn?1)表示，k?1,2,?,n。指标函数应具有可分离性，即Vk,n可表为xk,uk,Vk?1,n的函数，记为
Vk,n(xk,uk,xk?1,?,xn?1)??k(xk,uk,Vk?1,n(xk?1,uk?1,?,xn?1))并且函数?k对于变
量Vk?1,n是严格单调的。
过程在第j阶段的阶段指标取决于状态xj和决策uj，用vj(xj,uj)表示。指标函数由vj(j?1,2,?,n)组成，常见的形式有：
阶段指标之和，即
Vk,n(xk,uk,xk?1,?,xn?1)??vj(xj,uj)，
j?knn阶段指标之积，即
Vk,n(xk,uk,xk?1,?,xn?1)??vj(xj,uj)，
j?k阶段指标之极大（或极小），即
Vk,n(xk,uk,xk?1,?,xn?1)?max(min)vj(xj,uj).
k?j?n这些形式下第k到第j阶段子过程的指标函数为Vk,j(xk,uk,?,xj?1)。
根据状态转移方程指标函数Vk,n还可以表示为状态xk和策略pkn的函数，即在xk给定时指标函数Vk,n对pkn的最优值称为最优值函数（optimal value Vk,n(xk,pkn)。
function），记为fk(xk)，即
fk(xk)?pkn?Pkn(xk)optVk,n(xk,pkn)，
其中opt可根据具体情况取max或min。 2.1.7 最优策略和最优轨线
使指标函数Vk,n达到最优值的策略是从k开始的后部子过程的最优策略，记作
****。从初始pkn?{uk,?,un}。p1n是全过程的最优策略，简称最优策略（optimal policy）*状态x1(?x1)出发，过程按照p1n和状态转移方程演变所经历的状态序列***。 {x1,x2,?,xn?1}称最优轨线（optimal trajectory）
*2.1.8 递归方程
如下方程称为递归方程
-42-
f(x)?0或1??n?1n?1 ?f(x)?opt{v(x,u)?f(x)},k?n,?,1 （2）
kkkkkk?1k?1?uk?Uk(xk)?在上述方程中，当?为加法时取fn?1(xk?1)?0；当?为乘法时，取fn?1(xk?1)?1。
动态规划递归方程是动态规划的最优性原理的基础，即：最优策略的子策略，构成最优子策略。用状态转移方程（1）和递归方程（2）求解动态规划的过程，是由k?n?1逆推至k?1，故这种解法称为逆序解法。当然，对某些动态规划问题，也可采用顺序解法。这时，状态转移方程和递归方程分别为：
xk?Tkr(xk?1,uk),k?1,?,n?0或1?f0(x1）??fk(xk?1)?opt{vk(xk?1,uk)?fk?1(xk)},k?1,?,n
r?uk?Uk?1(xk?1)?，
纵上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列步骤，首
先建立起动态规划的数学模型：
（i）将过程划分成恰当的阶段。
（ii）正确选择状态变量xk，使它既能描述过程的状态，又满足无后效性，同时确定允许状态集合Xk。
（iii）选择决策变量uk，确定允许决策集合Uk(xk)。
（iv）写出状态转移方程。
（v）确定阶段指标vk(xk,uk)及指标函数Vkn的形式（阶段指标之和，阶段指标之积，阶段指标之极大或极小等）。
（vi）写出基本方程即最优值函数满足的递归方程，以及端点条件。 §3 逆序解法的计算框图
以自由终端、固定始端、指标函数取和的形式的逆序解法为例给出计算框图，其它情况容易在这个基础上修改得到。
一般化的自由终端条件为
fn?1(xn?1,i)??(xn?1,i),i?1,2,?,nn?1 (3) 其中?为已知。固定始端条件可表示为X1?{x1}?{x1}。
如果状态xk和决策uk是连续变量，用数值方法求解时需按照精度要求进行离散化。设状态xk的允许集合为
*Xk?{xki|i?1,2,?,nk},i?1,2,?,nk,k?1,2,?,n. 决策uki(xki)的允许集合为
(j)Uki?{uki|j?1,2,?,nki},i?1,2,?,nk,k?1,2,?,n.
(j)状态转移方程和阶段指标应对xk的每个取值xki和uki的每个取值uki计算，即(j)(j))。最优值函数应对xk的每个取值xki计算。基本方Tk?Tk(xki,uki)，vk?v(xki,uki程可以表为
-43-
(j)(j)fk(j)(xki)?vk(xki,uki)?fk?1(Tk(xki,uki)),fk(xki)?optfk(j)(xki),j （4）
j?1,2,?,nki,i?1,2,?,nk,k?n,?,2,1.*按照（3），（4）逆向计算出f1(x1)，为全过程的最优值。记状态xki的最优决策为****和uki。并得到相应的uki(xki)，由x1(xki)按照状态转移方程计算出最优状态，记作xk********最优决策，记作uk(xk)。于是最优策略为{u1(x1),u2(x2),?,un(xn)}。
算法程序的框图如下。
*图的左边部分是函数序列的递推计算，可输出全过程最优值f1(x1)，如果需要还
*可以输出后部子过程最优值函数序列fk(xki)和最优决策序列uk(xki)。计算过程中存*fk(xki)是备计算fk?1之用，在fk?1算完后可用fk?1将fk替换掉；存uk(xki)是备右边**部分读uk(xk)之用。
图的右边部分是最优状态和最优决策序列的正向计算，可输出最优策略
*********{u1(x1),u2(x2),?,un(xn)}和最优轨线{x1,x2,?,xn}。
§4 动态规划与静态规划的关系
动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。
-44-
数学建模算法动态规划
