4 动态规划
多阶段决策问题与动态规划
动态规划的基本概念
动态规划的步骤
动态规划的应用
1 求解静态规划问题
2 资源分配问题
3 不确定性采购问题
4 排序问题
例2 机器负荷分配问题
某种机器可以在高低两种不同的负荷下进行生产．在高负
荷下进行生产时，产品的年产量g和投入生产的机器数量u的关
系为 g＝g(u), 这时机器的年完好率为a（0<a<1)．在低负荷
下生产时，产品的年产量h和投入生产的机器数量v的关系为h
＝h(v), 这时机器的年完好率为b（a<b<1）．假定开始生产时
完好的机器数量为s1，要求制定一个五年计划,在每年开始时决
定机器在两种不同负荷下生产的数量,使五年内产品的总产量
最高。
多阶段决策问题与动态规划
多阶段决策问题和我们前面遇到的决策问题
不同，它是和时间有关的。与时间有关的活动过
程称为动态过程，其优化方法称为动态规划。而
与时间无关的活动过程称为静态过程，相应的的
优化方法称为静态规划。
(1)阶段（stage）把所研究的决策问题，按先后顺序
划分为若干相互联系的决策步骤，以便按一定的次序进
行求解。描述阶段的变量称阶段变量，常用k表示。
(2)状态（state）状态表示每个阶段开始时所处的自
然状况或客观条件，它描述了影响决策的因素随决策进
程的变化情况，它既是前面阶段所作决策的结果，又是
本阶段作出决策的出发点和依据。描述状态的变量称为
状态变量，第k阶段的状态变量常用sk表示。通常，在第
一阶段状态变量s1是确定的，称初始状态。
(3)决策（decision）决策表示在某一阶段处于某种
状态时，决策者在若干种方案中作出的选择决定。描述
决策的变量称决策变量，第k阶段的决策变量常用uk表
示。决策变量的取值会受到状态变量的制约，被限制在
某一范围之内。
动态规划的基本概念（一）
(4)策略（policy）把从第一阶段开始到最后阶段终
止的整个决策过程，称为问题的全过程；而把从第k
阶段开始到最后阶段终止的决策过程，或称为k子过
程。在全过程上，各阶段的决策按顺序排列组成的决
策序列p1,n＝{ u1,u2,……,un }称为全过程策略，简
称 策 略 ； 而 在 k子 过 程 上 的 决 策 序 列 pk,n＝ {
uk,uk+1,……,un }称为k子过程策略，也简称子策略。
(5)状态转移方程 若第k阶段的状态变量值为sk，当
决策变量uk的取值决定后，下一阶段状态变量sk+1的
值也就完全确定。即sk+1的值对应于sk和uk的值。这种
对应关系记为sk+1＝Tk(sk,uk)，称为状态转移方程。
状态转移方程描述了由一个阶段的状态到下一阶段的
状态的演变规律。
动态规划的基本概念（二）
(6)指标函数和最优值函数 指标函数分为阶段指标函数和过
程指标函数。阶段指标函数是对某一阶段的状态和决策产生
的效益值的度量，用vk(sk,uk)表示。过程指标函数是指过程
所包含的各阶段的状态和决策所产生的总的效益值，记为
Vk,n＝Vk,n(sk,uk,sk+1,uk+1,……,sn,un)
动态规划所要求的过程指标函数应具有可分离性，即可表
达为它所包含的各阶段指标函数的函数形式。常见的两种过
程指标函数形式是：
①各阶段指标函数的和 Vk,n＝∑vj(sj,uj)；
②各阶段指标函数的积 Vk,n＝∏vj(sj,uj)。
把过程指标函数Vk,n对k子过程策略pk,n求最优，得到一个
关于状态sk的函数，称为最优值函数，记为fk(sk)。即
fk(sk)＝ opt Vk,n(sk,uk,……,sn,un) uk,…,un
式中的“opt”（optimization）可根据具体问题而取min或
max。
(7)基本方程 通常动态规划问题的最优值函数满足
递推关系式。设过程指标函数为各阶段指标函数的和
的形式，即Vk,n＝∑vj(sj,uj)，则有
fk(sk)＝ opt {vk(sk,uk)+fk+1(sk+1)}
uk∈Dk(sk) (k＝n,n-1,…,1) 递推方程
fn+1(sn+1)＝0 边界条件
递推方程和边界条件一起称为动态规划的基本方程。
可根据边界条件，从k=n开始，由后向前逆推，逐
步求得各阶段的最优决策和相应的最优值，最后求出
f1(s1)时，就得到整个问题的最优解。
此问题的基本方程为
fk(sk)＝Min{dk(uk)+fk+1(sk+1)}
uk∈Dk(sk)
k＝6,5,4,3,2,1
f7(s7)＝0
动态规划的步骤（一）
当k=6时
按基本方程由后向前继续递推有:
当k=5时 当k=4时
当k=3时 当k=2时
当k=1时
由此可以看出，A到G
的最短路长为18，路径为：
A→B1→C2→D1→E2→F2
→G
现在把动态规划法的步骤归纳如下：
(1) 将所研究问题的过程划分为n个恰当的阶段，
k＝ 1,2,…,n；
(2) 正确地选择状态变量Sk，并确定初始状态S1的值；
(3) 确定决策变量uk以及各阶段的允许决策集Dk(Sk)；
(4) 给出状态转移方程；
(5) 给出满足要求的过程指标函数Vk,n及相应的最优
值函数；
(6) 写出递推方程和边界条件，建立基本方程；
(7) 按照基本方程递推求解。
以上步骤是动态规划法处理问题的基本步骤，其中
的前六步是建立动态规划模型的步骤。
动态规划的步骤（二）
例：机器负荷问题 某种机器可以在高低两种
不同的负荷下进行生产．在高负荷下进行生产
时，产品的年产量g和投入生产的机器数量u的
关系为 g＝8u, 这时机器的年完好率为a=
．在低负荷下生产时，产品的年产量h和投入
生产的机器数量v的关系为h＝5v, 这时机器的
年完好率为b=．假定开始生产时完好的机
器数量为s1，要求制定一个五年计划,在每年开
始时决定机器在两种不同负荷下生产的数量,
使五年内产品的总产量最高。
(1)按年数划分为5个阶段，k=1,2,3,4,5
(2)取第k年初完好的机器数sk为状态变量,
s1=1000(3)取第k年投入高负荷的机器数xk为决策变量, 0≤xk≤sk
(4)状态转移方程为 sk+1=+(sk-xk)=
(5)指标函数为Vk,5=∑[8xj+5(sj-xj)]=∑(5sj+3xj)
(6)基本方程为
fk(sk)＝ max {5sj+3xj +fk+1(sk+1)} k=5,4,3,2,1
0≤xk≤sk
f6(s6)＝0
解:
当k=5时
f5(s5)＝ max{5s5+3x5+f6(s6)}= max{5s5+3x5}=8s5
(x5*=s5) 0≤x5≤s5 0≤x5≤s5
当k=4时
f4(s4)＝max{5s4+3x4+8s5}=max{5s4+3x4+8()} 0≤x4≤s4 0≤x4≤s4
= max{+}= (x4*=s4) 0≤x4≤s4当k=3时
f3(s3)＝max{5s3+3x3+}=max{5s3+3x3+()} 0≤x3≤s3 0≤x3≤s3
= max{+}= (x3*=s3) 0≤x3≤s3当k=2时
f2(s2)=max{5s2+3x2+}=max{5s2+3x2+()} 0≤x2≤s2 0≤x2≤s2
= max{}= (x2*=0) 0≤x2≤s2当k=1时 f1(s1)= (x1*=0) f1(1000)=23700
s1=1000, x1*=0 s2=900, x2*=0 s3=810, x3*=810
s4=576, x4*=576 s5=397, x5*=397
某些静态规划问题可用动态规划法来求解。
例 用动态规划法求解
max z=
x1+x2+x3=c
xi≥0 i=1,2,3
动态规划的应用(一)
1 求解静态规划问题
资源分配问题可描述如下：设有某种原料，
总数量为a，分配给n个使用者。已知第i个使用
者得到数量xi的资源，可创造的收益为gi（xi）。
问应如何分配该资源，才能使总收益最大。
动态规划的应用(二)
用动态规划法处理这种问题时，通常把给一
个使用者分配资源的过程看成一个阶段，按n
个使用者分成先后n个决策阶段。即先给第1个
使用者分配资源，为第一阶段；再给第2个使
用者分配，为第2阶段；依此类推，最后给第n
个使用者分配，为第n阶段。
2 资源分配问题
例 某工业部门根据国家计划安排，拟将五
台某种高效率的机器分配给所属的甲、乙、
丙三个工厂，各工厂得到不同数量的机器可
获得的收益如下表。问应如何分配机器，才
能使各厂的总效益最大。
某单位准备在以后的n个时期内采购一批物资。各
时期的价格不是确定的，而是按照某种已知的概率分
布取值。试制定采购策略，确定在哪一时期以什么价
格采购，能使采购价的数学期望值最低。这类问题也
适合用动态规划法进行处理。下面通过实例加以说明。
例7 某厂生产上需要在近五周
内采购一批原料，而估计在未
来五周的价格有波动，其浮动
价格和概率策得如下表。试确
定该厂应在哪一周以什么价格
购入，能使其采购价的数学期
望值最小，并求出期望值。
动态规划的应用(三)
3 不确定性采购问题
设有n个工件需要在机床A、B上加工，每个工件都
必须先经过A而后B�两道加工工序。以ai、bi分别表示
工件i(1≤i≤n)在A、B上的加工时间。问应如何在两
机床上安排各工件的加工顺序，使在机床A上加工第一
个工件开始到在机床B上加工完最后一个工件为止，所
用的加工总时间最少？
加工工件在机床A上有加工顺序问题，在机床B上
也有加工顺序问题。可以证明：最优加工顺序在两台
机床上可同时实现。因此，最优排序方案可以只在机
床A、B上加工顺序相同的排序中寻找。即使如此，所
有可能的方案仍有n!个，这是一个不小的数，用穷举
法是不现实的。
动态规划的应用(四)
4 排序问题
用动态规划法可以推出，工件i应该排在工件j之
前的条件为 min(ai,bj)≤min(aj,bi)。根据这个条件，
构造下列排序方法：
a1 a2 … an
1)建立工时矩阵 M= b1 b2 … bn
2)在工时矩阵M中找出最小元素（若不止一个可任
选其一），若它在上行，则相应的工件排在最前位置；
若它在下行，则相应的工件排在最后位置。
3)将排定位置的工件所对应的列从M中划去，然后
对余下的工件再按2)进行排序。如此进行下去，直到
把所有工件都排完为止。
当加工顺序排定之后，工件在A上没有等待时间，
而在B上则常常需要等待。因此，寻求最优排序方案
只有尽量减少在B上等待加工的时间，才能使总加工
时间最短。
例 设有5个工件需在机床A、B上加工，加
工的次序为先A后B，每个工件需要的加工时
间如下表。 试安排加工顺序，使总加工时间
最少，并求出总加工时间。
