文档介绍：第四章动态规划
(Dynamic Programming)
重点:
理解动态规划基本概念、最优化原理和基本方程;
通过资源分配、生产与存储和设备更新等问题,学****应用动态规划解决多阶段决策问题;
重点掌握动态规划模型结构、逆序算法原理、资源分配问题、生产与存储问题。
难点为动态规划中状态变量、基本方程等的确定。
动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于,它可以把一个多阶段决策问题变换为几个相互联系的单阶段最优化问题,从而一个一个地去解决。
需指出:动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种算法。必须对具体问题进行具体分析,运用动态规划的原理和方法,划分阶段,建立相应的模型,然后再去求解。
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
E3
F1
F2
G
5
3
1
3
6
8
7
6
6
8
3
5
3
3
8
4
2
2
1
2
3
3
3
5
5
2
6
6
4
3
1
2
3
4
5
6
引例:
图中所示为从A到G的路线网络,图中数字表示相应线路的长度,如何求出从A到G的最短路线?
(穷举法48条路线)
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
E3
F1
F2
G
5
3
1
3
6
8
7
6
6
8
3
5
3
3
8
4
2
2
1
2
3
3
3
5
5
2
6
6
3
1
2
3
4
5
6
3
7
5
9
7
6
8
13
10
9
12
13
16
18
4
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
E3
F1
F2
G
5
3
1
3
6
8
7
6
6
8
3
5
3
3
8
4
2
2
1
2
3
3
3
5
5
2
6
6
3
1
2
3
4
5
6
15
13
13
15
11
13
13
6
8
10
9
5
3
18
17
4
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
E3
F1
F2
G
4
5
3
1
3
6
8
7
6
6
8
3
5
3
3
8
2
2
1
2
3
3
3
5
5
2
6
6
4
3
1
2
3
4
5
6
最短路的特性:
如果已有从起点到终点的一条最短路,那么从最短路线上中间任何一点出发到终点的路线仍然是最短路。(证明用反证法)
§1 动态规划的研究对象和引例
动态系统:
包含随时间变化的因素和变量的系统。
动态决策问题:
系统所处的状态和时刻是进行决策的重要因素。
找到不同时刻的最优决策以及整个过程的最优策略。
1
2
n
状态
决策
状态
决策
状态
状态
决策
全过程的最优
阶段
1、生产决策问题
企业在生产过程中,由于需求是随时间变化的,因此企业为了获得全年的最佳生产效益,就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。
多阶段决策问题的典型例子
2、机器负荷分配问题
某种机器
高负荷
低负荷
g=g(u1)
产品的年产量
投入生产的机器数量
机器的年完好率为a ,0<a<1
h=h(u2)
机器的年完好率为b ,0< b<1
年终完好的机器?
假定开始生产时完好的机器数量为s1。要求制定一个n年计划,在每年开始时,决定如何重新分配完好的机器在两种不同的负荷下生产的数量,使在n年内产品的总产量达到最高。
3、线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念,应用动态规划方法加以解决。
不包含时间因素的静态决策问题(一次决策问题)也可以适当地引入阶段的概念,作为多阶段的决策问题用动态规划方法来解决。
4、最短路问题(引例):给定一个交通网络图如前,其中两点之间的数字表示距离(或花费),试求从A点到G点的最短距离(总费用最小)。