文档介绍：第2讲动态规划模型
动态规划是运筹学的一个分支，它是解
决多阶段决策过程最优化问题的一种数学 方法。1951年美国数学家贝尔曼 （）等人，根据一类多阶段决策 问题的特点，提出了解决这类问题的“最优 性原理”，研究了许多| i 4 3 4 5 4 J
.'d (C , B ) + f (B )、
4 3 4 5 4
[d (C , C ) + f (C )|
v 4 3 4 5 4 J
C
T B
T B
T A
3
4
5
6
4 3 4
u4(C3) = B4，由C 3出发的最短线路是
⑷k = 3时，分别以A/ % % D2为出
发点来计算，有
f3( A2)= min K
> =13
.何(A , A ) + f (A ) 1
3 2 3 4 3
[d (A , B ) + f (B )J
L 3 2 3 4 3 J
气(A ) = A ,由a出发的最短线路是 3 2 3 2
A —» A —» B —» B —» A o
f3( B)= min K
.\d (B , A ) + f (A )1
3 2 3 4 3
d (B , B ) + f (B )J
3 2 3 4 3 J
3 + 7 =min K >
=10
u 3(B2) = A3，由B 2出发的最短线路是
B
T A
T B
T B
T A
2
3
4
5
6 o
f (C ) = min<
\d (C , B ) + f (B ) 1 . [3 + 61
3 2 3 4 3 > = min K
d (C , C ) + f (C ) 3 + 8
k 3 2 3 4 3 J i J
U3(C2) = B3，由C 2出发的最短线路是
f3( D2)= min K
.\d (D , B ) + f (B ) 1
3 2 3 4 3
[d (D , C ) + f (C )J
"3 2 3 4 3 J
'8 + 6、
=min K >
4 + 8
I
=12
C
T B
T B
T B
T A o
2
3
4
5
6
U3(D2) = C ,由D 2出发的最短线路是 D2 T C — B4 T B T A6。
(5) k = 2时，分别以A］，B1为出发点来 计算，有
u 3(B2) = A3，由B 2出发的最短线路是
B
T A
T B
T B
T A
2
3
4
5
6 o
f (C ) = min<
\d (C , B ) + f (B ) 1 . [3 + 61
3 2 3 4 3 > = min K
d (C , C ) + f (C ) 3 + 8
k 3 2 3 4 3 J i J
U3(C2) = B3，由C 2出发的最短线路是
f3( D2)= min K
.\d (D , B ) + f (B ) 1
3 2 3 4 3
[d (D , C ) + f (C )J
"3 2 3 4 3 J
'8 + 6、
=min K >
4 + 8
I
=12
C
T B
T B
T B
T A o
2
3
4
5
6
U3(D2) = C ,由D 2出发的最短线路是 D2 T C — B4 T B T A6。
(5) k = 2时，分别以A］，B1为出发点来 计算，有
\d (A , A ) + f (A )
2 1 2 3 2
2 1 2 "32
d (A , C ) + f (C )
v 2 1 2 3 2
由A1出发的最短线路是
事A1) = min皿(A，B ) + / (B )
、
'1 +13、
> =min <
3 +10>
6 + 9
=13
\d (B , B ) + f (B )、
2 1 2 3 2
d (B , C ) + f (C )
2 12 3 2
2 1 2 3 2
'8 +10、
f (B ) = min <
2 1
/ = min [
7 + 9 >
d (B , D ) + f (D ) l 2 1 2 3 2)
6 +12
1
=16
At B — A — B — B — A o
u2(B1)= C2 ,由B1出发的最短线路是
B t C t B t B t B t A o
1 (6) k3= 1时，出发点只有A ,有
.\d (A , A ) + f (A )、 1 0 1 2 1
d (A , B ) + f (B ) J
1 0 1 2 1)
由A o出发