文档介绍：动态规划
在实践中,人们常常会遇到这样决策问题,由于过程的特殊性,可以将决策的全过程依据时间和空间划分为若干个相互联系的阶段。动态规划方法的关键是将多阶段的决策问题变换成一系列的单阶段问题,并逐一解决。
什么是动态规划?
这类决策问题,属于运筹学的又一个重要分支,是一种多阶段决策过程最优化问题,称为动态规划(Dynamic programming)问题。
动态规划在工程技术、企业管理、工农业生产及军事等部门都有广泛的应用。
动态规划不是一个具体的算法,而是求解某类问题的一种方法,考察问题的一种途径。必需对具体问题运用动态规划的原理和方法进行具体分析,因此解题时,要有丰富的想象力去建立模型,灵活的技巧去求解。
动态规划方法的关键是将多阶段的决策问题变换成一系列的单阶段问题,并逐一求解。
什么是动态规划?
【例1】先看一个最优化的例子: 最短路线问题--–选择线路网络中由A到G的线路,使总距离(或总费用)最少?
A
B1
B2
C1
C3
C4
C2
D1
E1
F1
G
D2
D3
E2
E3
F2
5
3
1
3
6
6
8
7
6
6
6
3
3
3
3
3
3
3
8
5
5
8
4
4
2
2
2
2
1
5
共有2×3×2×2×2×1 = 48 条路线可供选择
什么是动态规划?
向后递推—每阶段各节点到 G 点的最短距离
A
B1
B2
C1
C3
C4
C2
D1
E1
F1
G
D2
D3
E2
E3
F2
5
3
1
3
6
6
8
7
6
6
6
3
3
3
3
3
3
3
8
5
5
8
4
4
2
2
2
2
1
5
回代:A → B1 → C2 → D1 → E2 → F2 → G
4
3
7
5
9
7
6
8
13
10
9
12
13
16
18
【例2】机器负荷分配问题
某种机器可以在高低两种负荷下进行生产,在高负荷下生产的机器数量为 x ,产品的年产量为 gx ,机器的完好率为 a (0 < a < 1);投产低负荷的机器数量 y ,年产量为 h y,相应的完好率为 b (a < b < 1) 。
刚开始生产时,完好的机器数量为 s1,要制定一个五年计划,确定每年投入高低两种负荷下生产的完好的机器数量,使 5 年内产品的总产量达到最大?
设 s1 = 1000(台),g = 8,h = 5,a = ,b = 。
这是一个五阶段决策问题
s1
s2
s3
s5
s4
x1
x2
x3
x4
最短路线问题的动态规划模型
阶段变量 k = 1, 2, 3, …, 6
状态变量如 s2 ∈S2 = { B1,B2 }
决策变量 x2(B1) ∈ D2(B1) = { C1,C2,C3 }
策略如 A→ B1→C2 →D1 →E2 → F2→ G
状态转移方程 sk+1 = xk(sk)
阶段指标函数 Vkn = dk( sk, xk ) + dk+1( sk, xk ) +……+ d6( s6, x6 )
= dk( sk, xk ) + Vk+1,n(sk+1,xk+1,…,s6,x6)
状态变量要求无后效性
指标函数的可分性
最短线路问题的动态规划基本方程
最优指标函数表示当前位置到终点的距离
状态转移方程
阶段指标函数表示距离
边界条件
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
E3
G
5
3
1
6
3
6
7
8
6
8
3
5
3
3
8
4
2
2
2
1
3
3
3
5
5
2
6
6
F1
F2
4
3
G
六个阶段状态(结点)决策(多种选择)
状态转移方程(连线) 指标函数(到终点的距离)
G
4
3
F1
F2
G
阶段 k = 6
状态 S6 = { F1, F2 }
逆序递推
0
4
3
最优指标函数
F1→G
F2→G
决策:
5
E1
E2
E3
3
5
2
6
6
4
3
F1
F2
阶段 k = 5
状态 S5 = { E1, E2, E3 }
逆序递推
7
5
9
最优指标函数
E1→F1
E2→F2
E3→F2
决策: