基于最短路的多阶段决策问题研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于最短路的多阶段决策问题研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：最短路问题是图论中的重要问题之一，许多实际问题都可以转化为最短路问题。文章重点研究了多阶段决策问题，如设备更新和生产策略用Dijkstra算法求解的过程。该方法清晰直观，具有通用性和实用性。

关键词：最短路问题；决策问题；Dijkstra算法；邻接矩阵

一、引言

图论中的最短路问题是研究多阶段决策问题的可行办法，关键在于将多阶段决策问题转化为最短路问题，构造出相应的图，使图的顶点、边、权值分别反映原问题的相关要素，从而清晰直观地显现出问题的实质，再通过求解图中某些顶点间的最短路来确定原问题的多阶段决策。这一问题可以利用现成的Dijkstra算法和Floyd算法来解决。

二、最短路问题

最短路是一条路径，它的任意一段也是最短路。从某一点出发到其余顶点的最短路会构成一棵以该点为根的树，可以采用树生长的过程来求指定顶点到其余顶点的最短路。Dijkstra算法可以实现这一过程。

设G为赋权有向图或无向图，G边上的权均非负，S表示具有永久标号的顶点集。对每个顶点，定义两个标记（l（v），z（v）），其中l（v）表示从顶点到v的一条路的权，z（v）表示v的父亲点，用以确定最短路的路线。算法的基本思想就是在每一步改进这两个标记，是最终l（v）达到从顶点u0到v的最短路的权。

具体步骤为：输入G的带权邻接矩阵W，首先赋初值S={u0，l（u0）=0}，?v∈S=V＼S令l（v）=W（u0，v），z（v）=u0，uu0；再更新l（v），z（v），?v∈S=V＼S，若l（v）>l（u）+W（u，v），则令l（v）=l（u）+W（u，v），z（v）=u；设v*是使得l（v）取最小值的S中的顶点，则令S=S∪{v*}；如果S≠?，继续更新l（v），z（v），直到S=?停止。如此求出的l（v）就是从u0到v的最短路的权，再反向追溯得到u0到v的最短路的路线。

三、多阶段决策问题的转化

在生产过程中需要考虑生产设备的更新问题。随着设备使用时间的增长，累积效益也会增长，同时维修费用也随之增加，而购买新设备的所需费用越来越多，旧设备的折旧费却越来越少。因此，要合理利用某一设备就需要考虑在该设备的使用年限内计划其更新问题，以使得生产效益达到最优。这就是一个多阶段决策过程。

例1：某学院数据中心有一组教学设备，需要在每年年初进行评估，决定是否更换新设备。该设备每年年初购置价格如表1所示，不同时间折旧费和维修费用如表2所示。其使用年限为五年，现要求制订一个设备更新计划，使得五年内学院对该教学设备所支付的总费用最少。

要将该问题转化为最短路问题，先构造加权有向图G（V，E），该图为完备图K6，如图1所示。

图1中有顶点集V={vi，i=1，2，3，4，5

，6}，其中vi表示第i年（i=1，2，3，4，5）年初购置新设备的决策，v6表示第五年年底的情况；边集E={（vi，vj），i=1，2，3，4，5；i

写出带权邻接矩阵为

0 3 8 15 24 27

0 5 10 17 26

0 6 11 18

0 8 13

0 10

迭代步骤如表3所示。

通过迭代得到从v1到v6的最短路径为v1-v2-v3-v6、v1-v2-v4-v6、v1-v3-v6，权值为26。也就是说有三种设计方法更新设备所需费用都最省，最省费用为26万元。

类似的还有生产策略问题。合理安排生产率对生产效益会有决定性的作用：生产率高了，一方面剩余产品会有积压损坏，另一方面流动资金不能及时回笼；生产率不够，供不应求，利润明显达不到最大值。所以，生产部门应该密切注意市场需求的变化，适时调整生产率，以获取最大利润。该问题要转化为最短路问题，关键在于设置合理的点集和边集，计算出准确的边的加权值。

例2：某加工厂生产某种产品，该产品在年初的需求量为60万单位并以每月10万单位递增。供大于求时，该厂每月花费0.2元保管剩余单位产品；供不应求时，该厂每月单位产品的短期损失费为0.4元。预计每调整一次生产率需要花费10万元的费用，现设计合理的年生产策略，使工厂的总损失最小。

同样的要先构造加权有向图G（V，E），该图仍为完备图K13（图略）。用顶点vi表示第i月（i=1，2，3，4，5，6，7，8，9，10，11，12）月初的决策，v13表示第12月月底的情况；用边（vi，vj）（i=1，2，3，4，5，6，7，8，9，10，

11，12；i

每月之间的库存保管费和短期损失费的算式为M1=（x-60）*0.2，显然最小值为0，下个月的产量调整费用为10万元，所以边（vi，vi+1）的权值为10，特别的（v12，v13）权值为0。

每两个月之间的库存保管费和短期损失费的算式为：（1）M1=（x-60）*0.2；（2）如果（2x-60）≥70，则赋值M2=（2x-130）*0.2，否则赋值M2=（130-2x）*0.4，解得M1+M2的最小值为1，所以边（vi，vi+2）的权值为11，特别的（v11，v13）权值为1。

同理可得（vi，vi+3）的权值为14，（v10，v13）权值为4；（vi，vi+4）的权值为20，（v9，v13）权值为10；（vi，vi+4）的权值为30，（v8，v13）权值为20；（vi，vi+5）的权值为42，（v7，v13）权值为32；（vi，vi+6）的权值为59，（v6，v13）权值为49；（vi，vi+7）的权值为82，（v5，v13）权值为72；（vi，vi+8）的权值为112，（v4，v13）权值为102；（vi，vi+9）的权值为150，（v3，v13）权值为140；（vi，vi+10）的权值为194，（v2，v13）权值为184；（vi，vi+11）的权值为235。

于是可以得到带权邻接矩阵，通过迭代得到从v1到v13的最短路径为v1-v4-v7-v10-v13，权值为46。也就是说该加工厂应该在4月初、7月初和10月初改变生产率总损耗最少，该方案的损耗费用为46万元。

Dijkstra算法的计算过程，除了可以直接用邻接矩阵迭代求解，也可以编写matlab程序实施。所以。把多阶段决策问题转化为最短路问题能客观形象地展示问题本身，同时轻松有效地解决实际问题。

参考文献：

[1]赵静，但琦.数学建模与数学实验[M].北京：高等教育出版社，2003.

[2]刘晓妍，麻兴斌，王晓明.基于最短路的设备更新问题的数学建模[J].河南教育学院学报：自然科学版，2013（04）.

[3]管志忠，刘永明.图论中最短路问题的MATLAB程序实现[J].安庆师范学院学报：自然科学版，2007（01）.

（作者单位：天津机电职业技术学院）