文档介绍：第九章动态规划 Dynamic programming
§1 多阶段决策过程最优化问题举例
§2 基本概念、基本方程与最优化原理
§3 动态规划的应用
1
动态规划是解决多阶段决策过程的最优化问题的一种方法。所谓多阶段决策过程是指这样的一类决策问题,由于它的特殊性,我们可以按时间、空间等标识把它分为很多阶段,每一阶段都需作出决策,使得整个过程达到最优。动态规划方法把这种困难的多阶段决策问题变成一系列互相联系较容易的单阶段问题,解决了这一系列较容易的单阶段问题,也就解决了这一困难的多阶段决策问题。
2
根据时间参量是离散的还是连续的变量,可以把动态规划的模型分为离散决策过程和连续决策过程;根据决策过程的演变是确定性的还是随机性的,动态规划又可以分为确定性的决策过程和随机性的决策过程。组合起来就有四种决策过程。
离散确定性离散随机性
连续确定性连续随机性
3
本章主要介绍离散确定性的决策过程。
用动态规划可以解决管理中的: 最短路问题、
装载问题、库存问题、资源分配问题、生产过程最优化问题、随机型采购问题等。
我们首先以最短路径问题为例,借以说明动态规划的特点、求解方法以及它的基本概念、基本方程与最优化原理等。
4
§1 多阶段决策过程最优化问题举例
例 1. 最短路径问题
图 1 表示从起点 A 到终点 E 之间各点的距离。求从 A 到 E 的最短路径。
图 1
5
我们可以用穷举法计算这个问题,但其计算量为:从 A 到 E 有 3 个中间站点,除 D 站有 2 个位置之外,B、C 每站都有 3 个位置,因此,从 A 到 E 总共有 3×3×2 =18 条路径;计算各路径长度共要进行 3×18 = 54 次加法,和 18 –1 =17 次比较。
随着中间站点个数的增加,需要进行的加法和比较的次数将迅速增加。
例如,设从 A 到 E 的中间站点的个数有 k 个,除最后一个中间站点有 2 个位置之外,其余每个中间站点都有 3 个位置,则从 A 到 E 总共有3 k-1×2 条
6
路径;计算各条路径长度总共要进行 k 3 k-1×2 次加法,以及 3 k-1×2 -1 次比较。
如果 k = 20,则加法次数为
×1015 次,
比较次数为
×1014 次。
即使用 1 亿次/秒的计算机计算,也需要约 508 天。因此,用穷举法计算这样的问题通常是不可行。
7
B
A
C
B
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
0
5
2
8
7
12
20
14
19
19
图 2
用标号法求解:
8
将上述标号法求解的步骤小结如下:(逆序递推)
第五阶段:
记从 E 到 E 的最短路径为 f5(E),显然 f5(E)=0。
第四阶段:
记从 Di 到 E 的最短路径为 f4(Di)(i =1, 2),则
f4(D1) = 5 + f5(E) = 5 + 0 = 5, D1 E
f4(D2) = 2 + f5(E) = 2 + 0 = 2, D2 E
9
第三阶段:
记从 Ci 到 E 的最短路径为 f3(Ci)(i =1, 2, 3),则
10