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

1、3.5 动态规划动态规划 50年代初，由美国数学家年代初，由美国数学家Bellman提出。提出。 将系统运转过程分为假设干相继的阶段，而在每个将系统运转过程分为假设干相继的阶段，而在每个阶段都要做出决策的过程，就叫做多段决策过程。多段阶段都要做出决策的过程，就叫做多段决策过程。多段决策过程的每一段的终了外形，就是下一段的初始外形。决策过程的每一段的终了外形，就是下一段的初始外形。 动态规划是研讨多段决策而提出来的一种数学方法，动态规划是研讨多段决策而提出来的一种数学方法，它的中心思想是所谓的它的中心思想是所谓的“最优性原理，这个原理归结最优性原理，这个原理归结为一个根本递推关系式，从整个过程的

2、终点出发，由后为一个根本递推关系式，从整个过程的终点出发，由后向前，使过程延续地转移，一步一步地推到始点，找到向前，使过程延续地转移，一步一步地推到始点，找到最优解。最优解。 系统动态最优化习惯称为最优控制，它与系统静态系统动态最优化习惯称为最优控制，它与系统静态最优化的区别在于其自变量是时间的函数，本质上属于最优化的区别在于其自变量是时间的函数，本质上属于泛函极值的范畴。泛函极值的范畴。2511214106104131112396581052C1C3D1AB1B3B2D2EC2例例 求从求从A到到E的最短途径的最短途径2511214106104131112396581052C1C3D1AB1

3、B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0505)(),()(5114EfEDdDf2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)(),()(5224EfEDdDf2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=51124211411138118min2953min)(),()(),

4、(min)(DCDfDCDfDCCf最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8222422141223DC7711min2556min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333DC121213min21058min)D(f)D,C()D

5、(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=81133312321131112CB20222120min1210714812min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C

6、1)=8f2(B1)=211233322322131222CB14161714min12471086min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142333332323131332CB19231921min1211712813min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策25112141

7、06104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=2123232221211BA19201923min191145212min)B(f)B,A()B(f)B,A()B(f)B,A(min)A(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21外形外形 最优决策最优决策 外形外形 最优