第二部分 动态规划（Dymamic Programming）
第三章 动态规划动态规划是解决一类多阶段决策问题的优化方法，也是考察问题的一种途径，而不是一种算法（如LP单纯形法）。因此它不象LP那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。
动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题，且它的每一阶段都需进行决策，则这类问题均可用动态规划方法进行求解。
根据多阶段决策过程的时序和决策过程的演变，动态规划方法有以下四种类型：离散确定性、离散随机性、连续确定性和连续随机性。
§1动态规划的基本概念和最优化原理一、引例（最短路线问题）
B1
1
C1
5
6
8
6
A 3
B2
C2
3
D1
5
6
E
B3
6
C3
5
D2
A
1
B 2
C 3
D 4
E
上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），试求一条由A到E的铺管线路，使总距离最短（或总费用最小）。
将该问题划分为4个阶段的决策问题，即第一阶段为从A到Bj（j=1，2，3），有三种决策方案可供选择；第二阶段为从Bj到Cj（j=1,2,3），也有三种方案可供选择；第三阶段为从Cj到Dj(j=1,2)，有两种方案可供选择；第四阶段为从Dj到E，只有一种方案选择。如果用完全枚举法，则可供选择的路线有3×3×2×1=18（条），将其一一比较才可找出最短路线：
A→B1→C2→D3→E
其长度为15。
显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。
由于我们考虑的是从全局上解决求A到E的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至A点：
第四阶段，由D1到E只有一条路线，其长度f4（D1）=4，同理f4（D2）=3。
第三阶段，由Cj到Di分别均有两种选择，即
，决策点为D1
,决策点为D1
，决策点为D2
第二阶段，由Bj到Cj分别均有三种选择，即：
，决策点为C2
，决策点为C2或C3
，决策点为C2
第一阶段，由A到B，有三种选择，即：
，决策点为B1
f1(A=15)说明从A到E的最短铺管线长为1，最短路线的确定可按计算顺序反推而得。即
A→B1→C2→D1→E
上述最短路线问题的计算过程，也可借助于图形直观的表示出来：
10
10
B1
C1
4
5
3
D1
15
14
7
3
0
A
B2
C2
E
D2
11
8
B3
C3
图中各点上方框的数，表示该点到E的最短距离。图中双箭线表示从A到E的最短路线。
从引例的求解过程可以得到以下启示：
①对一个问题是否用上述方法求解，其关键在于能否将问题转化为相互联系的多个阶段的决策问题。
所谓多阶段决策问题是：把一个问题看作是一个前后关联具有链状结构的多阶段过程，也称为序贯决策过程。如下图所示：
决策
决策
决策
状态
状态
状态
状态
状态
1
2
n
②在处理各阶段决策的选取上，不仅只依赖于当前面临的状态，而且还要注意对以后的发展。即是从全局考虑解决局部（阶段）的问题。
③各阶段选取的决策，一般与“时序”有关，决策依赖于当前的状态，又随即引起状态的转移，整个决策序列就是在变化的状态中产生出来，故有“动态”含义。因此，把这种方法称为动态规划方法。
④决策过程是与阶段发展过程逆向而行。
二、动态规划的基本概念
1、阶段。阶段的划分，一般根据时序和空间的自然特征来划分，但要便于把问题的过程能转化为阶段决策的过程。描述阶段的变量称为阶段变量，常用自然数k表示。如引例可划分为4个阶段求解，k=1，2，3，4。
2、状态。状态就是阶段的起始位置。它既是该阶段某支路的起点，又是前一阶段某支路的终点。
（1）状态变量和状态集合。描述过程状态的变量称为状态变量。它可用一个数、一组数或一向量（多维情形）来描述，常用Sk表示第k阶段的状态变量。通常一个阶段有若干个状态。第k阶段的状态就是该阶段所有始点的集合。如引例中
，，，
（2）状态应具有无后效性（即马尔可夫性）。即如果某阶段状态给考虑，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。
在构造决策过程的动态规划模型时，不能仅由描述过程的具体特征这点去规定状态变量，而要充分注意是否满足无后效性要求。
3、决策与决策变量。在某阶段对可供选择状态的决定（或选择），称为决策。描述的变量称为决策变量。常用dk(Sk)表示第k阶段处于状态Sk时的决策变量，它是状态变量的函数。决策变量允许取值的范围，称为允许决策集合，常用Dk(Sk)表示。显然dk（Sk）∈Dk(Sk)。
如在引例的第一阶段中，若从B1出发，D2（B1）=，如果决定选取C2，则d2（B1）=C2。
4、策略与子策略。策略是一个决策序列的集合。当k=1时，Pin（S1）=就称为全过程的一个策略，简称策略，简记为Pin(S1).
称Pk,n(Sk)= 为由第k阶段开始到最后阶段止的一个子策略，简称后部子策略。简记为Pk,n(Sk)
称可供选择策略的范围，为允许策略集，用P表示。
动态规划方法就是要从允许策略集P中找出最优策略Pin*。
5、状态转移方程。它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程，用Sk+1=Tk(Sk,dk)表示。该方程描述了由第k阶段到第k+1阶段的状态转移规律。因此又称其为状态转移函数。
6、阶段指标、指标函数和最优指标函数
（1）衡量某阶段决策效益优劣的数量指标，称为阶段指标，用vk(Sk,dk)表示第k阶段的阶段指标。
在不同的问题中，其含义不同。它可以是距离、利润、成本等。
在引例中，用dk=Uk(Sk,dk)表示在第k阶段由点Sk到点Sk+1=dk(Sk)距离。如d2(B3,C1)=2。
（2）用于衡量所选定策略优劣的数量指标，称为指标函数。它是定义在全过程和所有后部子过程上确定的数量函数。记为Vk,n(Sk,Pk,n).
Vk,n(Sk,Pk,n)=Vk,n(Sk,dk,Sk+1,…Sn+1) k=1,2,…,n。
构成动态规划模型的指标函数，应具有可分离性，并满足递推关系。
常见的指标函数的形式有：
①
②
（3）最优指标函数fk(Sk),表示从第k阶段的状态Sk开始采用最优子策略P*k,n，到第n阶段的终止时所得到的指标函数值。
即fk(Sk)=0PtVk,n(Sk,uk,…Sn+1)
其中0Pt是最优化（0Ptimiyation）的缩写，可根据题意取max或min。
在引例中，指标函数Vk,n表示在第k阶段由点Sk至终点E的距离。fk(sk)表示第k阶段点Sk到终E的最短距离。f2(B1)=10表示从第2阶段中的点B1到点E的最短距离。
7、基本方程（递推关系式）
从引例求A到E的最短路的计算过程中可以看出，在求解的各个阶段，我们利用了k阶段与k+1阶段之间的递推关系；
一般地，
若则有
若
以上递推关系式称为动态规划的基本方程。
三、动态规划方法的基本思想与最优化原理
1、基本思想：动态规划方法的关键在于正确地写出基本方程，因此首先必须将问题的过程划分为多个相互联系的多阶段决策过程，恰当地选取状态变量和决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题。然后从边界条件开始，逆过程行进方向，逐段递推寻优。在每个子问题求解时，均利用它前面已求出的子问题的最优化结果依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。
在多阶段决策过程中，动态规划方法是既把当前的一段和未来的各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每阶段决策的选取是从全局来考虑，与该段的最优选择一般是不同的。
动态规划方法的基本思想体现了多阶段性、无后效性、递归性、总体优化性。
2、最优化原理动态规划方法基于R·Bellman等人提出的最优化原理：“作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对于先前的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简言之，“一个最优策略的子策略总是最优的”。
但是，最优化原理仅是策略最优性的必要条件，而基本方程是策略最优性的充要条件。由此可见，基本方程是动态规划理论与方法的基础。
§2、动态规划模型的建立与求解一、构成动态规划模型的条件建立动态规划模型，就是分析问题并建立问题的动态规划基本方程。为此，必须满足以下条件：
1、将问题的过程划分成恰当的阶段；
2、正确选择状态变量Sk，使它既能描述过程的演变，又要满足无后效性；
3、确定决策变量dk及每阶段的允许决策集合Dk(Sk)；
4、正确写出状态转移方程；
5、正确写出指标函数Vk,n的关系式，它应具有以下三个性质；
（1）是定义全过程和所有后部子过程上的数量函数；
（2）具有可分离性，并满足递推关系，即
Vk,n(Sk,dk,…Sn+1)=￠ (Sk,dk,Vk+1,n)
（3）函数￠（Sk,dk,Vk+1,n）对于Vk+1,n要求严格单调。
以上五点是正确写出动态规划基本方程的要素。
二、求解动态规划模型的方法
1、在已知初始状态S1下，采用逆序解法：（反向递归）
d1(s1)
d2(S2)
dk(Sk)
dk+1(Sk+1)
dn(Sn)
S1
S2
Sk
Sk+1
Sn
Sn+1
阶段1
阶段2
阶段k
阶段k+1
阶段n
v1(S1,v1)
v2(S2,v2)
v2(Sk,vk)
vk+1(Sk+1,vk+1)
vn(Sn,vn)
Vkn
fk(Sk)=0ptVk,n
寻优方向
按上图示意的求解方法称为逆序法。例如引例的求解，就是把A看作始端，E为终端，规定从A到E为过程的行进方向，而寻优则是从E到A逆过程进行，所以是采用了逆序法。
2、在已知终止状态Sn下，采用顺序解法（正向递归）
如果我们把引例中E看作始端，A为终端，规定从E到A过程为行进方向，而寻优则是从A到E过程进行求解的方法称为顺序法。其示意图如下：
d1(s1)
d2(S2)
dk(Sk)
dk+1(Sk+1)
dn(Sn)
S
S1
S2
Sk
Sk+1
Sn
阶段1
阶段2
阶段k
阶段k+1
阶段n
v1(S1,d1)
v2(S2,d2)
vk(Sk,dk)
vk+1(Sk+1,dk+1)
vn(Sn,dn)
V1,k
fk,(Sk)=0ptV1,k
寻优方向
逆序法与顺序法的不同仅在对始端终端看法的颠倒或在规定的行进方向不同。但在寻优时却都是逆行进方向，从最后一阶段开始，逐段逆推向前计算，找出最优结果。
3、两种解法在建模时的区别如下表所示
逆 序 法
顺 序 法
状态转移方程
Sk+1=Tk(Sk,dk)
Sk-1=Tk(Sk,dk)
指标函数定义
Vk,n=
fk(Sk)=0Pt或Vk,n=
V1,k=
fk(Sk)=0Pt或V1k=
基本方程形式
§3、建模训练与求解
一、维资源分配问题
例1某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂获得这种设备，可以提供的期望盈利如下表所示。问如何分配这五台设备给各厂，才能使国家得到的期望盈利最大？
工厂盈利设备台数
甲
乙
丙
0
1
2
3
4
5
0
3
7
9
12
13
0
5
10
11
11
11
0
4
6
11
12
12
解：设xj（j=1,2,3）分别表示分配给甲、乙、丙三个厂的设备台数，则此问题可写成以下数学模型：max=g1(x1)+g2(x2)+g3(x3)
其中g1(x1),g2(x2),g3(x3)分别对应表中甲、乙、丙厂的期望盈利数。
先考虑构成动态规划模型的条件：
1、按工厂将问题划分为三个阶段，并将工厂编号为k=1,2,3。
2、设状态变量Sk表示为分配给第k个工厂至第3个工厂的设备台数。（显然S1=5，所以可考虑用逆序法。）
3、决策变量Xk，表示为分配给第k个工厂的设备数。0≤Xk≤Sk。
4、状态转移方程为Sk+1=Sk-Xk
5、阶段指标gk(sk,xk)表示Xk设备分配到第k个工厂所得的期望盈利值。
因此基本方程为：
下面用逆序法采用表格形式进行求解
k=3,0≤X3≤S3 S4=S3-X3
S3
X3(S3)
g3(S3，X3)+f4(S4)
f3(S3)
X3*(S3)
0
0
0+0
0
0
1
1
4+0*
4
1
2
2
6+0*
6
2
3
3
11+0*
11
3
4
4
12+0*
12
4
5
5
12+0*
12
5
k=2 0≤X2≤S2 S3=S2－X2
S2
X2(S2)
g2(S2,X2)+f3(s3)
f2(S2)
X2*(S2)
0
0
0+0
0
0
1
0
1
0+4
5+0*
5
1
2
0
1
2
0+6
5+4
10+0*
10
2
3
0
1
2
3
0+11
5+6
10+4*
11+0
14
2
4
0
1
2
3
4
0+12
5+11*
10+6*
11+4
11+0
16
1或2
5
0
1
2
3
4
5
0+12
5+12
10+11*
11+6
11+4
11+0
21
2
k=1 0≤X1≤S1 S2=S1－X1
S1
X1(S1)
g2(S1X1)+f2(s2)
f1(s1)
x1*
5
0
1
2
3
4
5
0+21*
3+16
7+14*
9+10
12+5
13+0
21
0或2
按计算表格的顺序反推，得最优分配方案有两个：
第一方案：x1*=0 x2*=2 x3*=3
第二方案：x1*=2 x2*=2 x3*=1
它们所得的总盈利都为21（万元）
本例若设Sk表示分配给从第1个工厂到第k个工厂的设备台数，即S3=5，因此，本例还可用顺序法求解，其结果完全一致。
例1实际上是一个一维资源分配问题。
一维资源分配问题总可以写成“静态规划”问题：
MaxZ=g1(x1)+g2(x2)+…+gn(xn)
由于这类问题的特殊结构，可以把它看成是一个阶多段决策问题，并利用动态规划的递推关系求解。一般有
（1）阶段划分：通常把资源分配给一个或几个使用者的过程作为一个阶段。即把问题中变量的个数作为阶段数，k=1,2,…n。
（2）状态变量SK的含义：SK表示分配用于生产第k种产品至第n种产品的资源数。显然S1=a，所以该类问题可用逆序法求解。（也可用顺序法，Sn=a）
（3）决策变量dk的选定：dk=xk，含义为分配给生产第k种产品的资源数。允许决策集合为：Dk(Sk)={dk| 0≤dk=xk≤Sk}。
（4）状态转移方程：Sk+1=Sk―dk=Sk―xk (Sk=Sk+1+xk)
（5）由于阶段指标vk(Sk,xk)=gk(xk)，所以指标函数：
于是基本方程为
二、生产存贮问题例2,某工厂要对一种产品制订今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的需求量如下表所示。假定生产每批产品的固定成本3(千元)，若不生产就为0；每单位产品成本为1(千元)；每个时期生产能力所允许的最大生产批量为不超过6个单位；每个时期未售出的产品，每单位需付存贮费0.5(千元)。还假定在第一个时期的初始库存量为0，第四个时期末的库存量也为0。问该厂应如何安排各个时期的生产与库存，才能在满足市场需求条件下，使总成本最小。
时 期(k)
1
2
3
4
需求量(dk)
2
3
2
4
解：先考虑构成动态规划模型的条件
1,阶段：把生产的四个时期作为四个阶段。k=1,2,3,4。
2,状态变量Sk表示第k时期初(发货以前)的库存量。(由题意有S1=0，S5=0，故可考虑用顺序法或逆序法。)
3,决策变量xk表示第k时期的生产量。
0≤xk≤min{Sk+1+dk,6} 其中dk为第k时期的需求量
4,状态转移方程为Sk+1=Sk+xk―dk（或Sk=Sk+1+dk―xk）。
5,阶段指标Vk(xk)表示第k时期的生产成本Ck(xk)与库存量的存贮费hk(Sk)之和。即Vk(xk)=Ck(xk)+hk(Sk)。其中
hk(Sk)=0.5Sk
于是指标函数，表示从第1时期到第k时期的总成本。
因此，基本方程为
下面用顺序法进行求解：
k=1，由f1(S2)=min{C1(x1)+h1(S2)}和s1=s2+d1－x1
x1=min{S2+2,6}
S2可在0与之间取值,即s2=0,1,2,3,4，于是由x1=min{S2+2,6}知，x1可取值为2,3,4,5,6。分别计算如下：
f1(0)=min{3+2+0.5×0}=5 有x1=2
x1=2
f1(1)=min{3+3+0.5×1}=6.5 有x1=3
x1=3
f1(2)=min{3+4+0.5×2}=8.5 有x1=4
x1=4
f1(3)=min{3+5+0.5×3}=9.5 有x1=5
x1=5
f1(4)=min{3+6+0.5×4}=11 有x1=6
x1=6
k=2，由f2(S3)=min{C2(x2)+h2(S3)+f1(S3+3－X2)}可知，
0≤x2≤min{S3+3,6}
S3可在0与之间取值。即S3可取值0,1,2,3。
x2可在0与min{S3+3,6}之间取值。分别计算如下：
由，有x2=0。
由，有x2=0。
用同样的方法计算f2(2)=min{C2(x2)+h2(2)+f1(5－x2)}=14，有x2=5
0≤x2≤5
f2(3)=min{C2(x2)+h2(3)+f1(6－x2)}=15.5，有x2=6
0≤x2≤6
k=3，由f3(S4)=min{C3(x3)+h3(S4)+f2(S3+2－x3)}可知，S4可在0与min{4,6－2}=4之间取值。x3可在0与min{S3+3,6}之间取值。分别计算如下：
，有x3=0。
，有x3=0或3。
用同样的方法计算
f3(2)=min{C3(x3)+h3(2)+f1(4－x3)}=17.5，有x3=4
0≤x3≤4
f3(3)=min{C3(x3)+h3(3)+f1(5－x3)}=19，有x3=5
0≤x3≤5
f3(4)=min{C3(x3)+h3(4)+f1(6－x3)}=20.5，有x3=6
0≤x3≤6
k=4，由f4(S5)=min{C4(x4)+h4(S5)+f3(S4+4－x4)}与S5=0
0≤x4≤min{S5+4,6}可知，
f4(0)=min{C4(x4)+h4(0)+f3(4－x4)}
0≤x4≤4
，有x4=0。
按计算顺序反推算，
x4=0—→x3=6—→x2=0—→x1=5(由Sk=Sk+1+dk―xk推出)
即每个时期的最优生产决策为:
x1*=5，x2*=0，x3=6，x4*=0
其相应的最小总成本为20.5千元。
三、设备更新问题在已知一台设备的效益函数r(t)，维修费用函数u(t)及更新费用函数C(t)条件下，在n年内，每年年初作出决策，是继续使用旧设备还是更换一台新设备，使n年总效益最大的这类问题称为设备更新问题。
设rk(t)表示在第k年设备已使用t年（或称役令为t年），再使用1年时的效益：
uk(t)表示在第k年设备役令为t年，再使用1年的维修费用；
Ck(t)表示在第k年卖掉一台役令为t的设备，买进一台新设备的更新净费用；
(为折旧因子(0≤(≤1)，表示1年以后的单位价值相当于现年的(单位。
构成该问题动态规划模型的条件：
阶段数k：计划设备使用的年限数，即k=1,2,…,n。
状态变量Sk：表示役令。即在第k年初，设备已使用的年数。
决策变量xk：表示在第k年初对役令为Sk的设备的决策，是更新，还是继续使用，即
状态转移方程：
阶段指标：
指标函数：(k=1,2,…,n)
最优指标函数fk(Sk)表示第k年初，使用一台役令为Sk年的设备，到第n年末最大收益。即
因此，基本方程为：
fn+1(sn+1)=0
例：设某台新设备的年效益及年均维修费，更新净费用如下表所示。试作今后5年内的更新决策计划，使总收益最大。（设(=1）
（千元）
役令t
项目
0
1
2
3
4
5
效 益rk(t)
5
4.5
4
3.75
3
2.5
维修费uk(t)
0.5
1
1.5
2
2.5
3
更新费ck(t)
0.5
1.5
2.2
2.5
3
3.5
解：如前所述建立动态规划模型。n=5，由于s1=0，所以用逆序法求解。
k=5
由于，s5可取1,2,3,4，所以有
=3.5 x5*(1)=K
=2.5 x5*(2)=K
=2 x5*(3)=R
=1.5 x5*(4)=R
k=4
此时s4可取1,2,3
=6.5 x4*(1)=R
=5.8 x4*(2)=R
=5.5 x4*(3)=R
k=3
此时s3可取1,2。按上述方法计算有
f3(1)=9.5 x3*(1)=R
f3(2)=8.8 x3*(2)=R
k=2
由于s2只能取1，所以
f2(1)=12.5 x2*(1)=R
k=1
由于s1只能取0，所以
f1(0)=17 x1*(0)=K
为了求得该问题的解，将上述计算结果，并由状态转移方程
反推。即
x1*(0)=k—→得S2=1查f2(1)，知x2*(1)=R
—→得S3=1—→x3*(1)=R
—→S4=1—→x4*(1)=R
—→S5=1—→x5*(1)=K。
于是该设备更新问题的最优策略为：(K,R,R,R,K)。即第1年初购买的设备第2,3,4年初各更新一次，用到第5年末，其最佳效益为17千元。
第三章 动态规划动态规划是解决一类多阶段决策问题的优化方法，也是考察问题的一种途径，而不是一种算法（如LP单纯形法）。因此它不象LP那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。
动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题，且它的每一阶段都需进行决策，则这类问题均可用动态规划方法进行求解。
根据多阶段决策过程的时序和决策过程的演变，动态规划方法有以下四种类型：离散确定性、离散随机性、连续确定性和连续随机性。
§1动态规划的基本概念和最优化原理一、引例（最短路线问题）
B1
1
C1
5
6
8
6
A 3
B2
C2
3
D1
5
6
E
B3
6
C3
5
D2
A
1
B 2
C 3
D 4
E
上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），试求一条由A到E的铺管线路，使总距离最短（或总费用最小）。
将该问题划分为4个阶段的决策问题，即第一阶段为从A到Bj（j=1，2，3），有三种决策方案可供选择；第二阶段为从Bj到Cj（j=1,2,3），也有三种方案可供选择；第三阶段为从Cj到Dj(j=1,2)，有两种方案可供选择；第四阶段为从Dj到E，只有一种方案选择。如果用完全枚举法，则可供选择的路线有3×3×2×1=18（条），将其一一比较才可找出最短路线：
A→B1→C2→D3→E
其长度为15。
显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。
由于我们考虑的是从全局上解决求A到E的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至A点：
第四阶段，由D1到E只有一条路线，其长度f4（D1）=4，同理f4（D2）=3。
第三阶段，由Cj到Di分别均有两种选择，即
，决策点为D1
,决策点为D1
，决策点为D2
第二阶段，由Bj到Cj分别均有三种选择，即：
，决策点为C2
，决策点为C2或C3
，决策点为C2
第一阶段，由A到B，有三种选择，即：
，决策点为B1
f1(A=15)说明从A到E的最短铺管线长为1，最短路线的确定可按计算顺序反推而得。即
A→B1→C2→D1→E
上述最短路线问题的计算过程，也可借助于图形直观的表示出来：
10
10
B1
C1
4
5
3
D1
15
14
7
3
0
A
B2
C2
E
D2
11
8
B3
C3
图中各点上方框的数，表示该点到E的最短距离。图中双箭线表示从A到E的最短路线。
从引例的求解过程可以得到以下启示：
①对一个问题是否用上述方法求解，其关键在于能否将问题转化为相互联系的多个阶段的决策问题。
所谓多阶段决策问题是：把一个问题看作是一个前后关联具有链状结构的多阶段过程，也称为序贯决策过程。如下图所示：
决策
决策
决策
状态
状态
状态
状态
状态
1
2
n
②在处理各阶段决策的选取上，不仅只依赖于当前面临的状态，而且还要注意对以后的发展。即是从全局考虑解决局部（阶段）的问题。
③各阶段选取的决策，一般与“时序”有关，决策依赖于当前的状态，又随即引起状态的转移，整个决策序列就是在变化的状态中产生出来，故有“动态”含义。因此，把这种方法称为动态规划方法。
④决策过程是与阶段发展过程逆向而行。
二、动态规划的基本概念
1、阶段。阶段的划分，一般根据时序和空间的自然特征来划分，但要便于把问题的过程能转化为阶段决策的过程。描述阶段的变量称为阶段变量，常用自然数k表示。如引例可划分为4个阶段求解，k=1，2，3，4。
2、状态。状态就是阶段的起始位置。它既是该阶段某支路的起点，又是前一阶段某支路的终点。
（1）状态变量和状态集合。描述过程状态的变量称为状态变量。它可用一个数、一组数或一向量（多维情形）来描述，常用Sk表示第k阶段的状态变量。通常一个阶段有若干个状态。第k阶段的状态就是该阶段所有始点的集合。如引例中
，，，
（2）状态应具有无后效性（即马尔可夫性）。即如果某阶段状态给考虑，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。
在构造决策过程的动态规划模型时，不能仅由描述过程的具体特征这点去规定状态变量，而要充分注意是否满足无后效性要求。
3、决策与决策变量。在某阶段对可供选择状态的决定（或选择），称为决策。描述的变量称为决策变量。常用dk(Sk)表示第k阶段处于状态Sk时的决策变量，它是状态变量的函数。决策变量允许取值的范围，称为允许决策集合，常用Dk(Sk)表示。显然dk（Sk）∈Dk(Sk)。
如在引例的第一阶段中，若从B1出发，D2（B1）=，如果决定选取C2，则d2（B1）=C2。
4、策略与子策略。策略是一个决策序列的集合。当k=1时，Pin（S1）=就称为全过程的一个策略，简称策略，简记为Pin(S1).
称Pk,n(Sk)= 为由第k阶段开始到最后阶段止的一个子策略，简称后部子策略。简记为Pk,n(Sk)
称可供选择策略的范围，为允许策略集，用P表示。
动态规划方法就是要从允许策略集P中找出最优策略Pin*。
5、状态转移方程。它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程，用Sk+1=Tk(Sk,dk)表示。该方程描述了由第k阶段到第k+1阶段的状态转移规律。因此又称其为状态转移函数。
6、阶段指标、指标函数和最优指标函数
（1）衡量某阶段决策效益优劣的数量指标，称为阶段指标，用vk(Sk,dk)表示第k阶段的阶段指标。
在不同的问题中，其含义不同。它可以是距离、利润、成本等。
在引例中，用dk=Uk(Sk,dk)表示在第k阶段由点Sk到点Sk+1=dk(Sk)距离。如d2(B3,C1)=2。
（2）用于衡量所选定策略优劣的数量指标，称为指标函数。它是定义在全过程和所有后部子过程上确定的数量函数。记为Vk,n(Sk,Pk,n).
Vk,n(Sk,Pk,n)=Vk,n(Sk,dk,Sk+1,…Sn+1) k=1,2,…,n。
构成动态规划模型的指标函数，应具有可分离性，并满足递推关系。
常见的指标函数的形式有：
①
②
（3）最优指标函数fk(Sk),表示从第k阶段的状态Sk开始采用最优子策略P*k,n，到第n阶段的终止时所得到的指标函数值。
即fk(Sk)=0PtVk,n(Sk,uk,…Sn+1)
其中0Pt是最优化（0Ptimiyation）的缩写，可根据题意取max或min。
在引例中，指标函数Vk,n表示在第k阶段由点Sk至终点E的距离。fk(sk)表示第k阶段点Sk到终E的最短距离。f2(B1)=10表示从第2阶段中的点B1到点E的最短距离。
7、基本方程（递推关系式）
从引例求A到E的最短路的计算过程中可以看出，在求解的各个阶段，我们利用了k阶段与k+1阶段之间的递推关系；
一般地，
若则有
若
以上递推关系式称为动态规划的基本方程。
三、动态规划方法的基本思想与最优化原理
1、基本思想：动态规划方法的关键在于正确地写出基本方程，因此首先必须将问题的过程划分为多个相互联系的多阶段决策过程，恰当地选取状态变量和决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题。然后从边界条件开始，逆过程行进方向，逐段递推寻优。在每个子问题求解时，均利用它前面已求出的子问题的最优化结果依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。
在多阶段决策过程中，动态规划方法是既把当前的一段和未来的各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每阶段决策的选取是从全局来考虑，与该段的最优选择一般是不同的。
动态规划方法的基本思想体现了多阶段性、无后效性、递归性、总体优化性。
2、最优化原理动态规划方法基于R·Bellman等人提出的最优化原理：“作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对于先前的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简言之，“一个最优策略的子策略总是最优的”。
但是，最优化原理仅是策略最优性的必要条件，而基本方程是策略最优性的充要条件。由此可见，基本方程是动态规划理论与方法的基础。
§2、动态规划模型的建立与求解一、构成动态规划模型的条件建立动态规划模型，就是分析问题并建立问题的动态规划基本方程。为此，必须满足以下条件：
1、将问题的过程划分成恰当的阶段；
2、正确选择状态变量Sk，使它既能描述过程的演变，又要满足无后效性；
3、确定决策变量dk及每阶段的允许决策集合Dk(Sk)；
4、正确写出状态转移方程；
5、正确写出指标函数Vk,n的关系式，它应具有以下三个性质；
（1）是定义全过程和所有后部子过程上的数量函数；
（2）具有可分离性，并满足递推关系，即
Vk,n(Sk,dk,…Sn+1)=￠ (Sk,dk,Vk+1,n)
（3）函数￠（Sk,dk,Vk+1,n）对于Vk+1,n要求严格单调。
以上五点是正确写出动态规划基本方程的要素。
二、求解动态规划模型的方法
1、在已知初始状态S1下，采用逆序解法：（反向递归）
d1(s1)
d2(S2)
dk(Sk)
dk+1(Sk+1)
dn(Sn)
S1
S2
Sk
Sk+1
Sn
Sn+1
阶段1
阶段2
阶段k
阶段k+1
阶段n
v1(S1,v1)
v2(S2,v2)
v2(Sk,vk)
vk+1(Sk+1,vk+1)
vn(Sn,vn)
Vkn
fk(Sk)=0ptVk,n
寻优方向
按上图示意的求解方法称为逆序法。例如引例的求解，就是把A看作始端，E为终端，规定从A到E为过程的行进方向，而寻优则是从E到A逆过程进行，所以是采用了逆序法。
2、在已知终止状态Sn下，采用顺序解法（正向递归）
如果我们把引例中E看作始端，A为终端，规定从E到A过程为行进方向，而寻优则是从A到E过程进行求解的方法称为顺序法。其示意图如下：
d1(s1)
d2(S2)
dk(Sk)
dk+1(Sk+1)
dn(Sn)
S
S1
S2
Sk
Sk+1
Sn
阶段1
阶段2
阶段k
阶段k+1
阶段n
v1(S1,d1)
v2(S2,d2)
vk(Sk,dk)
vk+1(Sk+1,dk+1)
vn(Sn,dn)
V1,k
fk,(Sk)=0ptV1,k
寻优方向
逆序法与顺序法的不同仅在对始端终端看法的颠倒或在规定的行进方向不同。但在寻优时却都是逆行进方向，从最后一阶段开始，逐段逆推向前计算，找出最优结果。
3、两种解法在建模时的区别如下表所示
逆 序 法
顺 序 法
状态转移方程
Sk+1=Tk(Sk,dk)
Sk-1=Tk(Sk,dk)
指标函数定义
Vk,n=
fk(Sk)=0Pt或Vk,n=
V1,k=
fk(Sk)=0Pt或V1k=
基本方程形式
§3、建模训练与求解
一、维资源分配问题
例1某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂获得这种设备，可以提供的期望盈利如下表所示。问如何分配这五台设备给各厂，才能使国家得到的期望盈利最大？
工厂盈利设备台数
甲
乙
丙
0
1
2
3
4
5
0
3
7
9
12
13
0
5
10
11
11
11
0
4
6
11
12
12
解：设xj（j=1,2,3）分别表示分配给甲、乙、丙三个厂的设备台数，则此问题可写成以下数学模型：max=g1(x1)+g2(x2)+g3(x3)
其中g1(x1),g2(x2),g3(x3)分别对应表中甲、乙、丙厂的期望盈利数。
先考虑构成动态规划模型的条件：
1、按工厂将问题划分为三个阶段，并将工厂编号为k=1,2,3。
2、设状态变量Sk表示为分配给第k个工厂至第3个工厂的设备台数。（显然S1=5，所以可考虑用逆序法。）
3、决策变量Xk，表示为分配给第k个工厂的设备数。0≤Xk≤Sk。
4、状态转移方程为Sk+1=Sk-Xk
5、阶段指标gk(sk,xk)表示Xk设备分配到第k个工厂所得的期望盈利值。
因此基本方程为：
下面用逆序法采用表格形式进行求解
k=3,0≤X3≤S3 S4=S3-X3
S3
X3(S3)
g3(S3，X3)+f4(S4)
f3(S3)
X3*(S3)
0
0
0+0
0
0
1
1
4+0*
4
1
2
2
6+0*
6
2
3
3
11+0*
11
3
4
4
12+0*
12
4
5
5
12+0*
12
5
k=2 0≤X2≤S2 S3=S2－X2
S2
X2(S2)
g2(S2,X2)+f3(s3)
f2(S2)
X2*(S2)
0
0
0+0
0
0
1
0
1
0+4
5+0*
5
1
2
0
1
2
0+6
5+4
10+0*
10
2
3
0
1
2
3
0+11
5+6
10+4*
11+0
14
2
4
0
1
2
3
4
0+12
5+11*
10+6*
11+4
11+0
16
1或2
5
0
1
2
3
4
5
0+12
5+12
10+11*
11+6
11+4
11+0
21
2
k=1 0≤X1≤S1 S2=S1－X1
S1
X1(S1)
g2(S1X1)+f2(s2)
f1(s1)
x1*
5
0
1
2
3
4
5
0+21*
3+16
7+14*
9+10
12+5
13+0
21
0或2
按计算表格的顺序反推，得最优分配方案有两个：
第一方案：x1*=0 x2*=2 x3*=3
第二方案：x1*=2 x2*=2 x3*=1
它们所得的总盈利都为21（万元）
本例若设Sk表示分配给从第1个工厂到第k个工厂的设备台数，即S3=5，因此，本例还可用顺序法求解，其结果完全一致。
例1实际上是一个一维资源分配问题。
一维资源分配问题总可以写成“静态规划”问题：
MaxZ=g1(x1)+g2(x2)+…+gn(xn)
由于这类问题的特殊结构，可以把它看成是一个阶多段决策问题，并利用动态规划的递推关系求解。一般有
（1）阶段划分：通常把资源分配给一个或几个使用者的过程作为一个阶段。即把问题中变量的个数作为阶段数，k=1,2,…n。
（2）状态变量SK的含义：SK表示分配用于生产第k种产品至第n种产品的资源数。显然S1=a，所以该类问题可用逆序法求解。（也可用顺序法，Sn=a）
（3）决策变量dk的选定：dk=xk，含义为分配给生产第k种产品的资源数。允许决策集合为：Dk(Sk)={dk| 0≤dk=xk≤Sk}。
（4）状态转移方程：Sk+1=Sk―dk=Sk―xk (Sk=Sk+1+xk)
（5）由于阶段指标vk(Sk,xk)=gk(xk)，所以指标函数：
于是基本方程为
二、生产存贮问题例2,某工厂要对一种产品制订今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的需求量如下表所示。假定生产每批产品的固定成本3(千元)，若不生产就为0；每单位产品成本为1(千元)；每个时期生产能力所允许的最大生产批量为不超过6个单位；每个时期未售出的产品，每单位需付存贮费0.5(千元)。还假定在第一个时期的初始库存量为0，第四个时期末的库存量也为0。问该厂应如何安排各个时期的生产与库存，才能在满足市场需求条件下，使总成本最小。
时 期(k)
1
2
3
4
需求量(dk)
2
3
2
4
解：先考虑构成动态规划模型的条件
1,阶段：把生产的四个时期作为四个阶段。k=1,2,3,4。
2,状态变量Sk表示第k时期初(发货以前)的库存量。(由题意有S1=0，S5=0，故可考虑用顺序法或逆序法。)
3,决策变量xk表示第k时期的生产量。
0≤xk≤min{Sk+1+dk,6} 其中dk为第k时期的需求量
4,状态转移方程为Sk+1=Sk+xk―dk（或Sk=Sk+1+dk―xk）。
5,阶段指标Vk(xk)表示第k时期的生产成本Ck(xk)与库存量的存贮费hk(Sk)之和。即Vk(xk)=Ck(xk)+hk(Sk)。其中
hk(Sk)=0.5Sk
于是指标函数，表示从第1时期到第k时期的总成本。
因此，基本方程为
下面用顺序法进行求解：
k=1，由f1(S2)=min{C1(x1)+h1(S2)}和s1=s2+d1－x1
x1=min{S2+2,6}
S2可在0与之间取值,即s2=0,1,2,3,4，于是由x1=min{S2+2,6}知，x1可取值为2,3,4,5,6。分别计算如下：
f1(0)=min{3+2+0.5×0}=5 有x1=2
x1=2
f1(1)=min{3+3+0.5×1}=6.5 有x1=3
x1=3
f1(2)=min{3+4+0.5×2}=8.5 有x1=4
x1=4
f1(3)=min{3+5+0.5×3}=9.5 有x1=5
x1=5
f1(4)=min{3+6+0.5×4}=11 有x1=6
x1=6
k=2，由f2(S3)=min{C2(x2)+h2(S3)+f1(S3+3－X2)}可知，
0≤x2≤min{S3+3,6}
S3可在0与之间取值。即S3可取值0,1,2,3。
x2可在0与min{S3+3,6}之间取值。分别计算如下：
由，有x2=0。
由，有x2=0。
用同样的方法计算f2(2)=min{C2(x2)+h2(2)+f1(5－x2)}=14，有x2=5
0≤x2≤5
f2(3)=min{C2(x2)+h2(3)+f1(6－x2)}=15.5，有x2=6
0≤x2≤6
k=3，由f3(S4)=min{C3(x3)+h3(S4)+f2(S3+2－x3)}可知，S4可在0与min{4,6－2}=4之间取值。x3可在0与min{S3+3,6}之间取值。分别计算如下：
，有x3=0。
，有x3=0或3。
用同样的方法计算
f3(2)=min{C3(x3)+h3(2)+f1(4－x3)}=17.5，有x3=4
0≤x3≤4
f3(3)=min{C3(x3)+h3(3)+f1(5－x3)}=19，有x3=5
0≤x3≤5
f3(4)=min{C3(x3)+h3(4)+f1(6－x3)}=20.5，有x3=6
0≤x3≤6
k=4，由f4(S5)=min{C4(x4)+h4(S5)+f3(S4+4－x4)}与S5=0
0≤x4≤min{S5+4,6}可知，
f4(0)=min{C4(x4)+h4(0)+f3(4－x4)}
0≤x4≤4
，有x4=0。
按计算顺序反推算，
x4=0—→x3=6—→x2=0—→x1=5(由Sk=Sk+1+dk―xk推出)
即每个时期的最优生产决策为:
x1*=5，x2*=0，x3=6，x4*=0
其相应的最小总成本为20.5千元。
三、设备更新问题在已知一台设备的效益函数r(t)，维修费用函数u(t)及更新费用函数C(t)条件下，在n年内，每年年初作出决策，是继续使用旧设备还是更换一台新设备，使n年总效益最大的这类问题称为设备更新问题。
设rk(t)表示在第k年设备已使用t年（或称役令为t年），再使用1年时的效益：
uk(t)表示在第k年设备役令为t年，再使用1年的维修费用；
Ck(t)表示在第k年卖掉一台役令为t的设备，买进一台新设备的更新净费用；
(为折旧因子(0≤(≤1)，表示1年以后的单位价值相当于现年的(单位。
构成该问题动态规划模型的条件：
阶段数k：计划设备使用的年限数，即k=1,2,…,n。
状态变量Sk：表示役令。即在第k年初，设备已使用的年数。
决策变量xk：表示在第k年初对役令为Sk的设备的决策，是更新，还是继续使用，即
状态转移方程：
阶段指标：
指标函数：(k=1,2,…,n)
最优指标函数fk(Sk)表示第k年初，使用一台役令为Sk年的设备，到第n年末最大收益。即
因此，基本方程为：
fn+1(sn+1)=0
例：设某台新设备的年效益及年均维修费，更新净费用如下表所示。试作今后5年内的更新决策计划，使总收益最大。（设(=1）
（千元）
役令t
项目
0
1
2
3
4
5
效 益rk(t)
5
4.5
4
3.75
3
2.5
维修费uk(t)
0.5
1
1.5
2
2.5
3
更新费ck(t)
0.5
1.5
2.2
2.5
3
3.5
解：如前所述建立动态规划模型。n=5，由于s1=0，所以用逆序法求解。
k=5
由于，s5可取1,2,3,4，所以有
=3.5 x5*(1)=K
=2.5 x5*(2)=K
=2 x5*(3)=R
=1.5 x5*(4)=R
k=4
此时s4可取1,2,3
=6.5 x4*(1)=R
=5.8 x4*(2)=R
=5.5 x4*(3)=R
k=3
此时s3可取1,2。按上述方法计算有
f3(1)=9.5 x3*(1)=R
f3(2)=8.8 x3*(2)=R
k=2
由于s2只能取1，所以
f2(1)=12.5 x2*(1)=R
k=1
由于s1只能取0，所以
f1(0)=17 x1*(0)=K
为了求得该问题的解，将上述计算结果，并由状态转移方程
反推。即
x1*(0)=k—→得S2=1查f2(1)，知x2*(1)=R
—→得S3=1—→x3*(1)=R
—→S4=1—→x4*(1)=R
—→S5=1—→x5*(1)=K。
于是该设备更新问题的最优策略为：(K,R,R,R,K)。即第1年初购买的设备第2,3,4年初各更新一次，用到第5年末，其最佳效益为17千元。
