系统工程硕士(动态规划例子)课件

1、系统工程硕士(动态规划例子)1 3.5 动态规划动态规划 50年代初，由美国数学家年代初，由美国数学家Bellman提出。提出。 将系统运行过程分为若干相继的阶段，而在每个阶将系统运行过程分为若干相继的阶段，而在每个阶 段都要做出决策的过程，就叫做多段决策过程。多段决段都要做出决策的过程，就叫做多段决策过程。多段决 策过程的每一段的结束状态，就是下一段的初始状态。策过程的每一段的结束状态，就是下一段的初始状态。 动态规划是研究多段决策而提出来的一种数学方法，动态规划是研究多段决策而提出来的一种数学方法， 它的中心思想是所谓的它的中心思想是所谓的“最优性原理最优性原理”，这个原理归结，这个原理归

2、结 为一个基本递推关系式，为一个基本递推关系式，从整个过程的终点出发，由后从整个过程的终点出发，由后 向前，使过程连续地转移，一步一步地推到始点，找到向前，使过程连续地转移，一步一步地推到始点，找到 最优解最优解。 系统动态最优化习惯称为最优控制，它与系统静态系统动态最优化习惯称为最优控制，它与系统静态 最优化的区别在于其自变量是时间的函数，实质上属于最优化的区别在于其自变量是时间的函数，实质上属于 泛函极值的范畴。泛函极值的范畴。 系统工程硕士(动态规划例子)2 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3

3、B2 D2 EC2 例例 求从求从A到到E的最短路径的最短路径 系统工程硕士(动态规划例子)3 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 EC2 f5(E)=0 系统工程硕士(动态规划例子)4 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 EC2 f4(D1)=5 f5(E)=0 505)(),()( 5114 EfEDdDf 系统工程硕士(动态规划例子)5 2 5 1 12 14 10 6 10 4

4、 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 EC2 f4(D2)=2 f5(E)=0 f4(D1)=5 202)(),()( 5224 EfEDdDf 系统工程硕士(动态规划例子)6 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 EC2 f4(D2)=2 f5(E)=0 f3(C1)=8 f4(D1)=5 11 2421 1411 13 8 11 8 min 29 53 min )(),( )(),( min)( DC DfDC DfDC Cf

5、 最优决策 系统工程硕士(动态规划例子)7 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 EC2 f4(D2)=2 f5(E)=0f3(C2)=7 f4(D1)=5 f3(C1)=8 22 2422 1412 23 DC7 7 11 min 25 56 min )D(f)D,C( )D(f)D,C( min)C(f 最优决策 系统工程硕士(动态规划例子)8 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E

6、C2 f4(D2)=2 f5(E)=0 f3(C3)=12 f4(D1)=5 f3(C1)=8 f3(C2)=7 23 2423 1413 33 DC12 12 13 min 210 58 min )D(f)D,C( )D(f)D,C( min)C(f 最优决策 系统工程硕士(动态规划例子)9 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 EC2 f4(D2)=2 f5(E)=0 f3(C3)=12 f4(D1)=5 f2(B1)=20 f3(C2)=7 f3(C1)=8 11 3331 2321

7、1311 12 CB 20 22 21 20 min 1210 714 812 min )C(f)C,B( )C(f)C,B( )C(f)C,B( min)B(f 最优决策 系统工程硕士(动态规划例子)10 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 EC2 f4(D2)=2 f5(E)=0 f3(C3)=12 f4(D1)=5 f2(B2)=14f3(C2)=7 f3(C1)=8f2(B1)=21 12 3332 2322 1312 22 CB 14 16 17 14 min 124 710 8

8、6 min )C(f)C,B( )C(f)C,B( )C(f)C,B( min)B(f 最优决策 系统工程硕士(动态规划例子)11 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 EC2 f4(D2)=2 f5(E)=0 f3(C3)=12 f4(D1)=5 f2(B3)=19 f3(C2)=7 f3(C1)=8f2(B1)=21 f2(B2)=14 23 3333 2323 1313 32 CB 19 23 19 21 min 1211 712 813 min )C(f)C,B( )C(f)C,B(

9、 )C(f)C,B( min)B(f 最优决策 系统工程硕士(动态规划例子)12 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 EC2 f4(D2)=2 f5(E)=0 f3(C3)=12 f4(D1)=5 f2(B3)=19 f3(C2)=7 f3(C1)=8 f1(A)=19f2(B2)=14 f2(B1)=21 2 323 222 121 1 BA 19 20 19 23 min 191 145 212 min )B(f)B,A( )B(f)B,A( )B(f)B,A( min)A(f 最优决策 系统工程硕士(动态规划例子)13 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 EC2 f4(D2)=2 f5(E)=0 f3(C3)=12 f4(D1)=5 f2(B3)=19 f3(C2)=7 f3(C1)=8 f1(A)=19f2(B2)=14 f2(