运筹学课件制作,北京理工大学 吴祈宗等
2
第五章 动态规划多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容重点
3
一,多阶段决策问题
(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.多阶段决策过程的最优化
4
1.多阶段决策过程的最优化动态规划方法与,时间,关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是,动态,的意思 。 然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入,时段,因素,就可以将其转化为一个多阶段决策问题 。 在本章中将介绍这种处理方法 。
5
1.多阶段决策过程的最优化二,多阶段决策问题举例属于多阶段决策类的问题很多,
例如：
1)工厂生产过程,由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排 。
6
1.多阶段决策过程的最优化
2)设备更新问题,一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,
维修费用增加,可正常使用的工时减少,
加工质量下降,经济效益差,并且,使用的年限越长,处理价值也越低,自然,如果卖去旧的买新的,还需要付出更新费,因此就需要综合权衡决定设备的使用年限,使总的经济效益最好 。
7
1.多阶段决策过程的最优化
3)连续生产过程的控制问题,
一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此,应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大 。
8
1.多阶段决策过程的最优化以上所举问题的发展过程都与时间因素有关,因此在这类多阶段决策问题中,阶段的划分常取时间区段来表示,
并且各个阶段上的决策往往也与时间因素有关,这就使它具有了,动态,的含义,所以把处理这类动态问题的方法称为动态规划方法 。 不过,实际中尚有许多不包含时间因素的一类,静态,决策问题,就其本质而言是一次决策问题,
是非动态决策问题,但是也可以人为地引入阶段的概念当作多阶段决策问题,
应用动态规划方法加以解决 。
9
1.多阶段决策过程的最优化
4） 资源分配问题,便属于这类静态问题 。 如：某工业部门或公司,拟对其所属企业进行稀缺资源分配,为此需要制定出收益最大的资源分配方案 。 这种问题原本要求一次确定出对各企业的资源分配量,它与时间因素无关,不属动态决策,但是,我们可以人为地规定一个资源分配的阶段和顺序,从而使其变成一个多阶段决策问题 (后面我们将详细讨论这个问题 )。
10
1.多阶段决策过程的最优化
5） 运输网络问题,如图 5-1所示的运输网络,点间连线上的数字表示两地距离 (也可是运费,时间等 ),要求从
fk(sk)至 v10的最短路线 。
这种运输网络问题也是静态决策问题 。 但是,按照网络中点的分布,可以把它分为 4个阶段,而作为多阶段决策问题来研究 。
11
1.多阶段决策过程的最优化图 5-11 运输网络图示
12
1.多阶段决策过程的最优化三,动态规划求解的多阶段决策问题的特点通常多阶段决策过程的发展是通过状态的一系列变换来实现的 。 一般情况下,系统在某个阶段的状态转移除与本阶段的状态和决策有关外,
还可能与系统过去经历的状态和决策有关 。 因此,
问题的求解就比较困难复杂 。 而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,
即 具有,无后效性,的多阶段决策过程 。 所谓无后效性,又称马尔柯夫性,是指系统从某个阶段往后的发展,仅由本阶段所处的状态及其往后的决策所决定,与系统以前经历的状态和决策 (历史 )
无关 。
13
1.多阶段决策过程的最优化四,动态规划方法导引例 5.1,为了说明动态规划的基本思想方法和特点,下面以图 5-1所示为例讨论的求最短路问题的方法 。
第一种方法称做全枚举法或穷举法 。 它的基本思想是列举出所有可能发生的方案和结果,
再对它们一一进行比较,求出最优方案 。 这里从
v1到 v10的路程可以分为 4个阶段 。 第一段的走法有三种,第二三两段的走法各有两种,第四段的走法仅一种,因此共有 3× 2× 2× 1＝ 12条可能的路线,分别算出各条路线的距离,最后进行比较,
可知最优路线是 v1 → v3 → v7 → v9 → v10,最短距离是 18．
14
1.多阶段决策过程的最优化显然,当组成交通网络的节点很多时,用穷举法求最优路线的计算工作量将会十分庞大,而且其中包含着许多重复计算,
第二种方法即所谓,局部最优路径,
法,是说某人从 k出发,他并不顾及全线是否最短,只是选择当前最短途径,
,逢近便走,,错误地以为局部最优会致整体最优,在这种想法指导下,所取决策必是 v1 → v3 → v5 → v8 → v10,全程长度是 20；显然,这种方法的结果常是错误的,
15
1.多阶段决策过程的最优化第三种方法是动态规划方法 。 动态规划方法寻求该最短路问题的基本思想是,首先将问题划分为 4个阶段,每次的选择总是综合后继过程的一并最优进行考虑,在各段所有可能状态的最优后继过程都已求得的情况下,全程的最优路线便也随之得到 。
为了找出所有可能状态的最优后继过程,动态规划方法总是从过程的最后阶段开始考虑,然后逆着实际过程发展的顺序,逐段向前递推计算直至始点 。
16
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 。
17
1.多阶段决策过程的最优化同样,当阶段 3上所有可能状态的最优后继过程都已求得后,便可以开始考虑阶段 2上所有可能状态的最优决策和最优后继过程,如 v2的最优决策是到 v5,最优路线是 v2→ v5→ v9→ v10,最短距离是 15…依此类推,最后可以得到从初始状态 v1的最优决策是到 v3最优路线是 v1→ v3→ v7→ v9→ v10,
全程的最短距离是 18。 图 5—1中粗实线表示各点到的最优路线,每点上方括号内的数字表示该点到终点的最短路距离 。
18
1.多阶段决策过程的最优化综上所述可见,全枚举法虽可找出最优方案,但不是个好算法,局部最优法则完全是个错误方法,只有 动态规划方法属较科学有效的算法 。 它的基本思想是,把一个比较复杂的问题分解为一系列同类型的更易求解的子问题,便于应用计算机 。 整个求解过程分为两个阶段,先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值,然后再顺序地求出整个问题的最优策略和最优路线 。 计算过程中,系统地删去了所有中间非最优的方案组合,从而使计算工作量比穷举法大为减少 。
19
2.动态规划的基本概念一,动态规划的基本概念使用动态规划方法解决多阶段决策问题,首先要将实际问题写成动态规划模型,同时也为了今后叙述和讨论方便,这里需要对动态规划的下述一些基本术语进一步加以说明和定义：
20
2.动态规划的基本概念
(一 ) 阶段和阶段变量为了便于求解和表示决策及过程的发展顺序,而把所给问题恰当地划分为若干个相互联系又有区别的子问题,称之为多段决策问题的阶段 。
一个阶段,就是需要作出一个决策的子问题,通常,阶段是按决策进行的时间或空间上先后顺序划分的 。 用以描述阶段的变量叫作阶段变量,一般以 k表示阶段变量,阶段数等于多段决策过程从开始到结束所需作出决策的数目,图 5—1所示的最短路问题就是一个四阶段决策过程 。
21
2.动态规划的基本概念
（ 二 ） 状态,状态变量和可能状态集
1.状态与状态变量 。 用以描述事物
(或系统 )在某特定的时间与空间域中所处位置及运动特征的量,称为状态 。 反映状态变化的量叫做状态变量 。 状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息 。 按照过程进行的先后,每个阶段的状态可分为初始状态和终止状态,
或称输入状态和输出状态,阶段 k的初始状态记作 sk,终止状态记为 sk+1。 但为了清楚起见,通常定义阶段的状态即指其初始状态 。
22
2.动态规划的基本概念
2,可能状态集一般状态变量的取值有一定的范围或允许集合,称为可能状态集,或可达状态集 。 可能状态集实际上是关于状态的约束条件 。 通常可能状态集用相应阶段状态 sk的大写字母 Sk表示,sk∈ Sk，
可能状态集可以是一离散取值的集合,也可以为一连续的取值区间,视具体问题而定,在图 5—1
所示的最短路问题中,第一阶段状态为 v1,状态变量 s1的状态集合 S1={v1}；第二阶段则有三个状态,v2,v3,v4,状态变量 s2 的 状 态 集 合
S2={v2,v3,v4} ； 第 三 阶 段 也 有 三 个 状态,v5,v6,v7,状 态 变 量 s3 的 状 态 集 合
S3={v5,v6,v7} ；第四阶 段则有 二个状态,
v8,v9,状态变量 s4的状态集合 S4={v8,v9} ；
23
（ 三 ） 决策,决策变量和允许决策集合所谓 决策,就是确定系统过程发展的方案 。
决策的实质是关于状态的选择,是决策者从给定阶段状态出发对下一阶段状态作出的选择 。
用以描述决策变化的量称之决策变量和状态变量一样,决策变量可以用一个数,一组数或一向量来描述,也可以是状态变量的函数,记以
uk= uk(sk),表示于阶段 k状态 sk时的决策变量 。
决策变量的取值往往也有一定的允许范围,
称之允许决策集合 。 决策变量 uk(sk)的允许决策集用 Uk(sk)表示,uk(sk)∈ Uk(sk)允许决策集合实际是决策的约束条件 。
2.动态规划的基本概念
24
（ 四 ）,策略和允许策略集合策略 (Policy)也叫决策序列,策略有全过程策略和 k部子策略之分,全过程策略是指具有 n个阶段的全部过程,由依次进行的 n个阶段决策构成 的 决 策 序 列,简 称 策 略,表 示 为
p1,n{u1,u2,…,un}。 从 k阶段到第 n阶段,依次进行的阶段决策构成的决策序列称为 k部子策略,表示为 pk,n{uk,uk+1,…,un},显然当 k=1时的 k部子策略就是全过程策略 。
在实际问题中,由于在各个阶段可供选择的决策有许多个,因此,它们的不同组合就构成了许多可供选择的决策序列 (策略 ),由它们组成的集合,
称之允许策略集合,记作 P1,n,从允许策略集中,
找出具有最优效果的策略称为最优策略 。
2.动态规划的基本概念
25
（ 五 ） 状态转移方程系统在阶段 k处于状态 sk,执行决策 uk(sk)
的结果是系统状态的转移,即系统由阶段 k的初始状态 sk转移到终止状态 sk+1,或者说,系统由
k阶段的状态 sk转移到了阶段 k+1的状态 sk+1,多阶段决策过程的发展就是用阶段状态的相继演变来描述的 。
对于具有无后效性的多阶段决策过程,系统由阶段 k到阶段 k+1的状态转移完全由阶段 k的状态 sk和决策 uk(sk)所确定,与系统过去的状态
s1,s2,…,sk-1及其决策 u1(s1),u2(s2)…uk-1(sk-1)
无关 。 系统状态的这种转移,用数学公式描述即有：
2.动态规划的基本概念
))(,(1 kkkkk susTs (5-1)
26
通常称式 (5-1)为多阶段决策过程的状态转移方程 。 有些问题的状态转移方程不一定存在数学表达式,但是它们的状态转移,还是有一定规律可循的 。
(六 ) 指标函数用来衡量策略或子策略或决策的效果的某种 数量指标,就称为指标函数 。 它是定义在全过程或各子过程或各阶段上的确定数量函数 。
对不同问题,指标函数可以是诸如费用,成本,
产值,利润,产量,耗量,距离,时间,效用,
等等 。 例如：图 5—1的指标就是运费 。
2.动态规划的基本概念
27
(1)阶段指标函数 （ 也称阶段效应 ） 。 用
gk(sk,uk)表示第 k段处于 sk状态且所作决策为
uk(sk)时的指标,则它就是第 k段指标函数,简记为 gk 。 图 5-1的 gk值就是从状态 sk到状态 sk+1的距离 。 譬如,gk(v2,v5)=3,即 v2到 v5的距离为 3。
(2)过程指标函数 （ 也称目标函数 ） 。 用
Rk(sk,uk)表示第 k子过程的指标函数 。 如图 5-1的
Rk(sk,uk)表示处于第 k段 sk状态且所作决策为 uk时,
从 sk点到终点 v10的距离 。 由此可见,Rk(sk,uk)不仅跟当前状态 sk有关,还跟该子过程策略 pk(sk)
有关,因此它是 sk和 pk(sk)的函数,严格说来,
应表示为,
2.动态规划的基本概念
))(,( kkkk spsR
28
不过实际应用中往往表示为 Rk(sk,uk)或
Rk(sk)。 还跟第 k子过程上各段指标函数有关,
过程指标函数 Rk(sk)通常是描述所实现的全过程或 k后部子过程效果优劣的数量指标,它是由各阶段的阶段指标函数 gk(sk,uk)累积形成的,
适于用动态规划求解的问题的过程指标函数
（ 即目标函数 ）,必须具有关于阶段指标的可分离形式,对于部子过程的指标函数可以表示为：
式中,?表示某种运算,可以是加,减,乘,
除,开方等 。
2.动态规划的基本概念
),(),(),(
),,,,,,(
111
11,,
nnnkkkkkk
nnkkkknknk
usgusgusg
usususRR
(5-2)
29
多阶段决策问题中,常见的目标函数形式之一是取各阶段效应之和的形式,即,
(5-3)
有些问题,如系统可靠性问题,其目标函数是取各阶段效应的连乘积形式,如：
(5-4)
总之,具体问题的目标函数表达形式需要视具体问题而定 。
2.动态规划的基本概念
n
ki
iiik usgR ),(
n
ki
iiik usgR ),(
30
(七 ) 最优解用 fk(sk)表示第 k子过程指标函数在状态 sk下的最优值,即称 fk(sk)为第 k子过程上的最优指标函数 ；与它相应的子策略称为 sk状态下的最优子策略,记为 pk*(sk) ；而构成该子策赂的各段决策称为该过程上的最优决策,记为 ；
有简记为
2.动态规划的基本概念
))(,( kkkk spsR
nkspsRoptsf kkkk
sPpkk kKk
,,2,1) ) },(,({)(
)(
)(,),(),( 11 nnkkkk sususu
nksusususp nnkkkkkk,,2,1) },(,),(),({)( 11
nkuuup nkkk,,2,1},,,,{ 1
31
特别当 k=1且 s1取值唯一时,f1(s1)就是问题的最优值，而 p1*就是最优策略。如例只有唯一始点 v1
即 s1取值唯一,故 f1(s1)=18就是例的最优值，而就是例的最优策略。
但若取值不唯一,则问题的最优值记为 f0有最优策略即为 s1=s1*状态下的最优策略：
我们把最优策略和最优值统称为问题的最优解 。
2.动态规划的基本概念
},,,{ 109731 vvvvp
)()}({ 111110
11
ssfsfo p tf
Ss
},,),({)( 211111 nuusussp?
32
按上述定义，所谓最优决策是指它们在全过程上整体最优 (即所构成的全过程策略为最优 )，而不一定在各阶段上单独最优。
(八 ) 多阶段决策问题的数学模型综上所述,适于应用动态规划方法求解的一类多阶段决策问题,亦即具有无后效性的多阶段决策问题的数学模型呈以下形式,
2.动态规划的基本概念
),,2,1( nku k
nk
Uu
Ss
usTs
ts
usususRRoptf
kk
kk
kkkk
nn
uu
n
,,2,1
),(
..
),,,,,,(
1
2211
~
1
（ 5-5）
33
式中,OPT”表示最优化,视具体问题取 max或 min。
上述数学模型说明了对于给定的多阶段决策过程,求取一个 (或多个 )最优策略或最优决策序列,使之既满足式 (5-5)给出的全部约束条件,又使式 (5-5)所示的目标函数取得极值,并且同时指出执行该最优策略时,过程状态演变序列即最优路线
2.动态规划的基本概念
},,,{ 21 nuuu?
},,,,{ 121 nn ssss?
34
二,动态规划的最优化原理与基本方程
1,标号法为进一步阐明动态规划方法的基本思路,
我们介绍一种只适用于例这类最优路线问题的特殊解法 ——标号法 。 标号法是借助网络图通过分段标号来求出最优路线的一种简便,直观的方法 。 通常标号法采取,逆序求解,的方法来寻找问题的最优解,即从最后阶段开始,逐次向阶段数小的方向推算,最终求得全局最优解 。
2.动态规划的基本原理
35
下面给出标号法的一般步骤：
1.从最后一段标起,该段各状态 (即各始点 )到终点的距离用数字分别标在各点上方的方格内,并用粗箭线连接各点和终点 。
2.向前递推,给前一阶段的各个状态标号 。 每个状态上方方格内的数字表示该状态到终点的最短距离 。 即为该状态到该阶段已标号的各终点的段长,再分别加上对应终点上方的数字而取其最小者 。 将刚标号的点沿着最短距离所对应的已标号的点用粗箭线连接起来,表示出各刚标号的点到终点的最短路线 。
2.动态规划的基本原理
36
3.逐次向前递推,直到将第一阶段的状态 (即起点 )也标号,起点方格内的数字就是起点到终点的最短距离,从起点开始连接终点的粗箭线就是最短路线 。
用标号法来求解下例例 5.2,网络图 5— 2表示某城市的局部道路分布图 。 一货运汽车从 S出发,最终到达目的地 E。 其中 Ai(i＝ 1,2,3),Bj(j＝ 1,2)和 Ck(k＝ 1,2)是可供汽车选择的途经站点,各点连线上的数字表示两个站点问的距离 。 问此汽车应走哪条路线,使所经过的路程距离最短?
2.动态规划的基本原理
37
2.动态规划的基本原理图 5-2 某城市的局部道路分布图
38
第一步：先考虑第四阶段,即 k=4,该阶段共有两个状态,C1,C2,设 f4(C1)和 f4(C2)分别表示 C1、
C2到 E的最短距离,显然有 f4(C1)=5和 f4(C2)=8,边界条件 f5(E)=0 。
第二步：即 k=3,该阶段共有两个状态,B1,B2
(1) 从 B1出发有两种决策,B1→ C1,B1→ C2 。
记 d3(B1,C1)表示 B1到 C1的距离,即,这里的每一种决策的阶段指标函数就是距离,所以,B1→ C1的阶段指标函数为 d3(B1,C1)＝ 6,B1→ C2的阶段指标函数为 d3(B1,C2)＝ 5。 因此有,
f3(B1)＝ min{d3(B1,C1)+f4(C1),d3(B1,C2)+f4(C2)}＝
min(6＋ 5,5＋ 8)＝ 11。 那么,从出发到 E的最短路线是 B1→ C1→ E,对应的决策 u3(B1) = C1 。
2.动态规划的基本原理
39
(2)从 B2出发也有两种决策,B2→ C1,B2→ C2同理,
有 f3(B2)=min{d3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)} ＝
min(9+5,8+87)＝ 14,那么,从 B2出发到 E的最短路线是 B2→ C1→ E,且 u3(B2)=C1 。
第三步：即 k＝ 2,该阶段共有三个状态,Al,A2,A3
(1)从 Al出发有两种决策,A1→ B1,A1→ B2。 则
f2(A1)=min{d2(A1,B1)+f3(B1),d2(A1,B2)+f3(B2)}＝ min{6
＋ 11,5 ＋ 14} ＝ 17,即 A1 到 E 的 最 短 路 线 为
A1→ B1→ C1→ E,且 u3(A1)＝ B1 。
(2)从 A2出发也有两种决策,A2→ B1,A2→ B2。 此时,
f2(A2) ＝ min{d2(A2,B1)+f3(B1),d2(A2,B2)+f3(B2)} ＝
min{8+11,6+14} ＝ 19,即 A2 到 E 的 最 短 路 线 为
A2→ B1→ C1→ E,且 u3(A2)＝ B1。
2.动态规划的基本原理
40
(3)从 A3出发也有两种决策,A3→ B1,A3→ B2 此时
f2(A2)=min{d2(A3,B1)+f3(B1),d2(A3,B2)+f3(B2)} ＝
min{7+11,4+14} ＝ 18,即 A3 到 E 的 最 短 路 线 为
A3→ B1→ C1→ E,对应的 u2(A3)＝ B2 。
第四步：即 k＝ 1,该阶段只有一个状态 S,从 S出发有三种决策,S→ A1,S→ A2,S→ A3,那么,
f1(S)=min{d1(S,A1)+f2(A1),d2(S,B2)+f3(B2)} ＝
min{8+11,6+14} ＝ 19,即 A2 到 E 的 最 短 路 线 为
A2→ B1→ C1→ E,且 u3(A2)＝ B1 。
那么,从 S到 E共有三条最短路线：
此时,u1(S)＝ A1题 和此时,u1(S)＝ A3,最短距离为 21。
2.动态规划的基本原理
ECBAS 111
ECBAS 113 ECBAS 123
41
结果如图 5-3所示 。
每个状态上方的方格内的数字表示该状态到 E的最短距离,首尾相连的粗箭线构成每一状态到 E的最短路线 。 因此,
标号法不但给出起点到终点的最短路线和最短距离,同时也给出每一状态到终点的最短路线及其最短距离 。 如,A1到 E
的最短路线是,最短矩离是
17
图见下页
2.动态规划的基本原理
ECBA 111
42
2.动态规划的基本原理图 5-3某城市局部道路求最短路径的过程
43
2,最优化原理 （ 贝尔曼最优化原理 ）
作为一个全过程的最优策略具有这样的性质,对于最优策略过程中的任意状态而言,无论其过去的状态和决策如何,余下的诸决策必构成一个最优子策略 。 该原理的具体解释是,若某一全过程最优策略为：
2.动态规划的基本原理
)}(),(,),(),({)( 221111 nnkk sususususp
则对上述策略中所隐含的任一状态而言,
第 k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略 p1*中,即为
)}(,),(),({)( 11 nnkkkkkk susususp
44
如第一节所述,基于上述原理,提出了一种逆序递推法；这里可以指出,该法的关键在于给出一种递推关系 。 一般把这种递推关系称为动态规划的函数基本方程 。
3.函数基本方程在例中,用标号法求解最短路线的计算公式可以概括写成：
(5-6)
其中,在这里表示从状态 sk到由决策 u
k(sk)所决定的状态 sk+1之间的距离,是边界条件,表示全过程到第四阶段终点结束 。
2.动态规划的基本原理
1,2,3,4) ) },(())(,({m i n)(
0)(
111)(
55
ksufsusgsf
sf
kkkkkkksUukk
kkk
))(,( kkkk susg
0)( 55?sf
45
一般地,对于 n个阶段的决策过程,假设只考虑指标函数是,和,与,积,的形式,第 k阶段和第 k+1阶段间的递推公式可表示如下：
(1)当过程指标函数为下列,和,的形式时,
相应的函数基本方程为
（ 5—7）
2.动态规划的基本原理
))}(,({)(
)( kkkksPpkk
spsRo p tsf
kKk?
n
ki
iii usg ),(
1,2,,1,) ) },(())(,({)(
0)(
111
11
nnksufsusgoptsf
sf
kkkkkkk
Uu
kk
nn
kk
46
(2) 当过程指标函数为下列,积,的形式时,
相应的函数基本方程为
（ 5—8）
可以看出,和,积函数的基本方程中边界条件 (即 的取值 )是不同的 。
2.动态规划的基本原理
))}(,({)(
)( kkkksPpkk
spsRo p tsf
kKk?
n
ki
iii usg ),(
1,2,,1,) ) },(())(,({)(
1)(
111
11
nnksufsusgoptsf
sf
kkkkkkk
Uu
kk
nn
kk
)( 11 nn sf
47
3.动态规划方法的基本步骤标号法仅适用于求解象最短路线问题那样可以用网络图表示的多阶段决策问题 。 但不少多阶段决策问题不能用网络图表示 。 此时,应该用函数基本方程来递推求解,一般来说,要用函数基本方程逆推求解,首先要有效地建立动态规划模型,然后再递推求解,最后得出结论,
然而,要把一个实际问题用动态规划方法来求解,还必须首先根据问题的要求 。 把它构造成动态规划模型,这是非常重要的一步 。 正确地建立一个动态规划模型,往往问题也就解决了一大半,而一个正确的动态规划模型,应该满足哪些条件呢?
48
3.动态规划方法的基本步骤
1,应将实际问题恰当地分割成 n个子问题 (n个阶段 )。 通常是根据时间或空间而划分的,或者在经由静态的数学规划模型转换为动态规划模型时,常取静态规划中变量的个数 n,即 k=n。
2,正确地定义状态变量 sk,使它既能正确地描述过程的状态,又能满足无后效性,动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的,动态规划中的状态变量必须具备以下三个特征：
49
3.动态规划方法的基本步骤
(1)要能够正确地描述受控过程的变化特征 。
(2)要满足无后效性 。 即如果在某个阶段状态已经给定,那么在该阶段以后,过程的发展不受前面各段状态的影响,如果所选的变量不具备无后效性,就不能作为状态变量来构造动态规划的模型 。
(3)要满足可知性 。 即所规定的各段状态变量的值,可以直接或间接地测算得到 。 一般在动态规划模型中,状态变量大都选取那种可以进行累计的量 。 此外,在与静态规划模型的对应关系上,
通常根据经验,线性与非线性规划中约束条件的个数,相当于动态规划中状态变量 sk的维数,而前者约束条件所表示的内容,常就是状态变量 sk
所代表的内容 。
50
3.动态规划方法的基本步骤
3,正确地定义决策变量及各阶段的允许决策集合 Uk(sk),根据经验,一般将问题中待求的量,选作动态规划模型中的决策变量 。 或者在把静态规划模型 (如线性与非线性规划 )转换为动态规划模型时,常取前者的变量 xj为后者的决策变量 uk。
4,能够 正确地写出状态转移方程,至少要能正确反映状态转移规律 。 如果给定第 k阶段状态变量 sk的值,则该段的决策变量 uk一经确定,第 k+1段的状态变量 sk+1的值也就完全确定,即有 sk+1=Tk(sk,uk)
51
3.动态规划方法的基本步骤
5,根据题意,正确地构造出目标与变量的函数关系 ——目标函数,目标函数应满足下列性质：
(1)可分性,即对于所有 k后部子过程,其目标函数仅取决于状态 sk及其以后的决策
uk,uk+1,┈,un,就是说它是定义在全过程和所有后部子过程上的数量函数 。
(2)要满足递推关系,即
(3)函数 对其变元 Rk+1来说要严格单调 。
)],,(,,[),,,,,( 111111, nkkkkknkkkknk ssRussususR
)],,(,,[ 111 nkkkkk ssRus
52
6,写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式其中 表示第 i阶段的指标,它显然是满足上述三个性质的 。 所以上式可以写成,
3.动态规划方法的基本步骤
n
ki
iiikk usgsR ),()(
),( iii usg
),,(),( 111 nkkkkkk ssRusgR
53
二,动态规划方法的基本步骤为进一步说明动态规划模型建立的基本方法及其求解过程,下面通过实际例子用上述方法具体给出求解动态规划方法的基本步骤：
例 5.3:有某种机床,可以在高低两种不同的负荷下进行生产,在高负荷下生产时,产品的年产量为 g,与年初投入生产的机床数量 u1的关系为 g=g(u1)=8u1,这时,年终机床完好台数将为
au1,(a为机床完好率,0<a<1,设 a=0.7).在低负荷下生产时,产品的年产量为 h,和投入生产的机床数量 u2的关系为 h=h(u2)=5u2,相应的机床完好率为 b(0<b<1,设 b=0,9),一般情况下 a<b。
3.动态规划方法的基本步骤
54
假设某厂开始有 x=1000台完好的机床,现要制定一个五年生产计划,问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量,
以使在 5年内产品的总产量为最高 。
解,首先构造这个问题的动态规划模型 。
1,变量设置
(1)设阶段变量 k表示年度,因此,阶段总数
n=5。
(2)状态变量 sk表示第 k年度初拥有的完好机床台数,同时也是第 k-1年度末时的完好机床数量 。
3.动态规划方法的基本步骤
55
(3)决策变量 uk,表示第 k年度中分配于高负荷下生产的机床台数 。 于是 sk- uk便为该年度中分配于低负荷下生产的机床台数,
这里 sk与 uk均取连续变量,当它们有非整数数值时,可以这样理解：如 sk＝ 0.6,就表示一台机器在 k年度中正常工作时间只占 6/10； uk=0.4时,
就表示一台机床在 k年度只有 4/10的时间于高负荷下工作,
2,状态转移方程为
k=1,2,…,6
3.动态规划方法的基本步骤
)(9.07.0)(1 kkkkkkk usuusbaus
56
3,允许决策集合,在第 k段为
4,目标函数 。 设 gk(sk,uk)为第 k年度的产量,则 gk(sk,uk)=8uk+5(sk-uk),因此,目标函数为 k＝ 1,2,．．．,5
5,条件最优目标函数递推方程 。
令 fk(sk)表示由第 k年的状态 sk出发,采取最优分配方案到第 5年度结束这段时间的产品产量,根据最优化原理有以下递推关系：
k=1,2,3,4,5
3.动态规划方法的基本步骤
}0{)( kkkkk xuusU
5 ),(
ki
kkkk usgR
)(m a x)( kUukk xsf
kk?
)]}(9.07.0[)](58{[ 1 kkkkkkk usufusu
57
6.边界条件为下面采用逆序递推计算法,从第 5年度开始递推计算。
k=5时有显然,当 u5*=s5时,f5(s5)有最大值,相应的有
f5(s5)=8s5
k=4时有
3.动态规划方法的基本步骤
0)( 1515 sf
,
5055
m a x)( su
k
sf )}()](58{[ 6555 ksfusu
50
m a xsu
k
)](58{[ 555 usu
)( 44 sf )]}(9.07.0[)](58{[m a x 4445444
0 44 usufususu
)]}(9.07.0[8)](58{[m a x 4444440
44
usuususu
)}(2.126.13{m a x 4440
44
ususu
=
=
因此,当 u4*=s4时,有最大值 f4(s4)=13.6s4
58
k=3 时有可见,当 u3*=s3 时,f3(s3) 有 最 大 值 f3(s3)
=17.55s3.
k=2 时有
= +
=
此时,当取 u2*=0时有最大值,即 f2(s2)=20.8s2,其中 s2=0.7u1+0.9(s1-u1)
3.动态规划方法的基本步骤
=?)(
33 sf )}()](58{[m a x 443330 33 sfususu )}(22.1755.17{m a x 3330 33 ususu
)}()](58{[m a x 332220
22
sfususu
)](58{[m a x 2220
22
ususu )]}(9.07.0[55.17 222 usu
)](8.2025.20{[m a x 2220
22
ususu
)( 22 sf
59
k=1时有
+
=
当取 u1*=0 时,f1(s1) 有 最 大 值,即
f1(s1)=23.7s1,因为 s1=1000,故
f1(s1)=23700个产品,
按照上述计算顺序寻踪得到下述计算结果：
3.动态规划方法的基本步骤
)( 11 sf )(58{m a x 1110
11
ususu )]}(9.07.0[8.20 111 usu
)}(7.2355.22{m a x 1110
11
ususu
01u 10001?s 5000),( 111?usg 23700)( 11?sf
02u 9002?s 4 5 0 0),( 222?usg 1 8 7 2 08.20)( 222 ssf
60
上面所讨论的最优决策过程是所谓始端状态 s
1固定,终端状态 s6自由,如果终端也附加上一定的约束条件,那么计算结果将会与之有所差别,例如,若规定在第五个年度结束时,完好的机床数量为 500台 (上面只有 278
台 ),问应该如何安排五年的生产,使之在满足这一终端要求的情况下产量最高？
3.动态规划方法的基本步骤
33 su 8103?s 6480),( 333?usg 1 4 2 1 655.17)( 333 ssf
44 su 5674?s 4 5 3 6),( 444?usg 77116.13)( 444 ssf
55 su 3975?s 3176),( 555?usg 3 1 7 66.13)( 555 ssf
2 7 87.0)(9.07.0 55556 xusus
61
解：由状态转移方程有得显而易见,由于固定了终端的状态 s6,第五年的决策变量 U5的允许决策集合 U5(s5)也有了约束,上式说明 U5(s5)已退化为一个点,即第五年投入高负荷下生产的机床数只能由式 U5=4.5s5-2500作出一种决策,故
3.动态规划方法的基本步骤
＝ 500
)(9.07.0)(1 kkkkkkk usuusbaus
)(9.07.0 5556 usus
2 5 0 05.4 55 su
62
当 k=5时有当 k=4时有显然，只有取 u4*=0,f4(s4)有最大值，即
f4(s4)=21.7s4-7500。同理类推
3.动态规划方法的基本步骤
=
5055
m a x)( su
k
sf )}(58{ 555 usu )2 5 0 05.4(5)2 5 0 05.4(8 555 usu
7 5 0 05.18 5 s
=
)( 44 sf )}()](58{[m a x 554440
44
sfususu
}75005.18)(58{m a x 54440
44
uususu
}7500)](9.07.0[5.18)(58{m a x 4444440
44
usuususu
}7 5 0 075.07.21{m a x 440
44
ussu
=
=
63
k=3时有可知,当 u3*=0时,f3(s3)有最大值 f4(s4)=24.5s3-
7500.
k=2时有此时,当 u2*=0时有最大值,即
f2(s2)=27.1s2-7500
3.动态规划方法的基本步骤
=
)( 33 sf )}()](58{[m a x 44333
0 33 sfususu
}7500)](9.07.0[7.21)](58{[m a x 3333330
33
usuususu
}7 5 0 05.243.1{m a x 330
33
susu=
)( 22 sf )}()](58{[m a x 332220
22
sfususu
)](58{[m a x 2220
22
ususu }7 5 0 0)](9.07.0[5.24 222 usu
}7 5 0 01.279.1{m a x 220
22
susu=
= +
64
k=1时有只有取 u1*=0时,f1(s1)有最大值,即
f1(s1)=29.4s1-7500 。
由此可见,为了使下一个五年计划开始的一年有完好的机床 500台,其最优策略应该为：在前 4年中,都应该把全部机床投人低负荷下生产,在第 5年,
只能把部分完好机投入高负荷下生产 。 根据最优策赂,从始端向终端递推计算出各年的状态,即算出每年年初的完好机床台数,因为 s
1＝ 1000台,于是有
3.动态规划方法的基本步骤
=
)( 11 sf )}()(58{m a x 221110
11
sfususu
}7500)](9.07.0[1.27)(58{m a x 1111110
11
usuususu
}7 5 0 04.294.2{m a x 110
11
susu=
65
因此,u5*=4.5s5-2500=425(台 ),这就是说第 5年里还有 204台投入低负荷下生产,否则不能保证
s6=0.7u5+0.9(u5-s5)=500(台 )。
在上述最优决策下,5年里所得最高产量为：
f1(s1)＝ 29.4s1-7500=29400-7500＝ 21900(个 )。
可见,附加了终端约束条件以后,其最高产量 f1(s1)
比终端自由时要低一些 。
3.动态规划方法的基本步骤
（台）
（台）
（台）
（台）
（台）
01u 10001?s
02u 9 0 09.0)(9.07.0 1*11*12 susus
03u 8 1 09.0)(9.07.0 2*22*23 susus
04u 7 2 99.0)(9.07.0 3*33*34 susus
6 5 69.0)(9.07.0 4*44*45 susus
2 7 87.0)(9.07.0 55556 xusus （台）
66
例 5.4：一个线路网络图，从 A到 E
要修建一条石油管道，必须 在 B,C、
D处设立加压站。各边上的数为长度，
现需要找一条路使总长度最短。
B3
B2
B1
C3
C2
C1
D3
D2
D1
EA
4
5
6
3
4
3
4
5
4
7
4
2
6
5
7
10
9
7
8
6
3.动态规划方法的基本步骤
67
解,可分成 4个阶段：
A到 B,B到 C,C到 D,D到 E；
每个阶段 k 的起点称为状态 Sk ；
从 k 阶段的起点出发可以做一选择，即决定到下一阶段的哪个节点,称为决策 Xk ； 可见,Sk+1 是由
Sk 和 Xk 所决定的。
3.动态规划方法的基本步骤
68
那么，从 A出发经过 4个阶段,A
到 B,B到 C,C到 D,D到 E，逐次作出决策，构成从 A到 E 的一条路线，记为 u 。
即
u = S1 X1 S2 X2 S3 X3 S4 X4 S5
其中 S1 = A,S5 = E
记 d 为两个相邻节点之间的长度，
如 d（ A,B 3） = 3 。
3.动态规划方法的基本步骤
69
① 记 fk(Sk)为从 Sk到 E的最短长度,称为从 Sk到 E的距离。
那么,f1(A)是从 A到 E的最短距离，即最优策略的值。
3.动态规划方法的基本步骤
70
② 最短路问题的特点：如果从 A
到 E的最优策略经过某节点，那么这个策略的从该节点到 E的一段，必定是该节点到 E的所有线路中 Sk最短的一条，即这一段的长度为 fk（ Sk）。
（ 1）逆序法,从 E到 A。
（ 2）顺序法,对节点 Sk，从 A到
Sk 所有线路中，最短的一条的长度记为 φ k（ S k），例如 φ 1（ A） = 0，
称为问题的边界条件 。
3.动态规划方法的基本步骤
71
动态规划模型建立后,对基本方程分段求解,不像线性规划或非线性规划那样有固定的解法,必须根据具体问题的特点,结合数学技巧灵活求解,如动态规划模型中的状态变量与决策变量若被限定只能取离散值,则可采用离散变量的分段穷举法 。 当动态规划模型中状态变量与决策变量为连续变量,就要根据方程的具体情况灵活选取连续变量的求解方法 。 如经典解析方法,线性规划方法,非线性规划法或其它数值计算方法等 。 还有连续变量的离散化解法和高维问题的降维法及疏密格子点法等等 。
3.动态规划方法的基本步骤
72
学习方法建议：
第一步 先看问题，充分理解问题的条件、情况及求解目标。
第二步 结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的
“四大要素、一个方程” —— 这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。
4.动态规划方法应用举例
73
第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。
第四步 把自己的求解放到一边，
看书中的求解方法，要充分理解教材中的论述。
第五步 对照自己的求解，分析成败。
4.动态规划方法应用举例
76
求 最 短 路 径
77
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
78
将问题分成五个阶段，第 k阶段到达的具体地点用状态变量 xk表示，例如,x2=B3表示第二阶段到达位置 B3，
等等。这里状态变量取字符值而不是数值。
将决策定义为到达下一站所选择的路径,例如目前的状态是 x2=B3,这时决策允许集合包含三个决策,它们是
D2(x2)=D2(B3)={B3?C1,B3?C2,B3?C3}
求 最 短 路 径
79
最优指标函数 fk(xk)表示从目前状态到 E的最短路径。终端条件为
f5(x5)=f5(E)=0
其含义是从 E到 E的最短路径为 0。
第四阶段的递推方程为,f x v x d f x
d D x4 4 4 4 4 5 54 4 4
( ) m i n { (,) ( )}
( )
从 f 5 (x 5 ) 到 f 4 (x 4 ) 的递推过程用下表表示,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
求 最 短 路 径
80
其中 *表示最优值，在上表中，由于决策允许集合 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
求 最 短 路 径
81
第三阶段的递推方程为：
从 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
求 最 短 路 径
82
由此得到 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 ) 的递推过程用表格表示如下,
求 最 短 路 径
83
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
求 最 短 路 径
84
由此得到 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
求 最 短 路 径
85
第一阶段的递推方程为：
)}(),({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
求 最 短 路 径
86
由此得到 f1(x1)的表达式
x 1 f 1 (x 1 ) 最优决策 d 1 *
A 19 A? B 2
求 最 短 路 径
87
资 源 分 配 问 题
88
例 5.6,有资金 4万元，投资 A,B,C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目 A,B,C的投资效益
（万吨）和投入资金（万元）关系见下表：
求对三个项目的最优投资分配，使总投资效益最大。
资 源 分 配 问 题
89
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
资 源 分 配 问 题
90
k=4,f4(x4)=0
k=3,0≤d3≤x3,x4=x3-d3
资 源 分 配 问 题
91
k=2,0≤d2≤x2,x3=x2-d2
资 源 分 配 问 题
92
k=1,0≤d1≤x1,x2=x1-d1
资 源 分 配 问 题
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,状态变量 xk：第 k次装载时背包还可以装载的重量；
3,决策变量 dk：第 k次装载第 k种物品的件数；
背 包 问 题
96
4,决策允许集合：
Dk(xk)={dk|0? dk?xk/wk,dk为整数 }；
5,状态转移方程,xk+1=xk-wkdk
6,阶段指标,vk=ckdk
7,递推方程
fk(xk)=max{ckdk+fk+1(xk+1)}
=max{ckdk+fk+1(xk-wkdk)}
8,终端条件,fn+1(xn+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
最短路径问题和背包问题的状态变量和决策 变量都只能取离散的整数值。当状态变量和决策变量的取值范围很大，或者这些变量是连续的，用列举的方法就比较困难或者根本不可能了。这就需要用连续变量的处理方法。
例 5,8,某种机器可以在高、低两种负荷下生产。
高负荷生产条件下机器完好率为 0.7,即如果年初有
u 台完好机器投入生产,则年末完好的机器数量为
0.7 u 台。系数 0.7 称为完好率。年初投入高负荷运行的 u 台机器的年产量为 8 u 吨。系数 8 称为单台产量。低负荷运行时，机器完好率为 0.9,单台产量为
5 吨。设开始时有 1000 台完好机器,要制订五年计划，每年年初将完好的机 器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。
104
构造动态规划模型如下：
阶段 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
机器负荷分配问题
105
递推方程：
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
根据题意，本题的决策允许集合应该是一个整数集合，但由于决策允许集合中 可取的决策数量很大，一一列举计算量很大,不妨认为状态变量和决策变量都是连续的,得到最优解后，再作取整处理。
机器负荷分配问题
106
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
机器负荷分配问题
107
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
机器负荷分配问题
108
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
机器负荷分配问题
109
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
机器负荷分配问题
110
由此可以得到：
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
机器负荷分配问题
111
每年投入高负荷运行的机器数以每年初完好的机器数为,
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
机器负荷分配问题
112
在这个例子中，状态变量的终端值 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满足,
机器负荷分配问题
113
则从 1— t-1年，年初将全部完好机器投入低负荷运行，从 t— n年，年初将全部完好机器投入高负荷运行，这样的决策，将使总产量达到最大。
tn
i
i
tn
i
i k
kkp
pp
k
0
1
121
21
)1(
0
1 )(
机器负荷分配问题
114
生 产 库 存 问 题
115
例 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 。 每个月生产的产品在月末入库，月初根据当月需求 发货。 求七个月的生产量，能满足各 月的需求，并使生产成本最低。
生 产 库 存 问 题
116
阶段 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；
生 产 库 存 问 题
117
递推方程：
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
生 产 库 存 问 题
118
对于 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
生 产 库 存 问 题
119
对于 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}
生 产 库 存 问 题
120
因为 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
生 产 库 存 问 题
121
对于 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)
生 产 库 存 问 题
122
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
生 产 库 存 问 题
123
对于 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
生 产 库 存 问 题
124
对于 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}
生 产 库 存 问 题
125
因为 13-x2>0
所以 d2(x2)={d2|13-x2?d2?17-x2}
由此 f2(x2)=5(13-x2)-13x2+377
=-18x2+442,
d2*=13-x2
生 产 库 存 问 题
126
对于 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}
生 产 库 存 问 题
127
根据题意 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
生 产 库 存 问 题
128
设 备 更 新 问 题
129
一台设备的价格为 P,运行寿命为 n年,
每年的维修费用是设备役龄的函数,记为 C(t),新设备的役龄为 t=0。 旧设备出售的价格是设备役龄的函数,记为 S(t)。
在 n年末,役龄为 t的设备残值为 R(t)。
现有一台役龄为 T的设备,在使用过程中,
使用者每年都面临,继续使用,或,更新,的策略,
设 备 更 新 问 题
130
阶段 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(
131
递推方程,
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 )
设 备 更 新 问 题
132
例 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
设 备 更 新 问 题
133
对于 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(
134
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(
135
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,
136
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(
137
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(
138
对于 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(
139
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(
140
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,
141
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
142
由以上计算可知，本问题有两个决策，它们对应的最小费用都是 115。
年份 1 2 3 4 5
决策 1 更新 更新 继续 更新 继续决策 2 更新 继续 更新 更新 继续这两个决策是设 备 更 新 问 题
2
第五章 动态规划多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容重点
3
一,多阶段决策问题
(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.多阶段决策过程的最优化
4
1.多阶段决策过程的最优化动态规划方法与,时间,关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是,动态,的意思 。 然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入,时段,因素,就可以将其转化为一个多阶段决策问题 。 在本章中将介绍这种处理方法 。
5
1.多阶段决策过程的最优化二,多阶段决策问题举例属于多阶段决策类的问题很多,
例如：
1)工厂生产过程,由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排 。
6
1.多阶段决策过程的最优化
2)设备更新问题,一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,
维修费用增加,可正常使用的工时减少,
加工质量下降,经济效益差,并且,使用的年限越长,处理价值也越低,自然,如果卖去旧的买新的,还需要付出更新费,因此就需要综合权衡决定设备的使用年限,使总的经济效益最好 。
7
1.多阶段决策过程的最优化
3)连续生产过程的控制问题,
一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此,应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大 。
8
1.多阶段决策过程的最优化以上所举问题的发展过程都与时间因素有关,因此在这类多阶段决策问题中,阶段的划分常取时间区段来表示,
并且各个阶段上的决策往往也与时间因素有关,这就使它具有了,动态,的含义,所以把处理这类动态问题的方法称为动态规划方法 。 不过,实际中尚有许多不包含时间因素的一类,静态,决策问题,就其本质而言是一次决策问题,
是非动态决策问题,但是也可以人为地引入阶段的概念当作多阶段决策问题,
应用动态规划方法加以解决 。
9
1.多阶段决策过程的最优化
4） 资源分配问题,便属于这类静态问题 。 如：某工业部门或公司,拟对其所属企业进行稀缺资源分配,为此需要制定出收益最大的资源分配方案 。 这种问题原本要求一次确定出对各企业的资源分配量,它与时间因素无关,不属动态决策,但是,我们可以人为地规定一个资源分配的阶段和顺序,从而使其变成一个多阶段决策问题 (后面我们将详细讨论这个问题 )。
10
1.多阶段决策过程的最优化
5） 运输网络问题,如图 5-1所示的运输网络,点间连线上的数字表示两地距离 (也可是运费,时间等 ),要求从
fk(sk)至 v10的最短路线 。
这种运输网络问题也是静态决策问题 。 但是,按照网络中点的分布,可以把它分为 4个阶段,而作为多阶段决策问题来研究 。
11
1.多阶段决策过程的最优化图 5-11 运输网络图示
12
1.多阶段决策过程的最优化三,动态规划求解的多阶段决策问题的特点通常多阶段决策过程的发展是通过状态的一系列变换来实现的 。 一般情况下,系统在某个阶段的状态转移除与本阶段的状态和决策有关外,
还可能与系统过去经历的状态和决策有关 。 因此,
问题的求解就比较困难复杂 。 而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,
即 具有,无后效性,的多阶段决策过程 。 所谓无后效性,又称马尔柯夫性,是指系统从某个阶段往后的发展,仅由本阶段所处的状态及其往后的决策所决定,与系统以前经历的状态和决策 (历史 )
无关 。
13
1.多阶段决策过程的最优化四,动态规划方法导引例 5.1,为了说明动态规划的基本思想方法和特点,下面以图 5-1所示为例讨论的求最短路问题的方法 。
第一种方法称做全枚举法或穷举法 。 它的基本思想是列举出所有可能发生的方案和结果,
再对它们一一进行比较,求出最优方案 。 这里从
v1到 v10的路程可以分为 4个阶段 。 第一段的走法有三种,第二三两段的走法各有两种,第四段的走法仅一种,因此共有 3× 2× 2× 1＝ 12条可能的路线,分别算出各条路线的距离,最后进行比较,
可知最优路线是 v1 → v3 → v7 → v9 → v10,最短距离是 18．
14
1.多阶段决策过程的最优化显然,当组成交通网络的节点很多时,用穷举法求最优路线的计算工作量将会十分庞大,而且其中包含着许多重复计算,
第二种方法即所谓,局部最优路径,
法,是说某人从 k出发,他并不顾及全线是否最短,只是选择当前最短途径,
,逢近便走,,错误地以为局部最优会致整体最优,在这种想法指导下,所取决策必是 v1 → v3 → v5 → v8 → v10,全程长度是 20；显然,这种方法的结果常是错误的,
15
1.多阶段决策过程的最优化第三种方法是动态规划方法 。 动态规划方法寻求该最短路问题的基本思想是,首先将问题划分为 4个阶段,每次的选择总是综合后继过程的一并最优进行考虑,在各段所有可能状态的最优后继过程都已求得的情况下,全程的最优路线便也随之得到 。
为了找出所有可能状态的最优后继过程,动态规划方法总是从过程的最后阶段开始考虑,然后逆着实际过程发展的顺序,逐段向前递推计算直至始点 。
16
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 。
17
1.多阶段决策过程的最优化同样,当阶段 3上所有可能状态的最优后继过程都已求得后,便可以开始考虑阶段 2上所有可能状态的最优决策和最优后继过程,如 v2的最优决策是到 v5,最优路线是 v2→ v5→ v9→ v10,最短距离是 15…依此类推,最后可以得到从初始状态 v1的最优决策是到 v3最优路线是 v1→ v3→ v7→ v9→ v10,
全程的最短距离是 18。 图 5—1中粗实线表示各点到的最优路线,每点上方括号内的数字表示该点到终点的最短路距离 。
18
1.多阶段决策过程的最优化综上所述可见,全枚举法虽可找出最优方案,但不是个好算法,局部最优法则完全是个错误方法,只有 动态规划方法属较科学有效的算法 。 它的基本思想是,把一个比较复杂的问题分解为一系列同类型的更易求解的子问题,便于应用计算机 。 整个求解过程分为两个阶段,先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值,然后再顺序地求出整个问题的最优策略和最优路线 。 计算过程中,系统地删去了所有中间非最优的方案组合,从而使计算工作量比穷举法大为减少 。
19
2.动态规划的基本概念一,动态规划的基本概念使用动态规划方法解决多阶段决策问题,首先要将实际问题写成动态规划模型,同时也为了今后叙述和讨论方便,这里需要对动态规划的下述一些基本术语进一步加以说明和定义：
20
2.动态规划的基本概念
(一 ) 阶段和阶段变量为了便于求解和表示决策及过程的发展顺序,而把所给问题恰当地划分为若干个相互联系又有区别的子问题,称之为多段决策问题的阶段 。
一个阶段,就是需要作出一个决策的子问题,通常,阶段是按决策进行的时间或空间上先后顺序划分的 。 用以描述阶段的变量叫作阶段变量,一般以 k表示阶段变量,阶段数等于多段决策过程从开始到结束所需作出决策的数目,图 5—1所示的最短路问题就是一个四阶段决策过程 。
21
2.动态规划的基本概念
（ 二 ） 状态,状态变量和可能状态集
1.状态与状态变量 。 用以描述事物
(或系统 )在某特定的时间与空间域中所处位置及运动特征的量,称为状态 。 反映状态变化的量叫做状态变量 。 状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息 。 按照过程进行的先后,每个阶段的状态可分为初始状态和终止状态,
或称输入状态和输出状态,阶段 k的初始状态记作 sk,终止状态记为 sk+1。 但为了清楚起见,通常定义阶段的状态即指其初始状态 。
22
2.动态规划的基本概念
2,可能状态集一般状态变量的取值有一定的范围或允许集合,称为可能状态集,或可达状态集 。 可能状态集实际上是关于状态的约束条件 。 通常可能状态集用相应阶段状态 sk的大写字母 Sk表示,sk∈ Sk，
可能状态集可以是一离散取值的集合,也可以为一连续的取值区间,视具体问题而定,在图 5—1
所示的最短路问题中,第一阶段状态为 v1,状态变量 s1的状态集合 S1={v1}；第二阶段则有三个状态,v2,v3,v4,状态变量 s2 的 状 态 集 合
S2={v2,v3,v4} ； 第 三 阶 段 也 有 三 个 状态,v5,v6,v7,状 态 变 量 s3 的 状 态 集 合
S3={v5,v6,v7} ；第四阶 段则有 二个状态,
v8,v9,状态变量 s4的状态集合 S4={v8,v9} ；
23
（ 三 ） 决策,决策变量和允许决策集合所谓 决策,就是确定系统过程发展的方案 。
决策的实质是关于状态的选择,是决策者从给定阶段状态出发对下一阶段状态作出的选择 。
用以描述决策变化的量称之决策变量和状态变量一样,决策变量可以用一个数,一组数或一向量来描述,也可以是状态变量的函数,记以
uk= uk(sk),表示于阶段 k状态 sk时的决策变量 。
决策变量的取值往往也有一定的允许范围,
称之允许决策集合 。 决策变量 uk(sk)的允许决策集用 Uk(sk)表示,uk(sk)∈ Uk(sk)允许决策集合实际是决策的约束条件 。
2.动态规划的基本概念
24
（ 四 ）,策略和允许策略集合策略 (Policy)也叫决策序列,策略有全过程策略和 k部子策略之分,全过程策略是指具有 n个阶段的全部过程,由依次进行的 n个阶段决策构成 的 决 策 序 列,简 称 策 略,表 示 为
p1,n{u1,u2,…,un}。 从 k阶段到第 n阶段,依次进行的阶段决策构成的决策序列称为 k部子策略,表示为 pk,n{uk,uk+1,…,un},显然当 k=1时的 k部子策略就是全过程策略 。
在实际问题中,由于在各个阶段可供选择的决策有许多个,因此,它们的不同组合就构成了许多可供选择的决策序列 (策略 ),由它们组成的集合,
称之允许策略集合,记作 P1,n,从允许策略集中,
找出具有最优效果的策略称为最优策略 。
2.动态规划的基本概念
25
（ 五 ） 状态转移方程系统在阶段 k处于状态 sk,执行决策 uk(sk)
的结果是系统状态的转移,即系统由阶段 k的初始状态 sk转移到终止状态 sk+1,或者说,系统由
k阶段的状态 sk转移到了阶段 k+1的状态 sk+1,多阶段决策过程的发展就是用阶段状态的相继演变来描述的 。
对于具有无后效性的多阶段决策过程,系统由阶段 k到阶段 k+1的状态转移完全由阶段 k的状态 sk和决策 uk(sk)所确定,与系统过去的状态
s1,s2,…,sk-1及其决策 u1(s1),u2(s2)…uk-1(sk-1)
无关 。 系统状态的这种转移,用数学公式描述即有：
2.动态规划的基本概念
))(,(1 kkkkk susTs (5-1)
26
通常称式 (5-1)为多阶段决策过程的状态转移方程 。 有些问题的状态转移方程不一定存在数学表达式,但是它们的状态转移,还是有一定规律可循的 。
(六 ) 指标函数用来衡量策略或子策略或决策的效果的某种 数量指标,就称为指标函数 。 它是定义在全过程或各子过程或各阶段上的确定数量函数 。
对不同问题,指标函数可以是诸如费用,成本,
产值,利润,产量,耗量,距离,时间,效用,
等等 。 例如：图 5—1的指标就是运费 。
2.动态规划的基本概念
27
(1)阶段指标函数 （ 也称阶段效应 ） 。 用
gk(sk,uk)表示第 k段处于 sk状态且所作决策为
uk(sk)时的指标,则它就是第 k段指标函数,简记为 gk 。 图 5-1的 gk值就是从状态 sk到状态 sk+1的距离 。 譬如,gk(v2,v5)=3,即 v2到 v5的距离为 3。
(2)过程指标函数 （ 也称目标函数 ） 。 用
Rk(sk,uk)表示第 k子过程的指标函数 。 如图 5-1的
Rk(sk,uk)表示处于第 k段 sk状态且所作决策为 uk时,
从 sk点到终点 v10的距离 。 由此可见,Rk(sk,uk)不仅跟当前状态 sk有关,还跟该子过程策略 pk(sk)
有关,因此它是 sk和 pk(sk)的函数,严格说来,
应表示为,
2.动态规划的基本概念
))(,( kkkk spsR
28
不过实际应用中往往表示为 Rk(sk,uk)或
Rk(sk)。 还跟第 k子过程上各段指标函数有关,
过程指标函数 Rk(sk)通常是描述所实现的全过程或 k后部子过程效果优劣的数量指标,它是由各阶段的阶段指标函数 gk(sk,uk)累积形成的,
适于用动态规划求解的问题的过程指标函数
（ 即目标函数 ）,必须具有关于阶段指标的可分离形式,对于部子过程的指标函数可以表示为：
式中,?表示某种运算,可以是加,减,乘,
除,开方等 。
2.动态规划的基本概念
),(),(),(
),,,,,,(
111
11,,
nnnkkkkkk
nnkkkknknk
usgusgusg
usususRR
(5-2)
29
多阶段决策问题中,常见的目标函数形式之一是取各阶段效应之和的形式,即,
(5-3)
有些问题,如系统可靠性问题,其目标函数是取各阶段效应的连乘积形式,如：
(5-4)
总之,具体问题的目标函数表达形式需要视具体问题而定 。
2.动态规划的基本概念
n
ki
iiik usgR ),(
n
ki
iiik usgR ),(
30
(七 ) 最优解用 fk(sk)表示第 k子过程指标函数在状态 sk下的最优值,即称 fk(sk)为第 k子过程上的最优指标函数 ；与它相应的子策略称为 sk状态下的最优子策略,记为 pk*(sk) ；而构成该子策赂的各段决策称为该过程上的最优决策,记为 ；
有简记为
2.动态规划的基本概念
))(,( kkkk spsR
nkspsRoptsf kkkk
sPpkk kKk
,,2,1) ) },(,({)(
)(
)(,),(),( 11 nnkkkk sususu
nksusususp nnkkkkkk,,2,1) },(,),(),({)( 11
nkuuup nkkk,,2,1},,,,{ 1
31
特别当 k=1且 s1取值唯一时,f1(s1)就是问题的最优值，而 p1*就是最优策略。如例只有唯一始点 v1
即 s1取值唯一,故 f1(s1)=18就是例的最优值，而就是例的最优策略。
但若取值不唯一,则问题的最优值记为 f0有最优策略即为 s1=s1*状态下的最优策略：
我们把最优策略和最优值统称为问题的最优解 。
2.动态规划的基本概念
},,,{ 109731 vvvvp
)()}({ 111110
11
ssfsfo p tf
Ss
},,),({)( 211111 nuusussp?
32
按上述定义，所谓最优决策是指它们在全过程上整体最优 (即所构成的全过程策略为最优 )，而不一定在各阶段上单独最优。
(八 ) 多阶段决策问题的数学模型综上所述,适于应用动态规划方法求解的一类多阶段决策问题,亦即具有无后效性的多阶段决策问题的数学模型呈以下形式,
2.动态规划的基本概念
),,2,1( nku k
nk
Uu
Ss
usTs
ts
usususRRoptf
kk
kk
kkkk
nn
uu
n
,,2,1
),(
..
),,,,,,(
1
2211
~
1
（ 5-5）
33
式中,OPT”表示最优化,视具体问题取 max或 min。
上述数学模型说明了对于给定的多阶段决策过程,求取一个 (或多个 )最优策略或最优决策序列,使之既满足式 (5-5)给出的全部约束条件,又使式 (5-5)所示的目标函数取得极值,并且同时指出执行该最优策略时,过程状态演变序列即最优路线
2.动态规划的基本概念
},,,{ 21 nuuu?
},,,,{ 121 nn ssss?
34
二,动态规划的最优化原理与基本方程
1,标号法为进一步阐明动态规划方法的基本思路,
我们介绍一种只适用于例这类最优路线问题的特殊解法 ——标号法 。 标号法是借助网络图通过分段标号来求出最优路线的一种简便,直观的方法 。 通常标号法采取,逆序求解,的方法来寻找问题的最优解,即从最后阶段开始,逐次向阶段数小的方向推算,最终求得全局最优解 。
2.动态规划的基本原理
35
下面给出标号法的一般步骤：
1.从最后一段标起,该段各状态 (即各始点 )到终点的距离用数字分别标在各点上方的方格内,并用粗箭线连接各点和终点 。
2.向前递推,给前一阶段的各个状态标号 。 每个状态上方方格内的数字表示该状态到终点的最短距离 。 即为该状态到该阶段已标号的各终点的段长,再分别加上对应终点上方的数字而取其最小者 。 将刚标号的点沿着最短距离所对应的已标号的点用粗箭线连接起来,表示出各刚标号的点到终点的最短路线 。
2.动态规划的基本原理
36
3.逐次向前递推,直到将第一阶段的状态 (即起点 )也标号,起点方格内的数字就是起点到终点的最短距离,从起点开始连接终点的粗箭线就是最短路线 。
用标号法来求解下例例 5.2,网络图 5— 2表示某城市的局部道路分布图 。 一货运汽车从 S出发,最终到达目的地 E。 其中 Ai(i＝ 1,2,3),Bj(j＝ 1,2)和 Ck(k＝ 1,2)是可供汽车选择的途经站点,各点连线上的数字表示两个站点问的距离 。 问此汽车应走哪条路线,使所经过的路程距离最短?
2.动态规划的基本原理
37
2.动态规划的基本原理图 5-2 某城市的局部道路分布图
38
第一步：先考虑第四阶段,即 k=4,该阶段共有两个状态,C1,C2,设 f4(C1)和 f4(C2)分别表示 C1、
C2到 E的最短距离,显然有 f4(C1)=5和 f4(C2)=8,边界条件 f5(E)=0 。
第二步：即 k=3,该阶段共有两个状态,B1,B2
(1) 从 B1出发有两种决策,B1→ C1,B1→ C2 。
记 d3(B1,C1)表示 B1到 C1的距离,即,这里的每一种决策的阶段指标函数就是距离,所以,B1→ C1的阶段指标函数为 d3(B1,C1)＝ 6,B1→ C2的阶段指标函数为 d3(B1,C2)＝ 5。 因此有,
f3(B1)＝ min{d3(B1,C1)+f4(C1),d3(B1,C2)+f4(C2)}＝
min(6＋ 5,5＋ 8)＝ 11。 那么,从出发到 E的最短路线是 B1→ C1→ E,对应的决策 u3(B1) = C1 。
2.动态规划的基本原理
39
(2)从 B2出发也有两种决策,B2→ C1,B2→ C2同理,
有 f3(B2)=min{d3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)} ＝
min(9+5,8+87)＝ 14,那么,从 B2出发到 E的最短路线是 B2→ C1→ E,且 u3(B2)=C1 。
第三步：即 k＝ 2,该阶段共有三个状态,Al,A2,A3
(1)从 Al出发有两种决策,A1→ B1,A1→ B2。 则
f2(A1)=min{d2(A1,B1)+f3(B1),d2(A1,B2)+f3(B2)}＝ min{6
＋ 11,5 ＋ 14} ＝ 17,即 A1 到 E 的 最 短 路 线 为
A1→ B1→ C1→ E,且 u3(A1)＝ B1 。
(2)从 A2出发也有两种决策,A2→ B1,A2→ B2。 此时,
f2(A2) ＝ min{d2(A2,B1)+f3(B1),d2(A2,B2)+f3(B2)} ＝
min{8+11,6+14} ＝ 19,即 A2 到 E 的 最 短 路 线 为
A2→ B1→ C1→ E,且 u3(A2)＝ B1。
2.动态规划的基本原理
40
(3)从 A3出发也有两种决策,A3→ B1,A3→ B2 此时
f2(A2)=min{d2(A3,B1)+f3(B1),d2(A3,B2)+f3(B2)} ＝
min{7+11,4+14} ＝ 18,即 A3 到 E 的 最 短 路 线 为
A3→ B1→ C1→ E,对应的 u2(A3)＝ B2 。
第四步：即 k＝ 1,该阶段只有一个状态 S,从 S出发有三种决策,S→ A1,S→ A2,S→ A3,那么,
f1(S)=min{d1(S,A1)+f2(A1),d2(S,B2)+f3(B2)} ＝
min{8+11,6+14} ＝ 19,即 A2 到 E 的 最 短 路 线 为
A2→ B1→ C1→ E,且 u3(A2)＝ B1 。
那么,从 S到 E共有三条最短路线：
此时,u1(S)＝ A1题 和此时,u1(S)＝ A3,最短距离为 21。
2.动态规划的基本原理
ECBAS 111
ECBAS 113 ECBAS 123
41
结果如图 5-3所示 。
每个状态上方的方格内的数字表示该状态到 E的最短距离,首尾相连的粗箭线构成每一状态到 E的最短路线 。 因此,
标号法不但给出起点到终点的最短路线和最短距离,同时也给出每一状态到终点的最短路线及其最短距离 。 如,A1到 E
的最短路线是,最短矩离是
17
图见下页
2.动态规划的基本原理
ECBA 111
42
2.动态规划的基本原理图 5-3某城市局部道路求最短路径的过程
43
2,最优化原理 （ 贝尔曼最优化原理 ）
作为一个全过程的最优策略具有这样的性质,对于最优策略过程中的任意状态而言,无论其过去的状态和决策如何,余下的诸决策必构成一个最优子策略 。 该原理的具体解释是,若某一全过程最优策略为：
2.动态规划的基本原理
)}(),(,),(),({)( 221111 nnkk sususususp
则对上述策略中所隐含的任一状态而言,
第 k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略 p1*中,即为
)}(,),(),({)( 11 nnkkkkkk susususp
44
如第一节所述,基于上述原理,提出了一种逆序递推法；这里可以指出,该法的关键在于给出一种递推关系 。 一般把这种递推关系称为动态规划的函数基本方程 。
3.函数基本方程在例中,用标号法求解最短路线的计算公式可以概括写成：
(5-6)
其中,在这里表示从状态 sk到由决策 u
k(sk)所决定的状态 sk+1之间的距离,是边界条件,表示全过程到第四阶段终点结束 。
2.动态规划的基本原理
1,2,3,4) ) },(())(,({m i n)(
0)(
111)(
55
ksufsusgsf
sf
kkkkkkksUukk
kkk
))(,( kkkk susg
0)( 55?sf
45
一般地,对于 n个阶段的决策过程,假设只考虑指标函数是,和,与,积,的形式,第 k阶段和第 k+1阶段间的递推公式可表示如下：
(1)当过程指标函数为下列,和,的形式时,
相应的函数基本方程为
（ 5—7）
2.动态规划的基本原理
))}(,({)(
)( kkkksPpkk
spsRo p tsf
kKk?
n
ki
iii usg ),(
1,2,,1,) ) },(())(,({)(
0)(
111
11
nnksufsusgoptsf
sf
kkkkkkk
Uu
kk
nn
kk
46
(2) 当过程指标函数为下列,积,的形式时,
相应的函数基本方程为
（ 5—8）
可以看出,和,积函数的基本方程中边界条件 (即 的取值 )是不同的 。
2.动态规划的基本原理
))}(,({)(
)( kkkksPpkk
spsRo p tsf
kKk?
n
ki
iii usg ),(
1,2,,1,) ) },(())(,({)(
1)(
111
11
nnksufsusgoptsf
sf
kkkkkkk
Uu
kk
nn
kk
)( 11 nn sf
47
3.动态规划方法的基本步骤标号法仅适用于求解象最短路线问题那样可以用网络图表示的多阶段决策问题 。 但不少多阶段决策问题不能用网络图表示 。 此时,应该用函数基本方程来递推求解,一般来说,要用函数基本方程逆推求解,首先要有效地建立动态规划模型,然后再递推求解,最后得出结论,
然而,要把一个实际问题用动态规划方法来求解,还必须首先根据问题的要求 。 把它构造成动态规划模型,这是非常重要的一步 。 正确地建立一个动态规划模型,往往问题也就解决了一大半,而一个正确的动态规划模型,应该满足哪些条件呢?
48
3.动态规划方法的基本步骤
1,应将实际问题恰当地分割成 n个子问题 (n个阶段 )。 通常是根据时间或空间而划分的,或者在经由静态的数学规划模型转换为动态规划模型时,常取静态规划中变量的个数 n,即 k=n。
2,正确地定义状态变量 sk,使它既能正确地描述过程的状态,又能满足无后效性,动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的,动态规划中的状态变量必须具备以下三个特征：
49
3.动态规划方法的基本步骤
(1)要能够正确地描述受控过程的变化特征 。
(2)要满足无后效性 。 即如果在某个阶段状态已经给定,那么在该阶段以后,过程的发展不受前面各段状态的影响,如果所选的变量不具备无后效性,就不能作为状态变量来构造动态规划的模型 。
(3)要满足可知性 。 即所规定的各段状态变量的值,可以直接或间接地测算得到 。 一般在动态规划模型中,状态变量大都选取那种可以进行累计的量 。 此外,在与静态规划模型的对应关系上,
通常根据经验,线性与非线性规划中约束条件的个数,相当于动态规划中状态变量 sk的维数,而前者约束条件所表示的内容,常就是状态变量 sk
所代表的内容 。
50
3.动态规划方法的基本步骤
3,正确地定义决策变量及各阶段的允许决策集合 Uk(sk),根据经验,一般将问题中待求的量,选作动态规划模型中的决策变量 。 或者在把静态规划模型 (如线性与非线性规划 )转换为动态规划模型时,常取前者的变量 xj为后者的决策变量 uk。
4,能够 正确地写出状态转移方程,至少要能正确反映状态转移规律 。 如果给定第 k阶段状态变量 sk的值,则该段的决策变量 uk一经确定,第 k+1段的状态变量 sk+1的值也就完全确定,即有 sk+1=Tk(sk,uk)
51
3.动态规划方法的基本步骤
5,根据题意,正确地构造出目标与变量的函数关系 ——目标函数,目标函数应满足下列性质：
(1)可分性,即对于所有 k后部子过程,其目标函数仅取决于状态 sk及其以后的决策
uk,uk+1,┈,un,就是说它是定义在全过程和所有后部子过程上的数量函数 。
(2)要满足递推关系,即
(3)函数 对其变元 Rk+1来说要严格单调 。
)],,(,,[),,,,,( 111111, nkkkkknkkkknk ssRussususR
)],,(,,[ 111 nkkkkk ssRus
52
6,写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式其中 表示第 i阶段的指标,它显然是满足上述三个性质的 。 所以上式可以写成,
3.动态规划方法的基本步骤
n
ki
iiikk usgsR ),()(
),( iii usg
),,(),( 111 nkkkkkk ssRusgR
53
二,动态规划方法的基本步骤为进一步说明动态规划模型建立的基本方法及其求解过程,下面通过实际例子用上述方法具体给出求解动态规划方法的基本步骤：
例 5.3:有某种机床,可以在高低两种不同的负荷下进行生产,在高负荷下生产时,产品的年产量为 g,与年初投入生产的机床数量 u1的关系为 g=g(u1)=8u1,这时,年终机床完好台数将为
au1,(a为机床完好率,0<a<1,设 a=0.7).在低负荷下生产时,产品的年产量为 h,和投入生产的机床数量 u2的关系为 h=h(u2)=5u2,相应的机床完好率为 b(0<b<1,设 b=0,9),一般情况下 a<b。
3.动态规划方法的基本步骤
54
假设某厂开始有 x=1000台完好的机床,现要制定一个五年生产计划,问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量,
以使在 5年内产品的总产量为最高 。
解,首先构造这个问题的动态规划模型 。
1,变量设置
(1)设阶段变量 k表示年度,因此,阶段总数
n=5。
(2)状态变量 sk表示第 k年度初拥有的完好机床台数,同时也是第 k-1年度末时的完好机床数量 。
3.动态规划方法的基本步骤
55
(3)决策变量 uk,表示第 k年度中分配于高负荷下生产的机床台数 。 于是 sk- uk便为该年度中分配于低负荷下生产的机床台数,
这里 sk与 uk均取连续变量,当它们有非整数数值时,可以这样理解：如 sk＝ 0.6,就表示一台机器在 k年度中正常工作时间只占 6/10； uk=0.4时,
就表示一台机床在 k年度只有 4/10的时间于高负荷下工作,
2,状态转移方程为
k=1,2,…,6
3.动态规划方法的基本步骤
)(9.07.0)(1 kkkkkkk usuusbaus
56
3,允许决策集合,在第 k段为
4,目标函数 。 设 gk(sk,uk)为第 k年度的产量,则 gk(sk,uk)=8uk+5(sk-uk),因此,目标函数为 k＝ 1,2,．．．,5
5,条件最优目标函数递推方程 。
令 fk(sk)表示由第 k年的状态 sk出发,采取最优分配方案到第 5年度结束这段时间的产品产量,根据最优化原理有以下递推关系：
k=1,2,3,4,5
3.动态规划方法的基本步骤
}0{)( kkkkk xuusU
5 ),(
ki
kkkk usgR
)(m a x)( kUukk xsf
kk?
)]}(9.07.0[)](58{[ 1 kkkkkkk usufusu
57
6.边界条件为下面采用逆序递推计算法,从第 5年度开始递推计算。
k=5时有显然,当 u5*=s5时,f5(s5)有最大值,相应的有
f5(s5)=8s5
k=4时有
3.动态规划方法的基本步骤
0)( 1515 sf
,
5055
m a x)( su
k
sf )}()](58{[ 6555 ksfusu
50
m a xsu
k
)](58{[ 555 usu
)( 44 sf )]}(9.07.0[)](58{[m a x 4445444
0 44 usufususu
)]}(9.07.0[8)](58{[m a x 4444440
44
usuususu
)}(2.126.13{m a x 4440
44
ususu
=
=
因此,当 u4*=s4时,有最大值 f4(s4)=13.6s4
58
k=3 时有可见,当 u3*=s3 时,f3(s3) 有 最 大 值 f3(s3)
=17.55s3.
k=2 时有
= +
=
此时,当取 u2*=0时有最大值,即 f2(s2)=20.8s2,其中 s2=0.7u1+0.9(s1-u1)
3.动态规划方法的基本步骤
=?)(
33 sf )}()](58{[m a x 443330 33 sfususu )}(22.1755.17{m a x 3330 33 ususu
)}()](58{[m a x 332220
22
sfususu
)](58{[m a x 2220
22
ususu )]}(9.07.0[55.17 222 usu
)](8.2025.20{[m a x 2220
22
ususu
)( 22 sf
59
k=1时有
+
=
当取 u1*=0 时,f1(s1) 有 最 大 值,即
f1(s1)=23.7s1,因为 s1=1000,故
f1(s1)=23700个产品,
按照上述计算顺序寻踪得到下述计算结果：
3.动态规划方法的基本步骤
)( 11 sf )(58{m a x 1110
11
ususu )]}(9.07.0[8.20 111 usu
)}(7.2355.22{m a x 1110
11
ususu
01u 10001?s 5000),( 111?usg 23700)( 11?sf
02u 9002?s 4 5 0 0),( 222?usg 1 8 7 2 08.20)( 222 ssf
60
上面所讨论的最优决策过程是所谓始端状态 s
1固定,终端状态 s6自由,如果终端也附加上一定的约束条件,那么计算结果将会与之有所差别,例如,若规定在第五个年度结束时,完好的机床数量为 500台 (上面只有 278
台 ),问应该如何安排五年的生产,使之在满足这一终端要求的情况下产量最高？
3.动态规划方法的基本步骤
33 su 8103?s 6480),( 333?usg 1 4 2 1 655.17)( 333 ssf
44 su 5674?s 4 5 3 6),( 444?usg 77116.13)( 444 ssf
55 su 3975?s 3176),( 555?usg 3 1 7 66.13)( 555 ssf
2 7 87.0)(9.07.0 55556 xusus
61
解：由状态转移方程有得显而易见,由于固定了终端的状态 s6,第五年的决策变量 U5的允许决策集合 U5(s5)也有了约束,上式说明 U5(s5)已退化为一个点,即第五年投入高负荷下生产的机床数只能由式 U5=4.5s5-2500作出一种决策,故
3.动态规划方法的基本步骤
＝ 500
)(9.07.0)(1 kkkkkkk usuusbaus
)(9.07.0 5556 usus
2 5 0 05.4 55 su
62
当 k=5时有当 k=4时有显然，只有取 u4*=0,f4(s4)有最大值，即
f4(s4)=21.7s4-7500。同理类推
3.动态规划方法的基本步骤
=
5055
m a x)( su
k
sf )}(58{ 555 usu )2 5 0 05.4(5)2 5 0 05.4(8 555 usu
7 5 0 05.18 5 s
=
)( 44 sf )}()](58{[m a x 554440
44
sfususu
}75005.18)(58{m a x 54440
44
uususu
}7500)](9.07.0[5.18)(58{m a x 4444440
44
usuususu
}7 5 0 075.07.21{m a x 440
44
ussu
=
=
63
k=3时有可知,当 u3*=0时,f3(s3)有最大值 f4(s4)=24.5s3-
7500.
k=2时有此时,当 u2*=0时有最大值,即
f2(s2)=27.1s2-7500
3.动态规划方法的基本步骤
=
)( 33 sf )}()](58{[m a x 44333
0 33 sfususu
}7500)](9.07.0[7.21)](58{[m a x 3333330
33
usuususu
}7 5 0 05.243.1{m a x 330
33
susu=
)( 22 sf )}()](58{[m a x 332220
22
sfususu
)](58{[m a x 2220
22
ususu }7 5 0 0)](9.07.0[5.24 222 usu
}7 5 0 01.279.1{m a x 220
22
susu=
= +
64
k=1时有只有取 u1*=0时,f1(s1)有最大值,即
f1(s1)=29.4s1-7500 。
由此可见,为了使下一个五年计划开始的一年有完好的机床 500台,其最优策略应该为：在前 4年中,都应该把全部机床投人低负荷下生产,在第 5年,
只能把部分完好机投入高负荷下生产 。 根据最优策赂,从始端向终端递推计算出各年的状态,即算出每年年初的完好机床台数,因为 s
1＝ 1000台,于是有
3.动态规划方法的基本步骤
=
)( 11 sf )}()(58{m a x 221110
11
sfususu
}7500)](9.07.0[1.27)(58{m a x 1111110
11
usuususu
}7 5 0 04.294.2{m a x 110
11
susu=
65
因此,u5*=4.5s5-2500=425(台 ),这就是说第 5年里还有 204台投入低负荷下生产,否则不能保证
s6=0.7u5+0.9(u5-s5)=500(台 )。
在上述最优决策下,5年里所得最高产量为：
f1(s1)＝ 29.4s1-7500=29400-7500＝ 21900(个 )。
可见,附加了终端约束条件以后,其最高产量 f1(s1)
比终端自由时要低一些 。
3.动态规划方法的基本步骤
（台）
（台）
（台）
（台）
（台）
01u 10001?s
02u 9 0 09.0)(9.07.0 1*11*12 susus
03u 8 1 09.0)(9.07.0 2*22*23 susus
04u 7 2 99.0)(9.07.0 3*33*34 susus
6 5 69.0)(9.07.0 4*44*45 susus
2 7 87.0)(9.07.0 55556 xusus （台）
66
例 5.4：一个线路网络图，从 A到 E
要修建一条石油管道，必须 在 B,C、
D处设立加压站。各边上的数为长度，
现需要找一条路使总长度最短。
B3
B2
B1
C3
C2
C1
D3
D2
D1
EA
4
5
6
3
4
3
4
5
4
7
4
2
6
5
7
10
9
7
8
6
3.动态规划方法的基本步骤
67
解,可分成 4个阶段：
A到 B,B到 C,C到 D,D到 E；
每个阶段 k 的起点称为状态 Sk ；
从 k 阶段的起点出发可以做一选择，即决定到下一阶段的哪个节点,称为决策 Xk ； 可见,Sk+1 是由
Sk 和 Xk 所决定的。
3.动态规划方法的基本步骤
68
那么，从 A出发经过 4个阶段,A
到 B,B到 C,C到 D,D到 E，逐次作出决策，构成从 A到 E 的一条路线，记为 u 。
即
u = S1 X1 S2 X2 S3 X3 S4 X4 S5
其中 S1 = A,S5 = E
记 d 为两个相邻节点之间的长度，
如 d（ A,B 3） = 3 。
3.动态规划方法的基本步骤
69
① 记 fk(Sk)为从 Sk到 E的最短长度,称为从 Sk到 E的距离。
那么,f1(A)是从 A到 E的最短距离，即最优策略的值。
3.动态规划方法的基本步骤
70
② 最短路问题的特点：如果从 A
到 E的最优策略经过某节点，那么这个策略的从该节点到 E的一段，必定是该节点到 E的所有线路中 Sk最短的一条，即这一段的长度为 fk（ Sk）。
（ 1）逆序法,从 E到 A。
（ 2）顺序法,对节点 Sk，从 A到
Sk 所有线路中，最短的一条的长度记为 φ k（ S k），例如 φ 1（ A） = 0，
称为问题的边界条件 。
3.动态规划方法的基本步骤
71
动态规划模型建立后,对基本方程分段求解,不像线性规划或非线性规划那样有固定的解法,必须根据具体问题的特点,结合数学技巧灵活求解,如动态规划模型中的状态变量与决策变量若被限定只能取离散值,则可采用离散变量的分段穷举法 。 当动态规划模型中状态变量与决策变量为连续变量,就要根据方程的具体情况灵活选取连续变量的求解方法 。 如经典解析方法,线性规划方法,非线性规划法或其它数值计算方法等 。 还有连续变量的离散化解法和高维问题的降维法及疏密格子点法等等 。
3.动态规划方法的基本步骤
72
学习方法建议：
第一步 先看问题，充分理解问题的条件、情况及求解目标。
第二步 结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的
“四大要素、一个方程” —— 这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。
4.动态规划方法应用举例
73
第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。
第四步 把自己的求解放到一边，
看书中的求解方法，要充分理解教材中的论述。
第五步 对照自己的求解，分析成败。
4.动态规划方法应用举例
76
求 最 短 路 径
77
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
78
将问题分成五个阶段，第 k阶段到达的具体地点用状态变量 xk表示，例如,x2=B3表示第二阶段到达位置 B3，
等等。这里状态变量取字符值而不是数值。
将决策定义为到达下一站所选择的路径,例如目前的状态是 x2=B3,这时决策允许集合包含三个决策,它们是
D2(x2)=D2(B3)={B3?C1,B3?C2,B3?C3}
求 最 短 路 径
79
最优指标函数 fk(xk)表示从目前状态到 E的最短路径。终端条件为
f5(x5)=f5(E)=0
其含义是从 E到 E的最短路径为 0。
第四阶段的递推方程为,f x v x d f x
d D x4 4 4 4 4 5 54 4 4
( ) m i n { (,) ( )}
( )
从 f 5 (x 5 ) 到 f 4 (x 4 ) 的递推过程用下表表示,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
求 最 短 路 径
80
其中 *表示最优值，在上表中，由于决策允许集合 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
求 最 短 路 径
81
第三阶段的递推方程为：
从 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
求 最 短 路 径
82
由此得到 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 ) 的递推过程用表格表示如下,
求 最 短 路 径
83
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
求 最 短 路 径
84
由此得到 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
求 最 短 路 径
85
第一阶段的递推方程为：
)}(),({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
求 最 短 路 径
86
由此得到 f1(x1)的表达式
x 1 f 1 (x 1 ) 最优决策 d 1 *
A 19 A? B 2
求 最 短 路 径
87
资 源 分 配 问 题
88
例 5.6,有资金 4万元，投资 A,B,C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目 A,B,C的投资效益
（万吨）和投入资金（万元）关系见下表：
求对三个项目的最优投资分配，使总投资效益最大。
资 源 分 配 问 题
89
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
资 源 分 配 问 题
90
k=4,f4(x4)=0
k=3,0≤d3≤x3,x4=x3-d3
资 源 分 配 问 题
91
k=2,0≤d2≤x2,x3=x2-d2
资 源 分 配 问 题
92
k=1,0≤d1≤x1,x2=x1-d1
资 源 分 配 问 题
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,状态变量 xk：第 k次装载时背包还可以装载的重量；
3,决策变量 dk：第 k次装载第 k种物品的件数；
背 包 问 题
96
4,决策允许集合：
Dk(xk)={dk|0? dk?xk/wk,dk为整数 }；
5,状态转移方程,xk+1=xk-wkdk
6,阶段指标,vk=ckdk
7,递推方程
fk(xk)=max{ckdk+fk+1(xk+1)}
=max{ckdk+fk+1(xk-wkdk)}
8,终端条件,fn+1(xn+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
最短路径问题和背包问题的状态变量和决策 变量都只能取离散的整数值。当状态变量和决策变量的取值范围很大，或者这些变量是连续的，用列举的方法就比较困难或者根本不可能了。这就需要用连续变量的处理方法。
例 5,8,某种机器可以在高、低两种负荷下生产。
高负荷生产条件下机器完好率为 0.7,即如果年初有
u 台完好机器投入生产,则年末完好的机器数量为
0.7 u 台。系数 0.7 称为完好率。年初投入高负荷运行的 u 台机器的年产量为 8 u 吨。系数 8 称为单台产量。低负荷运行时，机器完好率为 0.9,单台产量为
5 吨。设开始时有 1000 台完好机器,要制订五年计划，每年年初将完好的机 器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。
104
构造动态规划模型如下：
阶段 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
机器负荷分配问题
105
递推方程：
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
根据题意，本题的决策允许集合应该是一个整数集合，但由于决策允许集合中 可取的决策数量很大，一一列举计算量很大,不妨认为状态变量和决策变量都是连续的,得到最优解后，再作取整处理。
机器负荷分配问题
106
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
机器负荷分配问题
107
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
机器负荷分配问题
108
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
机器负荷分配问题
109
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
机器负荷分配问题
110
由此可以得到：
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
机器负荷分配问题
111
每年投入高负荷运行的机器数以每年初完好的机器数为,
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
机器负荷分配问题
112
在这个例子中，状态变量的终端值 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满足,
机器负荷分配问题
113
则从 1— t-1年，年初将全部完好机器投入低负荷运行，从 t— n年，年初将全部完好机器投入高负荷运行，这样的决策，将使总产量达到最大。
tn
i
i
tn
i
i k
kkp
pp
k
0
1
121
21
)1(
0
1 )(
机器负荷分配问题
114
生 产 库 存 问 题
115
例 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 。 每个月生产的产品在月末入库，月初根据当月需求 发货。 求七个月的生产量，能满足各 月的需求，并使生产成本最低。
生 产 库 存 问 题
116
阶段 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；
生 产 库 存 问 题
117
递推方程：
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
生 产 库 存 问 题
118
对于 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
生 产 库 存 问 题
119
对于 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}
生 产 库 存 问 题
120
因为 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
生 产 库 存 问 题
121
对于 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)
生 产 库 存 问 题
122
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
生 产 库 存 问 题
123
对于 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
生 产 库 存 问 题
124
对于 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}
生 产 库 存 问 题
125
因为 13-x2>0
所以 d2(x2)={d2|13-x2?d2?17-x2}
由此 f2(x2)=5(13-x2)-13x2+377
=-18x2+442,
d2*=13-x2
生 产 库 存 问 题
126
对于 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}
生 产 库 存 问 题
127
根据题意 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
生 产 库 存 问 题
128
设 备 更 新 问 题
129
一台设备的价格为 P,运行寿命为 n年,
每年的维修费用是设备役龄的函数,记为 C(t),新设备的役龄为 t=0。 旧设备出售的价格是设备役龄的函数,记为 S(t)。
在 n年末,役龄为 t的设备残值为 R(t)。
现有一台役龄为 T的设备,在使用过程中,
使用者每年都面临,继续使用,或,更新,的策略,
设 备 更 新 问 题
130
阶段 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(
131
递推方程,
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 )
设 备 更 新 问 题
132
例 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
设 备 更 新 问 题
133
对于 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(
134
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(
135
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,
136
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(
137
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(
138
对于 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(
139
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(
140
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,
141
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
142
由以上计算可知，本问题有两个决策，它们对应的最小费用都是 115。
年份 1 2 3 4 5
决策 1 更新 更新 继续 更新 继续决策 2 更新 继续 更新 更新 继续这两个决策是设 备 更 新 问 题
