《基于动态规划的教育装备运输线路选择问题研究.docx》由会员分享，可在线阅读，更多相关《基于动态规划的教育装备运输线路选择问题研究.docx（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、基于动态规划的教育装备运输线路选择问题研究 摘 要 教化装备运输线路的选择和优化是教化装备管理中常常遇到的多阶段决策问题。采纳动态规划的原理及方法，结合实际案例，探讨教化装备运输线路的最优化选择，为教化装备管理者供应重要的科学决策依据。 关键词 教化装备；运筹学；运输 中图分类号：G40-057 文献标识码：A 文章编号：1673-489X33-0014-03 在教化装备管理活动中，决策是一个多阶段、多步骤的分析推断过程，贯穿于教化装备管理活动的各个阶段，绝大多数教化领域的管理决策都是多阶段决策问题。教化装备运输线路的选择是教化装备管理中常常遇到的多阶段决策问题。由于运输线路的有限性、决策变量
2、的动态性、最优方案的不稳定性等多种制约因素，各教化装备生产厂商如何依据现有交通条件选择最短的运输线路，将装备送达教化机构，使总的运输代价最小，属于典型的教化装备运输问题，是教化装备运筹学的重要探讨内容之一1-2。本文以教化装备运输线路选择问题为详细探讨对象，采纳动态规划的原理及方法，结合实际案例，给出详细的数学模型和决策过程，从而有助于教化装备管理活动中的科学决策。 1 动态规划的原理 1951年，美国数学家贝尔曼创立了解决过程优化问题的经典方法动态规划，常用于解决多阶段决策问题，是一种重要的管理决策技术1-6。多阶段决策是指将决策过程划分为一系列相互关联的阶段，在每个阶段均需做出相应的决策，
3、上一个阶段的决策不仅会影响下一个阶段的决策，而且将影响整个决策过程。因此，每个阶段最优决策的选取，不仅要考虑当前阶段所取得的效果，而且要综合考虑各个阶段的决策所形成的总体效果。 作为解决多阶段决策问题的一种有效方法，动态规划在工程技术、社会经济、国防军事等领域应用广泛，并取得了显著成果，已经成为现代管理学中进行科学决策不行或缺的重要工具。动态规划的最大优势在于把一个多阶段决策问题转化为若干个单阶段最优化问题，并逐个求解全部单阶段最优化问题。因此，在采纳动态规划的原理和方法求解多阶段决策问题时，必需详细问题详细分析，建立相应的数学模型。 求解步骤 下面为动态规划方法求解多阶段决策问题的主要步骤。
4、 1）划分阶段。根据时间、空间、变量等特征，将某一实际问题划分为若干个有序的阶段，通常采纳i表示阶段变量。 2）确定状态和决策。依据无后效性原则，选择不同的状态表示各个阶段；并逐一确定阶段i的状态变量si、决策变量di及各自的取值范围。 3）撰写状态转移方程。依据上一阶段的状态si-1和决策di-1，可以导出本阶段的状态si，即写出状态转移方程T。 4）建立指标函数gi。得到实际问题的函数方程，即递推关系式。 5）求解最优指标值和最优策略。采纳逆序算法，求出每个阶段的最优指标值及相应的最优策略。最终求得全过程的最优策略。 动态规划的逆序算法 最优指标函数通常表示为： . 其中，“opt”表示最
5、优化，通常指“取最大值”或“取最小值”；表示某种运算，通常指“和”运算或“积”运算；n表示阶段数。 依据最优化原理，将式表示为递推关系式： . 利用式可表示出最终一个阶段的最优指标函数为： 其中，fn+1称为边界条件，其取值依据实际问题确定。 已知边界条件fn+1，利用式可求得第n个阶段的最优指标函数fn；依据fn，接着利用式可求得第n-1个阶段的最优指标函数fn-1；依据fn-1，进而可得第n-2个阶段的最优指标函数 fn-2；依此递推，直至求得第1个阶段的最优指标函数f1，从而使问题得到解决。由于上述最优指标函数的构建是按阶段的逆序从后向前进行的，所以也称为动态规划的逆序算法。 2 实例分
6、析 下面以实际案例分析教化装备运输线路选择问题： 某教化装备厂商欲将装备由库房A运输至目的地E，从A不能干脆到达E，必需经过3次停靠进行各种补充和休息：第一次停靠有两个可供选择的中转站，其次次停靠有三个可供选择的中转站，第三次停靠有两个可供选择的中转站。其运输路途图如图1所示，箭头表示单行线，旁边的数字表示距离。明显从A到E有多种运输路途，请选择最短的运输路途。 对于比较困难的交通路途图来说，将全部可能的路途全部排列出来，再比较它们的路程虽然可行，但并不行取。由最优化原理可知，最短路径有一个重要性质：假如由起点A经过B点和C点到达终点D是A到D的一条最短路径，则由B点经C点到达终点D肯定是B到
7、D的最短路径。因此，找寻最佳运输线路的方法为：从最终阶段起先，由后向前逐步递推求出各点到终点的最短路径，最终求得由始点到终点的最短运输线路。 根据动态规划的求解方法，将全过程划分为4个阶段，即阶段变量i=1，2，3，4，取过程在各阶段所处的位置为状态变量si，按动态规划的逆序算法求解。 1）当i=4时，由中间点D1到达目的地有一条路途可以选择，则 f4=6 由中间点D2到达目的地有一条路途可以选择，则 f4=7 因此，分别给D1和D2加上标号6和7，如图2所示。 2）当i=3时，由中间点C1到达下一阶段有两条路途可以选择，即选择D1或D2，则 ，选择D1 由中间点C2到达下一阶段有两条路途可以
8、选择，即选择D1或D2，则 ，选择D2 由中间点C3到达下一阶段有一条路途可以选择，即选择D2，则 f3=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。从而通过计算的反依次追踪，得到最佳的运输线路，即一条从
9、A到E的最短路径：AB1C2D2E，最短的运输距离是2200公里。图2中每个停靠站都有自己的标号，它表示从该站动身到目的地E的最短路径长度。 3 总结 教化装备管理的多阶段决策优化问题是教化装备运筹学的重要探讨内容之一，可以为教化装备的决策者或管理者供应合理有效的协助决策支持方案。本文以教化装备运输线路选择问题为探讨对象，结合实际案例，采纳动态规划的理论及方法探讨教化装备运输线路的最优化选择，探讨教化装备管理活动中的科学决策，并给出详细的求解算法和决策过程，从而定量地供应了可操作的决策理论和方法。 参考文献 1李慧.教化装备运筹规划M.北京：北京高校出版社， 2022：36-85. 2陈庆华.
10、装备运筹学M.北京：国防工业出版社，2022： 103，122. 3Winston W L.运筹学：决策方法M.北京：清华高校出版社，2004：214-235. 4Winston W L.运筹学：数学规划M.北京：清华高校出版社，2004：490-542. 5焦宝聪，陈兰平.运筹学的思想方法及应用M.北京：北京高校出版社，2022：63-68. 6董肇君.系统工程与运筹学M.北京：国防工业出版社， 2022：239-245. 第7页 共7页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页