数学模型动态规划

《数学模型动态规划》由会员分享，可在线阅读，更多相关《数学模型动态规划（25页珍藏版）》请在金锄头文库上搜索。

1、1 动态规划动态规划 动态规划动态规划(dynamic(dynamic programming)programming)是运筹学的一个重要分支，它是解决多是运筹学的一个重要分支，它是解决多 阶段决策问题的一种有效的数量化方法动态规划是由美国学者贝尔曼阶段决策问题的一种有效的数量化方法动态规划是由美国学者贝尔曼 (R(RBellmanBellman）等人所创立的）等人所创立的19511951 年贝尔曼首先提出了动态规划中解决多年贝尔曼首先提出了动态规划中解决多 阶段决策问题的最优化原理，并给出了许多实际问题的解法阶段决策问题的最优化原理，并给出了许多实际问题的解法19571957 年贝尔曼年贝尔

2、曼 发表了发表了动态规划动态规划一书，标志着运筹学这一重要分支的诞生一书，标志着运筹学这一重要分支的诞生 11 动态规划的概念与原理动态规划的概念与原理 一、动态规划的基本概念一、动态规划的基本概念 引例引例: : 最短路线问题最短路线问题 美国黑金石油公司（美国黑金石油公司（TheThe BlackBlack GoldGold PetroleumPetroleum CompanyCompany）最近在阿拉）最近在阿拉 斯加（斯加（AlaskaAlaska）的北斯洛波（）的北斯洛波（NorthNorth SlopeSlope）发现了大的石油储量。为了大规）发现了大的石油储量。为了大规 模开发这

3、一油田，首先必须建立相应的输运网络，使北斯洛波生产的原油能模开发这一油田，首先必须建立相应的输运网络，使北斯洛波生产的原油能 运至美国的运至美国的 3 3 个装运港之一。在油田的集输站（结点个装运港之一。在油田的集输站（结点C C）与装运港（结点）与装运港（结点 P P1 1、P P2 2、P P3 3）之间需要若干个中间站，中间站之间的联通情况如图）之间需要若干个中间站，中间站之间的联通情况如图 1 1 所示，图所示，图 中线段上的数字代表两站之间的距离（单位：中线段上的数字代表两站之间的距离（单位：1010 千米）千米） 。试确定一最佳的输。试确定一最佳的输 运线路，使原油的输送距离最短。

4、运线路，使原油的输送距离最短。 解：最短路线有一个重要性质，即如果由起点解：最短路线有一个重要性质，即如果由起点A A经过经过B B点和点和C C点到达终点到达终 点点D D是一条最短路线，则由是一条最短路线，则由B B点经点经C C点到达终点点到达终点D D一定是一定是B B到到D D的最短路的最短路 （贝尔曼最优化原理）（贝尔曼最优化原理） 。此性质用反证法很容易证明，因为如果不是这样，则。此性质用反证法很容易证明，因为如果不是这样，则 从从B B点到点到D D点有另一条距离更短的路线存在，不妨假设为点有另一条距离更短的路线存在，不妨假设为B BP PD D；从而可；从而可 知路线知路线A

5、 AB BP PD D比原路线比原路线A AB BC CD D距离短，这与原路线距离短，这与原路线A AB BC CD D是是 最短路线相矛盾，性质得证。最短路线相矛盾，性质得证。 根据最短路线的这一性质，寻找最短路线的方法就是从最后阶段开始，根据最短路线的这一性质，寻找最短路线的方法就是从最后阶段开始， 由后向前逐步递推求出各点到终点的最短路线，最后求得由始点到终点的最由后向前逐步递推求出各点到终点的最短路线，最后求得由始点到终点的最 短路；即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。短路；即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。 按照动态规划的方法，

6、将此过程划分为按照动态规划的方法，将此过程划分为 4 4 个阶段，即阶段变量个阶段，即阶段变量；取；取4 , 3 , 2 , 1k 过程在各阶段所处的位置为状态变量过程在各阶段所处的位置为状态变量，按逆序算法求解。，按逆序算法求解。 k x 2 当当时：时：4k 由结点由结点M M31 31到达目的地有两条路线可以选择，即选择 到达目的地有两条路线可以选择，即选择P P1 1或或P P2 2；故：；故： 选择选择P P2 26 6 8 min)( 3144 Mxf 由结点由结点M M32 32到达目的地有三条路线可以选择，即选择 到达目的地有三条路线可以选择，即选择P P1 1、P P2 2或

7、或P P3 3；故：；故： 选择选择P P2 23 7 3 4 min)( 3244 Mxf 由结点由结点M M33 33到达目的地也有三条路线可以选择，即选择 到达目的地也有三条路线可以选择，即选择P P1 1、P P2 2或或P P3 3；故：；故： 选择选择P P3 35 5 6 7 min)( 3344 Mxf 由结点由结点M M34 34到达目的地有两条路线可以选择，即选择 到达目的地有两条路线可以选择，即选择P P2 2或或P P3 3；故：；故： 选择选择P P2 23 4 3 min)( 3444 Mxf 当当时：时：3k 由结点由结点M M21 21到达下一阶段有三条路线可以

8、选择，即选择 到达下一阶段有三条路线可以选择，即选择M M31 31、 、M M32 32或 或M M33 33； ； 故：故： C P3 P2 P1 M11 M12 M21 M22 M23 M31 M32 M33 M34 10 12 8 6 9 11 10 7 6 9 7 5 11 4 6 8 6 4 3 7 7 6 5 3 4 k=1k=2k=3k=4 图 1 3 选择选择M M32 32 10 56 37 610 min)( 2133 Mxf 由结点由结点M M22 22到达下一阶段也有三条路线可以选择，即选择 到达下一阶段也有三条路线可以选择，即选择M M31 31、 、M M32 3

9、2或 或 M M33 33；故： ；故： 选择选择M M32 32或 或M M33 33 10 55 37 69 min)( 2233 Mxf 由结点由结点M M23 23到达下一阶段也有三条路线可以选择，即选择 到达下一阶段也有三条路线可以选择，即选择M M32 32、 、M M33 33或 或 M M34 34；故： ；故： 选择选择M M33 33或 或M M34 34 9 36 54 311 min)( 2333 Mxf 当当时：时：2k 由结点由结点M M11 11到达下一阶段有两条路线可以选择，即选择 到达下一阶段有两条路线可以选择，即选择M M21 21或 或M M22 22；故

10、： ；故： 选择选择M M22 22 16 106 108 min)( 1122 Mxf 由结点由结点M M12 12到达下一阶段也有两条路线可以选择，即选择 到达下一阶段也有两条路线可以选择，即选择M M22 22或 或M M23 23；故： ；故： 选择选择M M22 22 19 911 109 min)( 1222 Mxf 当当时：时：1k 由结点由结点C C到达下一阶段有两条路线可以选择，即选择到达下一阶段有两条路线可以选择，即选择M M11 11或 或M M12 12；故： ；故： 选择选择M M11 11 28 1910 1612 min)( 11 Cxf 从而通过顺序（计算的反顺

11、序）追踪（黑体标示）可以得到两条最佳的从而通过顺序（计算的反顺序）追踪（黑体标示）可以得到两条最佳的 输运线路：输运线路：C CM M11 11 M M22 22 M M32 32 P P2 2；C CM M11 11 M M22 22 M M33 33 P P3 3。最短的输送距离是。最短的输送距离是 280280 千米。千米。 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。 1 1、阶段、阶段 阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，

12、 常用常用k k来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，但来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，但 要便于将问题的过程转化为多阶段决策的过程。阶段变量一般用要便于将问题的过程转化为多阶段决策的过程。阶段变量一般用 表示。表示。nk, 2 , 1L 4 2 2、状态、状态 状态（状态（statestate）表示每个阶段开始时过程所处的自然状况。它应能描述过）表示每个阶段开始时过程所处的自然状况。它应能描述过 程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程 的演变与该阶段以前

13、各阶段的状态无关。通常还要求状态是直接或间接可以的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以 观测的。观测的。 描述状态的变量称状态变量（描述状态的变量称状态变量（statestate variablevariable） 。变量允许取值的范围称。变量允许取值的范围称 允许状态集合允许状态集合(set(set ofof admissibleadmissible states)states)。用。用表示第表示第阶段的状态变量，阶段的状态变量， k xk 它可以是一个数或一个向量。用它可以是一个数或一个向量。用表示第表示第阶段的允许状态集合。阶段的允许状态集合。 k Dk 个阶

14、段的决策过程有个阶段的决策过程有个状态变量，个状态变量，表示表示演变的结果。演变的结果。n1n 1n x n x 根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方 便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。 状态变量简称为状态。状态变量简称为状态。 3 3 决策决策 当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某 个状态，这种选择手段称为决策（个

15、状态，这种选择手段称为决策（decisiondecision） ，在最优控制问题中也称为控制，在最优控制问题中也称为控制 （controlcontrol） 。 描述决策的变量称决策变量（描述决策的变量称决策变量（decisiondecision variablevariable） ，变量允许取值的范围称，变量允许取值的范围称 允许决策集合（允许决策集合（setset ofof admissibleadmissible decisionsdecisions） 。用。用表示第表示第阶段处阶段处)( kk xuk 于状态于状态时的决策变量，它是时的决策变量，它是的函数，用的函数，用表示表示的允许决策集合。的允许决策集合。 k x k x)( kk uU k u 决策变量简称决策。决策变量简称决策。 4 4 策略策略 决策组成的序列称为策略（决策组成的序列称为策略（policypolicy） 。由初始状态。由初始状态开始的全过程的策开始的全过程的策 1 x 略记作略记作，即，即. .)( 11 xp n )(,),(),()( 221111nnn xux