数学模型动态规划 .pdfVIP

数学模型动态规划

动态规划

动态规划(dynamicprogramming)是运筹学的⼀个重要分⽀，它是解决多阶段决策问题的⼀种有效的数量化⽅法．动态规划是

由美国学者贝尔曼(R．Bellman）等⼈所创⽴的．1951年贝尔曼⾸先提出了动态规划中解决多阶段决策问题的最优化原理，并

给出了许多实际问题的解法．1957年贝尔曼发表了《动态规划》⼀书，标志着运筹学这⼀重要分⽀的诞⽣．

§1动态规划的概念与原理

⼀、动态规划的基本概念

引例:最短路线问题

美国⿊⾦⽯油公司（TheBlackGoldPetroleumCompany）最近在阿拉斯加（Alaska）的北斯洛波（NorthSlope）发现了⼤

的⽯油储量。为了⼤规模开发这⼀油⽥，⾸先必须建⽴相应的输运⽹络，使北斯洛波⽣产的原油能运⾄美国的3个装运港之

⼀。在油⽥的集输站（结点C）与装运港（结点P1、P

、P3）之间需要若⼲个中间站，中间站之间的联通情况如图1所⽰，图中线2

段上的数字代表两站之间的距离（单位：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；取

x，按逆序算法求解。

过程在各阶段所处的位置为状态变量

k

当4=k时：

由结点M31P1或P2；故：

668min)(3144=?

==Mxf选择P2

由结点M32到达⽬的地有三条路线可以选择，即选择P1、P2或P3；故：

3734min)(3244=

==Mxf选择P2

由结点M33到达⽬的地也有三条路线可以选择，即选择P1、P2或P3；故：

5567min)(3344=

==Mxf选择P3

由结点M34到达⽬的地有两条路线可以选择，即选择P2或P3；故：

343min)(3444=?

==Mxf选择P2

当3=k时：

由结点M21到达下⼀阶段有三条路线可以选择，即选择M31、M32或M33；故：

105637610min)(2133=??

+++==Mxf选择M32

由结点M22到达下⼀阶段也有三条路线可以选择，即选择M31、M32或M33；

故：in)(2233=

+++==Mxf选择M32或M33

由结点M23到达下⼀阶段也有三条路线可以选择，即选择M32、M33或M34；

故：in)(2333=

+++==Mxf选择M33或M34

当2=k时：

由结点M11到达下⼀阶段有两条路线可以选择，即选择M21或M22；故：in)(1122=?

++==Mxf选择M22

由结点M12到达下⼀阶段也有两条路线可以选择，即选择M22或M23；故：in)(1222=?

++==Mxf选择M22

当1=k时：

由结点C到达下⼀阶段有两条路线可以选择，即选择M11或M12；故：

2819101612min)(11=?

++==Cxf选择M11

从⽽通过顺序（计算的反顺序）追踪（⿊体标⽰）可以得到两条最佳的输运线路：C—M11—M22—M32—P2；C—M11

—M22—M33—P3。最短的输送距离是280千⽶。

⼀个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。

1、阶段

阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，常⽤k来表⽰。阶段的划分⼀般是根据时间和空间的⾃

然特征来进⾏的，但要便于将问题的过程转化为多阶段决策的过程。阶段变量⼀般⽤nk,,2,1=表⽰。

2、状态

状态（