数学模型动态规划.doc

------------------------------------------------------------------------------------------------ ——————————————————————————————————————数学模型动态规划动态规划动态规划(dynamic programming) 是运筹学的一个重要分支, 它是解决多阶段决策问题的一种有效的数量化方法. 动态规划是由美国学者贝尔曼(R. Bellman )等人所创立的. 1951 年贝尔曼首先提出了动态规划中解决多阶段决策问题的最优化原理, 并给出了许多实际问题的解法. 1957 年贝尔曼发表了《动态规划》一书,标志着运筹学这一重要分支的诞生. §1 动态规划的概念与原理一、动态规划的基本概念引例: 最短路线问题美国黑金石油公司( The Black Gold pany )最近在阿拉斯加( Alaska ) 的北斯洛波( North Slope ) 发现了大的石油储量。为了大规模开发这一油田, 首先必须建立相应的输运网络, 使北斯洛波生产的原油能运至美国的 3 个装运港之一。在油田的集输站(结点 C) 与装运港( 结点 P1、 P2、 P3) 之间需要若干个中间站, 中间站之间的联通情况如图 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 个阶段, 即阶段变量 k?1,2,3,4 ; 取过程在各阶段所处的位置为状态变量 xk, 按逆序算法求解。 1当 k?4 时: 由结点 M31P1 或 P2 ;故: ?8? f4(x4?M31)?min???6 选择 P2 ?6? 由结点 M32 到达目的地有三条路线可以选择, 即选择 P1、 P2或 P3 ;故: ?4??? f4(x4?M32)?min?3??3 选择 P2 ?7??? 由结点 M3 3 到达目的地也有三条路线可以选择, 即选择 P1、 P2或 P3 ;故: ------------------------------------------------------------------------------------------------ ——————————————————————————————————————?7??? f4(x4?M33)?min?6??5 选择 P3 ?5??? 由结点 M34 到达目的地有两条路线可以选择,即选择 P2 或 P3 ;故: ?3? f4(x4?M34)?min???3 选择 P2 ?4? 当 k?3 时: 由结点 M21 到达下一阶段有三条路线可以选择,即选择 M31 、 M32 或 M33 ;故: 2 ?10?6???f3(x3?M21)?min?7?3??10 选择 M32 ?6?5??? 由结点 M22 到达下一阶段也有三条路线可以选择, 即选择 M31 、 M32 或 M33 ;故: ?9?6???f3(x3?M22)?min?7?3??10 选择 M32 或 M33 ?5?5??? 由结点 M23 到达下一阶段也有三条路线可以选择, 即选择 M32 、 M33 或 M34 ;故: ?11?3???f3(x3?M23)?min?4?5??9 选择 M33 或 M34 ?6?3??? 当 k?2 时: ------------------------------------------------------------------------------------------------ —————