17
2
12
B1
10
14
C1 3
9
D1 5
6
A
5 B2 10
1
4
13
6
C2 5
8
E
2
D2
B3
12 11
C3 10
考虑经过 C3 的两条路线
f3(C3 )
d mind
(C (C
3 3
, ,
D1 ) D2 )
f4(D1 ) f4(D2 )
8 5 min10 2
12
(最短路线为 C 3 D2 E )
问题：如何确定各工厂的资金数，使得总的利润为最大。
据此，有下式：
n
max z gi ( xi )
i 1
n
xi a i1 xi 0 i 1.2. .n
27
令：fk(x) 表示 以数量为 x 的资金分配给前k 个工厂，所 得到的最大利润值。
用动态规划求解，就是求 fn(a) 的问题。
7
动态规划基本步骤
找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优
解。
8
最短路径问题：给定一个交通网络图如下，其中两点之间 的数字表示距离（或运费），试求从A点到G点的最短距离 （总运输费用最小）。
5 A
3
1
1 B1 3
1 19
(最短路线为 A B2 C1 D1 E )
（最短距离为19）
22
动态规划是用来解决多阶段决策过程最优化的一种数量 方法。其特点在于，它可以把一个n 维决策问题变换为几个 一维最优化问题，从而一个一个地去解决。
需指出：动态规划是求解某类问题的一种方法，是考察 问题的一种途径，而不是一种算法。必须对具体问题进行具 体分析，运用动态规划的原理和方法，建立相应的模型，然 后再用动态规划方法去求解。
因而也就决定了整个过程的一条活动路线，这样的一 个前后关联具有链状结构的多阶段过程就称为多阶段 决策问题。
12
针对多阶段决策过程的最优化问题，美国数学家Bellman等 人在20世纪50年代初提出了著名的最优化原理，把多阶段 决策问题转化为一系列单阶段最优化问题，从而逐个求解， 创立了解决这类过程优化问题的新方法：动态规划。
T(n)
=n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
5
算法总体思想
但是经分解得到的子问题往往不是互相独立的。不同子问题的 数目常常只有多项式量级。在用分治法求解时，有些子问题被 重复计算了许多次。
T(n)
=n
n/2
n/2
n/2
n/2
T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4
6 8
f2 (B2 ) mind(B2 ,C2 ) f4 (C2 ) min10 7 14
d (B2 , C3 ) f4 (C3 )
4 12
(最短路线为 B2 C1 D1 E )
20
2
12
B1
10
14
C1 3
9
D1 5
6
A
5 B2 10
1
4
13
6
C2 5
8
E
2
D2
B3
12 11
11
多阶段决策过程的特点：
• 根据过程的特性可以将过程按空间、时间等标志分为
若干个互相联系又互相区别的阶段。
• 在每一个阶段都需要做出决策，从而使整个过程达到
最好的效果。
• 各个阶段决策的选取不是任意确定的，它依赖于当前
面临的状态，又影响以后的发展。
• 当各个阶段的决策确定后，就组成了一个决策序列，
Bellman在1957年出版的《Dynamic Programming》是动 态规划领域的第一本著作。
对最佳路径（最佳决策过程）所经过的各个阶段，其中每 个阶段始点到全过程终点的路径，必定是该阶段始点到全 过程终点的一切可能路径中的最佳路径（最优决策），这 就是Bellman提出的著名的最优化原理。
25
动态规划求解的多阶段问题的特点：
• 每个阶段的最优决策过程只与本阶段的初始状态有关， 而与以前各阶段的决策（即为了到达本阶段的初始状态 而采用哪组决策路线无关）。换言之，本阶段之前的状 态与决策，只是通过系统在本阶段所处的初始状态来影 响本阶段及以后各个阶段的决策。或者说，系统过程的 历史只能通过系统现阶段的状态去影响系统的未来。
9
D1 5
6
A
5 B2 10
1
4
13
6
C2 5
8
E
2
D2
B3
12 11
C3 10
第三阶段（C →D）： C 到D 有 6 条路线。
首先考虑经过 C1 的两条路线
f3(C1 )
d mind
(C1 (C1
, ,
D1 ) D2 )
ff44((DD12))
3 min9
5 2
8
(最短路线为 C1 D1 E )
6
算法总体思想
如果能够保存已解决的子问题的答案，而在需要时再找出已求 得的答案，就可以避免大量重复计算，从而得到多项式时间算 法。
T(n)
=n
n/2
n/2
n/2
n/2
T(n/4) T(n/4)
T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n/4)
16
2
12
B1
10
14
C1 3
9
D1 5
6
A
5 B2 10
1
4
13
6
C2 5
8
E
2
D2
B3
12 11
C3 10
考虑经过 C2 的两条路线
f3(C2 )
d mind
(C (C
2 2
, ,
D1 ) D2 )
f4 (D1 ) f4(D2 )
6 min5
5 2
7
(最短路线为 C2 D2 E )
18
2
12
B1
10
14
C1 3
9
D1 5
6
A
5 B2 10
1
4
13
6
C2 5
8
E
2
D2
B3
12 11
C3 10
第二阶段（B →C）： B 到C 有 9 条路线。
首先考虑经过 B1 的3条路线
d (B1 , C1 ) f3 (C1 )
12 8
f2 (B1 ) mind (B1 , C2 )
f3 (C2 ) min14 7
20
d (B1 , C3 ) f3 (C3 )
10 12
(最短路线为 B1 C1 D1 E )
19
2
12
B1
10
14
C1 3
9
D1 5
6A5 B2 10 Nhomakorabea1
4
13
6
C2 5
8
E
2
D2
B3
12 11
C3 10
考虑经过 B2 的3条路线
d (B2 , C1 ) f4 (C1 )
3
动态规划是运筹学的一个分支，是求解多阶段决策过 程最优化问题的数学方法。
动态规划在经济管理、工程技术、工农业生产及军事 部门中都有着广泛的应用，并且获得了显著的效果。
学习动态规划，我们首先要了解多阶段决策问题。
4
算法总体思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分 解成若干个子问题
• 具有这种性质的状态称为无后效性（即马尔科夫性）状 态。
• 动态规划方法只适用于求解具有无后效性状态的多阶段 决策问题。
26
三. 投资分配问题
现有数量为a（万元）的资金，计划分配给n 个工厂,用 于扩大再生产。
假设：xi 为分配给第i 个工厂的资金数量（万元）；gi(xi) 为第i 个工厂得到资金后提供的利润值（万元）。
当 k=1 时， f1(x) = g1(x) （因为只给一个工厂）
动态决策问题的特点：
系统所处的状态和时刻是进行决策的重要因素； 即在系统发展的不同时刻（或阶段）根据系统所处的状 态，不断地做出决策；
找到不同时刻的最优决策以及整个过程的最优策略。
23
动态规划方法的关键：在于正确地写出基本的递推关 系式和恰当的边界条件（简称基本方程）。
要做到这一点，就必须将问题的过程分成几个相互联 系的阶段，恰当的选取状态变量和决策变量及定义最优值 函数，从而把一个大问题转化成一组同类型的子问题，然 后逐个求解。
机器负荷分配问题：某种机器可以在高低两种不同的负荷 下进行生产。要求制定一个五年计划，在每年开始时，决 定如何重新分配完好的机器在两种不同的负荷下生产的数 量，使在五年内产品的总产量达到最高。
航天飞机飞行控制问题：由于航天飞机的运动的环境是不 断变化的，因此就要根据航天飞机飞行在不同环境中的情 况，不断地决定航天飞机的飞行方向和速度（状态），使 之能最省燃料和完成飞行任务（如软着陆）。
简言之， 一个最优策略的子策略必然也是最优的
13
二. 最短路径问题
例1、从A 地到E 地要铺设一条煤气管道,其中需经过三级
中间站，两点之间的连线上的数字表示距离，如图所示。 问应该选择什么路线，使总距离最短？