基于动态规划的教育装备运输线路选择问题研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于动态规划的教育装备运输线路选择问题研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要 教育装备运输线路的选择和优化是教育装备管理中经常遇到的多阶段决策问题。采用动态规划的原理及方法，结合实际案例，研究教育装备运输线路的最优化选择，为教育装备管理者提供重要的科学决策依据。

关键词 教育装备；运筹学；运输

中图分类号：G40-057 文献标识码：A

文章编号：1671-489X（2013）33-0014-03

在教育装备管理活动中，决策是一个多阶段、多步骤的分析判断过程，贯穿于教育装备管理活动的各个阶段，绝大多数教育领域的管理决策都是多阶段决策问题。教育装备运输线路的选择是教育装备管理中经常遇到的多阶段决策问题。由于运输线路的有限性、决策变量的动态性、最优方案的不稳定性等多种制约因素，各教育装备生产厂商如何根据现有交通条件选择最短的运输线路，将装备送达教育机构，使总的运输代价最小，属于典型的教育装备运输问题，是教育装备运筹学的重要研究内容之一[1-2]。本文以教育装备运输线路选择问题为具体研究对象，采用动态规划的原理及方法，结合实际案例，给出具体的数学模型和决策过程，从而有助于教育装备管理活动中的科学决策。

1 动态规划的原理

1951年，美国数学家贝尔曼（Richard Bellman）创立了解决过程优化问题的经典方法——动态规划，常用于解决多阶段决策问题（如最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题、生产过程最优控制问题等），是一种重要的管理决策技术[1-6]。多阶段决策是指将决策过程划分为一系列相互关联的阶段，在每个阶段均需做出相应的决策，上一个阶段的决策不仅会影响下一个阶段的决策，而且将影响整个决策过程。因此，每个阶段最优决策的选取，不仅要考虑当前阶段所取得的效果，而且要综合考虑各个阶段的决策所形成的总体效果。

作为解决多阶段决策问题的一种有效方法，动态规划在工程技术、社会经济、国防军事等领域应用广泛，并取得了显著成果，已经成为现代管理学中进行科学决策不可或缺的重要工具。动态规划的最大优势在于把一个多阶段决策问题转化为若干个单阶段最优化问题，并逐个求解所有单阶段最优化问题。因此，在采用动态规划的原理和方法求解多阶段决策问题时，必须具体问题具体分析，建立相应的数学模型。

求解步骤 下面为动态规划方法求解多阶段决策问题的主要步骤。

1）划分阶段。按照时间、空间、变量等特征，将某一实际问题划分为若干个有序的阶段，通常采用i表示阶段变量。

2）确定状态和决策。根据无后效性原则，选择不同的状态表示各个阶段；并逐一确定阶段i的状态变量si、决策变量di及各自的取值范围。

3）撰写状态转移方程。根据上一阶段的状态si-1和决策di-1，可以导出本阶段的状态si，即写出状态转移方程T。

4）建立指标函数gi。得到实际问题的函数方程，即递推关系式。

5）求解最优指标值和最优策略。采用逆序算法，求出每个阶段的最优指标值及相应的最优策略。最后求得全过程的最优策略。

动态规划的逆序算法 最优指标函数通常表示为：

...（1）

其中，“opt”表示最优化，通常指“取最大值”或“取最小值”；表示某种运算，通常指“和”运算或“积”运算；n表示阶段数。

根据最优化原理，将式（1）表示为递推关系式：

...（2）

利用式（2）可表示出最后一个阶段（第n个阶段）的最优指标函数为：

（3）

其中，fn+1（sn+1）称为边界条件，其取值根据实际问题确定。

已知边界条件fn+1（sn+1），利用式（3）可求得第n个阶段的最优指标函数fn（sn）；根据fn（sn），继续利用式（3）可求得第n-1个阶段的最优指标函数fn-1（sn-1）；根据fn-1（sn-1），进而可得第n-2个阶段的最优指标函数 fn-2（sn-2）；……；依此递推，直至求得第1个阶段的最优指标函数f1（s1），从而使问题得到解决。由于上述最优指标函数的构建是按阶段的逆序从后向前进行的，所以也称为动态规划的逆序算法。

2 实例分析

下面以实际案例分析教育装备运输线路选择问题：

某教育装备厂商欲将装备由库房A运送至目的地E，从A不能直接到达E，必须经过3次停靠进行各种补充和休息：第一次停靠有两个可供选择的中转站，第二次停靠有三个可供选择的中转站，第三次停靠有两个可供选择的中转站。其运输路线图如图1所示，箭头表示单行线，旁边的数字表示距离（单位：百公里）。显然从A到E有多种运输路线，请选择最短的运输路线。

对于比较复杂的交通路线图来说，将所有可能的路线全部罗列出来，再比较它们的路程虽然可行，但并不可取。由最优化原理可知，最短路径有一个重要性质：如果由起点A经过B点和C点到达终点D是A到D的一条最短路径，则由B点经C点到达终点D一定是B到D的最短路径。因此，寻找最佳运输线路的方法为：从最后阶段开始，由后向前逐步递推求出各点到终点的最短路径，最后求得由始点到终点的最短运输线路。

按照动态规划的求解方法，将全过程划分为4个阶段，即阶段变量i=1，2，3，4，取过程在各阶段所处的位置为状态变量si，按动态规划的逆序算法求解。

1）当i=4时，由中间点D1到达目的地有一条路线可以选择，则

f4（s4=D1）=6

由中间点D2到达目的地有一条路线可以选择，则

f4（s4=D2）=7

因此，分别给D1和D2加上标号6和7，如图2所示。

2）当i=3时，由中间点C1到达下一阶段有两条路线可以选择，即选择D1或D2，则

，选择D1

由中间点C2到达下一阶段有两条路线可以选择，即选择D1或D2，则

，选择D2

由中间点C3到达下一阶段有一条路线可以选择，即选择D2，则

f3（s3=C3）=7+7=14，选择D2

因此，分别给C1、C2和C3加上标号15、13和14，如图2所示。

3）当i=2时，由中间点B1到达下一阶段有三条路线可以选择，即选择C1或C2或C3，则

，选择C2

由中间点B2到达下一阶段有两条路线可以选择，即选择C2或C3，则

，选择C2

因此，分别给B1和B2加上标号18和24，如图2所示。

4）当i=1时，由起点S到达下一阶段有两条路线可以选择，即选择B1或B2，则

，选择B1

因此，给A加上标号22。从而通过计算的反顺序追踪，得到最佳的运输线路，即一条从A到E的最短路径：AB1C2D2E（如图2中加粗线条所示），最短的运输距离是2200公里。图2中每个停靠站都有自己的标号，它表示从该站出发到目的地E的最短路径长度。

3 总结

教育装备管理的多阶段决策优化问题是教育装备运筹学的重要研究内容之一，可以为教育装备的决策者或管理者提供合理有效的辅助决策支持方案。本文以教育装备运输线路选择问题为研究对象，结合实际案例，采用动态规划的理论及方法研究教育装备运输线路的最优化选择，探讨教育装备管理活动中的科学决策，并给出具体的求解算法和决策过程，从而定量地提供了可操作的决策理论和方法。

参考文献

[1]李慧.教育装备运筹规划[M].北京：北京大学出版社，

2010：36-85.

[2]陈庆华.装备运筹学[M].北京：国防工业出版社，2005：

103，122.

[3]Winston W L.运筹学：决策方法[M].北京：清华大学出版社，2004：214-235.

[4]Winston W L.运筹学：数学规划[M].北京：清华大学出版社，2004：490-542.

[5]焦宝聪，陈兰平.运筹学的思想方法及应用[M].北京：北京大学出版社，2008：63-68.

[6]董肇君.系统工程与运筹学[M].北京：国防工业出版社，

2011：239-245.