文档介绍：1 动态规划动态规划(dynamic programming) 是运筹学的一个重要分支,(R. Bellman ) 等人所创立的. 1951 年贝尔曼首先提出了动态规划中解决多阶段决策问题的最优化原理,并给出了许多实际问题的解法. 1957 年贝尔曼发表了《动态规划》一书,标志着运筹学这一重要分支的诞生. §1 动态规划的概念与原理一、动态规划的基本概念引例: 最短路线问题美国黑金石油公司( The Black Gold pany )最近在阿拉斯加( Alaska )的北斯洛波( North Slope )发现了大的石油储量。为了大规模开发这一油田,首先必须建立相应的输运网络,使北斯洛波生产的原油能运至美国的 3 个装运港之一。在油田的集输站(结点 C )与装运港(结点 P 1、 P 2、P 3) 之间需要若干个中间站, 中间站之间的联通情况如图 1 所示, 图中线段上的数字代表两站之间的距离( 单位: 10 千米)。试确定一最佳的输运线路, 使原油的输送距离最短。解:最短路线有一个重要性质,即如果由起点 A 经过 B 点和 C 点到达终点D 是一条最短路线, 则由 B 点经 C 点到达终点 D 一定是 B到D 的最短路(贝尔曼最优化原理) 。此性质用反证法很容易证明,因为如果不是这样,则从 B 点到 D 点有另一条距离更短的路线存在, 不妨假设为 B—P—D; 从而可知路线 A—B—P—D 比原路线 A—B—C—D 距离短,这与原路线 A—B—C—D 是最短路线相矛盾,性质得证。根据最短路线的这一性质,寻找最短路线的方法就是从最后阶段开始, 由后向前逐步递推求出各点到终点的最短路线,最后求得由始点到终点的最短路; 即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。按照动态规划的方法,将此过程划分为 4 个阶段,即阶段变量 4,3,2,1?k ;取过程在各阶段所处的位置为状态变量 kx ,按逆序算法求解。 2 当4?k 时: 由结点 M 31 到达目的地有两条路线可以选择,即选择 P 1或P 2 ;故: 66 8 min )( 31 44?????????Mxf 选择 P 2 由结点 M 32 到达目的地有三条路线可以选择,即选择 P 1、P 2或P 3 ;故: 37 3 4 min )( 32 44?????????????Mxf 选择 P 2 由结点 M 33 到达目的地也有三条路线可以选择,即选择 P 1、P 2或P 3 ;故: 55 6 7 min )( 33 44?????????????Mxf 选择 P 3 由结点 M 34 到达目的地有两条路线可以选择,即选择 P 2或P 3 ;故: 34 3 min )( 34 44?????????Mxf 选择 P 2 当3?k 时: 由结点 M 21 到达下一阶段有三条路线可以选择, 即选择 M 31、M 32或M 33;故: C P 3 P 2 P 1 M 11M 12 M 21M 22M 23 M 31M 32M 33M 34 10 12 869 11 10 76975 1146 8643776534 k=1 k=2 k=3 k=4 图13 10 56 37 610 min )( 21 33????????????????Mxf 选择 M 32 由结点 M 22 到达下一阶段也有三条路线可以选择,即选择 M 31、M 32或M 33; 故:10 55 37 69 min )( 22 33????????????????Mxf 选择 M 32或M 33 由结点 M 23 到达下一阶段也有三条路线可以选择,即选择 M 32、M 33或M 34; 故:936 54 3 11 min )( 23 33????????????????Mxf 选择 M 33或M 34 当2?k 时: 由结点 M 11 到达下一阶段有两条路线可以选择,即选择 M 21或M 22 ;故: 16 10 6 10 8 min )( 11 22???????????Mxf 选择 M 22 由结点 M 12 到达下一阶段也有两条路线可以选择,即选择 M 22或M 23 ;故: 19 9 11 10 9 min )( 12 22???????????Mxf 选择 M 22 当1?k 时: 由结点 C 到达下一阶段有两条路线可以选择,即选择 M 11或M 12 ;故: 28 19 10 16 12 min )( 11???????????Cxf 选择 M 11 从而通过顺序(计算的反顺序)追踪(黑体标示)可以得到两条最佳的输运线路: C—M 11—M 22—M 32—P 2;C—M 11—M 22—M 33—P 3 。最短的输送距