运筹学课件第五章动态规划制作：北京理工大学 吴祈宗等
2
第五章 动态规划多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容重点一,多阶段决策问题
(Multi-Stage decision process)
多阶段决策过程特点,
状态
x1 阶段 1
T1
决策 u1
状态
x2
决策 u2
阶段 2
T2
状态
x3,..
状态
xk
决策 uk
阶段 k
Tk
状态
xk+1...
状态
xn
决策 un
阶段 n
Tn
状态
xn+1
1.多阶段决策过程的最优化
1.多阶段决策过程的最优化动态规划方法与,时间,关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是,动态,的意思 。 然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入,时段,因素,就可以将其转化为一个多阶段决策问题 。
在本章中将介绍这种处理方法 。
5
1.多阶段决策过程的最优化二,多阶段决策问题举例属于多阶段决策类的问题很多,
例如：
1)工厂生产过程,由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,
就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排 。
1.多阶段决策过程的最优化
2)设备更新问题,一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,
维修费用增加,可正常使用的工时减少,
加工质量下降,经济效益差,并且,使用的年限越长,处理价值也越低,自然,如果卖去旧的买新的,还需要付出更新费,因此就需要综合权衡决定设备的使用年限,使总的经济效益最好 。
7
1.多阶段决策过程的最优化
3)连续生产过程的控制问题,一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此,应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大 。
1.多阶段决策过程的最优化
许多问题的发展过程都与时间因素有关 。
在这类多阶段决策问题中,阶段的划分常取时间区段 来表示,并且各个阶段上的决策往往也与时间因素有关 。 这就使它具有了,动态,的含义,所以把处理这类动态问题的方法称为动态规划方法 。
实际中尚有许多不包含时间因素的一类
,静态,决策问题,就其本质而言是一次决策问题,是非动态决策问题,但是也可以 人为地引入阶段的概念 当作多阶段决策问题,应用动态规划方法加以解决 。
1.多阶段决策过程的最优化
4） 资源分配问题,资源分配问题便属于这类静态问题 。 如：某工业部门或公司,拟对其所属企业进行稀缺资源分配,
为此需要制定出收益最大的资源分配方案 。 这种问题原本要求一次确定出对各企业的资源分配量,它与时间因素无关,
不属动态决策,但是,我们可以人为地规定一个资源分配的阶段和顺序,从而使其变成一个多阶段决策问题 (后面我们将详细讨论这个问题 )。
10
1.多阶段决策过程的最优化
5） 运输网络问题,如 图 5-1所示的运输网络,点间连线上的数字表示两地距离 (也可是运费,时间等 ),要求从
fk(sk)至 v10的最短路线 。
这种运输网络问题也是静态决策问题 。 但是,按照网络中点的分布,
可以把它分为 4个阶段,而作为多阶段决策 问题来研究 。
1.多阶段决策过程的最优化三,动态规划求解的多阶段决策问题的特点
通常多阶段决策过程的发展是通过状态的一系列变换来实现的 。
一般情况下,系统在某个阶段的状态转移除与本阶段的状态和决策有关外,还可能与系统过去经历的状态和决策有关 。
适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,即 具有
,无后效性,的多阶段决策过程 。
12
1.多阶段决策过程的最优化
无后效性 （又称马尔柯夫性）
无后效性 （又称马尔柯夫性）
是指系统从某个阶段往后的发展，
仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策 (历史 )无关。
13
1.多阶段决策过程的最优化四,动态规划方法导引为了说明动态规划的基本思想方法和特点,
下面以图 5-1所示为例讨论的求最短路问题的方法
1.多阶段决策过程的最优化图 5-11 运输网络图示 返回
1.多阶段决策过程的最优化
一般有三种思路求解全枚举法或穷举法,它的基本思想是列举出所有可能发生的方案和结果,再对它们一一进行比较,求出最优方案 。
可以计算：从 v1到 v10的路程可以分为 4个阶段 。 第一段走法有 3种,第二,三两段走法各有 2 种,第 四 段 走 法 仅 1 种,共有
3× 2× 2× 1＝ 12条可能的路线,分别算出各条路线的距离,最后进行比较,可知 最优路线是 v1 → v3 → v7 → v9 → v10,最短距离是
18,用穷举法求最优路线的计算工作量将会十分庞大,而且其中包含着许多重复计算,
16
1.多阶段决策过程的最优化局部最优路径法,某人从 k点出发,并不顾及全线是否最短,
只是选择当前最短途径,,逢近便走,,错误地以为局部最优会致整体最优,在这种想法指导下,所取决策必是 v1 → v3
→ v5 → v8 → v10,全程长度是 20；显然,这种方法的结果常是错误的,
17
1.多阶段决策过程的最优化动态规划方法,动态规划方法寻求该最短路问题的基本思想是,
首先将问题划分为 4个阶段,每次的选择总是综合后继过程的一并最优进行考虑,在各段所有可能状态的最优后继过程都已求得的情况下,全程的最优路线便也随之得到 （ 如图 ）
1.多阶段决策过程的最优化图 1 运输网络动态规划方法求解图示跳过过程
19
1.多阶段决策过程的最优化具体说,此问题先从 v10开始,因为 v10是终点 。 再无后继过程,故可以接着考虑第 4阶段上所有可能状态 v8,v9的最优后续过程,因为从 v8,v9 到 v10的路线是唯一的,所以 v8,v9
的最优决策和最优后继过程就是到 v10,它们的最短距离分别是 5和 3。
接着考虑阶段 3上可能的状态 v5,v6,v7,
到 v10的最优决策和最优后继过程,在状态 V5
上,虽然到 v8是 8,到 v9是 9,但是综合考虑后继过程整体最优,取最优决策是到 v9,最优后继过程是 v5→ v9 → v10,最短距离是 12,同理,状态 v6的最优决策是至 v8 ； v7的最优决策是到 v9 。
20
1.多阶段决策过程的最优化同样,当阶段 3上所有可能状态的最优后继过程都已求得后,便可以开始考虑阶段 2上所有可能状态的最优决策和最优后继过程,如 v2的最优决策是到 v5,最优路线是 v2→ v5→ v9→ v10,最短距离是 15…依此类推,最后可以得到从初始状态 v1的最优决策是到 v3最优路线是 v1→ v3→ v7→ v9→ v10,
全程的最短距离是 18。 图 5—1中粗实线表示各点到的最优路线,每点上方括号内的数字表示该点到终点的最短路距离 。
21
1.多阶段决策过程的最优化小 结
全枚举法虽可找出最优方案,
但不是个好算法,
局部最优法则完全是个错误方法,
只有 动态规划方法属较科学有效的算法
22
2.动态规划的基本概念一,动态规划的基本概念使用动态规划方法解决多阶段决策问题,首先要将实际问题写成动态规划模型,同时也为了今后叙述和讨论方便,这里需要对动态规划的下述一些基本术语进一步加以说明和定义：
2.动态规划的基本概念
(一 ) 阶段和阶段变量为了便于求解和表示决策及过程的发展顺序,而把所给问题恰当地划分为若干个相互联系又有区别的子问题,称之为多段决策问题的 阶段 。 通常,阶段是按决策进行的时间或空间上先后顺序划分的 。
用以描述阶段的变量叫作 阶段变量,一般以 k表示阶段变量,阶段数等于多段决策过程从开始到结束所需作出决策的数目 。
2.动态规划的基本概念
（ 二 ） 状态,状态变量和可能状态集
1.状态与状态变量：描述事物 (或系统 )在某特定的时间与空间域中所处位置及运动特征的量,称为 状态 。 反映状态变化的量叫做 状态变量 。 状态变量包含在给定的阶段上确定全部允许决策所需要的信息 。 每个阶段的状态可分为初始状态和终止状态,或称输入状态和输出状态,阶段 k的初始状态记作 sk,终止状态记为 sk+1。 通常定义阶段的状态即指其初始状态 。
25
2.动态规划的基本概念
2,可能状态集一般状态变量的取值有一定的范围或允许集合,称为可能状态集,或可达状态集 。 可能状态集实际上是关于状态的约束条件 。 通常可能状态集用相应 阶段状态 sk的大写字母 Sk表示,
sk?Sk,可能状态集可以是一离散取值的集合,也可以为一连续的取值区间,视具体问题而定,
（ 三 ） 决策,决策变量和允许决策集合决策 的实质是关于状态的选择,
是决策者从给定阶段状态出发对下一阶段状态作出的选择 。
用以描述决策变化的量称之 决策变量 。 决策变量的值可以用数,向量,
其它量,也可以是状态变量的函数,记以 uk= uk(sk),表示于阶段 k状态 sk时的决策变量 。
2.动态规划的基本概念
27
2.动态规划的基本概念决策变量的取值往往也有一定的允许范围,称之 允许决策集合 。 决策变量 uk(sk)的允许决策集用 Uk(sk)表示,
uk(sk)∈ Uk(sk)
允许决策集合实际是决策的约束条件 。
28
（ 四 ） 策略和允许策略集合策略 (Policy)也叫决策序列,策略有 全过程策略 和 k部子策略 之分,
全过程策略是指由依次进行的 n个阶段决策构成的决策序列,简称策略,
表示为 p1,n{u1,u2,…,un}。 从 k阶段到第
n阶段,依次进行的阶段决策构成的决 策序 列称 为 k 部子 策略,表示 为
pk,n{uk,uk+1,…,un},显然当 k=1时的 k
部子策略就是全过程策略 。
2.动态规划的基本概念
29
2.动态规划的基本概念
在实际问题中，由于在各个阶段可供选择的决策有许多个，
因此，它们的不同组合就构成了许多可供选择的决策序列 (策略 )，由它们组成的集合，称之允许策略集合,记作 P1,n,从允许策略集中，找出具有最优效果的策略称为 最优策略 。
30
（ 五 ） 状态转移方程系统在阶段 k处于状态 sk，
执行决策 uk(sk)的结果是系统状态的转移,即系统由阶段 k的初始状态 sk转移到终止状态 sk+1 。
2.动态规划的基本概念
31
2.动态规划的基本概念对于具有无后效性的多阶段决策过程,系统由阶段 k到阶段
k+1的状态转移完全由阶段 k的状态 sk和决策 uk(sk) 所确定,与系统过去的状态 s1,s2,…,sk -1及其决策 u1(s1),u2(s2),…,uk-1(sk-1)
无关 。
32
系统状态的这种转移,用数学公式描述即有：
(5－ 1)
通常称上式 (5-1)为多阶段决策过程的状态转移方程 。 有些问题的状态转移方程不一定存在数学表达式,但是它们的状态转移,还是有一定规律可循的 。
2.动态规划的基本概念
))((1 kkkkk su,sTs
33
2.动态规划的基本概念
(六 ) 指标函数用来衡量策略或子策略或决策的效果的某种 数量指标,就称为 指标函数 。 它是定义在全过程或各子过程或各阶段上的确定数量函数 。 对不同问题,指标函数可以是诸如费用,成本,产值,
利润,产量,耗量,距离,时间,
效用,等等 。
34
1)阶段指标函数 （ 阶段效应 ）
用 gk(sk,uk)表示第 k段处于 sk状态且所作决策为 uk(sk)时的指标,
则它就是 第 k段指标函数,简记为 gk
2.动态规划的基本概念
35
(2)过程指标函数（目标函数）
用 Rk(sk,uk)表示第 k子过程的指标函数 。
Rk(sk,uk) 不仅跟当前状态 sk有关,还跟该子过程策略 pk(sk)有关,因此它是 sk和 pk(sk)的函数,
严格说来,应表示为,
))s(p,s(R kkkk
实际应用中上式可表示为
Rk(sk,uk) 或 Rk(sk) ；
过程指标函数 Rk(sk) 通常是描述所实现的全过程或 k 后部子过程效果优劣的数量指标,它是由各阶段的阶段指标函数 gk(sk,uk) 累积形成的 。
2.动态规划的基本概念
37
过程指标函数形式：
适于用动态规划求解的问题的过程指标函数 （ 即目标函数 ）,必须具有关于阶段指标的可分离形式,对于 k部子过程的指标函数可以表示为：
（?表示某种运算 ）
)u,s(g)u,s(g)u,s(g
)u,s,,u,s,u,s(RR
nnnkkkkkk
nnkkkkn,kn,k
111
11
38
多阶段决策问题中,常见的目标函数形式之一是取各阶段效应之和的形式,即,
2.动态规划的基本概念
n
ki
i
u
i
s
i
g
k
R ),(
39
总之，具体问题的目标函数表达形式需要视具体问题而定。
有些问题,如系统可靠性问题,其目标函数是取各阶段效应的连乘积形式,如
n
ki
iiik usgR ),(
40
(七 ) 最优解用 fk(sk)表示第 k子过程指标函数,在状态 sk下的最优值,即称 fk(sk)为第 k子过程上的最优指标函数 ；
2.动态规划的基本概念
))(,( kkkk spsR
nkspsRoptsf kkkk
sPp
kk
kKk
,,2,1) ) },(,({)(
)(
41
2.动态规划的基本概念
相应的子策略称为 sk状态下的最优子策略,记为 pk*(sk) ；而构成该子策赂的各段决策称为该过程上的最优决策,记为
有简记为
)(,),(),( 11 nnkkkk sususu
nksusususp nnkkkkkk,,2,1) },(,),(),({)( 11
nkuuup nkkk,,2,1},,,,{ 1
42
特别当 k=1且 s1取值唯一时,f1(s1)就是问题的最优值，而 p1* 就是最优策略。
但若取值不唯一,则问题的最优值记为 f0有最优策略即为 s1=s1*状态下的最优策略：
我们把最优策略和最优值统称为问题的最优解 。
2.动态规划的基本概念
)()}({ 111110
11
ssfsfo p tf
Ss
},,),({)( 211111 nuusussp?
),,2,1( nku k
43
2.动态规划的基本概念
(八 ) 多阶段决策问题的数学模型综上所述,适于应用动态规划方法求解的一类多阶段决策问题,亦即具有无后效性的多阶段决策问题的数学模型呈以下形式,
nk
Uu
Ss
usTs
ts
usususRRoptf
kk
kk
kkkk
nn
uu
n
,,2,1
),(
..
),,,,,,(
1
2211
~
1
（ 5-5）
44
式中,OPT”表示最优化,视具体问题取 max或 min。
上述数学模型说明了对于给定的多阶段决策过程,求取一个 (或多个 )最优策略或最优决策序列,使之既满足式 (5-5)给出的全部约束条件,又使式 (5-5)所示的目标函数取得极值,并且同时指出执行该最优策略时,过程状态演变序列即最优路线
2.动态规划的基本概念
},,,{ 21 nuuu?
},,,,{ 121 nn ssss?
二,动态规划的最优化原理与基本方程
1,标号法 (只适用于一类最优路线问题的特殊解法 ）
标号法是借助网络图通过分段标号来求出最优路线的一种简便,直观的方法 。
通常标号法采取,逆序求解,的方法来寻找问题的最优解,即从最后阶段开始,
逐次向阶段数小的方向推算,最终求得全局最优解 。
2.动态规划的基本原理
46
标号法的一般步骤：
（ 1） 给最后一段 标号,该段各状态 (即各始点 )到终点的距离用数字分别标在各点上方的方格内,并 用粗箭线连接各点和终点 。
2.动态规划的基本原理
47
标号法的一般步骤（续）：
（ 2） 向前递推,给前一阶段的各个状态 标号 。 每个状态上方方格内的数字表示该状态到终点的最短距离 。 将刚标号的点沿着最短距离所对应的已标号的点用粗箭线连接起来,
表示出各刚标号的点到终点的最短路线 。
48
（ 3） 逐次向前递推,直到将第一阶段的状态 (即起点 )标号,起点方格内的数字就是起点到终点的 最短距离,从 起点开始连接终点的粗箭线 就是 最短路线 。
标号法的一般步骤（续）：
49
2.动态规划的基本原理例 5.2：网络图 5－ 2表示某城市的局部道路分布图。一货运汽车从 S出发，最终到达目的地
E。其中 Ai(i＝ 1,2,3),Bj(j＝ 1，
2)和 Ck(k＝ 1,2)是可供汽车选择的途经站点，各点连线上的数字表示两个站点问的距离。
问此汽车应走哪条路线，使所经过的路程距离最短?
50
2.动态规划的基本原理图 5-2 某城市的局部道路分布图
0
5
8
11
14
17
19
18
21
2.动态规划的基本原理图 5-3某城市局部道路求最短路径的过程结果如图 5-3所示 。 从 S到 E最短距离为
21共有三条最短路线：
(1)
(2)
(3)
标号法不但给出起点到终点的最短路线和最短距离,同时也给出每一状态到终点的最短路线及其最短距离 。
2.动态规划的基本原理
ECBAS 111
ECBAS 113
ECBAS 123
54
作业：
习题 --1
55
2,最优化原理 （ 贝尔曼最优化原理 ）
作为一个全过程的最优策略具有这样的性质,对于最优策略过程中的任意状态而言,无论其过去的状态和决策如何,
余下的诸决策必构成一个最优子策略 。
2.动态规划的基本原理
56
2.动态规划的基本原理该原理的具体解释是,若某一全过程最优策略为：
则对上述策略中所隐含的任一状态而言,第 k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略 p1*中,即为
)}(),(,),(),({)( 221111 nnkk sususususp
)}(,),(),({)( 11 nnkkkkkk susususp
3.函数基本方程基于这个原理,提出了一种逆序递推法；该法的关键在于给出一种递推关系 。 一般把这种递推关系称为 动态规划的函数基本方程 。
对于求最小的加法的计算公式为：
2.动态规划的基本原理
121
0
11
11
,,,n,nk
) },s(f))s(u,s(g{m i n)s(f
)s(f
kkkkkk
)s(Uu
kk
nn
kkk
（边界条件）
阶段指标一般地,
(1)当过程指标函数为,和,的形式时,相应的函数基本方程为
2.动态规划的基本原理
))}(,({)(
)( kkkksPpkk
spsRo p tsf
kKk?
}),({
n
ki iii
usgopt
121
0
11
11
,,,n,nk
) },s(f))s(u,s(g{opt)s(f
)s(f
kkkkkk
Uu
kk
nn
kk
(2) 当过程指标函数为,积,的形式时,相应的函数基本方程为可以看出,和,积函数的基本方程中边界条件 (即 的取值 )是不同的 。
2.动态规划的基本原理
))}(,({)(
)( kkkksPpkk
spsRo p tsf
kKk?
n
ki iii
usgo p t )},({
121
1
11
11
,,,n,nk
)}s(f))s(u,s(g{opt)s(f
)s(f
kkkkkk
Uu
kk
nn
kk
)( 11 nn sf
3.动态规划方法的基本步骤
用函数基本方程逆推求解是常用的方法：
首先要有效地 建立动态规划模型,
然后再 递推求解,最后 得出结论,
正确地建立一个动态规划模型,
是解决问题的关键 。
正确的动态规划模型,应该满足下列条件：
61
3.动态规划方法的基本步骤
（ 1） 应将实际问题恰当地分割成 n个子问题 (n个阶段 )
通常是根据时间或空间而划分的,或者在经由静态的数学规划模型转换为动态规划模型时,
常取静态规划中变量的个数 n。
62
3.动态规划方法的基本步骤
（ 2） 正确地定义状态变量 sk，
使它既能正确地描述过程的状态，
又能满足无后效性．
动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：
63
3.动态规划方法的基本步骤
要能够 正确地描述受控过程的变化特征 。
要满足无后效性 。 即如果在某个阶段状态已经给定,那么在该阶段以后,过程的发展不受前面各段状态的影响,如果所选的变量不具备无后效性,就不能作为状态变量来构造动态规划的模型 。
64
3.动态规划方法的基本步骤
要满足可知性 。 即所规定的各段状态变量的值,可以直接或间接地测算得到 。
一般在动态规划模型中,状态变量大都选取那种可以进行累计的量 。
在解静态规划模型时,线性与非线性规划中约束条件的个数,相当于动态规划中状态变量 sk的维数,约束条件所表示的内容,就是状态变量 sk所代表的内容 。
65
3.动态规划方法的基本步骤
（ 3） 正确地定义决策变量及各阶段的允许决策集合 Uk(sk)。
一般将问题中待求的量,选作动态规划模型中的决策变量,或者在把静态规划模型 (如线性与非线性规划 )转换为动态规划模型时,常常取前者的变量 xj 为后者的决策变量 uk 。
66
3.动态规划方法的基本步骤
（ 4） 正确地写出状态转移方程 。 要能正确反映状态转移规律 。 如果给定第 k 阶段状态变量 sk 的值,则该段的决策变量
uk 一经确定,第 k+1段的状态变量 sk+1的值也就完全确定,即有
sk+1=Tk(sk,uk)
67
3.动态规划方法的基本步骤
（ 5） 正确地写出目标函数,
目标函数应满足下列性质：
可分性,即对于所有 k后部子过程,其目标函数仅取决于状态 sk
及其以后的决策
uk,uk+1,┈,un
就是说它是定义在全过程和所有后部子过程上的数量函数 。
68
3.动态规划方法的基本步骤
要满足递推关系,即
函数对其变元 Rk+1来说要 严格单调 。
)],,(,,[
),,,,,(,
111
111
nkkkkk
nkkkknk
ssRus
sususR
)],,(,,[ 111 nkkkkk ssRus
69
写出动态规划函数基本方程
3.动态规划方法的基本步骤
121
0
11
11
,,,n,nk
) },s(f))s(u,s(g{opt)s(f
)s(f
kkkkkk
Uu
kk
nn
kk
121
1
11
11
,,,n,nk
)}s(f))s(u,s(g{opt)s(f
)s(f
kkkkkk
Uu
kk
nn
kk
或
70
学习例题的方法建议：
第一步 先看问题，充分理解问题的条件、情况及求解目标。
第二步 结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的
“四大要素、一个方程” —— 这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。
4.动态规划方法应用举例
71
第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。
第四步 把自己的求解放到一边，
看书中的求解方法，要充分理解教材中的论述。
第五步 对照自己的求解，分析成败。
4.动态规划方法应用举例
74
求 最 短 路 径
75
BA
CB
D
B
C
D
E
C
2
1
2
3
1
2
3
1
2
5
1
12
14
10
6
10
4
13
12
11
3
9
6
5
8
10
5
2
阶段 1 阶段 2 阶段 3 阶段 4 阶段 5
求 最 短 路 径例 5.5
76
将问题分成五个阶段，第 k阶段到达的具体地点用状态变量 xk表示，例如,x2=B3表示第二阶段到达位置 B3，
等等。这里状态变量取字符值而不是数值。
将决策定义为到达下一站所选择的路径,例如目前的状态是 x2=B3,这时决策允许集合包含三个决策,它们是
D2(x2)=D2(B3)={B3?C1,B3?C2,B3?C3}
求 最 短 路 径
77
求最短路径最优指标函数 fk(xk) 表示从目前状态到 E的最短路径 。 终端条件为
f5 ( x5 ) = f5 ( E ) = 0
其含义是从 E到 E的最短路径为 0。
第四阶段的递推方程为
从 f5 ( x5 ) 到 f4 ( x4 ) 的递推过程用下表表示 x 4 D 4 (x 4 ) x 5 v 4 (x 4,d 4 ) v 4 (x 4,d 4 )+f 5 (x 5 ) f 4 (x 4 ) 最优决策 d 4 *
D 1 D 1? E E 5 5 + 0 = 5 * 5 D 1? E
D 2 D 2? E E 2 2 + 0 = 2 * 2 D 2? E
)}x(f)d,x(V{m i n)x(f
)x(Dd 5544444 444
79
其中 *表示最优值，在上表中，由于决策允许集合 D4(x4)中的决策是唯一的，因此这个值就是最优值。
由此得到 f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：
f 4 (x 4 ) 的表达式
x 4 f 4 (x 4 ) 最优决策 d 4 *
D 1 5 D 1? E
D 2 2 D 2? E
求 最 短 路 径第三阶段的递推方程为：
从 f 4 (x 4 ) 到 f 3 (x 3 ) 的递推过程用表格表示如下,
x 3 D 3 (x 3 ) x 4 v 3 (x 3,d 3 ) v 3 (x 3,d 3 )+f 4 (x 4 ) f 3 (x 3 ) 最优决策 d 3 *
C 1
C 1? D 1
C 1? D 2
D 1
D 2
3
9
3+5=8*
9+2=11
8 C 1? D 1
C 2
C 2? D 1
C 2? D 2
D 1
D 2
6
5
6+5=11
5+2=7*
7
C 2? D 2
C 3
C 3? D 1
C 3? D 2
D 1
D 2
8
10
8+5=13
10+2=12*
12 C 3? D 2
)}(),({m in)( 44333
)(33 333
xfdxvxf
xDd
求 最 短 路 径
81
由此得到 f3(x3)的表达式：
x 3 f 3 ( x 3 ) 最优决策 d 3 *
C 1 8 C 1? D 1
C 2 7 C 2? D 2
C 3 12 C 3? D 2
第二阶段的递推方程为,
)}(),({m i n)( 33222
)(22 222
xfdxvxf
xDd
从 f 3 ( x 3 ) 到 f 2 ( x 2 ) 的递推过程用表格表示如下,
求 最 短 路 径
82
x 2 D 2 (x 2 ) x 3 v 2 (x 2,d 2 ) v 2 (x 2,d 2 )+f 3 (x 3 ) f 2 (x 2 ) 最优决策 d 2 *
B
1
B
1
C
1
B
1
C
2
B
1
C
3
C
1
C
2
C
3
12
14
10
12+8=20*
14+7=21
10+12=22
20
B
1
C
1
B
2
B
2
C
1
B
2
C
2
B
2
C
3
C
1
C
2
C
3
6
10
4
6+8=14*
10+7=17
4+12=16
14
B
2
C
1
B
3
B
3
C
1
B
3
C
2
B
3
C
3
C
1
C
2
C
3
13
12
11
13+8= 21
12+7=19*
11+12=23
19
B
3
C
2
求 最 短 路 径
83
由此得到 f2(x2)的表达式：
x 2 f 2 (x 2 ) 最优决策 d 2 *
B 1 20 B 1? C 1
B 2 14 B 2? C 1
B 3 19 B 3? C 2
求 最 短 路 径
84
第一阶段的递推方程为：
)}(),({m i n)( 22111
)(11 111
xfdxvxf
xDd
从 f 2 ( x 2 ) 到 f 1 ( x 1 ) 的递推过程用表格表示如下,
x 1 D 1 (x 1 ) x 2 v 1 (x 1,d 1 ) v 1 (x 1,d 1 )+f 2 (x 2 ) f 1 (x 1 ) 最优决策 d 1 *
A
A? B 1
A? B 2
A? B 3
B 1
B 2
B 3
2
5
1
2+20=22
5+14=19*
1+19=20
19
A? B 2
求 最 短 路 径
85
由此得到 f1(x1)的表达式
x 1 f 1 (x 1 ) 最优决策 d 1 *
A 19 A? B 2
求 最 短 路 径
86
资 源 分 配 问 题
87
例 5.6,有资金 4万元，投资 A,B,C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目 A,B,C的投资效益
（万吨）和投入资金（万元）关系见下表：
求对三个项目的最优投资分配，使总投资效益最大。
资 源 分 配 问 题
1,阶段 k：每投资一个项目作为一个阶段；
2,状态变量 xk：投资第 k个项目前的资金数；
3,决策变量 dk：第 k个项目的投资；
4,决策允许集合,0≤dk≤xk
5,状态转移方程,xk+1=xk-dk
6,阶段指标,vk(xk,dk)见表中所示；
7,递推方程：
fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}
8,终端条件,f4(x4)=0
资 源 分 配 问 题
89
k=4,f4(x4)=0
k=3,0≤d3≤x3,x4=x3-d3
资 源 分 配 问 题
90
k=2,0≤d2≤x2,x3=x2-d2
资 源 分 配 问 题
91
k=1,0≤d1≤x1,x2=x1-d1
资 源 分 配 问 题
92
作业：
习题 — 2,3
93
背 包 问 题
94
背 包 问 题
95
则 Max z = c1x1+c2x2+…+cnxn
s.t,w1x1+w2x2+…+wnxn≤W
x1,x2,…,xn为正整数
1,阶段 k,第 k 次装载第 k 种物品
（ k=1,2,…,n）
2,状态变量 sk：第 k次装载时背包还可以装载的重量；
3,决策变量 xk：第 k次装载第 k种物品的件数；
背 包 问 题
96
4,决策允许集合：
Dk(sk)={xk|0? xk?sk/wk,xk为整数 }；
5,状态转移方程,sk+1=sk-wkxk
6,阶段指标,vk=ckxk
7,递推方程
fk(sk)=max{ckxk+fk+1(sk+1)}
=max{ckxk+fk+1(sk-wkxk)}
8,终端条件,fn+1(sn+1)=0
背 包 问 题
97
例 5.7:对于一个具体问题 c1=65，
c2=80,c3=30； w1=2,w2=3,w3=1；以及 W=5
用动态规划求解 f4(x4)=0
对于 k=3
列出 f 3 ( x 3 ) 的数值表背 包 问 题
98
99
100
101
由题意知,x
1
=5,由表 f
1
( x
1
),f
2
( x
2
),
f
3
( x
3
),经回朔可得,
d
1
* = 2,x
2
= x
1
- 2 d
1
=1,d
2
* = 0,x
3
= x
2
- 3 d
2
=1,
d
3
*=1,x
4
= x
3
- d
3
=0
即应取第一种物品 2 件,第三种物品 1 件,最高价值为 1 6 0 元,背包没有余量。由 f
1
( x
1
)
得列表可以看出，如果背包得容量为 W =4,
W =3,W =2 和 W =1 时，相应的最优解立即可以得到。
102
机器负荷分配问题
103
离散问题与连续问题最短路径问题和背包问题的状态变量和决策变量都只能取离散的整数值 。 当状态变量和决策变量的取值范围很大,或者这些变量是连续的,用列举的方法就比较困难或者根本不可能了 。 这就需要用连续变量的处理方法 。
某种机器可以在高,低两种负荷下生产 。 高负荷生产条件下机器完好率为 0.7，
即如果年初有 u台完好机器投入生产,则年末完好的机器数量为 0.7u台 。 系数 0.7
称为完好率 。 年初投入高负荷运行的 u台机器的年产量为 8u吨 。 系数 8称为单台产量 。 低负荷运行时,机器完好率为 0.9，
单台产量为 5吨 。 设开始时有 1000台完好机器,要制订五年计划,每年年初将完好的机器一部分分配到高负荷生产,剩下的机器分配到低负荷生产,使五年的总产量为最高 。
构造动态规划模型如下：
阶段 k,运行年份（ k=1,2,3,4,5,6），其中 k=1
表示第一年初,…,依次类推； k=6表示第五年末（即第六年初）。
状态变量 xk,第 k年初完好的机器数
（ k=1,2,3,4,5,6），其中 x6表示第五年末（即第六年初）的完好机器数。
决策变量 dk,第 k年投入高负荷运行的机器数；
状态转移方程,xk+1=0.7dk+0.9(xk-dk)
决策允许集合,Dk(xk)={dk|0?dk?xk}
阶段指标,vk(xk,dk)=8dk+5(xk-dk)
终端条件,f6(x6)=0
机器负荷分配问题递推方程：
fk(xk) = max{vk(xk,dk)+fk+1(xk+1)}
dk?Dk(xk)
= max{8dk+5(xk- dk)+fk+1[0.7dk+0.9(xk-dk)]}
0?dk?xk
根据题意，本题的决策允许集合应该是一个整数集合，但由于决策允许集合中 可取的决策数量很大，一一列举计算量很大,不妨认为状态变量和决策变量都是连续的,得到最优解后，再作取整处理。
机器负荷分配问题
107
f5(x5)=max{8d5+5(x5-d5)+f6(x6)}
0?d5?x5
=max{3d5+5x5}=8x5,d5*=x5
0?d5?x5
f4(x4)=max{8d4+5(x4-d4)+f5(x5)}
0?d4?x4
=max{8d4+5(x4-d4)+8x5}
0?d4?x4
=max{8d4+5(x4-d4)+8[0.7d4+0.9(x4-d4)]}
0?d4?x4
=max{1.4d4+12.3x4}=13.7x4,
d4*=x4
0?d4?x4
机器负荷分配问题
108
f3(x3)=max{8d3+5(x3-d3)+f4(x4)}
0?d3?x3
=max{8d3+5(x3-d3)+13.7x4}
0?d3?x3
=max{8d3+5(x3-d3)+13.7[0.7d3+0.9(x3-d3)]}
0?d3?x3
=max{0.28d3+17.24x3}=17.52x3,d3*=x3
0?d3?x3
机器负荷分配问题
109
f2(x2)=max{8d2+5(x2-d2)+f3(x3)}
0?d2?x2
=max{8d2+5(x2-d2)+17.52x3}
0?d2?x2
=max{8d2+5(x2-d2)+17.52[0.7d2+0.9(x2-d2)]}
0?d2?x2
=max{-0.504d2+20.77x2}=20.77x2,d2*=0
0?d2?x2
机器负荷分配问题
110
f1(x1)=max{8d1+5(x1-d1)+f2(x2)}
0?d1?x1
=max{8d1+5(x1-d1)+20.77x2}
0?d1?x1
=max{8d1+5(x1-d1)+20.77[0.7d1+0.9(x1-d1)]}
0?d1?x1
=max{-0.05d1+23.69x1}=23.69x1,d1*=0
0?d1?x1
机器负荷分配问题
111
由此可以得到：
f1(x1)=23.69x1,d1*=0
f2(x2)=20.77x2,d2*=0
f3(x3)=17.52x3,d3*=x3
f4(x4)=13.60x4,d4*=x4
f5(x5)=8x5 d5*=x5
用 x1=1000代入,得到五年最大产量为
f1(x1)=f1(1000)=23690
机器负荷分配问题
112
每年投入高负荷运行的机器数以每年初完好的机器数为,
x1=1000
d1*=0,x2=0.7d1+0.9(x1-d1)=900
d2*=0,x3=0.7d2+0.9(x2-d2)=810
d3*=x3=810,x4=0.7d3+0.9(x3-d3)=567
d4*=x4=567,x5=0.7d4+0.9(x4-d4)=397
d5*=x5=397,x6=0.7d5+0.9(x5-d5)=278
机器负荷分配问题机器负荷分配问题
在这个例子中，状态变量的终端值 x6
是未加约束的，如果要求在第五年末
（即第六年初）完好的机器数不少于
500台，这时决策变量 d5的决策允许集合将成为：
D5(x5)={d5|0.7d5+0.9(x5-d5)?500,d5?0}
即 0.9x5-0.2d5?500
d5?0 或 0?d5?4.5x5-2500
机器负荷分配问题容易想象,这时的最大产量将比 x6 是自由的情况下小 。
这个例子可以推广到一般情况 。
设高负荷生产时机器的完好率为
k1,单台产量为 p1；低负荷完好率为 k2,单台产量为 p2。 若有 t满足,
115
则从 1-t-1年，年初将全部完好机器投入低负荷运行，从 t-n年，年初将全部完好机器投入高负荷运行，这样的决策，将使总产量达到最大。
tn
i
i
)t(n
i
i k
)kk(p
pp
k
0
1
121
21
1
0
1
机器负荷分配问题
116
生 产 库 存 问 题例 5.9：一个工厂生产某种产品,1-7月份生产成本和产品需求量的变化情况如下表：
月份 ( k ) 1 2 3 4 5 6 7
生产成本 ( c k ) 11 18 13 17 20 10 15
需求量 ( r k ) 0 8 5 3 2 7 4
生 产 库 存 问 题为了调节生产和需求,工厂设有一个产品仓库,库容量 H =9。 已知期初库存量为 2,要求期末 （ 七月底 ） 库存量为
0。 每个月生产的产品在月末入库,月初根据当月需求发货 。 求七个月的生产量,
能满足各月的需求,并使生产成本最低 。
118
阶段 k,月份,k=1,2,…,7,8；
状态变量 xk,第 k个月初 （ 发货以前 ） 的库存量；
决策变量 dk,第 k个月的生产量；
状态转移方程,xk+1=xk-rk+dk；
决策允许集合：
Dk(xk)={dk | dk?0,rk+1?xk+1?H }
={dk | dk?0,rk+1?xk-rk+dk?H }；
阶段指标,vk(xk,dk)=ckdk；
终端条件,f8(x8)=0,x8=0；
生 产 库 存 问 题
119
递推方程：
fk(xk)=min{vk(xk,dk)+fk+1(xk+1)}
dk?Dk(xk)
=min{ckdk+fk+1(xk-rk+dk)}
dk?Dk(xk)
对于 k=7
因为 x8=0
有 d7=0
递推方程为
f7(x7)=min{c7d7+f8(x8)}=0
d7=0
生 产 库 存 问 题
120
对于 k=6
因为 d7=0，所以 x7=r7=4
而 x6-r6+d6=x7=4
因此有 d6=x7+r6-x6=4+7-x6=11-x6
也是唯一的决策。因此递推方程为：
f6(x6)=min{c6d6+f7(x7)}
d6=11-x6
=10d6=10(11-x6)=110-10x6
生 产 库 存 问 题
121
对于 k=5
f5(x5)=min{c5d5+f6(x6)} d5?D5(x5)
=min{20d5+110-10x6} d5?D5(x5)
=min{20d5+110-10(x5-r5+d5)}
d5?D5(x5)
=min{20d5+110-10(x5-2+d5)}
d5?D5(x5)
=min{10d5-10x5+130}
d5?D5(x5)
D5(x5) ={d5| d5?0,r6?x5-r5+d5?H }
={d5|d5?0,r6+r5-x5?d5?H+r5-x5}
={d5| d5?0,9-x5?d5?11-x5}
生 产 库 存 问 题
122
因为 x5?H=9，因此 9-x5?0,决策允许集合可以简化为
D5(x5)={d5| 9-x5?d5?11-x5}
递推方程成为
f5(x5)=min{10d5-10x5+130}
9-x5?d5?11-x5
=10(9-x5)-10x5+130
=220-20x5
d5*=9-x5
生 产 库 存 问 题
123
对于 k=4
f4(x4)=min{c4d4+f5(x5)}
d4?D4(x4)
=min{17d4+220-20x5}
d4?D4(x4)
=min{17d4+220-20(x4-r4+d4)}
d4?D4(x4)
=min{17d4+220-20(x4-3+d4)}
d4?D4(x4)
=min{-3d4-20x4+280}
d4?D4(x4)
生 产 库 存 问 题
124
D4(x4)={d4| d4?0,r5?x4-r4+d4?H}
={d4| d4?0,r5+r4-x4?d4?H+r4-x4}
={d4| d4?0,5-x4?d4?12-x4}
={d4| max[0,5-x4]?d4?12-x4}
由于 在 f4(x4)的表达式中 d4的系数是 -3，
因此 d4在决策允许集合中应取集合中的最大值，即 d4=12-x4
由此 f4(x4)=-3(12-x4)-20x4+280
=-17x4+244
生 产 库 存 问 题
125
对于 k=3
f3(x3)=min {c3d3+f4(x4)} d3?D3(x3)
=min {13d3+244-17x4} d3?D3(x3)
=min {13d3+244-17(x3-r3+d3)}
d3?D3(x3)
=min {-4d3-17x3+329} d3?D3(x3)
D3(x3)={d3| d3?0,r4?x3-r3+d3?H}
={d3| d3?0,r4+r3-x3?d3?H+r3-x3}
={d3| d3?0,8-x3?d3?14-x3}
={d3| max[0,8-x3]?d3?14-x3}
由此 f3(x3)=-4(14-x3)-17x3+329
=-13x3+273,d3*=14-x3
生 产 库 存 问 题
126
对于 k=2
f2(x2)=min{c2d2+f3(x3)} d2?D2(x2)
=min{18d2+273-13x3} d2?D2(x2)
=min{18d2+273-13(x2-r2+d2)}
d2?D2(x2)
=min{18d2+273-13(x2-8+d2)}
d2?D2(x2)
=min{5d2-13x2+377} d2?D2(x2)
D2(x2)={d2|d2?0,r3?x2-r2+d2?H}
={d2|d2?0,r3+r2-x2?d2?H+r2-x2}
={d2|d2?0,13-x2?d2?17-x2}
生 产 库 存 问 题
127
因为 13-x2>0
所以 d2(x2)={d2|13-x2?d2?17-x2}
由此 f2(x2)=5(13-x2)-13x2+377
=-18x2+442,
d2*=13-x2
生 产 库 存 问 题
128
对于 k=1
f1(x1)=min{c1d1+f2(x2)} d1?D1(x1)
=min{11d1+442-18x2} d1?D1(x1)
=min{11d1+442-18(x1-r1+d1)}
d1?D1(x1)
=min{11d1+442-18(x1-0+d1)}
d1?D1(x1)
=min{-7d1-18x1+442}
d1?D1(x1)
D1(x1)={d1|d1?0,r2?x1-r1+d1?H}
={d1|d1?0,r2+r1-x1?d1?H+r1-x1}
={d1|d1?0,8-x1?d1?9-x1}
生 产 库 存 问 题
129
根据题意 x1=2
所以 D1(x1)={d1| 6?d1?7}
由此 d1=7
f1(x1)=-7d1-18x1+442
=-7× 7－ 18× 2＋ 442
=357
将以上结果总结成下表,
k 1 2 3 4 5 6 7
c k 11 18 13 17 20 10 15
r k 0 8 5 3 2 7 4
x k 2 9 5 9 9 7 4
d k 7 13 - x 2 =4 14 - x 3 =9 12 - x 4 =3 9 - x 5 =0 11 - x 6 =4 0
生 产 库 存 问 题
130
作业：
P145— 4,7
131
设 备 更 新 问 题
132
一台设备的价格为 P,运行寿命为 n年,
每年的维修费用是设备役龄的函数,记为 C(t),新设备的役龄为 t=0。 旧设备出售的价格是设备役龄的函数,记为 S(t)。
在 n年末,役龄为 t的设备残值为 R(t)。
现有一台役龄为 T的设备,在使用过程中,
使用者每年都面临,继续使用,或,更新,的策略,
设 备 更 新 问 题
133
阶段 k,运行年份；
状态变量 x k,设备的役龄 t ；
决策变量 d k,
继续使用更新
)(
)( R e
K e e pK
p l a c eR
d
k
状态转移方程,
Kdx
Rd
x
kk
k
k
1
1
1
阶段指标,
KdtC
RdtSCP
KdxC
RdxSCP
v
k
k
kk
kk
k
)(
)()0(
)(
)()0(
134
递推方程,
KdtftC
RdftSCP
KdxfxC
RdxfxSCP
xf
kk
kk
kkkk
kkkk
kk
)1()(
)1()()0(
m in
)()(
)()()0(
m in)(
1
1
11
11
终端条件,f n ( t )= - R ( t )
设 备 更 新 问 题
135
例 5.10：设具体数据如下：
T 0 1 2 3 4 5 6 7
C (t ) 10 13 20 40 70 100 100 --
S ( t ) -- 32 21 11 5 0 0 0
R (t ) -- 25 17 8 0 0 0 0
且 n =5,T =2,P =50
由上表开始，终端条件为,
f 6 (1)= - 25,f 6 (2)= - 17,f 6 (3)= - 8
f 6 (4)= f 6 (5)= f 6 (6)= f 6 (7)=0
设 备 更 新 问 题
136
对于 k =5,
Kd
Rd
tftC
ftSCP
tf
5
5
6
6
5
)1()(
)1()()0(
m i n)(
Kd
fC
fSCP
f
*
5
6
6
5
,4
4
3
m i n
)17(13
)25(321050
m i n
)2()1(
)1()1()0(
m i n)1(
Kd
fC
fSCP
f
*
5
6
6
5
,12
12
14
m i n
)8(20
)25(211050
m i n
)3()2(
)1()2()0(
m i n)2(
137
Rd
fC
fSCP
f
*
5
6
6
5
,24
40
24
min
040
)25(111050
min
)4()3(
)1()3()0(
min)3(
Rd
fC
fSCP
f
*
5
6
6
5
,30
70
30
m i n
070
)25(51050
m i n
)5()4(
)1()4()0(
m i n)4(
Rd
fC
fSCP
f
*
5
6
6
5
,35
100
35
m i n
0100
)25(01050
m i n
)6()5(
)1()5()0(
m i n)5(
138
Rd
fC
fSCP
f
*
5
6
6
5
,35
100
35
m i n
0100
)25(01050
m i n
)7()6(
)1()6()0(
m i n)6(
Kd
Rd
tftC
ftSCP
tf
4
4
5
5
4
)1()(
)1()()0(
m i n)(
Rd
fC
fSCP
f
*
4
5
5
4
,24
25
24
m i n
1213
)4(321050
m i n
)2()1(
)1()1()0(
m i n)1(
对于 k =4,
139
Rd
fC
fSCP
f
*
4
5
5
4
,35
44
35
m i n
2420
)4(211050
m i n
)3()2(
)1()2()0(
m i n)2(
Rd
fC
fSCP
f
*
4
5
5
4
,45
70
45
m i n
3040
)4(111050
m i n
)4()3(
)1()3()0(
m i n)3(
140
Rd
fC
fSCP
f
*
4
5
5
4
,51
1 0 5
51
m i n
3570
)4(51050
m i n
)5()4(
)1()4()0(
m i n)4(
Rd
fC
fSCP
f
*
5
5
5
4
,56
1 3 5
56
m i n
351 0 0
)4(01050
m i n
)6()5(
)1()5()0(
m i n)5(
141
对于 k =3,
Kd
Rd
tftC
ftSCP
tf
3
3
4
4
3
)1()(
)1()()0(
min)(
Kd
fC
fSCP
f
*
3
4
4
3
,48
48
52
m i n
3513
24321050
m i n
)2()1(
)1()1()0(
m i n)1(
142
Rd
fC
fSCP
f
*
3
4
4
3
,73
91
73
m i n
5140
24111050
m i n
)4()3(
)1()3()0(
m i n)3(
Rd
fC
fSCP
f
*
3
4
4
3
,79
126
79
m i n
5670
2451050
m i n
)5()4(
)1()4()0(
m i n)4(
Rd
fC
fSCP
f
*
3
4
4
3
,63
65
63
m i n
4520
24211050
m i n
)3()2(
)1()2()0(
m i n)2(
143
Kd
Rd
tftC
ftSCP
tf
2
2
3
3
2
)1()(
)1()()0(
m i n)(
RdKd
fC
fSCP
f
*
2
*
2
3
3
2
,76
76
76
m in
6313
48321050
m in
)2()1(
)1()1()0(
m in)1(
或者
Rd
fC
fSCP
f
*
2
3
3
2
,87
93
87
m i n
7320
48211050
m i n
)3()2(
)1()2()0(
m i n)2(
对于 k =2,
144
Rd
fC
fSCP
f
*
2
3
3
2
,73
119
97
m i n
7940
48111050
m i n
)4()3(
)1()3()0(
m i n)3(
对于 k =1,
Kd
Rd
tftC
ftSCP
tf
1
1
2
2
1 )1()(
)1()()0(
m i n)(
Rd
fC
fSCP
f
*
1
2
2
1
,115
117
115
m i n
9720
76211050
m i n
)3()2(
)1()2()0(
m i n)2(
97
145
由以上计算可知，本问题有两个决策，它们对应的最小费用都是 115。
年份 1 2 3 4 5
决策 1 更新 更新 继续 更新 继续决策 2 更新 继续 更新 更新 继续这两个决策是设 备 更 新 问 题
146
作业：
习题 — 12,13(1)
2
第五章 动态规划多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容重点一,多阶段决策问题
(Multi-Stage decision process)
多阶段决策过程特点,
状态
x1 阶段 1
T1
决策 u1
状态
x2
决策 u2
阶段 2
T2
状态
x3,..
状态
xk
决策 uk
阶段 k
Tk
状态
xk+1...
状态
xn
决策 un
阶段 n
Tn
状态
xn+1
1.多阶段决策过程的最优化
1.多阶段决策过程的最优化动态规划方法与,时间,关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是,动态,的意思 。 然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入,时段,因素,就可以将其转化为一个多阶段决策问题 。
在本章中将介绍这种处理方法 。
5
1.多阶段决策过程的最优化二,多阶段决策问题举例属于多阶段决策类的问题很多,
例如：
1)工厂生产过程,由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,
就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排 。
1.多阶段决策过程的最优化
2)设备更新问题,一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,
维修费用增加,可正常使用的工时减少,
加工质量下降,经济效益差,并且,使用的年限越长,处理价值也越低,自然,如果卖去旧的买新的,还需要付出更新费,因此就需要综合权衡决定设备的使用年限,使总的经济效益最好 。
7
1.多阶段决策过程的最优化
3)连续生产过程的控制问题,一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此,应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大 。
1.多阶段决策过程的最优化
许多问题的发展过程都与时间因素有关 。
在这类多阶段决策问题中,阶段的划分常取时间区段 来表示,并且各个阶段上的决策往往也与时间因素有关 。 这就使它具有了,动态,的含义,所以把处理这类动态问题的方法称为动态规划方法 。
实际中尚有许多不包含时间因素的一类
,静态,决策问题,就其本质而言是一次决策问题,是非动态决策问题,但是也可以 人为地引入阶段的概念 当作多阶段决策问题,应用动态规划方法加以解决 。
1.多阶段决策过程的最优化
4） 资源分配问题,资源分配问题便属于这类静态问题 。 如：某工业部门或公司,拟对其所属企业进行稀缺资源分配,
为此需要制定出收益最大的资源分配方案 。 这种问题原本要求一次确定出对各企业的资源分配量,它与时间因素无关,
不属动态决策,但是,我们可以人为地规定一个资源分配的阶段和顺序,从而使其变成一个多阶段决策问题 (后面我们将详细讨论这个问题 )。
10
1.多阶段决策过程的最优化
5） 运输网络问题,如 图 5-1所示的运输网络,点间连线上的数字表示两地距离 (也可是运费,时间等 ),要求从
fk(sk)至 v10的最短路线 。
这种运输网络问题也是静态决策问题 。 但是,按照网络中点的分布,
可以把它分为 4个阶段,而作为多阶段决策 问题来研究 。
1.多阶段决策过程的最优化三,动态规划求解的多阶段决策问题的特点
通常多阶段决策过程的发展是通过状态的一系列变换来实现的 。
一般情况下,系统在某个阶段的状态转移除与本阶段的状态和决策有关外,还可能与系统过去经历的状态和决策有关 。
适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,即 具有
,无后效性,的多阶段决策过程 。
12
1.多阶段决策过程的最优化
无后效性 （又称马尔柯夫性）
无后效性 （又称马尔柯夫性）
是指系统从某个阶段往后的发展，
仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策 (历史 )无关。
13
1.多阶段决策过程的最优化四,动态规划方法导引为了说明动态规划的基本思想方法和特点,
下面以图 5-1所示为例讨论的求最短路问题的方法
1.多阶段决策过程的最优化图 5-11 运输网络图示 返回
1.多阶段决策过程的最优化
一般有三种思路求解全枚举法或穷举法,它的基本思想是列举出所有可能发生的方案和结果,再对它们一一进行比较,求出最优方案 。
可以计算：从 v1到 v10的路程可以分为 4个阶段 。 第一段走法有 3种,第二,三两段走法各有 2 种,第 四 段 走 法 仅 1 种,共有
3× 2× 2× 1＝ 12条可能的路线,分别算出各条路线的距离,最后进行比较,可知 最优路线是 v1 → v3 → v7 → v9 → v10,最短距离是
18,用穷举法求最优路线的计算工作量将会十分庞大,而且其中包含着许多重复计算,
16
1.多阶段决策过程的最优化局部最优路径法,某人从 k点出发,并不顾及全线是否最短,
只是选择当前最短途径,,逢近便走,,错误地以为局部最优会致整体最优,在这种想法指导下,所取决策必是 v1 → v3
→ v5 → v8 → v10,全程长度是 20；显然,这种方法的结果常是错误的,
17
1.多阶段决策过程的最优化动态规划方法,动态规划方法寻求该最短路问题的基本思想是,
首先将问题划分为 4个阶段,每次的选择总是综合后继过程的一并最优进行考虑,在各段所有可能状态的最优后继过程都已求得的情况下,全程的最优路线便也随之得到 （ 如图 ）
1.多阶段决策过程的最优化图 1 运输网络动态规划方法求解图示跳过过程
19
1.多阶段决策过程的最优化具体说,此问题先从 v10开始,因为 v10是终点 。 再无后继过程,故可以接着考虑第 4阶段上所有可能状态 v8,v9的最优后续过程,因为从 v8,v9 到 v10的路线是唯一的,所以 v8,v9
的最优决策和最优后继过程就是到 v10,它们的最短距离分别是 5和 3。
接着考虑阶段 3上可能的状态 v5,v6,v7,
到 v10的最优决策和最优后继过程,在状态 V5
上,虽然到 v8是 8,到 v9是 9,但是综合考虑后继过程整体最优,取最优决策是到 v9,最优后继过程是 v5→ v9 → v10,最短距离是 12,同理,状态 v6的最优决策是至 v8 ； v7的最优决策是到 v9 。
20
1.多阶段决策过程的最优化同样,当阶段 3上所有可能状态的最优后继过程都已求得后,便可以开始考虑阶段 2上所有可能状态的最优决策和最优后继过程,如 v2的最优决策是到 v5,最优路线是 v2→ v5→ v9→ v10,最短距离是 15…依此类推,最后可以得到从初始状态 v1的最优决策是到 v3最优路线是 v1→ v3→ v7→ v9→ v10,
全程的最短距离是 18。 图 5—1中粗实线表示各点到的最优路线,每点上方括号内的数字表示该点到终点的最短路距离 。
21
1.多阶段决策过程的最优化小 结
全枚举法虽可找出最优方案,
但不是个好算法,
局部最优法则完全是个错误方法,
只有 动态规划方法属较科学有效的算法
22
2.动态规划的基本概念一,动态规划的基本概念使用动态规划方法解决多阶段决策问题,首先要将实际问题写成动态规划模型,同时也为了今后叙述和讨论方便,这里需要对动态规划的下述一些基本术语进一步加以说明和定义：
2.动态规划的基本概念
(一 ) 阶段和阶段变量为了便于求解和表示决策及过程的发展顺序,而把所给问题恰当地划分为若干个相互联系又有区别的子问题,称之为多段决策问题的 阶段 。 通常,阶段是按决策进行的时间或空间上先后顺序划分的 。
用以描述阶段的变量叫作 阶段变量,一般以 k表示阶段变量,阶段数等于多段决策过程从开始到结束所需作出决策的数目 。
2.动态规划的基本概念
（ 二 ） 状态,状态变量和可能状态集
1.状态与状态变量：描述事物 (或系统 )在某特定的时间与空间域中所处位置及运动特征的量,称为 状态 。 反映状态变化的量叫做 状态变量 。 状态变量包含在给定的阶段上确定全部允许决策所需要的信息 。 每个阶段的状态可分为初始状态和终止状态,或称输入状态和输出状态,阶段 k的初始状态记作 sk,终止状态记为 sk+1。 通常定义阶段的状态即指其初始状态 。
25
2.动态规划的基本概念
2,可能状态集一般状态变量的取值有一定的范围或允许集合,称为可能状态集,或可达状态集 。 可能状态集实际上是关于状态的约束条件 。 通常可能状态集用相应 阶段状态 sk的大写字母 Sk表示,
sk?Sk,可能状态集可以是一离散取值的集合,也可以为一连续的取值区间,视具体问题而定,
（ 三 ） 决策,决策变量和允许决策集合决策 的实质是关于状态的选择,
是决策者从给定阶段状态出发对下一阶段状态作出的选择 。
用以描述决策变化的量称之 决策变量 。 决策变量的值可以用数,向量,
其它量,也可以是状态变量的函数,记以 uk= uk(sk),表示于阶段 k状态 sk时的决策变量 。
2.动态规划的基本概念
27
2.动态规划的基本概念决策变量的取值往往也有一定的允许范围,称之 允许决策集合 。 决策变量 uk(sk)的允许决策集用 Uk(sk)表示,
uk(sk)∈ Uk(sk)
允许决策集合实际是决策的约束条件 。
28
（ 四 ） 策略和允许策略集合策略 (Policy)也叫决策序列,策略有 全过程策略 和 k部子策略 之分,
全过程策略是指由依次进行的 n个阶段决策构成的决策序列,简称策略,
表示为 p1,n{u1,u2,…,un}。 从 k阶段到第
n阶段,依次进行的阶段决策构成的决 策序 列称 为 k 部子 策略,表示 为
pk,n{uk,uk+1,…,un},显然当 k=1时的 k
部子策略就是全过程策略 。
2.动态规划的基本概念
29
2.动态规划的基本概念
在实际问题中，由于在各个阶段可供选择的决策有许多个，
因此，它们的不同组合就构成了许多可供选择的决策序列 (策略 )，由它们组成的集合，称之允许策略集合,记作 P1,n,从允许策略集中，找出具有最优效果的策略称为 最优策略 。
30
（ 五 ） 状态转移方程系统在阶段 k处于状态 sk，
执行决策 uk(sk)的结果是系统状态的转移,即系统由阶段 k的初始状态 sk转移到终止状态 sk+1 。
2.动态规划的基本概念
31
2.动态规划的基本概念对于具有无后效性的多阶段决策过程,系统由阶段 k到阶段
k+1的状态转移完全由阶段 k的状态 sk和决策 uk(sk) 所确定,与系统过去的状态 s1,s2,…,sk -1及其决策 u1(s1),u2(s2),…,uk-1(sk-1)
无关 。
32
系统状态的这种转移,用数学公式描述即有：
(5－ 1)
通常称上式 (5-1)为多阶段决策过程的状态转移方程 。 有些问题的状态转移方程不一定存在数学表达式,但是它们的状态转移,还是有一定规律可循的 。
2.动态规划的基本概念
))((1 kkkkk su,sTs
33
2.动态规划的基本概念
(六 ) 指标函数用来衡量策略或子策略或决策的效果的某种 数量指标,就称为 指标函数 。 它是定义在全过程或各子过程或各阶段上的确定数量函数 。 对不同问题,指标函数可以是诸如费用,成本,产值,
利润,产量,耗量,距离,时间,
效用,等等 。
34
1)阶段指标函数 （ 阶段效应 ）
用 gk(sk,uk)表示第 k段处于 sk状态且所作决策为 uk(sk)时的指标,
则它就是 第 k段指标函数,简记为 gk
2.动态规划的基本概念
35
(2)过程指标函数（目标函数）
用 Rk(sk,uk)表示第 k子过程的指标函数 。
Rk(sk,uk) 不仅跟当前状态 sk有关,还跟该子过程策略 pk(sk)有关,因此它是 sk和 pk(sk)的函数,
严格说来,应表示为,
))s(p,s(R kkkk
实际应用中上式可表示为
Rk(sk,uk) 或 Rk(sk) ；
过程指标函数 Rk(sk) 通常是描述所实现的全过程或 k 后部子过程效果优劣的数量指标,它是由各阶段的阶段指标函数 gk(sk,uk) 累积形成的 。
2.动态规划的基本概念
37
过程指标函数形式：
适于用动态规划求解的问题的过程指标函数 （ 即目标函数 ）,必须具有关于阶段指标的可分离形式,对于 k部子过程的指标函数可以表示为：
（?表示某种运算 ）
)u,s(g)u,s(g)u,s(g
)u,s,,u,s,u,s(RR
nnnkkkkkk
nnkkkkn,kn,k
111
11
38
多阶段决策问题中,常见的目标函数形式之一是取各阶段效应之和的形式,即,
2.动态规划的基本概念
n
ki
i
u
i
s
i
g
k
R ),(
39
总之，具体问题的目标函数表达形式需要视具体问题而定。
有些问题,如系统可靠性问题,其目标函数是取各阶段效应的连乘积形式,如
n
ki
iiik usgR ),(
40
(七 ) 最优解用 fk(sk)表示第 k子过程指标函数,在状态 sk下的最优值,即称 fk(sk)为第 k子过程上的最优指标函数 ；
2.动态规划的基本概念
))(,( kkkk spsR
nkspsRoptsf kkkk
sPp
kk
kKk
,,2,1) ) },(,({)(
)(
41
2.动态规划的基本概念
相应的子策略称为 sk状态下的最优子策略,记为 pk*(sk) ；而构成该子策赂的各段决策称为该过程上的最优决策,记为
有简记为
)(,),(),( 11 nnkkkk sususu
nksusususp nnkkkkkk,,2,1) },(,),(),({)( 11
nkuuup nkkk,,2,1},,,,{ 1
42
特别当 k=1且 s1取值唯一时,f1(s1)就是问题的最优值，而 p1* 就是最优策略。
但若取值不唯一,则问题的最优值记为 f0有最优策略即为 s1=s1*状态下的最优策略：
我们把最优策略和最优值统称为问题的最优解 。
2.动态规划的基本概念
)()}({ 111110
11
ssfsfo p tf
Ss
},,),({)( 211111 nuusussp?
),,2,1( nku k
43
2.动态规划的基本概念
(八 ) 多阶段决策问题的数学模型综上所述,适于应用动态规划方法求解的一类多阶段决策问题,亦即具有无后效性的多阶段决策问题的数学模型呈以下形式,
nk
Uu
Ss
usTs
ts
usususRRoptf
kk
kk
kkkk
nn
uu
n
,,2,1
),(
..
),,,,,,(
1
2211
~
1
（ 5-5）
44
式中,OPT”表示最优化,视具体问题取 max或 min。
上述数学模型说明了对于给定的多阶段决策过程,求取一个 (或多个 )最优策略或最优决策序列,使之既满足式 (5-5)给出的全部约束条件,又使式 (5-5)所示的目标函数取得极值,并且同时指出执行该最优策略时,过程状态演变序列即最优路线
2.动态规划的基本概念
},,,{ 21 nuuu?
},,,,{ 121 nn ssss?
二,动态规划的最优化原理与基本方程
1,标号法 (只适用于一类最优路线问题的特殊解法 ）
标号法是借助网络图通过分段标号来求出最优路线的一种简便,直观的方法 。
通常标号法采取,逆序求解,的方法来寻找问题的最优解,即从最后阶段开始,
逐次向阶段数小的方向推算,最终求得全局最优解 。
2.动态规划的基本原理
46
标号法的一般步骤：
（ 1） 给最后一段 标号,该段各状态 (即各始点 )到终点的距离用数字分别标在各点上方的方格内,并 用粗箭线连接各点和终点 。
2.动态规划的基本原理
47
标号法的一般步骤（续）：
（ 2） 向前递推,给前一阶段的各个状态 标号 。 每个状态上方方格内的数字表示该状态到终点的最短距离 。 将刚标号的点沿着最短距离所对应的已标号的点用粗箭线连接起来,
表示出各刚标号的点到终点的最短路线 。
48
（ 3） 逐次向前递推,直到将第一阶段的状态 (即起点 )标号,起点方格内的数字就是起点到终点的 最短距离,从 起点开始连接终点的粗箭线 就是 最短路线 。
标号法的一般步骤（续）：
49
2.动态规划的基本原理例 5.2：网络图 5－ 2表示某城市的局部道路分布图。一货运汽车从 S出发，最终到达目的地
E。其中 Ai(i＝ 1,2,3),Bj(j＝ 1，
2)和 Ck(k＝ 1,2)是可供汽车选择的途经站点，各点连线上的数字表示两个站点问的距离。
问此汽车应走哪条路线，使所经过的路程距离最短?
50
2.动态规划的基本原理图 5-2 某城市的局部道路分布图
0
5
8
11
14
17
19
18
21
2.动态规划的基本原理图 5-3某城市局部道路求最短路径的过程结果如图 5-3所示 。 从 S到 E最短距离为
21共有三条最短路线：
(1)
(2)
(3)
标号法不但给出起点到终点的最短路线和最短距离,同时也给出每一状态到终点的最短路线及其最短距离 。
2.动态规划的基本原理
ECBAS 111
ECBAS 113
ECBAS 123
54
作业：
习题 --1
55
2,最优化原理 （ 贝尔曼最优化原理 ）
作为一个全过程的最优策略具有这样的性质,对于最优策略过程中的任意状态而言,无论其过去的状态和决策如何,
余下的诸决策必构成一个最优子策略 。
2.动态规划的基本原理
56
2.动态规划的基本原理该原理的具体解释是,若某一全过程最优策略为：
则对上述策略中所隐含的任一状态而言,第 k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略 p1*中,即为
)}(),(,),(),({)( 221111 nnkk sususususp
)}(,),(),({)( 11 nnkkkkkk susususp
3.函数基本方程基于这个原理,提出了一种逆序递推法；该法的关键在于给出一种递推关系 。 一般把这种递推关系称为 动态规划的函数基本方程 。
对于求最小的加法的计算公式为：
2.动态规划的基本原理
121
0
11
11
,,,n,nk
) },s(f))s(u,s(g{m i n)s(f
)s(f
kkkkkk
)s(Uu
kk
nn
kkk
（边界条件）
阶段指标一般地,
(1)当过程指标函数为,和,的形式时,相应的函数基本方程为
2.动态规划的基本原理
))}(,({)(
)( kkkksPpkk
spsRo p tsf
kKk?
}),({
n
ki iii
usgopt
121
0
11
11
,,,n,nk
) },s(f))s(u,s(g{opt)s(f
)s(f
kkkkkk
Uu
kk
nn
kk
(2) 当过程指标函数为,积,的形式时,相应的函数基本方程为可以看出,和,积函数的基本方程中边界条件 (即 的取值 )是不同的 。
2.动态规划的基本原理
))}(,({)(
)( kkkksPpkk
spsRo p tsf
kKk?
n
ki iii
usgo p t )},({
121
1
11
11
,,,n,nk
)}s(f))s(u,s(g{opt)s(f
)s(f
kkkkkk
Uu
kk
nn
kk
)( 11 nn sf
3.动态规划方法的基本步骤
用函数基本方程逆推求解是常用的方法：
首先要有效地 建立动态规划模型,
然后再 递推求解,最后 得出结论,
正确地建立一个动态规划模型,
是解决问题的关键 。
正确的动态规划模型,应该满足下列条件：
61
3.动态规划方法的基本步骤
（ 1） 应将实际问题恰当地分割成 n个子问题 (n个阶段 )
通常是根据时间或空间而划分的,或者在经由静态的数学规划模型转换为动态规划模型时,
常取静态规划中变量的个数 n。
62
3.动态规划方法的基本步骤
（ 2） 正确地定义状态变量 sk，
使它既能正确地描述过程的状态，
又能满足无后效性．
动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：
63
3.动态规划方法的基本步骤
要能够 正确地描述受控过程的变化特征 。
要满足无后效性 。 即如果在某个阶段状态已经给定,那么在该阶段以后,过程的发展不受前面各段状态的影响,如果所选的变量不具备无后效性,就不能作为状态变量来构造动态规划的模型 。
64
3.动态规划方法的基本步骤
要满足可知性 。 即所规定的各段状态变量的值,可以直接或间接地测算得到 。
一般在动态规划模型中,状态变量大都选取那种可以进行累计的量 。
在解静态规划模型时,线性与非线性规划中约束条件的个数,相当于动态规划中状态变量 sk的维数,约束条件所表示的内容,就是状态变量 sk所代表的内容 。
65
3.动态规划方法的基本步骤
（ 3） 正确地定义决策变量及各阶段的允许决策集合 Uk(sk)。
一般将问题中待求的量,选作动态规划模型中的决策变量,或者在把静态规划模型 (如线性与非线性规划 )转换为动态规划模型时,常常取前者的变量 xj 为后者的决策变量 uk 。
66
3.动态规划方法的基本步骤
（ 4） 正确地写出状态转移方程 。 要能正确反映状态转移规律 。 如果给定第 k 阶段状态变量 sk 的值,则该段的决策变量
uk 一经确定,第 k+1段的状态变量 sk+1的值也就完全确定,即有
sk+1=Tk(sk,uk)
67
3.动态规划方法的基本步骤
（ 5） 正确地写出目标函数,
目标函数应满足下列性质：
可分性,即对于所有 k后部子过程,其目标函数仅取决于状态 sk
及其以后的决策
uk,uk+1,┈,un
就是说它是定义在全过程和所有后部子过程上的数量函数 。
68
3.动态规划方法的基本步骤
要满足递推关系,即
函数对其变元 Rk+1来说要 严格单调 。
)],,(,,[
),,,,,(,
111
111
nkkkkk
nkkkknk
ssRus
sususR
)],,(,,[ 111 nkkkkk ssRus
69
写出动态规划函数基本方程
3.动态规划方法的基本步骤
121
0
11
11
,,,n,nk
) },s(f))s(u,s(g{opt)s(f
)s(f
kkkkkk
Uu
kk
nn
kk
121
1
11
11
,,,n,nk
)}s(f))s(u,s(g{opt)s(f
)s(f
kkkkkk
Uu
kk
nn
kk
或
70
学习例题的方法建议：
第一步 先看问题，充分理解问题的条件、情况及求解目标。
第二步 结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的
“四大要素、一个方程” —— 这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。
4.动态规划方法应用举例
71
第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。
第四步 把自己的求解放到一边，
看书中的求解方法，要充分理解教材中的论述。
第五步 对照自己的求解，分析成败。
4.动态规划方法应用举例
74
求 最 短 路 径
75
BA
CB
D
B
C
D
E
C
2
1
2
3
1
2
3
1
2
5
1
12
14
10
6
10
4
13
12
11
3
9
6
5
8
10
5
2
阶段 1 阶段 2 阶段 3 阶段 4 阶段 5
求 最 短 路 径例 5.5
76
将问题分成五个阶段，第 k阶段到达的具体地点用状态变量 xk表示，例如,x2=B3表示第二阶段到达位置 B3，
等等。这里状态变量取字符值而不是数值。
将决策定义为到达下一站所选择的路径,例如目前的状态是 x2=B3,这时决策允许集合包含三个决策,它们是
D2(x2)=D2(B3)={B3?C1,B3?C2,B3?C3}
求 最 短 路 径
77
求最短路径最优指标函数 fk(xk) 表示从目前状态到 E的最短路径 。 终端条件为
f5 ( x5 ) = f5 ( E ) = 0
其含义是从 E到 E的最短路径为 0。
第四阶段的递推方程为
从 f5 ( x5 ) 到 f4 ( x4 ) 的递推过程用下表表示 x 4 D 4 (x 4 ) x 5 v 4 (x 4,d 4 ) v 4 (x 4,d 4 )+f 5 (x 5 ) f 4 (x 4 ) 最优决策 d 4 *
D 1 D 1? E E 5 5 + 0 = 5 * 5 D 1? E
D 2 D 2? E E 2 2 + 0 = 2 * 2 D 2? E
)}x(f)d,x(V{m i n)x(f
)x(Dd 5544444 444
79
其中 *表示最优值，在上表中，由于决策允许集合 D4(x4)中的决策是唯一的，因此这个值就是最优值。
由此得到 f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：
f 4 (x 4 ) 的表达式
x 4 f 4 (x 4 ) 最优决策 d 4 *
D 1 5 D 1? E
D 2 2 D 2? E
求 最 短 路 径第三阶段的递推方程为：
从 f 4 (x 4 ) 到 f 3 (x 3 ) 的递推过程用表格表示如下,
x 3 D 3 (x 3 ) x 4 v 3 (x 3,d 3 ) v 3 (x 3,d 3 )+f 4 (x 4 ) f 3 (x 3 ) 最优决策 d 3 *
C 1
C 1? D 1
C 1? D 2
D 1
D 2
3
9
3+5=8*
9+2=11
8 C 1? D 1
C 2
C 2? D 1
C 2? D 2
D 1
D 2
6
5
6+5=11
5+2=7*
7
C 2? D 2
C 3
C 3? D 1
C 3? D 2
D 1
D 2
8
10
8+5=13
10+2=12*
12 C 3? D 2
)}(),({m in)( 44333
)(33 333
xfdxvxf
xDd
求 最 短 路 径
81
由此得到 f3(x3)的表达式：
x 3 f 3 ( x 3 ) 最优决策 d 3 *
C 1 8 C 1? D 1
C 2 7 C 2? D 2
C 3 12 C 3? D 2
第二阶段的递推方程为,
)}(),({m i n)( 33222
)(22 222
xfdxvxf
xDd
从 f 3 ( x 3 ) 到 f 2 ( x 2 ) 的递推过程用表格表示如下,
求 最 短 路 径
82
x 2 D 2 (x 2 ) x 3 v 2 (x 2,d 2 ) v 2 (x 2,d 2 )+f 3 (x 3 ) f 2 (x 2 ) 最优决策 d 2 *
B
1
B
1
C
1
B
1
C
2
B
1
C
3
C
1
C
2
C
3
12
14
10
12+8=20*
14+7=21
10+12=22
20
B
1
C
1
B
2
B
2
C
1
B
2
C
2
B
2
C
3
C
1
C
2
C
3
6
10
4
6+8=14*
10+7=17
4+12=16
14
B
2
C
1
B
3
B
3
C
1
B
3
C
2
B
3
C
3
C
1
C
2
C
3
13
12
11
13+8= 21
12+7=19*
11+12=23
19
B
3
C
2
求 最 短 路 径
83
由此得到 f2(x2)的表达式：
x 2 f 2 (x 2 ) 最优决策 d 2 *
B 1 20 B 1? C 1
B 2 14 B 2? C 1
B 3 19 B 3? C 2
求 最 短 路 径
84
第一阶段的递推方程为：
)}(),({m i n)( 22111
)(11 111
xfdxvxf
xDd
从 f 2 ( x 2 ) 到 f 1 ( x 1 ) 的递推过程用表格表示如下,
x 1 D 1 (x 1 ) x 2 v 1 (x 1,d 1 ) v 1 (x 1,d 1 )+f 2 (x 2 ) f 1 (x 1 ) 最优决策 d 1 *
A
A? B 1
A? B 2
A? B 3
B 1
B 2
B 3
2
5
1
2+20=22
5+14=19*
1+19=20
19
A? B 2
求 最 短 路 径
85
由此得到 f1(x1)的表达式
x 1 f 1 (x 1 ) 最优决策 d 1 *
A 19 A? B 2
求 最 短 路 径
86
资 源 分 配 问 题
87
例 5.6,有资金 4万元，投资 A,B,C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目 A,B,C的投资效益
（万吨）和投入资金（万元）关系见下表：
求对三个项目的最优投资分配，使总投资效益最大。
资 源 分 配 问 题
1,阶段 k：每投资一个项目作为一个阶段；
2,状态变量 xk：投资第 k个项目前的资金数；
3,决策变量 dk：第 k个项目的投资；
4,决策允许集合,0≤dk≤xk
5,状态转移方程,xk+1=xk-dk
6,阶段指标,vk(xk,dk)见表中所示；
7,递推方程：
fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}
8,终端条件,f4(x4)=0
资 源 分 配 问 题
89
k=4,f4(x4)=0
k=3,0≤d3≤x3,x4=x3-d3
资 源 分 配 问 题
90
k=2,0≤d2≤x2,x3=x2-d2
资 源 分 配 问 题
91
k=1,0≤d1≤x1,x2=x1-d1
资 源 分 配 问 题
92
作业：
习题 — 2,3
93
背 包 问 题
94
背 包 问 题
95
则 Max z = c1x1+c2x2+…+cnxn
s.t,w1x1+w2x2+…+wnxn≤W
x1,x2,…,xn为正整数
1,阶段 k,第 k 次装载第 k 种物品
（ k=1,2,…,n）
2,状态变量 sk：第 k次装载时背包还可以装载的重量；
3,决策变量 xk：第 k次装载第 k种物品的件数；
背 包 问 题
96
4,决策允许集合：
Dk(sk)={xk|0? xk?sk/wk,xk为整数 }；
5,状态转移方程,sk+1=sk-wkxk
6,阶段指标,vk=ckxk
7,递推方程
fk(sk)=max{ckxk+fk+1(sk+1)}
=max{ckxk+fk+1(sk-wkxk)}
8,终端条件,fn+1(sn+1)=0
背 包 问 题
97
例 5.7:对于一个具体问题 c1=65，
c2=80,c3=30； w1=2,w2=3,w3=1；以及 W=5
用动态规划求解 f4(x4)=0
对于 k=3
列出 f 3 ( x 3 ) 的数值表背 包 问 题
98
99
100
101
由题意知,x
1
=5,由表 f
1
( x
1
),f
2
( x
2
),
f
3
( x
3
),经回朔可得,
d
1
* = 2,x
2
= x
1
- 2 d
1
=1,d
2
* = 0,x
3
= x
2
- 3 d
2
=1,
d
3
*=1,x
4
= x
3
- d
3
=0
即应取第一种物品 2 件,第三种物品 1 件,最高价值为 1 6 0 元,背包没有余量。由 f
1
( x
1
)
得列表可以看出，如果背包得容量为 W =4,
W =3,W =2 和 W =1 时，相应的最优解立即可以得到。
102
机器负荷分配问题
103
离散问题与连续问题最短路径问题和背包问题的状态变量和决策变量都只能取离散的整数值 。 当状态变量和决策变量的取值范围很大,或者这些变量是连续的,用列举的方法就比较困难或者根本不可能了 。 这就需要用连续变量的处理方法 。
某种机器可以在高,低两种负荷下生产 。 高负荷生产条件下机器完好率为 0.7，
即如果年初有 u台完好机器投入生产,则年末完好的机器数量为 0.7u台 。 系数 0.7
称为完好率 。 年初投入高负荷运行的 u台机器的年产量为 8u吨 。 系数 8称为单台产量 。 低负荷运行时,机器完好率为 0.9，
单台产量为 5吨 。 设开始时有 1000台完好机器,要制订五年计划,每年年初将完好的机器一部分分配到高负荷生产,剩下的机器分配到低负荷生产,使五年的总产量为最高 。
构造动态规划模型如下：
阶段 k,运行年份（ k=1,2,3,4,5,6），其中 k=1
表示第一年初,…,依次类推； k=6表示第五年末（即第六年初）。
状态变量 xk,第 k年初完好的机器数
（ k=1,2,3,4,5,6），其中 x6表示第五年末（即第六年初）的完好机器数。
决策变量 dk,第 k年投入高负荷运行的机器数；
状态转移方程,xk+1=0.7dk+0.9(xk-dk)
决策允许集合,Dk(xk)={dk|0?dk?xk}
阶段指标,vk(xk,dk)=8dk+5(xk-dk)
终端条件,f6(x6)=0
机器负荷分配问题递推方程：
fk(xk) = max{vk(xk,dk)+fk+1(xk+1)}
dk?Dk(xk)
= max{8dk+5(xk- dk)+fk+1[0.7dk+0.9(xk-dk)]}
0?dk?xk
根据题意，本题的决策允许集合应该是一个整数集合，但由于决策允许集合中 可取的决策数量很大，一一列举计算量很大,不妨认为状态变量和决策变量都是连续的,得到最优解后，再作取整处理。
机器负荷分配问题
107
f5(x5)=max{8d5+5(x5-d5)+f6(x6)}
0?d5?x5
=max{3d5+5x5}=8x5,d5*=x5
0?d5?x5
f4(x4)=max{8d4+5(x4-d4)+f5(x5)}
0?d4?x4
=max{8d4+5(x4-d4)+8x5}
0?d4?x4
=max{8d4+5(x4-d4)+8[0.7d4+0.9(x4-d4)]}
0?d4?x4
=max{1.4d4+12.3x4}=13.7x4,
d4*=x4
0?d4?x4
机器负荷分配问题
108
f3(x3)=max{8d3+5(x3-d3)+f4(x4)}
0?d3?x3
=max{8d3+5(x3-d3)+13.7x4}
0?d3?x3
=max{8d3+5(x3-d3)+13.7[0.7d3+0.9(x3-d3)]}
0?d3?x3
=max{0.28d3+17.24x3}=17.52x3,d3*=x3
0?d3?x3
机器负荷分配问题
109
f2(x2)=max{8d2+5(x2-d2)+f3(x3)}
0?d2?x2
=max{8d2+5(x2-d2)+17.52x3}
0?d2?x2
=max{8d2+5(x2-d2)+17.52[0.7d2+0.9(x2-d2)]}
0?d2?x2
=max{-0.504d2+20.77x2}=20.77x2,d2*=0
0?d2?x2
机器负荷分配问题
110
f1(x1)=max{8d1+5(x1-d1)+f2(x2)}
0?d1?x1
=max{8d1+5(x1-d1)+20.77x2}
0?d1?x1
=max{8d1+5(x1-d1)+20.77[0.7d1+0.9(x1-d1)]}
0?d1?x1
=max{-0.05d1+23.69x1}=23.69x1,d1*=0
0?d1?x1
机器负荷分配问题
111
由此可以得到：
f1(x1)=23.69x1,d1*=0
f2(x2)=20.77x2,d2*=0
f3(x3)=17.52x3,d3*=x3
f4(x4)=13.60x4,d4*=x4
f5(x5)=8x5 d5*=x5
用 x1=1000代入,得到五年最大产量为
f1(x1)=f1(1000)=23690
机器负荷分配问题
112
每年投入高负荷运行的机器数以每年初完好的机器数为,
x1=1000
d1*=0,x2=0.7d1+0.9(x1-d1)=900
d2*=0,x3=0.7d2+0.9(x2-d2)=810
d3*=x3=810,x4=0.7d3+0.9(x3-d3)=567
d4*=x4=567,x5=0.7d4+0.9(x4-d4)=397
d5*=x5=397,x6=0.7d5+0.9(x5-d5)=278
机器负荷分配问题机器负荷分配问题
在这个例子中，状态变量的终端值 x6
是未加约束的，如果要求在第五年末
（即第六年初）完好的机器数不少于
500台，这时决策变量 d5的决策允许集合将成为：
D5(x5)={d5|0.7d5+0.9(x5-d5)?500,d5?0}
即 0.9x5-0.2d5?500
d5?0 或 0?d5?4.5x5-2500
机器负荷分配问题容易想象,这时的最大产量将比 x6 是自由的情况下小 。
这个例子可以推广到一般情况 。
设高负荷生产时机器的完好率为
k1,单台产量为 p1；低负荷完好率为 k2,单台产量为 p2。 若有 t满足,
115
则从 1-t-1年，年初将全部完好机器投入低负荷运行，从 t-n年，年初将全部完好机器投入高负荷运行，这样的决策，将使总产量达到最大。
tn
i
i
)t(n
i
i k
)kk(p
pp
k
0
1
121
21
1
0
1
机器负荷分配问题
116
生 产 库 存 问 题例 5.9：一个工厂生产某种产品,1-7月份生产成本和产品需求量的变化情况如下表：
月份 ( k ) 1 2 3 4 5 6 7
生产成本 ( c k ) 11 18 13 17 20 10 15
需求量 ( r k ) 0 8 5 3 2 7 4
生 产 库 存 问 题为了调节生产和需求,工厂设有一个产品仓库,库容量 H =9。 已知期初库存量为 2,要求期末 （ 七月底 ） 库存量为
0。 每个月生产的产品在月末入库,月初根据当月需求发货 。 求七个月的生产量,
能满足各月的需求,并使生产成本最低 。
118
阶段 k,月份,k=1,2,…,7,8；
状态变量 xk,第 k个月初 （ 发货以前 ） 的库存量；
决策变量 dk,第 k个月的生产量；
状态转移方程,xk+1=xk-rk+dk；
决策允许集合：
Dk(xk)={dk | dk?0,rk+1?xk+1?H }
={dk | dk?0,rk+1?xk-rk+dk?H }；
阶段指标,vk(xk,dk)=ckdk；
终端条件,f8(x8)=0,x8=0；
生 产 库 存 问 题
119
递推方程：
fk(xk)=min{vk(xk,dk)+fk+1(xk+1)}
dk?Dk(xk)
=min{ckdk+fk+1(xk-rk+dk)}
dk?Dk(xk)
对于 k=7
因为 x8=0
有 d7=0
递推方程为
f7(x7)=min{c7d7+f8(x8)}=0
d7=0
生 产 库 存 问 题
120
对于 k=6
因为 d7=0，所以 x7=r7=4
而 x6-r6+d6=x7=4
因此有 d6=x7+r6-x6=4+7-x6=11-x6
也是唯一的决策。因此递推方程为：
f6(x6)=min{c6d6+f7(x7)}
d6=11-x6
=10d6=10(11-x6)=110-10x6
生 产 库 存 问 题
121
对于 k=5
f5(x5)=min{c5d5+f6(x6)} d5?D5(x5)
=min{20d5+110-10x6} d5?D5(x5)
=min{20d5+110-10(x5-r5+d5)}
d5?D5(x5)
=min{20d5+110-10(x5-2+d5)}
d5?D5(x5)
=min{10d5-10x5+130}
d5?D5(x5)
D5(x5) ={d5| d5?0,r6?x5-r5+d5?H }
={d5|d5?0,r6+r5-x5?d5?H+r5-x5}
={d5| d5?0,9-x5?d5?11-x5}
生 产 库 存 问 题
122
因为 x5?H=9，因此 9-x5?0,决策允许集合可以简化为
D5(x5)={d5| 9-x5?d5?11-x5}
递推方程成为
f5(x5)=min{10d5-10x5+130}
9-x5?d5?11-x5
=10(9-x5)-10x5+130
=220-20x5
d5*=9-x5
生 产 库 存 问 题
123
对于 k=4
f4(x4)=min{c4d4+f5(x5)}
d4?D4(x4)
=min{17d4+220-20x5}
d4?D4(x4)
=min{17d4+220-20(x4-r4+d4)}
d4?D4(x4)
=min{17d4+220-20(x4-3+d4)}
d4?D4(x4)
=min{-3d4-20x4+280}
d4?D4(x4)
生 产 库 存 问 题
124
D4(x4)={d4| d4?0,r5?x4-r4+d4?H}
={d4| d4?0,r5+r4-x4?d4?H+r4-x4}
={d4| d4?0,5-x4?d4?12-x4}
={d4| max[0,5-x4]?d4?12-x4}
由于 在 f4(x4)的表达式中 d4的系数是 -3，
因此 d4在决策允许集合中应取集合中的最大值，即 d4=12-x4
由此 f4(x4)=-3(12-x4)-20x4+280
=-17x4+244
生 产 库 存 问 题
125
对于 k=3
f3(x3)=min {c3d3+f4(x4)} d3?D3(x3)
=min {13d3+244-17x4} d3?D3(x3)
=min {13d3+244-17(x3-r3+d3)}
d3?D3(x3)
=min {-4d3-17x3+329} d3?D3(x3)
D3(x3)={d3| d3?0,r4?x3-r3+d3?H}
={d3| d3?0,r4+r3-x3?d3?H+r3-x3}
={d3| d3?0,8-x3?d3?14-x3}
={d3| max[0,8-x3]?d3?14-x3}
由此 f3(x3)=-4(14-x3)-17x3+329
=-13x3+273,d3*=14-x3
生 产 库 存 问 题
126
对于 k=2
f2(x2)=min{c2d2+f3(x3)} d2?D2(x2)
=min{18d2+273-13x3} d2?D2(x2)
=min{18d2+273-13(x2-r2+d2)}
d2?D2(x2)
=min{18d2+273-13(x2-8+d2)}
d2?D2(x2)
=min{5d2-13x2+377} d2?D2(x2)
D2(x2)={d2|d2?0,r3?x2-r2+d2?H}
={d2|d2?0,r3+r2-x2?d2?H+r2-x2}
={d2|d2?0,13-x2?d2?17-x2}
生 产 库 存 问 题
127
因为 13-x2>0
所以 d2(x2)={d2|13-x2?d2?17-x2}
由此 f2(x2)=5(13-x2)-13x2+377
=-18x2+442,
d2*=13-x2
生 产 库 存 问 题
128
对于 k=1
f1(x1)=min{c1d1+f2(x2)} d1?D1(x1)
=min{11d1+442-18x2} d1?D1(x1)
=min{11d1+442-18(x1-r1+d1)}
d1?D1(x1)
=min{11d1+442-18(x1-0+d1)}
d1?D1(x1)
=min{-7d1-18x1+442}
d1?D1(x1)
D1(x1)={d1|d1?0,r2?x1-r1+d1?H}
={d1|d1?0,r2+r1-x1?d1?H+r1-x1}
={d1|d1?0,8-x1?d1?9-x1}
生 产 库 存 问 题
129
根据题意 x1=2
所以 D1(x1)={d1| 6?d1?7}
由此 d1=7
f1(x1)=-7d1-18x1+442
=-7× 7－ 18× 2＋ 442
=357
将以上结果总结成下表,
k 1 2 3 4 5 6 7
c k 11 18 13 17 20 10 15
r k 0 8 5 3 2 7 4
x k 2 9 5 9 9 7 4
d k 7 13 - x 2 =4 14 - x 3 =9 12 - x 4 =3 9 - x 5 =0 11 - x 6 =4 0
生 产 库 存 问 题
130
作业：
P145— 4,7
131
设 备 更 新 问 题
132
一台设备的价格为 P,运行寿命为 n年,
每年的维修费用是设备役龄的函数,记为 C(t),新设备的役龄为 t=0。 旧设备出售的价格是设备役龄的函数,记为 S(t)。
在 n年末,役龄为 t的设备残值为 R(t)。
现有一台役龄为 T的设备,在使用过程中,
使用者每年都面临,继续使用,或,更新,的策略,
设 备 更 新 问 题
133
阶段 k,运行年份；
状态变量 x k,设备的役龄 t ；
决策变量 d k,
继续使用更新
)(
)( R e
K e e pK
p l a c eR
d
k
状态转移方程,
Kdx
Rd
x
kk
k
k
1
1
1
阶段指标,
KdtC
RdtSCP
KdxC
RdxSCP
v
k
k
kk
kk
k
)(
)()0(
)(
)()0(
134
递推方程,
KdtftC
RdftSCP
KdxfxC
RdxfxSCP
xf
kk
kk
kkkk
kkkk
kk
)1()(
)1()()0(
m in
)()(
)()()0(
m in)(
1
1
11
11
终端条件,f n ( t )= - R ( t )
设 备 更 新 问 题
135
例 5.10：设具体数据如下：
T 0 1 2 3 4 5 6 7
C (t ) 10 13 20 40 70 100 100 --
S ( t ) -- 32 21 11 5 0 0 0
R (t ) -- 25 17 8 0 0 0 0
且 n =5,T =2,P =50
由上表开始，终端条件为,
f 6 (1)= - 25,f 6 (2)= - 17,f 6 (3)= - 8
f 6 (4)= f 6 (5)= f 6 (6)= f 6 (7)=0
设 备 更 新 问 题
136
对于 k =5,
Kd
Rd
tftC
ftSCP
tf
5
5
6
6
5
)1()(
)1()()0(
m i n)(
Kd
fC
fSCP
f
*
5
6
6
5
,4
4
3
m i n
)17(13
)25(321050
m i n
)2()1(
)1()1()0(
m i n)1(
Kd
fC
fSCP
f
*
5
6
6
5
,12
12
14
m i n
)8(20
)25(211050
m i n
)3()2(
)1()2()0(
m i n)2(
137
Rd
fC
fSCP
f
*
5
6
6
5
,24
40
24
min
040
)25(111050
min
)4()3(
)1()3()0(
min)3(
Rd
fC
fSCP
f
*
5
6
6
5
,30
70
30
m i n
070
)25(51050
m i n
)5()4(
)1()4()0(
m i n)4(
Rd
fC
fSCP
f
*
5
6
6
5
,35
100
35
m i n
0100
)25(01050
m i n
)6()5(
)1()5()0(
m i n)5(
138
Rd
fC
fSCP
f
*
5
6
6
5
,35
100
35
m i n
0100
)25(01050
m i n
)7()6(
)1()6()0(
m i n)6(
Kd
Rd
tftC
ftSCP
tf
4
4
5
5
4
)1()(
)1()()0(
m i n)(
Rd
fC
fSCP
f
*
4
5
5
4
,24
25
24
m i n
1213
)4(321050
m i n
)2()1(
)1()1()0(
m i n)1(
对于 k =4,
139
Rd
fC
fSCP
f
*
4
5
5
4
,35
44
35
m i n
2420
)4(211050
m i n
)3()2(
)1()2()0(
m i n)2(
Rd
fC
fSCP
f
*
4
5
5
4
,45
70
45
m i n
3040
)4(111050
m i n
)4()3(
)1()3()0(
m i n)3(
140
Rd
fC
fSCP
f
*
4
5
5
4
,51
1 0 5
51
m i n
3570
)4(51050
m i n
)5()4(
)1()4()0(
m i n)4(
Rd
fC
fSCP
f
*
5
5
5
4
,56
1 3 5
56
m i n
351 0 0
)4(01050
m i n
)6()5(
)1()5()0(
m i n)5(
141
对于 k =3,
Kd
Rd
tftC
ftSCP
tf
3
3
4
4
3
)1()(
)1()()0(
min)(
Kd
fC
fSCP
f
*
3
4
4
3
,48
48
52
m i n
3513
24321050
m i n
)2()1(
)1()1()0(
m i n)1(
142
Rd
fC
fSCP
f
*
3
4
4
3
,73
91
73
m i n
5140
24111050
m i n
)4()3(
)1()3()0(
m i n)3(
Rd
fC
fSCP
f
*
3
4
4
3
,79
126
79
m i n
5670
2451050
m i n
)5()4(
)1()4()0(
m i n)4(
Rd
fC
fSCP
f
*
3
4
4
3
,63
65
63
m i n
4520
24211050
m i n
)3()2(
)1()2()0(
m i n)2(
143
Kd
Rd
tftC
ftSCP
tf
2
2
3
3
2
)1()(
)1()()0(
m i n)(
RdKd
fC
fSCP
f
*
2
*
2
3
3
2
,76
76
76
m in
6313
48321050
m in
)2()1(
)1()1()0(
m in)1(
或者
Rd
fC
fSCP
f
*
2
3
3
2
,87
93
87
m i n
7320
48211050
m i n
)3()2(
)1()2()0(
m i n)2(
对于 k =2,
144
Rd
fC
fSCP
f
*
2
3
3
2
,73
119
97
m i n
7940
48111050
m i n
)4()3(
)1()3()0(
m i n)3(
对于 k =1,
Kd
Rd
tftC
ftSCP
tf
1
1
2
2
1 )1()(
)1()()0(
m i n)(
Rd
fC
fSCP
f
*
1
2
2
1
,115
117
115
m i n
9720
76211050
m i n
)3()2(
)1()2()0(
m i n)2(
97
145
由以上计算可知，本问题有两个决策，它们对应的最小费用都是 115。
年份 1 2 3 4 5
决策 1 更新 更新 继续 更新 继续决策 2 更新 继续 更新 更新 继续这两个决策是设 备 更 新 问 题
146
作业：
习题 — 12,13(1)
