数学模型动态规划

《数学模型动态规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、........................................................................动态规划动态规划(dynamicprogramming)是运筹学的一个重要分支，它是解决多阶段决策问题的一种有效的数量化方法．动态规划是由美国学者贝尔曼(R．Bellman）等人所创立的．1951年贝尔曼首先提出了动态规划中解决多阶段决策问题的最优化原理，并给出了许多实际问题的解法．1957年贝尔曼发表了《动态规划》一书，标志着运筹学这一重要分支的诞生．§1动态规划的概念与原理一、动态规划的基

2、本概念引例:最短路线问题美国黑金石油公司（TheBlackGoldPetroleumCompany）最近在阿拉斯加（Alaska）的北斯洛波（NorthSlope）发现了大的石油储量。为了大规模开发这一油田，首先必须建立相应的输运网络，使北斯洛波生产的原油能运至美国的3个装运港之一。在油田的集输站（结点C）与装运港（结点P1、P2、P3）之间需要若干个中间站，中间站之间的联通情况如图1所示，图中线段上的数字代表两站之间的距离（单位：10千米）。试确定一最佳的输运线路，使原油的输送距离最短。解：最短路线有一个重要性质，即如果由起点A经过

3、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个阶段，即阶段变量；取过程在各阶段所处的位置为状态变量，按逆序算法求解。专业技术资料........................................................................CP3P2P1M11M12M21M22M23M31M32M33M34101286911107697511468643776534k=1k=2k=3k=4图1当时：由结点M31到达目的地有两条路线可以选择，即选择P1或P2；故：选择P2由结点M32到达目的地有三条路线可以选择，即选择P1、P2或P3；故

5、：选择P2由结点M33到达目的地也有三条路线可以选择，即选择P1、P2或P3；故：选择P3由结点M34到达目的地有两条路线可以选择，即选择P2或P3；故：选择P2当时：由结点M21到达下一阶段有三条路线可以选择，即选择M31、M32或M33；故：专业技术资料........................................................................选择M32由结点M22到达下一阶段也有三条路线可以选择，即选择M31、M32或M33；故：选择M32或M33由结点M23到达下一阶段也有三

6、条路线可以选择，即选择M32、M33或M34；故：选择M33或M34当时：由结点M11到达下一阶段有两条路线可以选择，即选择M21或M22；故：选择M22由结点M12到达下一阶段也有两条路线可以选择，即选择M22或M23；故：选择M22当时：由结点C到达下一阶段有两条路线可以选择，即选择M11或M12；故：选择M11从而通过顺序（计算的反顺序）追踪（黑体标示）可以得到两条最佳的输运线路：C—M11—M22—M32—P2；C—M11—M22—M33—P3。最短的输送距离是280千米。一个多阶段决策过程最优化问题的动态规划模型通常包含以下

7、要素。1、阶段阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，常用k来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，但要便于将问题的过程转化为多阶段决策的过程。阶段变量一般用表示。专业技术资料........................................................................2、状态状态（state）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通

8、常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量（statevariable）。变量允许取值的范围称允许状态集合(setofadmissiblestates)。用表示第阶段的状态变量，它可以是一个数或一个向量