10第十章动态规划.pptx

管理运筹学
第十章动态规划
§ 0
前言
动态规划是解决多阶段决策过程最优化问题的一种方法。它将困难的多阶段决策问题变换成一系列互相联系较容易的单阶段问题,解决了这一系列较容易的单阶段问题,也就解决了复杂的多阶段决策问题。
可以解决管理中的问题:最短路问题、装载问题、库存问题、资源分配问题、生产过程最优化问题等
§ 0
前言
按时间变量是离散还是连续,可将动态规划分为离散决策过程和连续决策过程;
根据决策过程的演变是确定性的还是随机的,又可分为确定性的决策过程和随机性的决策过程,
组合起来就有离散确定、离散随机、连续确定、连续随机四种决策过程。
本章主要介绍离散确定性过程。
多阶段决策过程最优化问题举例
基本概念、基本方程与最优化原理
动态规划的应用(1)
动态规划的应用(2)
本章内容
2
3
4
1
多阶段决策过程最优化问题举例
例1 最短路径问题
下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。
B
A
C
B
D
B
C
D
E
C
4
1
2
3
1
2
3
1
2
3
2
2
1
6
4
7
2
4
8
3
8
6
7
5
6
1
10
6
3
7
5
1
§ 1
用穷举法的计算量:
如果从A到E的站点有k个,包括A、E两个站点,除A、
E之外每站有3个位置则总共有3k-2条路径;
计算各路径长度总共要进行(k-1) 3k-2次加法以及
3k-2-1次比较。随着 k 的值增加时,需要进行的加法和比较
的次数将迅速增加;
例如当 k=20时,要做七亿二千五百多万次加法,
要做三千八百多万次比较。
§1 多阶段决策过程最优化问题举例
讨论:
以上求从A到E的最短路径问题,可以转化为四个性质完全相同,但规模较小的子问题,即分别从Di 、Ci、Bi、A到E的最短路径问题。
§ 1
§1 多阶段决策过程最优化问题举例
第四阶段:
两个始点D1和D2,终点只有一个;

分析得知:从D1和D2到E的最短路径唯一。
本阶段始点
(状态)
本阶段各终点(决策)
到E的最短距离
本阶段最优终点
(最优决策)
E
D1
D2
10
6
10
6
E
E
§ 1
第三阶段:
有三个始点C1,C2,C3,终点有D1,D2,分别求C1,C2,C3经D1,D2 到E的最短路径问题:

分析得知:如果经过C1,则最短路为C1-D2-E;
如果经过C2,则最短路为C2-D2-E;
如果经过C3,则最短路为C3-D1-E。
多阶段决策过程最优化问题举例
本阶段始点
(状态)
本阶段各终点(决策)
到E的最短距离
本阶段最优终点
(最优决策)
D1
D2
C1
C2
C3
8+10=18
7+10=17
1+10=11
6+6=12
5+6=11
6+6=12
12 11 11
D2
D2
D1
§ 1
第二阶段:
始点B1,B2,B3,B4,终点C1,C2,C3,分别求B1,B2,B3,B4经C1,C2,C3到E的最短路径问题:

分析得知:如果经过B1,则走B1-C2-D2-E;
如果经过B2,则走B2-C3-D1-E;
如果经过B3,则走B3-C3-D1-E;
如果经过B4,则走B4-C3-D1-E。
本阶段始点
(状态)
本阶段各终点(决策)
到E的最短距离
本阶段最优终点(最优决策)
C1
C2
C3
B1
B2
B3
B4
2+12=14
4+12=16
4+12=16
7+12=19
1+11=12
7+11=18
8+11=19
5+11=16
6+11=17
2+11=13
3+11=14
1+11=12
12
13
14
12
C2
C3
C3
C3
§ 1
多阶段决策过程最优化问题举例