2009-7-30 1
第五章 动态规划
§ 5.1 动态规划的基本概念和方法
§ 5.2 动态规划的基本原理 ﹑ 模型和解法
§ 5.3 前向动态规划法
§ 5.4 动态规划的应用
§ 5.5 运用 QSB解动态规划问题
2009-7-30 2
5.1.1 多阶段决策及过程最优化多阶段决策是指这样一类特殊的活动过程,它们可以按时间顺序分解成若干相互联系的阶段,每个阶段都要作出决策,全部过程的决策是一个决策序列,所以多阶段决策问题又称为序贯决策问题。
多阶段决策的目标 是要达到整个活动过程的总体效果最优,所以多阶段决策又叫做过程最优化。也正是因为如此,多阶段决策并非各阶段决策的简单总和,由于各阶段决策之间的有机联系,某一段决策的执行必将影响到下一段的决策，以至于影响到总体效果,所以决策者在每一段决策中不仅应考虑本段最优,还应考虑对最终目标的影响,从而做出对全局来说最优的决策。动态规划就是符合这种要求的一种决策方法。
所以,所谓 动态规划,就是解决多阶段决策和过程最优化问题的一种数学规划方法。 显然,由于它所解决问题的多阶段性,因此它必然与时间有着密切的关系,随着时间的推移或过程的发展而决定各阶段的决策,从而,产生了一个决策序列,这就是动态的意思。然而它也可处理与时间无关的静态问题,只要在问题中人为地引入,时间”因素,将问题看成一个多阶段的决策过程即可。
§ 5.1 动态规划的基本概念和方法
2009-7-30 3
动态规划是现代管理中一种重要的决策方法,它可以广泛地用于解决 最短路径问题、资源分配问题、生产计划与库存问题、投资问题、
装载问题、排序问题及生产过程的最优控制 等。由于它具有独特的解题思路因此在处理某些优化问题时常比线性规划等方法更为有效。,
动态规划模型一般根据决策过程的时间参数是离散的还是连续的过程的演变是确定型的还是随机型的可以划分为 离散确定型、离散随机型、连续确定型和连续随机型四种类型,其中 离散确定型 是最基本的例 5.1 设 A地的某一企业要把一批货物由 A地运到 E城销售,其间要经过八个城市,各城市间的交通路线及距离如图 5.1所示,问应选择什么路线才能使总的距离最短?
图 5.1 例 5.1路线图 (共 18条路线,3× 3× 2× 1=18)
2009-7-30 4
这是一个最短路径问题的动态规划,QSB中也叫车马驿站问题。由图 5.1 不难看出,本例是一个四阶段的决策问题,
因此,无疑可以用动态规划方法求解。
5.1.2 动态规划的基本概念一、阶段 (stage)
将所给问题的过程，按时间或空间特征分解成若干相互联系的段落以便按次序求解就形成了阶段,阶段变量常用字母
k来表示 。
如例 5.1若有四个阶段,k就等于 1,2,3,4。第一阶段共有 3
条路线即 (A,B1),(A,B2)和 (A,B3),第二阶段有 9条路线，第 3
阶段有 6条路线,第 4 阶段有 2 条 路线。
2009-7-30 5
二,状态 (state)
各阶段开始时的客观条件或出发点称作 状态,描述各阶段状态的变最称作 状态变量,用 s表示 。 状态变量的取值集合称为状态集合,用 S表示 。 在例 5.1中,第一阶段的状态为 A，
第二阶段的状态为城市 B1,B2和 B3。 所以状态变量 s1的集合
S1={A},s2 的集合是 S2={B1,B2,B3},依 次 有 S3={C1,C2,C3},
S4={D1,D2}。 所以,在这里,状态变量的取值实际上是给定集合的一个元素 。
在动态规划中,状态必须具有如下性质,即当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各状态的影响,这称作 无后效性 。如果所选定的变量不具备无后效性，
就不能作为状态变量来构造动态规划模型。如在例 5.1中，当某阶段的状态变量确定以后，假定 s3=C2,因而在确定第 3 阶段的货运路线时，就只与 C2 这个城市有关，而与货物由哪个城市到达此地无关，所以满足状态的无后效性
2009-7-30 6
三,决策和策略 (Decision and Policy)
当各阶段的状态确定以后，就可以做出不同的决定或选择，从而确定下一阶段的状态，这种决定就是 决策 。 表示决策的变量称为决策变量，
常 用 kU （ ks ） 表示第 k 阶段当状态为 ks 时的 决策变量,在实际问题中,
决策变量的取值是被限制在一定的范围内，我们称此范围为允许的决策集合,用 kD （ ks ） 表示第 k 阶段从状态 ks 出发时的 允许决策集合,显然有 kU （ ks ） ∈ kD （ ks ）。
在例 5.1 中第二阶段如决定从 B1 出发，即 s2=B1,可选择走 C1 或
C2,C3，即其允许的决策变量集合 D2(B1)={C1,C2,C3} 。如果我们选择从 C2 走，则此时的决策变量可表示为 U2(B1)=C2 。所以,在这里决策变量的取值实际上也是给定集合的一个元素。
在各阶段决策确定以后,整个问题的决策序列就构成了一个 策略,用
nP,1 (U1,U2,…,U n) 表示,如对于例 5.1,nP,1 (A,B2,C1,D2,E) 就是一个策略。
对于每个实际问题,可供选择的策略有一定范围,称为 允许策略集合,用 P
表示，使整个问题达到最优效果的策略就是 最优策略 。如对于例 5.1 总共可有 18 个策略，但最优策略只有一个。
2009-7-30 7
四、状态转移方程在动态规划中，本阶段的状态往往是上阶段决策的结果。所以如果给定了第 k 阶段的状态 ks 和该阶段的决策 kU ( ks )，则第 k+1 段的状态 1+ks
由于 k 阶段决策的完成也就完全确定了,它们之间的关系可用如下公式表示：
1+ks ＝ kT （ ks,kU ）
其中,kT 表示从状态 ks 出发经过 kU 向下一阶段的转移 (Transfer),换言之,即 1+ks 是从状态 ks 出发经过决策 kU 转移的结果。
由于上式表示了由 k 段到第 k+1 段的状态转移规律，所以就称为 状态转移方程 。在例 5.1 中,状态转移方程即 1+ks ＝ kU 。
五、指标函数用于衡量所选定策略优劣的数量指标称作 指标函数 。 一个 n 阶段的决策过程,从 1 到 n 叫作问题的原过程,对于任意一个给定的 k(1 ≦ k≦ n),从 k
段到第 n 段称为原过程的一个 后部子过程,用 nV,1 (s1,nP,1 )表示初始状态为
s1采用策略 nP,1 时原过程的 效益值,用 nkV,（ ks,nkP,）表示在第 k 阶段状态
2009-7-30 8
为 ks 采用策略 nkP,时的后部子过程的效益值。 最优指标函数 记为 )( kk sf,
它表示从第 k 阶段的状态 ks 出发采用最优策略 *,nkp 到过程终止时的最佳效益值,于是有下面的关系式：
kf （ ks ）＝ nkV,（ ks,
*
,nkp ）＝ opt nkV,( ks,nkP,)
其中,opt 全称 optimization 即最优化，在最大化时用 max,在最小化时用
min。 kf （ ks ）也称作 k 阶段从状态 ks 出发时的 后部子过程的最佳效益值,
当 k=1 时,)( 11 sf 就是从初始状态 s1 到全过程结束的整体最优指标函数。
在例 5.1 中,指标函数就是距离。如在第 2 阶段,状态为 B2 时,V2,4(B2)
就表示从 B2 到 E 的可能距离,f2(B2)则表示从 B2 到 E 的最短距离。本问题的总目标是求 f1(A),即从 A 到 E 的最短距离 。
2009-7-30 9
为了求出例 5.1的最短路线,一个简单的方法是,可以求出所有从 A到 E的可能走法的路长并加以比较。不难知道,从 A到
E共有 18条不同的路线,每条路线有四个阶段,要做 3次加法,要求出最最短路线需做 54次加法运算和 17次比较运算,这叫做 穷举法 。不难理解,当问题的段数很多,各段的状态也很多时,这种方法的计算量会大大增加,甚至使得寻优成为不可能。
下面应用动态规划方法求解例 5.1。为了获得每一个后部子过程的最佳效益值,只能运用 逆序递推方法 求解,即由最后一段到第一段逐步求出各点到终点的最短路线,最后求出 A点到 E
点的最短路线。运用逆序递推方法的好处是可以始终盯住目标,不致脱离最终目标。例 5.1是一个四阶段决策问题,一般可分为四步：
第一步,从 k=4开始,状态变量 s4可取两种状态 D1,D2,它们到 E点的距离分别为 4和 3,这也就是由 D1和 D2到终点 E 的最短距离即 f4(D1)=4,f4(D2)=3。
5.1.3 最短路径问题的动态规划
2009-7-30 10
第二步,k=3,状态变量 s3 可取 3 个值即 C1,C2 和 C3,这是需经过一个中间站才能到达终点 E 的 二级决策问题 。 为方便应用，规定用 d( ks,kU )表示由状态 ks 出发,采用决策 kU 到达下一阶段 1+ks 时的两点距离。显然从 C1
到 E 有两条路线需加以比较,取其中最短的,即：
3f （ 1C ）＝ min
+
+
)(),(
)(),(
2421
1411
DfDCd
DfDCd =min
+
+
35
43
=7
这说明,由 C1到 E 的最短距离为 7,其路径为以 1C → 1D → E,相应的决策为 *3U （ 1C ） = 1D
3f （ 2C ）＝ min
+
+
)(),(
)(),(
2422
1412
DfDCd
DfDCd =min
+
+
32
46 =5
即从 C2 到 E 的最短距离为 5,其路径为 2C → 2D → E,相应的决策为
*
3U （ 2C ） = 2D
2009-7-30 11
3f （ 3C ）＝ min
+
+
)(),(
)(),(
2423
1413
DfDCd
DfDCd =min
+
+
33
41 |=5
即从 C3 到 E 的最短距离为 5,其路径为 C3→ D1→ E,相应的决策为
*
3U （ 3C ） = 1D 。
第三步,k=2,这是一个具有三个状态,要经过两个中间站才能到达终点的 三级决策问题 。由于第 3 段各点 C1,C2,C3 到终点 E 的最短距离 f3(C1),
f3(C2),f3(C3),已知,所以要求城市 B1 到 E 的最短距离,只需以它们为基础,
分别加上 B1 到达 C1,C2,C3 的一段距离,加以比较取其最短者即可。
)( 12 Bf =min
+
+
+
)(),(
)(),(
)(),(
3331
2321
1311
CfCBd
CfCBd
CfCBd
=min
+
+
+
55
54
76
=9
即 B1 到终点 E 的最短距离为 9,其路径为 B1→ C2→ D2→ E,本段的相应决策为 *2U （ 1B ） = 2C
2009-7-30 12
同理有,
)( 22 Bf =min
+
+
+
)(),(
)(),(
)(),(
3332
2322
1312
CfCBd
CfCBd
CfCBd
=min
+
+
+
56
57
78
=11
即 *2U （ 2B ）＝ 3C
)( 32 Bf =min
+
+
+
)(),(
)(),(
)(),(
3333
2323
1313
CfCBd
CfCBd
CfCBd
=min
+
+
+
59
58
77
=13
即 *2U （ 3B ）＝ 2C
第四步,k=1,只有一个状态点 A,则
)(1 Af =min
+
+
+
)(),(
)(),(
)(),(
333
232
121
BfBAd
BfBAd
BfBAd
=min
+
+
+
135
119
98
=17
即 *1U （ A）＝ 1B
2009-7-30 13
从城市 A 到城市 E 的最短距离为 17。把各段的最优决策按计算顺序反推,即得到最优决策序列,即 *1U （ A）＝ 1B,*2U （ 1B ） = 2C,*3U （ 2C ）
＝ 2D,*4U （ 2D ）＝ E，所以最短路线为,A→ B1→ C2→ D2→ E。
4
3
7
5
513
11
9
17
上述最优路线是通过计算最优指标函数得到的，可以称作指标函数法 。还可以采用在图上直接标记的方法求得，这种直接标记的方法可称作 图上作业法 （ Click to show）
这种方式使用起来更简单明了，最佳路线的确定方法也很容易 [f(sk)－ d(sk,sk+1)=f(sk+1)]，是一种值得推荐的方法。
（课堂练习参教材）
2009-7-30 14
在上述的求解过程中,各段的计算都利用了第 k 段和第 k+1 段的如下关系：
kf （ ks ）＝ min{ kd （ ks,kU ）＋ )( 11 ++ kk sf (k=4,3,2,1) (1)
)( 55 sf ＝ 0 (2)
这种递推关系称为 动态规划的基本方程,(2)式称边界条件,容易算出,
运用动态规划方法解例 5.1 只进行了 17 次加法运算,11 次比较运算，就获得了最优解,比穷举法的计算量明显地要少,而且随着问题段数的增加和变量数目的增多,计算量将呈指数规律减少。其次,动态规划的计算结果不仅得到了 A 到 E 的最短路线,而且得到了任意一点到 E 点的最优路线 。
这可由图 5.2 来描述 (用彩色线表示最优路线,各点上的数字表最短距离 )
图 5.2
2009-7-30 15
根据例 5.1,动态规划的基本思想 可总结如下：
一,将多阶段决策过程划分阶段,恰当地选取状态变量,决策变量和定义最优指标函数,从而把问题化成一族同类型的子问题,然后逐个求解 。
二,求解时总是从边界条件开始,沿过程行进方向,逐段递推寻优 。 在每一个子问题求解时,都要利用它前边已求出的子问题的最优结果 。 最后一个子问题的最优解,就是整个问题的最优解 。
三,动态规划方法是既把当前一段与未来各段分开,又把当前效益和未来效益结合起来考虑的一种最优化方法 。 因此,每段的最优策略的选取都是从全局考虑的,它与该段的最优选择是不同的 。
§ 5.2 动态规划的基本原理、模型和解法
5.2.1 最优化原理动态规划方法是由美国数学家贝尔曼 (R.Bellman)等人于本世纪 50
年代提出的 。 他们针对多阶段决策问题的特点,提出了解决这类问题的,最优化原理,,并成功地解决了生产管理,工程技术许多方面的实际问题 。
2009-7-30 16
最优化原理用反证法极易证明。 假定 sk 是由始点到终点的最短路 线上的一点,如果存在另一条最短路 ks 与终点相连,则这条最短路线 与 ks 以前的部分必构成全程的最短路线,这就与原策略为最短路线的假定相矛 盾。 所以,对于一个过程的最优策略而言,不管其初始状态和决策如何,其后 的任一决策都构成最优策略。 这也就是动态规划所以可以采用逆序递推法 寻优的依据。
如果把最优化原理用数学语言描述,就得到了 动态规划的基本方程,这就是,
kf （ ks ）＝ opt[ ])(),( 11 +++ kkkkk sfusd (k=n,n-1,…,1)
1+nf （ 1+ns ）＝ 0 其中,opt 可依题意取 max 或 min
最优化原理 可以表述为：,一个过程的最优策略具有这样的性质,
即无论初始状态和初始决策如何,对于先前决策所形成的状态而言,其以后的所有决策必构成最优策略,,
将这一基本原理应用于例 5.1的最短路线问题时可表述为：一方面,
一条路线如果是最短路线,则对于该线上的任何一点来说,最短路线以此点为起点的剩余部分,必然是从此点到终点的最短路线 。 另一方面,无论是从哪一段的哪一种状态出发,到终点 E的最短路线只与此状态有关,而与以前的状态路线无关,即并不受从 A点是如何到达这点的决策的影响 。
图 5.2中的 C2点可以清楚地证明这两种情况 。
2009-7-30 17
5.2.2 动态规划模型的建立建立动态规划的模型,就是分析问题并建立问题的动态规划基本方程。
成功地应用动态规划方法的 关键,在于识别问题的多阶段特征,将问题分解成可用递推关系式联系起来的若干子问题,或者说是 要正确地建立具体问题的基本方程,无疑这需要经验和技巧。 而正确地建立关于递推关系基本方程的关键，又在于 正确地选择状态变量,保证各阶段的状态变 量具有递推的状态转移关系 1+ks ＝ ),( kkk usT 。 这是 建立动态规划模型的两个基本要点。
下面举例来说明动态规划模型的建立。
例 5.2 生产与存储问题设某工厂生产并销售某种产品,已知每千件的 变动成本 为 1 万元,每季度生产的 固定成本 为 3 万元,经预测某一年四个季度中该产品的市场需求量分别为 2,3,2,4 千件,设该厂的最大生产能力是 6 千件,最大库容是 3 千件,每千件产品一个季度的存储费用为 0.5 万元,如果要求年初和年末该产品均无库存,问如何安排各季度的产量,才 能使全年的总费用最小。
2009-7-30 18
解,1,设阶段变量为 k,则每季度为一个阶段,k=1,2,3,4 。
2,每季度初的产品库存量可作为状态变量,由已知条件显然有 s1=s5=0 。
3,决策变量是每季度的产品生产量,由已知条件知,0≤ Uk ≤ 6,Uk 的单位为千件。
4,显然,状态转移方程由下式确定：
1+ks ＝ kkk dus -+
其中,kd 表示第 k 阶段的需 求量或销量。
即第 k+1 阶段的库存量就等于第 k 段的库存量加本段的生产量减去本段的需求量 (销售量 )。
5,指标函数本例的指标函数是生产与存储的总费用,最优指标函数是指生产与存储的总费用和最低。
第 k 段的指标即总费用为：
),( kkk usV ＝ 0.5 ks ＋ =
+
)0(0
)60(3
k
kk
u
uu
kV 的单位为万元。6,建立基本方程 （即成本最小化）
)](),([m i n)( 11 +++= kkkkkUkk sfusVsf
k
（ k=4,3,2,1）
0)( 55 =sf
5.2.3 动态规划模型的求解动态规划模型建立以后,对基本方程的分段求解,并不象线性 规 划那样有固定的解法,它需要根据具体问题的特 点,结合数学方法 灵 活求解。 在各种解法中,常用的对于离散变量的 分段穷举算法 是一 种基 本方法。
分段穷举法使用的前提 是,动态规划模型中的状态变量和决策变量均取离散值。 例 5.2 中最短路线的求解用的就是分段穷举法。 如果每段的状态变量和决策变量是离散的且取值数目较少,运用分段穷举法比一般问题使用的穷举法会更有效。 运用分段穷举法求最优指标函数值,最重要的是要正确确定每段状态变量的取值范围和允许的决策变量集合,一般使用表格形式进行。 下面以 例 5.2 的求解为例,对这种方法作以总结。
第一步,先考虑 k= 4,因为要求第四季度末库存为 0,即 s5=0,本季度需求为 4,所以据状态转移方程应有 44 4 su -=,由于库存量最大为 3,
所以 s4 的取值只能是 0,1,2,3。
根据 )](),(min[)( 5544444 sfusvsf +=,及 0)( 55 =sf,
444 35.0 usv ++=,可列出 4u 与 4f 如表 5.1。
2009-7-30 20
表 5.1 解例 5.2 的第 1 步
4s 0 1 2 3
)( 44 su 4 3 2 1
)( 44 sf 7 6.5 6 5.5
第二步,k=3 时,ks 的取值范围仍然是 }3,2,1,0{3 =s 。 根 据状态 转移方程,3433 ssdu -+=,因 23 =d,所以 343 2 ssu -+=,即在需求量一定的情况下,生产量由期末和期初的库存量决定。 由于 3u ≥ 0,所以有
34 ss - ≥ － 2,由 3u ≤ 6 有 34 ss - ≤ 4,于是 3u 的允许的取值范围是,－ 2
≤ 34 ss - ≤ 4，决策过 程过程如表 5.2：
44 4 su -=
)](),(min[)( 5544444 sfusvsf +=
444 35.0 usv ++=
2009-7-30 21
表 5.2 解例 5.2的第二步
s3 0 1 2 3
s4 0 1 2 3 0 1 2 3 0 1 2 3 1 2 3
u3(s3) 2 3 4 5 1 2 3 4 0 1 2 3 0 1 2
V3+f4 12 12.5 13 13.5 11.5 12 12.5 13 8 11.5 12 12.5 8 11.5 12
f3(s3) 12 11.5 8 8
u3*(s3) 2 1 0 0
第三步,当 k=2 时,状态变量 2s 的取值范围是 2s ={0,1,2,3},根据状态转移方程应有,2322 ssdu -+=,已知 2d ＝ 3，所以 根据232 3 ssu -+=
0≤ 2u ≤ 6，应有－ 3≤ 23 ss - ≤ 3,决策过程如表 5.3。
333 35.0 usv ++=343 2 ssu -+=
)](),(min[)( 4433333 sfusvsf +=
2009-7-30 22
表 5.3 解例 5.2 的第三步
s2 0 1 2 3
s3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
u2(s2) 3 4 5 6 2 3 4 5 1 2 3 4 0 1 2 3
V2+f3 18 18.5 16 17 17.5 18 15.5 16.5 17 17.5 15 16 13.5 17 14.5 15.5
f2( s2) 16 15.5 15 13.5
u2*(s2) 5 4 3 0
第四步,当 k=1 时,只有一种状态即 1s =0,根据 1211 ssdu -+=,有
21 2 su +=,由于 2s 最大为 3,即 1u 最大为 5,不超过最大生产能力 显,
然,1u 的允许集合是 1(s1)D ＝｛ 2,3,4,5｝因 11 3 uv += 所以,有：
232 3 ssu -+=
)](),(min[)( 3322222 sfusvsf +=
222 35.0 usv ++=
2009-7-30 23
21
5.138
157
5.156
165
min)( 11 =
+
+
+
+
=sf 即 )( 1*1 su ＝ 2
整个过程的最优计划可依状态方程即 1+=-+ kkkk sdus 确定，即当
1s ＝ 0,1u ＝ 2,1d ＝ 2 时,2s ＝ 0，在 表 5.3 中,2s ＝ 0 对应于
*
2u (s2)＝ 5
若 2s ＝ 0,2u ＝ 5,2d ＝ 3，则 2,3 =s 在 表 5.2 中,23 =s 对应于 )( 3*3 su ＝ 0;
)( 44 su ＝ 4。 即第一季度生产 2 千件。 第二 季度生产 5 千件。
第三季度不生产； 第四季度生产 4 千件。 全年生产 11 千件,总需求 11 千件,总费用 21 万元。
根据例 5.1 和例 5.2 的求解过程,运用 分段穷举法的要点 包括 (1)确定状态变量集合 ； (2)确定决策变量集合 kk sD ； (3)计算 ),( kkk usV ； (4)计算
)( kk sf ； (5)确定 )(* kk su
若 s3＝ 2,u3＝ 0,d3＝ 2，则 s4＝ 0，在 表 5.1中，对应于 s4＝ 0，有
2009-7-30 24
动态规划的求解除了运用逆序解法 (又称后向动态规划法 )外,还可以运用 顺序解法 (又称前向动态规划法 )。
前面所使用的动态规划解法,由于寻优的方向与多阶段决策过程的实际行进方向相反,是从最后一段开始计算逐段向前推进,最后求得全过程的最优策略，所以称为 逆序解法 。
与逆序法相反，顺序解法的寻优方向与过程的行进方向相同，求解时是从第一段开始计算逐段向后推进，计算后一阶段时要用到前一段求优的结果，最后一段的计算结果就是全过程的最优结果。
逆序解法和顺序解法都属于动态规划的基本解法。
下面仅以最短路线问题为例对顺序解法予以说明。
§ 5.3 前向动态规划法
5.3.1 顺序解法的基本思路
2009-7-30 25
在例 5.1中，当 k=0 时 0)()( 000 == Afsf,这是边界条件。
当 k=1 时,1s表示第一阶段的终点，其允许取值集合
},,{ 3211 BBBS =,于是有：
)( 11 Bf ＝ 8,)( 21 Bf ＝ 9,)( 31 Bf ＝ 5
ABu =)( 11,ABu =)( 21,ABu =)( 31
当 k=2 时,有
+
+
+
=
),()(
),()(
),()(
min)(
1331
1221
1111
12
CBdBf
CBdBf
CBdBf
cf ＝ 12
75
89
68
min =?
+
+
+
即 312 )( BCU =最短路线问题的顺序解法
5.3.2 最短路径问题的顺序解法
2009-7-30 26
+
+
+
=
),()(
),()(
),()(
min)(
2331
2221
2111
22
CBdBf
CBdBf
CBdBf
cf ＝ 12
85
79
48
min =
+
+
+
即 122 )( BCU =
+
+
+
=
),()(
),()(
),()(
min)(
3331
3221
3111
32
CBdBf
CBdBf
CBdBf
cf ＝ 13
95
69
58
min =
+
+
+
即 132 )( BCU =
当 k=3 时,有
+
+
+
=
),()(
),()(
),()(
min)(
1332
1222
1112
13
DCdCf
DCdCf
DCdCf
Df ＝ 14
113
612
312
min =
+
+
+
即 313 )( CDU =
2009-7-30 27
+
+
+
=
),()(
),()(
),()(
min)(
2332
2222
2112
23
DCdCf
DCdCf
DCdCf
Df ＝ 14
313
212
512
min =
+
+
+
即 223 )( CDU =
当 k=4 时,有
+
+=
),()(
),()(min)(
223
113
4 EDdDf
EDdDfEf ＝ 17
314
414min =
+
+
即 24 )( DEU =
将选定的决策变量按计算顺序反推即可得到决策序列 ｛ ku ｝，即最短路线为 24 )( DEu =,223 )( CDu =,122 )( BCu =,ABu =)( 11,即最短路线为 A→ B1→ C2→ D2→ E,最短距离为 17。其结果与逆序解法完全相同。
2009-7-30 28
一般地说，顺序解法与逆序解法在本质上没有什么不同,通常情况下，
当初始状态给定时用逆序解法较方便,当终止状态给定时用顺序解法较方便。
但若初始状态虽已给定，然而 终点状态较多,需比较到达不同终点状态的各个路径及指标函数值,以选取总效益最佳的终点状态时,以 使用顺序解法比较方便。 另外,在初始状态和终止状态均为已知，但当使用不同方法第一步需处理的状态不同时，以选择第一步需处理较多状态的方法为比较合适,这样可以减少运算工作量，如例 5.1 采用顺序法只需作 17 次加法运算,比逆序法要少一次。总之,针对问题的不同特点,灵活地选用这两种方法之一,可以使求解过程简化。
在使用这两种方法求解时，除了求解时的行进方向不同外，在建模时还需要注意以下区别：
1,状态变量的含义不同在逆序解法中,状态变量 ks 是第 k 段的出发点；而在顺序解法中,ks
则是第 k 段的终点。
5.3.3 顺序解法与逆序解法的异同
2009-7-30 29
2.决策过程和结果不同在逆序解法中,每一段的决策是对于给定的出发点选择符合要求的终点,也就是说在逆序解法中决策过程是顺序的；而在顺序解法中,每一段的决策则是对于给定的终点选择符合要求的出发点,也就是说在顺序解法中,
决策过程逆序的。
逆序法得到的结果，是每一点到终点的最短路线和距离；顺序法得到的结果,是起点到每一点的最短路线和距离，如图 5.3。
3.状态转移方式不同在逆序解法中，如 图 5.4，第 k 段的输入状态为 ks,决策为 kU,由此决定输出为 1+kS,所以状态转移方程为：
1+kS ＝ kT （ ks,kU ）
该方程称之为状态 ks 到 1+kS 的顺序转移方程。
图 5.3
2009-7-30 30
图 5.4 逆序解法的决策过程而在顺序解法中，如图 5.5,第 k 段的输入状态为 ks,决策为 kU,由此确定的输出则为 1-kS,所以状态转移方程为：
1-kS ＝ kT （ ks,kU ） 该方程称作状态 ks 到 1-kS 的逆序转移方程。
图 5.5 顺序解法的决策过程
2009-7-30 31
4,指标函数的定义不同在逆序解法中,最优指标函数 )( Kk Sf 定义为第 K 段从状态 ks 出发,到过程终点的后部子过程的最优效益值,)( 11 Sf 是整体最优函数值。
在顺序解法中,最优指标函数 )( Kk Sf 定义为第 K 段从状态 ks 回返,到过程始点的前部子过程的最优效益值,)( nn Sf 是整体最优函数值。
5,基本方程形式不同在逆序解法中,）j
n
kj
jnk usVV,(,?
=
=,基本方程为：
-==
+=
++
++
1,2,...,1,0)(
)}(),({)(
11
11
nnksf
sfusVoptsf
nn
kkkkkkk
在顺序解法中,）j
k
j
jk usVV,(
1
,1?
=
=,基本方程为：
==
+= --
nksf
usVsfoptsf kkkkkkk
,...,2,10)(
)},()({)(
00
11
2009-7-30 32
一、应用之一 —— 投资问题设总投资额为 a 万元,拟投资于 n个项目上，已知对第 i 个 项目投资 ix 万元,收益函数为 )( ii xg,问应如何分配资金才可以使总收益最大?
这是一个与时间无明显关系的静态最优化问题,可先列出其静态模型为：
maxV＝?
=
n
i
ii xg
1
)(
s.t,ax
n
i
i
=1
0?ix (i=1,2,…,n)
为了应用动态规划方法求解,我们可以人为地赋予它“时段”的概念。 方法是将投资项目排序,假想对各个投资项目有先后顺序。 首先考虑对项 目 1 的投资,然后考虑对项目 2 的投资,依次最后考虑第 n 项投 资,这样就 把原问题转化为 n 阶段的决策过程。 接下来的问题，便是如何 选择正确的 状态变量,并使各后部子过程间具有递推关系。
§ 5.4 动态规划的应用
2009-7-30 33
1,状态变量 ks,表示第 K 段可用于剩余的 n-k+1 个项目的资金数,
显 然有 1s =a,1+ns =0。
2,决策变量 ku,即应分配第 K 个项目上的投资额。
3,状态转移方程,kkk uss -=+1
4,指标函数,?
=
=
n
ki
ii ugV nk )(,
最优指标函数 kf （ ks ）：表示当可投资金数为 ks 时,投资于剩余的
n-k+1 个项目的最大收益。
5,基本方程为：
=
+=
++
++
0)(
)]()(max[)(
11
11
nn
kkkkkk
sf
sfugsf k=n,n-1,…,2,1
如果运用逆序递推寻优,则 )(1 af 就是所求的最大收益。
2009-7-30 34
例 5.3 某企业共有设备 4 台,拟分给三个车间,各车间利用这些设备为企业可提供的盈利 kk (u )g 各不相同 (资料见表 4.4),问应如何分配这四台设备才能使企业获得的盈利最大?
表 5.4 例 5.3 的有关资料解：该问题与上述的资源分配问题 (即投资分配问题 )具有完全相同的模型，
因初始状态 S1=4 为已知，故可 运用逆序解法，在这里 n=3,a=4。
设备分配数 )(
11 ug )( 22 ug )( 33 ug
0
1
2
3
4
0
4
6
7
7
0
2
5
6
8
0
3
5
7
8
一车间 二车间 三车间单位：万元
2009-7-30 35
当 k=3 时,状态变量 3s 的取值范围为 3s ＝ ｛ 0,1,2,3,4｝，同样
3u 的取值范围也是 3D ＝ ｛ 0,1,2,3,4｝,根据 334 uss -=,04 =s,
即 33 su =,即 0)( 44 =sf,依基本方程可列出 K=3 时的结果如表 4.5
表 5.5 例 5.3 k=3 时的结果说明：因本段是最后一个阶段，
所以每状态只与一个变量对应。
当 k=2 时,状态变量的取值范围为 2s ＝ ｛ 0,1,2,3,4｝，根据
223 uss -= 即 322 ssu -= 和基本方程，可得表 4.6(注意条件 u>0)。
3s 0 1 2 3 4
3u 0 1 2 3 4
3f 0 3 5 7 8
2009-7-30 36
表 5.6 例 5.4 当 k=2 时的结果
2s
3s
2u
2v
)( 33 sf
)( 22 sf
*
2u
0
0
0
0
0
0
0
1
1 0
0 1
0 2
3 0
(3) 2
0
2
2 1 0
0 1 2
0 2 5
5 3 0
5 5 5
0 1 2
3
3 2 1 0
0 1 2 3
0 2 5 6
7 5 3 0
7 7 （ 8） 6
2
4
4 3 2 1 0
0 1 2 3 4
0 2 5 6 8
8 7 5 3 0
8 9 （ 10） 9 8
2
223 uss -=322
ssu -=
2009-7-30 37
当 K = 1 时,
1
s 的取值是
1
s ＝ 4,
1
u 的取值范围是
1
D ＝ ｛ 0,1,2,3,4 ｝，
根据
112
uss -= （即
21
4 su -= ）和基本方程，有：
12
07
37
56
84
100
m ax)4(
1
=
+
+
+
+
+
=f 即 1)(
1
*
1
=su
根据状态转移方程,若 =1,=4，则 =3；
在表 5.6中,=3时 ＝ 2,这时 ＝ 1；在表 5.5中,若 ＝ 1,则
=1。于是最优决策是分配 1车间 1台设备,2车间 2台设备,3车间
1台设备,得最大利润 12个单位。
kkk uss -=+ 1 *1u 1s 2
s
2s *2u 3s 3s
*3u
2009-7-30 38
对于投资问题的上述解法可称作 详表解法,虽然看起来比较清楚，但显得有些繁琐。因此，在掌握规律后可采用 简表解法,借助于辅助线同样也很清楚。现运用上述的设备分配问题，
对简表解法予以说明。
表 5.7 设备分配问题简表
éè ±? k ￡? 1 k ￡? 2 k ￡? 3
· êy g 1 ( x 1 ) f 1 ( s 1 ) g 2 ( x 2 ) f 2 ( s 2 ) g 3 ( x 3 ) f 3 ( s 3 )
0 0 0 0 0
1 4 12 2 3 3
2 6 5 5 5
3 7 6 8 7
4 7 8 10 8
U * u 1* =1 u 2* =2 u 3* =1
在使用 逆序方法求解 时，第 n－ 1以后各段，必须注意决策变量的允许集合。最后一步即第 1段的最优指标函数写在取得最优值的相应行。最优决策的寻找方法类似于最短路径问题的 图上作业法,即 fi(si)－ vi(si)＝ f i+1(s i+1)，但有时需分析。
2009-7-30 39
运用简表法求解较大规模的问题具有很大的优越性。如在下面的投资分配问题中，共有 6个单位的资源和 4个方案，各个方案在不同投资数量条件下的收益不同，试确定最佳投资方案。
í? ×ê k ￡? 1 k ￡? 2 k ￡? 3 k ￡? 4
· êy g 1 ( x 1 ) f 1 ( s 1 ) g 2 ( x 2 ) f 2 ( s 2 ) g 3 ( x 3 ) f 3 ( s 3 ) g 4 ( x 4 ) f 4 ( s 4 )
0 0 0 0 0
1 20 30 50 40
2 80 50 70 60
3 100 70 100 80
4 120 90 110 100
5 130 120 110 110
6 100 130 110 120
0 0
50 50
220 90 90
220 120 110
140 140
170 160
190 180
（ Click to show answer）
这种方法同样适用于求最小化问题。如某房地产公司拟在三个不同地区建造 5栋商住楼，已知在不同地区建造商住楼所需的投资不同，有关资料如下表，试求一个投资费用最低的投资方案。
2009-7-30 40
¨?ì k ￡? 1 k ￡? 2 k ￡? 3
￥?ì êy g 1( x 1) f 1( s 1) g 2( x 2) f 2( s 2) g 3( x 3) f 3( s 3)
0 0 0 0
1 210 150 160
2 400 360 370
3 520 500 520
4 800 730 740
5 950 1000 900
0
150
310
830 500
660
870
这种简表法的基本思路是由北京经济管理干部学院的赵景文教授首先提出来的，感兴趣的同学可以在中国数据期刊网上下载,用动态规划解设点问题,一文阅读。
正确使用这种简表法的前提是，必须熟悉最短路径问题的分段穷举法和投资分配问题的详表解法。
2009-7-30 41
背包问题是动态规划的典型问题。一维背包问题的典型提法是：一位旅行者能承受的背包最大重量是 b 千克，现有 n 种物品供他选择装入背包，第 i 种物品单件重量为
i
a 千克，其价值 ( 或重要性参数 ) 为 c
i
，总价值是携带数量
i
x 的函数即
ii
xc,问旅行者应如何选择所携带物品的件数以使总价值最大?
背包问题实际上就是运输问题中车船的最优配载问题,还可以广泛地用于解决其它的问题。其一般的整数规划可表述为：
=
=
n
i
ii
xcz
1
m ax
s,t,bxa
n
i
ii
= 1
0?
i
x
且为整数 （ i= 1,2,…,n ）
二、动态规划的应用之二－－背包问题
2009-7-30 42
下面用动态规划方法来求解：
1,阶段 k：即需要装入的 n 种物品的次序,每段装入一种,共 n 段。
2,状态变量 ks,即在第 k 段开始时,允许装入前 k 种物品的总重量，显然有 ns =b,因 ns 已知故可采用顺序解法。
3,决策变量 kx,即装入第 k 种物品的件数
4,状态转移方程,kkkk xass -=-1
允许的决策集合是：
=
k
k
kkkk a
sxxsD 0|)( 且为整数
5,基本方程是,
{ }
==
-+= -
nksf
xasfxcsf kkkkkkkk
,...,2,10)(
)(max)(
00
1
2009-7-30 43
例 5.4 一贩运商拟用一 10 吨载重量的大卡车装载 3 种货物,有资料如下表,问应如何组织装载,可使总价值最大?
解,设装载每一种货物的件数为 ix,则有：
maxz=4 1x +5 2x +6 3x
s.t,3 1x +4 2x +5 3x ≤ 10
0?ix 且为整数用动态规划方法的顺序解法求解，则当 k=1 时,{ }1
30
11 4)( max
11
11
xsf
x
sx
为整数
=
货物编号 1 2 3
单位重量 （吨）
单位价值
3 4 5
4 5 6
2009-7-30 44
这是一个简单的线性规划问题,0 13x 1s 即 30 11 sx,因线性规划的最大值只能在极点取得,于是有 { } )3(44max)( 11]3[011
11
sIntxsf
sx
==
计算结果可列入下表,
1s 0 1 2 3 4 5 6 7 8 9 10
1x 0 0 0 1 1 1 2 2 2 3
3
)( 11 sf 0 0 0 4 4 4 8 8 8 12 12
当 k=2 时,?
+-=
2221
]4[0
22 5)4(max)(
1
2
2
xxsfsf
ssx
计算结果如下表：
2009-7-30 45
S2 0 1 2 3 4 5 6 7 8 9 10
x2 0 0 0 0 0 1 0 1 0 1 0 1 0 1 2 0 1 2 0 1 2
V2 0 0 0 0 0 5 0 5 0 5 0 5 0 5 10 0 5 10 0 5 10
f1+V2 0 0 0 4 4 5 4 5 8 5 8 9 8 9 10 12 9 10 12 13 10
f2(s2) 0 0 0 4 5 5 8 9 10 12 13
x2* 0 0 0 0 1 1 0 1 2 0 1
+-=
2221
]4[0
22 5)4(max)(
1
2
2
xxsfsf
ssx
V2 ＝ 5x2
2009-7-30 46
当 k=3 时,因 3s =10,故 2s =10-5 3x,5x3≤ s3 即 x3≤ 2，所以
3f （ 10） = max 20
3x
{ 2f (10-5 3x )+6 3x
= max
2,1,03=x
{ 2f (10-5 3x )+6 3x
= max{ 2f (10),2f (5)+6,2f (0)+12}
=max{13,5+6,0+12}=13
即 *3x =0,依状态转移方程反推,此时有 2s =10,当 2s =10 时,依第 2 段计算结果 *2x =1，当 2x =1,2s =10 时,依 1s = 2s -4 2x 有 1s =6,由第一段计算结果知,当 1s =6 时,*1x =2.即最优方案为,*1x =2,*2x =1,*3x =0,最大价值为 13。
}
}
2009-7-30 47
本章应完成作业,
p203－ 1。 P204－ 4。
§ 5.5 运用 QSB解动态规划问题动态规划的应用范围很广，各种问题的模型结构都不完全相同，因而解法也各有千秋。ＱＳＢ主要设计了三类动态规划问题的解法，即：（１） Stagecoach Problem（最短路径或车马驿站问题 ） ；（２） Knapsach Problem（ 背包问题） ；（３）
Production and Inventory Control Problem（ 生产与存储问题）。
1,最短路径问题演示
2,背包问题演示
3,生产与存储问题
第五章 动态规划
§ 5.1 动态规划的基本概念和方法
§ 5.2 动态规划的基本原理 ﹑ 模型和解法
§ 5.3 前向动态规划法
§ 5.4 动态规划的应用
§ 5.5 运用 QSB解动态规划问题
2009-7-30 2
5.1.1 多阶段决策及过程最优化多阶段决策是指这样一类特殊的活动过程,它们可以按时间顺序分解成若干相互联系的阶段,每个阶段都要作出决策,全部过程的决策是一个决策序列,所以多阶段决策问题又称为序贯决策问题。
多阶段决策的目标 是要达到整个活动过程的总体效果最优,所以多阶段决策又叫做过程最优化。也正是因为如此,多阶段决策并非各阶段决策的简单总和,由于各阶段决策之间的有机联系,某一段决策的执行必将影响到下一段的决策，以至于影响到总体效果,所以决策者在每一段决策中不仅应考虑本段最优,还应考虑对最终目标的影响,从而做出对全局来说最优的决策。动态规划就是符合这种要求的一种决策方法。
所以,所谓 动态规划,就是解决多阶段决策和过程最优化问题的一种数学规划方法。 显然,由于它所解决问题的多阶段性,因此它必然与时间有着密切的关系,随着时间的推移或过程的发展而决定各阶段的决策,从而,产生了一个决策序列,这就是动态的意思。然而它也可处理与时间无关的静态问题,只要在问题中人为地引入,时间”因素,将问题看成一个多阶段的决策过程即可。
§ 5.1 动态规划的基本概念和方法
2009-7-30 3
动态规划是现代管理中一种重要的决策方法,它可以广泛地用于解决 最短路径问题、资源分配问题、生产计划与库存问题、投资问题、
装载问题、排序问题及生产过程的最优控制 等。由于它具有独特的解题思路因此在处理某些优化问题时常比线性规划等方法更为有效。,
动态规划模型一般根据决策过程的时间参数是离散的还是连续的过程的演变是确定型的还是随机型的可以划分为 离散确定型、离散随机型、连续确定型和连续随机型四种类型,其中 离散确定型 是最基本的例 5.1 设 A地的某一企业要把一批货物由 A地运到 E城销售,其间要经过八个城市,各城市间的交通路线及距离如图 5.1所示,问应选择什么路线才能使总的距离最短?
图 5.1 例 5.1路线图 (共 18条路线,3× 3× 2× 1=18)
2009-7-30 4
这是一个最短路径问题的动态规划,QSB中也叫车马驿站问题。由图 5.1 不难看出,本例是一个四阶段的决策问题,
因此,无疑可以用动态规划方法求解。
5.1.2 动态规划的基本概念一、阶段 (stage)
将所给问题的过程，按时间或空间特征分解成若干相互联系的段落以便按次序求解就形成了阶段,阶段变量常用字母
k来表示 。
如例 5.1若有四个阶段,k就等于 1,2,3,4。第一阶段共有 3
条路线即 (A,B1),(A,B2)和 (A,B3),第二阶段有 9条路线，第 3
阶段有 6条路线,第 4 阶段有 2 条 路线。
2009-7-30 5
二,状态 (state)
各阶段开始时的客观条件或出发点称作 状态,描述各阶段状态的变最称作 状态变量,用 s表示 。 状态变量的取值集合称为状态集合,用 S表示 。 在例 5.1中,第一阶段的状态为 A，
第二阶段的状态为城市 B1,B2和 B3。 所以状态变量 s1的集合
S1={A},s2 的集合是 S2={B1,B2,B3},依 次 有 S3={C1,C2,C3},
S4={D1,D2}。 所以,在这里,状态变量的取值实际上是给定集合的一个元素 。
在动态规划中,状态必须具有如下性质,即当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各状态的影响,这称作 无后效性 。如果所选定的变量不具备无后效性，
就不能作为状态变量来构造动态规划模型。如在例 5.1中，当某阶段的状态变量确定以后，假定 s3=C2,因而在确定第 3 阶段的货运路线时，就只与 C2 这个城市有关，而与货物由哪个城市到达此地无关，所以满足状态的无后效性
2009-7-30 6
三,决策和策略 (Decision and Policy)
当各阶段的状态确定以后，就可以做出不同的决定或选择，从而确定下一阶段的状态，这种决定就是 决策 。 表示决策的变量称为决策变量，
常 用 kU （ ks ） 表示第 k 阶段当状态为 ks 时的 决策变量,在实际问题中,
决策变量的取值是被限制在一定的范围内，我们称此范围为允许的决策集合,用 kD （ ks ） 表示第 k 阶段从状态 ks 出发时的 允许决策集合,显然有 kU （ ks ） ∈ kD （ ks ）。
在例 5.1 中第二阶段如决定从 B1 出发，即 s2=B1,可选择走 C1 或
C2,C3，即其允许的决策变量集合 D2(B1)={C1,C2,C3} 。如果我们选择从 C2 走，则此时的决策变量可表示为 U2(B1)=C2 。所以,在这里决策变量的取值实际上也是给定集合的一个元素。
在各阶段决策确定以后,整个问题的决策序列就构成了一个 策略,用
nP,1 (U1,U2,…,U n) 表示,如对于例 5.1,nP,1 (A,B2,C1,D2,E) 就是一个策略。
对于每个实际问题,可供选择的策略有一定范围,称为 允许策略集合,用 P
表示，使整个问题达到最优效果的策略就是 最优策略 。如对于例 5.1 总共可有 18 个策略，但最优策略只有一个。
2009-7-30 7
四、状态转移方程在动态规划中，本阶段的状态往往是上阶段决策的结果。所以如果给定了第 k 阶段的状态 ks 和该阶段的决策 kU ( ks )，则第 k+1 段的状态 1+ks
由于 k 阶段决策的完成也就完全确定了,它们之间的关系可用如下公式表示：
1+ks ＝ kT （ ks,kU ）
其中,kT 表示从状态 ks 出发经过 kU 向下一阶段的转移 (Transfer),换言之,即 1+ks 是从状态 ks 出发经过决策 kU 转移的结果。
由于上式表示了由 k 段到第 k+1 段的状态转移规律，所以就称为 状态转移方程 。在例 5.1 中,状态转移方程即 1+ks ＝ kU 。
五、指标函数用于衡量所选定策略优劣的数量指标称作 指标函数 。 一个 n 阶段的决策过程,从 1 到 n 叫作问题的原过程,对于任意一个给定的 k(1 ≦ k≦ n),从 k
段到第 n 段称为原过程的一个 后部子过程,用 nV,1 (s1,nP,1 )表示初始状态为
s1采用策略 nP,1 时原过程的 效益值,用 nkV,（ ks,nkP,）表示在第 k 阶段状态
2009-7-30 8
为 ks 采用策略 nkP,时的后部子过程的效益值。 最优指标函数 记为 )( kk sf,
它表示从第 k 阶段的状态 ks 出发采用最优策略 *,nkp 到过程终止时的最佳效益值,于是有下面的关系式：
kf （ ks ）＝ nkV,（ ks,
*
,nkp ）＝ opt nkV,( ks,nkP,)
其中,opt 全称 optimization 即最优化，在最大化时用 max,在最小化时用
min。 kf （ ks ）也称作 k 阶段从状态 ks 出发时的 后部子过程的最佳效益值,
当 k=1 时,)( 11 sf 就是从初始状态 s1 到全过程结束的整体最优指标函数。
在例 5.1 中,指标函数就是距离。如在第 2 阶段,状态为 B2 时,V2,4(B2)
就表示从 B2 到 E 的可能距离,f2(B2)则表示从 B2 到 E 的最短距离。本问题的总目标是求 f1(A),即从 A 到 E 的最短距离 。
2009-7-30 9
为了求出例 5.1的最短路线,一个简单的方法是,可以求出所有从 A到 E的可能走法的路长并加以比较。不难知道,从 A到
E共有 18条不同的路线,每条路线有四个阶段,要做 3次加法,要求出最最短路线需做 54次加法运算和 17次比较运算,这叫做 穷举法 。不难理解,当问题的段数很多,各段的状态也很多时,这种方法的计算量会大大增加,甚至使得寻优成为不可能。
下面应用动态规划方法求解例 5.1。为了获得每一个后部子过程的最佳效益值,只能运用 逆序递推方法 求解,即由最后一段到第一段逐步求出各点到终点的最短路线,最后求出 A点到 E
点的最短路线。运用逆序递推方法的好处是可以始终盯住目标,不致脱离最终目标。例 5.1是一个四阶段决策问题,一般可分为四步：
第一步,从 k=4开始,状态变量 s4可取两种状态 D1,D2,它们到 E点的距离分别为 4和 3,这也就是由 D1和 D2到终点 E 的最短距离即 f4(D1)=4,f4(D2)=3。
5.1.3 最短路径问题的动态规划
2009-7-30 10
第二步,k=3,状态变量 s3 可取 3 个值即 C1,C2 和 C3,这是需经过一个中间站才能到达终点 E 的 二级决策问题 。 为方便应用，规定用 d( ks,kU )表示由状态 ks 出发,采用决策 kU 到达下一阶段 1+ks 时的两点距离。显然从 C1
到 E 有两条路线需加以比较,取其中最短的,即：
3f （ 1C ）＝ min
+
+
)(),(
)(),(
2421
1411
DfDCd
DfDCd =min
+
+
35
43
=7
这说明,由 C1到 E 的最短距离为 7,其路径为以 1C → 1D → E,相应的决策为 *3U （ 1C ） = 1D
3f （ 2C ）＝ min
+
+
)(),(
)(),(
2422
1412
DfDCd
DfDCd =min
+
+
32
46 =5
即从 C2 到 E 的最短距离为 5,其路径为 2C → 2D → E,相应的决策为
*
3U （ 2C ） = 2D
2009-7-30 11
3f （ 3C ）＝ min
+
+
)(),(
)(),(
2423
1413
DfDCd
DfDCd =min
+
+
33
41 |=5
即从 C3 到 E 的最短距离为 5,其路径为 C3→ D1→ E,相应的决策为
*
3U （ 3C ） = 1D 。
第三步,k=2,这是一个具有三个状态,要经过两个中间站才能到达终点的 三级决策问题 。由于第 3 段各点 C1,C2,C3 到终点 E 的最短距离 f3(C1),
f3(C2),f3(C3),已知,所以要求城市 B1 到 E 的最短距离,只需以它们为基础,
分别加上 B1 到达 C1,C2,C3 的一段距离,加以比较取其最短者即可。
)( 12 Bf =min
+
+
+
)(),(
)(),(
)(),(
3331
2321
1311
CfCBd
CfCBd
CfCBd
=min
+
+
+
55
54
76
=9
即 B1 到终点 E 的最短距离为 9,其路径为 B1→ C2→ D2→ E,本段的相应决策为 *2U （ 1B ） = 2C
2009-7-30 12
同理有,
)( 22 Bf =min
+
+
+
)(),(
)(),(
)(),(
3332
2322
1312
CfCBd
CfCBd
CfCBd
=min
+
+
+
56
57
78
=11
即 *2U （ 2B ）＝ 3C
)( 32 Bf =min
+
+
+
)(),(
)(),(
)(),(
3333
2323
1313
CfCBd
CfCBd
CfCBd
=min
+
+
+
59
58
77
=13
即 *2U （ 3B ）＝ 2C
第四步,k=1,只有一个状态点 A,则
)(1 Af =min
+
+
+
)(),(
)(),(
)(),(
333
232
121
BfBAd
BfBAd
BfBAd
=min
+
+
+
135
119
98
=17
即 *1U （ A）＝ 1B
2009-7-30 13
从城市 A 到城市 E 的最短距离为 17。把各段的最优决策按计算顺序反推,即得到最优决策序列,即 *1U （ A）＝ 1B,*2U （ 1B ） = 2C,*3U （ 2C ）
＝ 2D,*4U （ 2D ）＝ E，所以最短路线为,A→ B1→ C2→ D2→ E。
4
3
7
5
513
11
9
17
上述最优路线是通过计算最优指标函数得到的，可以称作指标函数法 。还可以采用在图上直接标记的方法求得，这种直接标记的方法可称作 图上作业法 （ Click to show）
这种方式使用起来更简单明了，最佳路线的确定方法也很容易 [f(sk)－ d(sk,sk+1)=f(sk+1)]，是一种值得推荐的方法。
（课堂练习参教材）
2009-7-30 14
在上述的求解过程中,各段的计算都利用了第 k 段和第 k+1 段的如下关系：
kf （ ks ）＝ min{ kd （ ks,kU ）＋ )( 11 ++ kk sf (k=4,3,2,1) (1)
)( 55 sf ＝ 0 (2)
这种递推关系称为 动态规划的基本方程,(2)式称边界条件,容易算出,
运用动态规划方法解例 5.1 只进行了 17 次加法运算,11 次比较运算，就获得了最优解,比穷举法的计算量明显地要少,而且随着问题段数的增加和变量数目的增多,计算量将呈指数规律减少。其次,动态规划的计算结果不仅得到了 A 到 E 的最短路线,而且得到了任意一点到 E 点的最优路线 。
这可由图 5.2 来描述 (用彩色线表示最优路线,各点上的数字表最短距离 )
图 5.2
2009-7-30 15
根据例 5.1,动态规划的基本思想 可总结如下：
一,将多阶段决策过程划分阶段,恰当地选取状态变量,决策变量和定义最优指标函数,从而把问题化成一族同类型的子问题,然后逐个求解 。
二,求解时总是从边界条件开始,沿过程行进方向,逐段递推寻优 。 在每一个子问题求解时,都要利用它前边已求出的子问题的最优结果 。 最后一个子问题的最优解,就是整个问题的最优解 。
三,动态规划方法是既把当前一段与未来各段分开,又把当前效益和未来效益结合起来考虑的一种最优化方法 。 因此,每段的最优策略的选取都是从全局考虑的,它与该段的最优选择是不同的 。
§ 5.2 动态规划的基本原理、模型和解法
5.2.1 最优化原理动态规划方法是由美国数学家贝尔曼 (R.Bellman)等人于本世纪 50
年代提出的 。 他们针对多阶段决策问题的特点,提出了解决这类问题的,最优化原理,,并成功地解决了生产管理,工程技术许多方面的实际问题 。
2009-7-30 16
最优化原理用反证法极易证明。 假定 sk 是由始点到终点的最短路 线上的一点,如果存在另一条最短路 ks 与终点相连,则这条最短路线 与 ks 以前的部分必构成全程的最短路线,这就与原策略为最短路线的假定相矛 盾。 所以,对于一个过程的最优策略而言,不管其初始状态和决策如何,其后 的任一决策都构成最优策略。 这也就是动态规划所以可以采用逆序递推法 寻优的依据。
如果把最优化原理用数学语言描述,就得到了 动态规划的基本方程,这就是,
kf （ ks ）＝ opt[ ])(),( 11 +++ kkkkk sfusd (k=n,n-1,…,1)
1+nf （ 1+ns ）＝ 0 其中,opt 可依题意取 max 或 min
最优化原理 可以表述为：,一个过程的最优策略具有这样的性质,
即无论初始状态和初始决策如何,对于先前决策所形成的状态而言,其以后的所有决策必构成最优策略,,
将这一基本原理应用于例 5.1的最短路线问题时可表述为：一方面,
一条路线如果是最短路线,则对于该线上的任何一点来说,最短路线以此点为起点的剩余部分,必然是从此点到终点的最短路线 。 另一方面,无论是从哪一段的哪一种状态出发,到终点 E的最短路线只与此状态有关,而与以前的状态路线无关,即并不受从 A点是如何到达这点的决策的影响 。
图 5.2中的 C2点可以清楚地证明这两种情况 。
2009-7-30 17
5.2.2 动态规划模型的建立建立动态规划的模型,就是分析问题并建立问题的动态规划基本方程。
成功地应用动态规划方法的 关键,在于识别问题的多阶段特征,将问题分解成可用递推关系式联系起来的若干子问题,或者说是 要正确地建立具体问题的基本方程,无疑这需要经验和技巧。 而正确地建立关于递推关系基本方程的关键，又在于 正确地选择状态变量,保证各阶段的状态变 量具有递推的状态转移关系 1+ks ＝ ),( kkk usT 。 这是 建立动态规划模型的两个基本要点。
下面举例来说明动态规划模型的建立。
例 5.2 生产与存储问题设某工厂生产并销售某种产品,已知每千件的 变动成本 为 1 万元,每季度生产的 固定成本 为 3 万元,经预测某一年四个季度中该产品的市场需求量分别为 2,3,2,4 千件,设该厂的最大生产能力是 6 千件,最大库容是 3 千件,每千件产品一个季度的存储费用为 0.5 万元,如果要求年初和年末该产品均无库存,问如何安排各季度的产量,才 能使全年的总费用最小。
2009-7-30 18
解,1,设阶段变量为 k,则每季度为一个阶段,k=1,2,3,4 。
2,每季度初的产品库存量可作为状态变量,由已知条件显然有 s1=s5=0 。
3,决策变量是每季度的产品生产量,由已知条件知,0≤ Uk ≤ 6,Uk 的单位为千件。
4,显然,状态转移方程由下式确定：
1+ks ＝ kkk dus -+
其中,kd 表示第 k 阶段的需 求量或销量。
即第 k+1 阶段的库存量就等于第 k 段的库存量加本段的生产量减去本段的需求量 (销售量 )。
5,指标函数本例的指标函数是生产与存储的总费用,最优指标函数是指生产与存储的总费用和最低。
第 k 段的指标即总费用为：
),( kkk usV ＝ 0.5 ks ＋ =
+
)0(0
)60(3
k
kk
u
uu
kV 的单位为万元。6,建立基本方程 （即成本最小化）
)](),([m i n)( 11 +++= kkkkkUkk sfusVsf
k
（ k=4,3,2,1）
0)( 55 =sf
5.2.3 动态规划模型的求解动态规划模型建立以后,对基本方程的分段求解,并不象线性 规 划那样有固定的解法,它需要根据具体问题的特 点,结合数学方法 灵 活求解。 在各种解法中,常用的对于离散变量的 分段穷举算法 是一 种基 本方法。
分段穷举法使用的前提 是,动态规划模型中的状态变量和决策变量均取离散值。 例 5.2 中最短路线的求解用的就是分段穷举法。 如果每段的状态变量和决策变量是离散的且取值数目较少,运用分段穷举法比一般问题使用的穷举法会更有效。 运用分段穷举法求最优指标函数值,最重要的是要正确确定每段状态变量的取值范围和允许的决策变量集合,一般使用表格形式进行。 下面以 例 5.2 的求解为例,对这种方法作以总结。
第一步,先考虑 k= 4,因为要求第四季度末库存为 0,即 s5=0,本季度需求为 4,所以据状态转移方程应有 44 4 su -=,由于库存量最大为 3,
所以 s4 的取值只能是 0,1,2,3。
根据 )](),(min[)( 5544444 sfusvsf +=,及 0)( 55 =sf,
444 35.0 usv ++=,可列出 4u 与 4f 如表 5.1。
2009-7-30 20
表 5.1 解例 5.2 的第 1 步
4s 0 1 2 3
)( 44 su 4 3 2 1
)( 44 sf 7 6.5 6 5.5
第二步,k=3 时,ks 的取值范围仍然是 }3,2,1,0{3 =s 。 根 据状态 转移方程,3433 ssdu -+=,因 23 =d,所以 343 2 ssu -+=,即在需求量一定的情况下,生产量由期末和期初的库存量决定。 由于 3u ≥ 0,所以有
34 ss - ≥ － 2,由 3u ≤ 6 有 34 ss - ≤ 4,于是 3u 的允许的取值范围是,－ 2
≤ 34 ss - ≤ 4，决策过 程过程如表 5.2：
44 4 su -=
)](),(min[)( 5544444 sfusvsf +=
444 35.0 usv ++=
2009-7-30 21
表 5.2 解例 5.2的第二步
s3 0 1 2 3
s4 0 1 2 3 0 1 2 3 0 1 2 3 1 2 3
u3(s3) 2 3 4 5 1 2 3 4 0 1 2 3 0 1 2
V3+f4 12 12.5 13 13.5 11.5 12 12.5 13 8 11.5 12 12.5 8 11.5 12
f3(s3) 12 11.5 8 8
u3*(s3) 2 1 0 0
第三步,当 k=2 时,状态变量 2s 的取值范围是 2s ={0,1,2,3},根据状态转移方程应有,2322 ssdu -+=,已知 2d ＝ 3，所以 根据232 3 ssu -+=
0≤ 2u ≤ 6，应有－ 3≤ 23 ss - ≤ 3,决策过程如表 5.3。
333 35.0 usv ++=343 2 ssu -+=
)](),(min[)( 4433333 sfusvsf +=
2009-7-30 22
表 5.3 解例 5.2 的第三步
s2 0 1 2 3
s3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
u2(s2) 3 4 5 6 2 3 4 5 1 2 3 4 0 1 2 3
V2+f3 18 18.5 16 17 17.5 18 15.5 16.5 17 17.5 15 16 13.5 17 14.5 15.5
f2( s2) 16 15.5 15 13.5
u2*(s2) 5 4 3 0
第四步,当 k=1 时,只有一种状态即 1s =0,根据 1211 ssdu -+=,有
21 2 su +=,由于 2s 最大为 3,即 1u 最大为 5,不超过最大生产能力 显,
然,1u 的允许集合是 1(s1)D ＝｛ 2,3,4,5｝因 11 3 uv += 所以,有：
232 3 ssu -+=
)](),(min[)( 3322222 sfusvsf +=
222 35.0 usv ++=
2009-7-30 23
21
5.138
157
5.156
165
min)( 11 =
+
+
+
+
=sf 即 )( 1*1 su ＝ 2
整个过程的最优计划可依状态方程即 1+=-+ kkkk sdus 确定，即当
1s ＝ 0,1u ＝ 2,1d ＝ 2 时,2s ＝ 0，在 表 5.3 中,2s ＝ 0 对应于
*
2u (s2)＝ 5
若 2s ＝ 0,2u ＝ 5,2d ＝ 3，则 2,3 =s 在 表 5.2 中,23 =s 对应于 )( 3*3 su ＝ 0;
)( 44 su ＝ 4。 即第一季度生产 2 千件。 第二 季度生产 5 千件。
第三季度不生产； 第四季度生产 4 千件。 全年生产 11 千件,总需求 11 千件,总费用 21 万元。
根据例 5.1 和例 5.2 的求解过程,运用 分段穷举法的要点 包括 (1)确定状态变量集合 ； (2)确定决策变量集合 kk sD ； (3)计算 ),( kkk usV ； (4)计算
)( kk sf ； (5)确定 )(* kk su
若 s3＝ 2,u3＝ 0,d3＝ 2，则 s4＝ 0，在 表 5.1中，对应于 s4＝ 0，有
2009-7-30 24
动态规划的求解除了运用逆序解法 (又称后向动态规划法 )外,还可以运用 顺序解法 (又称前向动态规划法 )。
前面所使用的动态规划解法,由于寻优的方向与多阶段决策过程的实际行进方向相反,是从最后一段开始计算逐段向前推进,最后求得全过程的最优策略，所以称为 逆序解法 。
与逆序法相反，顺序解法的寻优方向与过程的行进方向相同，求解时是从第一段开始计算逐段向后推进，计算后一阶段时要用到前一段求优的结果，最后一段的计算结果就是全过程的最优结果。
逆序解法和顺序解法都属于动态规划的基本解法。
下面仅以最短路线问题为例对顺序解法予以说明。
§ 5.3 前向动态规划法
5.3.1 顺序解法的基本思路
2009-7-30 25
在例 5.1中，当 k=0 时 0)()( 000 == Afsf,这是边界条件。
当 k=1 时,1s表示第一阶段的终点，其允许取值集合
},,{ 3211 BBBS =,于是有：
)( 11 Bf ＝ 8,)( 21 Bf ＝ 9,)( 31 Bf ＝ 5
ABu =)( 11,ABu =)( 21,ABu =)( 31
当 k=2 时,有
+
+
+
=
),()(
),()(
),()(
min)(
1331
1221
1111
12
CBdBf
CBdBf
CBdBf
cf ＝ 12
75
89
68
min =?
+
+
+
即 312 )( BCU =最短路线问题的顺序解法
5.3.2 最短路径问题的顺序解法
2009-7-30 26
+
+
+
=
),()(
),()(
),()(
min)(
2331
2221
2111
22
CBdBf
CBdBf
CBdBf
cf ＝ 12
85
79
48
min =
+
+
+
即 122 )( BCU =
+
+
+
=
),()(
),()(
),()(
min)(
3331
3221
3111
32
CBdBf
CBdBf
CBdBf
cf ＝ 13
95
69
58
min =
+
+
+
即 132 )( BCU =
当 k=3 时,有
+
+
+
=
),()(
),()(
),()(
min)(
1332
1222
1112
13
DCdCf
DCdCf
DCdCf
Df ＝ 14
113
612
312
min =
+
+
+
即 313 )( CDU =
2009-7-30 27
+
+
+
=
),()(
),()(
),()(
min)(
2332
2222
2112
23
DCdCf
DCdCf
DCdCf
Df ＝ 14
313
212
512
min =
+
+
+
即 223 )( CDU =
当 k=4 时,有
+
+=
),()(
),()(min)(
223
113
4 EDdDf
EDdDfEf ＝ 17
314
414min =
+
+
即 24 )( DEU =
将选定的决策变量按计算顺序反推即可得到决策序列 ｛ ku ｝，即最短路线为 24 )( DEu =,223 )( CDu =,122 )( BCu =,ABu =)( 11,即最短路线为 A→ B1→ C2→ D2→ E,最短距离为 17。其结果与逆序解法完全相同。
2009-7-30 28
一般地说，顺序解法与逆序解法在本质上没有什么不同,通常情况下，
当初始状态给定时用逆序解法较方便,当终止状态给定时用顺序解法较方便。
但若初始状态虽已给定，然而 终点状态较多,需比较到达不同终点状态的各个路径及指标函数值,以选取总效益最佳的终点状态时,以 使用顺序解法比较方便。 另外,在初始状态和终止状态均为已知，但当使用不同方法第一步需处理的状态不同时，以选择第一步需处理较多状态的方法为比较合适,这样可以减少运算工作量，如例 5.1 采用顺序法只需作 17 次加法运算,比逆序法要少一次。总之,针对问题的不同特点,灵活地选用这两种方法之一,可以使求解过程简化。
在使用这两种方法求解时，除了求解时的行进方向不同外，在建模时还需要注意以下区别：
1,状态变量的含义不同在逆序解法中,状态变量 ks 是第 k 段的出发点；而在顺序解法中,ks
则是第 k 段的终点。
5.3.3 顺序解法与逆序解法的异同
2009-7-30 29
2.决策过程和结果不同在逆序解法中,每一段的决策是对于给定的出发点选择符合要求的终点,也就是说在逆序解法中决策过程是顺序的；而在顺序解法中,每一段的决策则是对于给定的终点选择符合要求的出发点,也就是说在顺序解法中,
决策过程逆序的。
逆序法得到的结果，是每一点到终点的最短路线和距离；顺序法得到的结果,是起点到每一点的最短路线和距离，如图 5.3。
3.状态转移方式不同在逆序解法中，如 图 5.4，第 k 段的输入状态为 ks,决策为 kU,由此决定输出为 1+kS,所以状态转移方程为：
1+kS ＝ kT （ ks,kU ）
该方程称之为状态 ks 到 1+kS 的顺序转移方程。
图 5.3
2009-7-30 30
图 5.4 逆序解法的决策过程而在顺序解法中，如图 5.5,第 k 段的输入状态为 ks,决策为 kU,由此确定的输出则为 1-kS,所以状态转移方程为：
1-kS ＝ kT （ ks,kU ） 该方程称作状态 ks 到 1-kS 的逆序转移方程。
图 5.5 顺序解法的决策过程
2009-7-30 31
4,指标函数的定义不同在逆序解法中,最优指标函数 )( Kk Sf 定义为第 K 段从状态 ks 出发,到过程终点的后部子过程的最优效益值,)( 11 Sf 是整体最优函数值。
在顺序解法中,最优指标函数 )( Kk Sf 定义为第 K 段从状态 ks 回返,到过程始点的前部子过程的最优效益值,)( nn Sf 是整体最优函数值。
5,基本方程形式不同在逆序解法中,）j
n
kj
jnk usVV,(,?
=
=,基本方程为：
-==
+=
++
++
1,2,...,1,0)(
)}(),({)(
11
11
nnksf
sfusVoptsf
nn
kkkkkkk
在顺序解法中,）j
k
j
jk usVV,(
1
,1?
=
=,基本方程为：
==
+= --
nksf
usVsfoptsf kkkkkkk
,...,2,10)(
)},()({)(
00
11
2009-7-30 32
一、应用之一 —— 投资问题设总投资额为 a 万元,拟投资于 n个项目上，已知对第 i 个 项目投资 ix 万元,收益函数为 )( ii xg,问应如何分配资金才可以使总收益最大?
这是一个与时间无明显关系的静态最优化问题,可先列出其静态模型为：
maxV＝?
=
n
i
ii xg
1
)(
s.t,ax
n
i
i
=1
0?ix (i=1,2,…,n)
为了应用动态规划方法求解,我们可以人为地赋予它“时段”的概念。 方法是将投资项目排序,假想对各个投资项目有先后顺序。 首先考虑对项 目 1 的投资,然后考虑对项目 2 的投资,依次最后考虑第 n 项投 资,这样就 把原问题转化为 n 阶段的决策过程。 接下来的问题，便是如何 选择正确的 状态变量,并使各后部子过程间具有递推关系。
§ 5.4 动态规划的应用
2009-7-30 33
1,状态变量 ks,表示第 K 段可用于剩余的 n-k+1 个项目的资金数,
显 然有 1s =a,1+ns =0。
2,决策变量 ku,即应分配第 K 个项目上的投资额。
3,状态转移方程,kkk uss -=+1
4,指标函数,?
=
=
n
ki
ii ugV nk )(,
最优指标函数 kf （ ks ）：表示当可投资金数为 ks 时,投资于剩余的
n-k+1 个项目的最大收益。
5,基本方程为：
=
+=
++
++
0)(
)]()(max[)(
11
11
nn
kkkkkk
sf
sfugsf k=n,n-1,…,2,1
如果运用逆序递推寻优,则 )(1 af 就是所求的最大收益。
2009-7-30 34
例 5.3 某企业共有设备 4 台,拟分给三个车间,各车间利用这些设备为企业可提供的盈利 kk (u )g 各不相同 (资料见表 4.4),问应如何分配这四台设备才能使企业获得的盈利最大?
表 5.4 例 5.3 的有关资料解：该问题与上述的资源分配问题 (即投资分配问题 )具有完全相同的模型，
因初始状态 S1=4 为已知，故可 运用逆序解法，在这里 n=3,a=4。
设备分配数 )(
11 ug )( 22 ug )( 33 ug
0
1
2
3
4
0
4
6
7
7
0
2
5
6
8
0
3
5
7
8
一车间 二车间 三车间单位：万元
2009-7-30 35
当 k=3 时,状态变量 3s 的取值范围为 3s ＝ ｛ 0,1,2,3,4｝，同样
3u 的取值范围也是 3D ＝ ｛ 0,1,2,3,4｝,根据 334 uss -=,04 =s,
即 33 su =,即 0)( 44 =sf,依基本方程可列出 K=3 时的结果如表 4.5
表 5.5 例 5.3 k=3 时的结果说明：因本段是最后一个阶段，
所以每状态只与一个变量对应。
当 k=2 时,状态变量的取值范围为 2s ＝ ｛ 0,1,2,3,4｝，根据
223 uss -= 即 322 ssu -= 和基本方程，可得表 4.6(注意条件 u>0)。
3s 0 1 2 3 4
3u 0 1 2 3 4
3f 0 3 5 7 8
2009-7-30 36
表 5.6 例 5.4 当 k=2 时的结果
2s
3s
2u
2v
)( 33 sf
)( 22 sf
*
2u
0
0
0
0
0
0
0
1
1 0
0 1
0 2
3 0
(3) 2
0
2
2 1 0
0 1 2
0 2 5
5 3 0
5 5 5
0 1 2
3
3 2 1 0
0 1 2 3
0 2 5 6
7 5 3 0
7 7 （ 8） 6
2
4
4 3 2 1 0
0 1 2 3 4
0 2 5 6 8
8 7 5 3 0
8 9 （ 10） 9 8
2
223 uss -=322
ssu -=
2009-7-30 37
当 K = 1 时,
1
s 的取值是
1
s ＝ 4,
1
u 的取值范围是
1
D ＝ ｛ 0,1,2,3,4 ｝，
根据
112
uss -= （即
21
4 su -= ）和基本方程，有：
12
07
37
56
84
100
m ax)4(
1
=
+
+
+
+
+
=f 即 1)(
1
*
1
=su
根据状态转移方程,若 =1,=4，则 =3；
在表 5.6中,=3时 ＝ 2,这时 ＝ 1；在表 5.5中,若 ＝ 1,则
=1。于是最优决策是分配 1车间 1台设备,2车间 2台设备,3车间
1台设备,得最大利润 12个单位。
kkk uss -=+ 1 *1u 1s 2
s
2s *2u 3s 3s
*3u
2009-7-30 38
对于投资问题的上述解法可称作 详表解法,虽然看起来比较清楚，但显得有些繁琐。因此，在掌握规律后可采用 简表解法,借助于辅助线同样也很清楚。现运用上述的设备分配问题，
对简表解法予以说明。
表 5.7 设备分配问题简表
éè ±? k ￡? 1 k ￡? 2 k ￡? 3
· êy g 1 ( x 1 ) f 1 ( s 1 ) g 2 ( x 2 ) f 2 ( s 2 ) g 3 ( x 3 ) f 3 ( s 3 )
0 0 0 0 0
1 4 12 2 3 3
2 6 5 5 5
3 7 6 8 7
4 7 8 10 8
U * u 1* =1 u 2* =2 u 3* =1
在使用 逆序方法求解 时，第 n－ 1以后各段，必须注意决策变量的允许集合。最后一步即第 1段的最优指标函数写在取得最优值的相应行。最优决策的寻找方法类似于最短路径问题的 图上作业法,即 fi(si)－ vi(si)＝ f i+1(s i+1)，但有时需分析。
2009-7-30 39
运用简表法求解较大规模的问题具有很大的优越性。如在下面的投资分配问题中，共有 6个单位的资源和 4个方案，各个方案在不同投资数量条件下的收益不同，试确定最佳投资方案。
í? ×ê k ￡? 1 k ￡? 2 k ￡? 3 k ￡? 4
· êy g 1 ( x 1 ) f 1 ( s 1 ) g 2 ( x 2 ) f 2 ( s 2 ) g 3 ( x 3 ) f 3 ( s 3 ) g 4 ( x 4 ) f 4 ( s 4 )
0 0 0 0 0
1 20 30 50 40
2 80 50 70 60
3 100 70 100 80
4 120 90 110 100
5 130 120 110 110
6 100 130 110 120
0 0
50 50
220 90 90
220 120 110
140 140
170 160
190 180
（ Click to show answer）
这种方法同样适用于求最小化问题。如某房地产公司拟在三个不同地区建造 5栋商住楼，已知在不同地区建造商住楼所需的投资不同，有关资料如下表，试求一个投资费用最低的投资方案。
2009-7-30 40
¨?ì k ￡? 1 k ￡? 2 k ￡? 3
￥?ì êy g 1( x 1) f 1( s 1) g 2( x 2) f 2( s 2) g 3( x 3) f 3( s 3)
0 0 0 0
1 210 150 160
2 400 360 370
3 520 500 520
4 800 730 740
5 950 1000 900
0
150
310
830 500
660
870
这种简表法的基本思路是由北京经济管理干部学院的赵景文教授首先提出来的，感兴趣的同学可以在中国数据期刊网上下载,用动态规划解设点问题,一文阅读。
正确使用这种简表法的前提是，必须熟悉最短路径问题的分段穷举法和投资分配问题的详表解法。
2009-7-30 41
背包问题是动态规划的典型问题。一维背包问题的典型提法是：一位旅行者能承受的背包最大重量是 b 千克，现有 n 种物品供他选择装入背包，第 i 种物品单件重量为
i
a 千克，其价值 ( 或重要性参数 ) 为 c
i
，总价值是携带数量
i
x 的函数即
ii
xc,问旅行者应如何选择所携带物品的件数以使总价值最大?
背包问题实际上就是运输问题中车船的最优配载问题,还可以广泛地用于解决其它的问题。其一般的整数规划可表述为：
=
=
n
i
ii
xcz
1
m ax
s,t,bxa
n
i
ii
= 1
0?
i
x
且为整数 （ i= 1,2,…,n ）
二、动态规划的应用之二－－背包问题
2009-7-30 42
下面用动态规划方法来求解：
1,阶段 k：即需要装入的 n 种物品的次序,每段装入一种,共 n 段。
2,状态变量 ks,即在第 k 段开始时,允许装入前 k 种物品的总重量，显然有 ns =b,因 ns 已知故可采用顺序解法。
3,决策变量 kx,即装入第 k 种物品的件数
4,状态转移方程,kkkk xass -=-1
允许的决策集合是：
=
k
k
kkkk a
sxxsD 0|)( 且为整数
5,基本方程是,
{ }
==
-+= -
nksf
xasfxcsf kkkkkkkk
,...,2,10)(
)(max)(
00
1
2009-7-30 43
例 5.4 一贩运商拟用一 10 吨载重量的大卡车装载 3 种货物,有资料如下表,问应如何组织装载,可使总价值最大?
解,设装载每一种货物的件数为 ix,则有：
maxz=4 1x +5 2x +6 3x
s.t,3 1x +4 2x +5 3x ≤ 10
0?ix 且为整数用动态规划方法的顺序解法求解，则当 k=1 时,{ }1
30
11 4)( max
11
11
xsf
x
sx
为整数
=
货物编号 1 2 3
单位重量 （吨）
单位价值
3 4 5
4 5 6
2009-7-30 44
这是一个简单的线性规划问题,0 13x 1s 即 30 11 sx,因线性规划的最大值只能在极点取得,于是有 { } )3(44max)( 11]3[011
11
sIntxsf
sx
==
计算结果可列入下表,
1s 0 1 2 3 4 5 6 7 8 9 10
1x 0 0 0 1 1 1 2 2 2 3
3
)( 11 sf 0 0 0 4 4 4 8 8 8 12 12
当 k=2 时,?
+-=
2221
]4[0
22 5)4(max)(
1
2
2
xxsfsf
ssx
计算结果如下表：
2009-7-30 45
S2 0 1 2 3 4 5 6 7 8 9 10
x2 0 0 0 0 0 1 0 1 0 1 0 1 0 1 2 0 1 2 0 1 2
V2 0 0 0 0 0 5 0 5 0 5 0 5 0 5 10 0 5 10 0 5 10
f1+V2 0 0 0 4 4 5 4 5 8 5 8 9 8 9 10 12 9 10 12 13 10
f2(s2) 0 0 0 4 5 5 8 9 10 12 13
x2* 0 0 0 0 1 1 0 1 2 0 1
+-=
2221
]4[0
22 5)4(max)(
1
2
2
xxsfsf
ssx
V2 ＝ 5x2
2009-7-30 46
当 k=3 时,因 3s =10,故 2s =10-5 3x,5x3≤ s3 即 x3≤ 2，所以
3f （ 10） = max 20
3x
{ 2f (10-5 3x )+6 3x
= max
2,1,03=x
{ 2f (10-5 3x )+6 3x
= max{ 2f (10),2f (5)+6,2f (0)+12}
=max{13,5+6,0+12}=13
即 *3x =0,依状态转移方程反推,此时有 2s =10,当 2s =10 时,依第 2 段计算结果 *2x =1，当 2x =1,2s =10 时,依 1s = 2s -4 2x 有 1s =6,由第一段计算结果知,当 1s =6 时,*1x =2.即最优方案为,*1x =2,*2x =1,*3x =0,最大价值为 13。
}
}
2009-7-30 47
本章应完成作业,
p203－ 1。 P204－ 4。
§ 5.5 运用 QSB解动态规划问题动态规划的应用范围很广，各种问题的模型结构都不完全相同，因而解法也各有千秋。ＱＳＢ主要设计了三类动态规划问题的解法，即：（１） Stagecoach Problem（最短路径或车马驿站问题 ） ；（２） Knapsach Problem（ 背包问题） ；（３）
Production and Inventory Control Problem（ 生产与存储问题）。
1,最短路径问题演示
2,背包问题演示
3,生产与存储问题
