基于矩阵算法的最小费用优化模型选择及实现

一、引言

在大型企业集团当中，各个子工厂、加工车间、原材料供给单位等部门之间，经常存在物流运输，物资调度等现象。如何节约企业内部运输的总费用，减少人力、物力、财力的消耗，使其费用最优化，是每个企业都需要重点考虑的问题。也是企业健康持续发展的重要条件之一。

对于优化问题在文献[1-3]中有大量的论述和应用。而针对这种企业运输布局中的费用优化问题。以前，主要是根据网络图的基本原理，通过运用Dijkstra算法[4]，分别求解图中某一点到其他点的最短路径，然后逐个解析其他各点分别到其他各点的最短路径，获得网络图中任意两点之间的最优路径集合。这种方法尽管可以解决问题，可其算法时间复杂度较大；另外，最短的路径未必是运输费用最低的路径。对其存在问题，文章提出应用矩阵算法思想结合权值合理选择，在着重考虑影响运输费用的重要因素（各单位的物资调度数量）基础上，构建一个较为实际的影响运输费用的算法模型。以期达到运输布局中真正费用最优化。

二、模型算法的改进和设计

在日常生活中，我们经常遇到各种各样的图：公路交通网或者铁路交通网、管网图、通讯联络图等。本文则主要是针对企业集团内部各子单位之间的物资调度等构建的运输图。通常，我们用一个二元组[5]V=（V，E）来表示一个图。其中V={V1，V2…Vn}是点的集合，称为节点集，E{（Vi，Vj）；i，j∈（1，2，…n）}是边的集合，称为边集。对于G中的一条边（Vi，Vj），称Vi为边的起点，称Vj为边的终点，有时V中各点也称为顶点。如果在边的集合中，每条边都有一个权值，则该图称为赋权图。这类图是实际生活生产中最常用的网络图。在此，为了研究方便，假设顶点Vi到Vj的物资运输路径长度为Vij。

假设，在运输图中存在r个顶点，我们定义dij为图中任意两个相邻点的距离，若i与j不相邻，令dij=∞。

其主要算法过程：我们求V1与V2之间的最短路径时，考虑之间存在一个中间点的情况。那么，V1到V2的最短路径应为min{d11+d12，d12+22，……d1r+dr2}。对于Vi和Vj而言，也就是min{dir+drj}。

此时，构造新矩阵D（1），令D（1）中每个元素dij（1）= min{dir+drj}，则新构造矩阵给出的是网络中任意两点之间直接到达和包含一个中间点时的最短路径距离。以此类推，逐渐增加可能的中间点数目，就可以得到，直接达到或者包含最大中间点数目时的最短路径距离的构造矩阵。

假若网络图中有p个顶点，则其计算一般不会超过D（k）。k值范围大小，可由式子2k-1

通过该运算，所得的结果是路径最短距离所构成的矩阵D。针对企业实际的运输费用问题，选择合理适当的权值附加矩阵M=[m11，m12，……m1r]，进一步计算获得运输费用最优矩阵min Z=M×D。

我们依据某大型企业集团中内部各个子单位之间物资运输实际情况，对于所构成的运输矩阵，通过VC6.0编译器进行算法仿真验证。

首先，列出该企业集团中各个子单位作为顶点时的任意两点之间的路径距离初始矩阵如图1所示。

其次，根据迭代次数控制算式2k-1

最后，采用运输图中各个顶点子单位运输物资量作为权值附加矩阵参照因数。其数值假定分别为V1—3，V2—4，V3—2.5，V4—2，V5—5，V6—6，V7—6。按照模型min Z=M×D，我们将计算所得的D（3）的第一行乘顶点V1的物资运输量，则其乘积数含义为：是当假定主要加工车间建于各个布局顶点时，V1顶点物资运输所耗费的运输费用。以此类推，则可以分别求得各个顶点物资运输费用的具体数值，经过演算，我们可以列出当主要加工厂分别建于Vi顶点时，所得到的七个顶点物资运输费用总和表，如表1所示。

显然，上表的累加计算表明，当企业的主要加工厂建于顶点V6时最合适。因为此时的综合运输费用最少。

三、结束语

本文通过针对大型企业集团内部，主要加工车间地点和其他材料供应单位之间的综合运输费用达到最少这一目标，运用数据结构当中矩阵算法并附加各顶点物资运输量参照因子，提出了解决诸如此类问题的相对通用的模型算法，并进行了模拟演示，获得了最终优化结果。

针对这类问题，除了关注矩阵算法以外，我们着重要强调的是附加因子的设置要合理，符合实际应用及计算用途。这就需要一定的实际工作经验和把握事物本质的能力和处理方法。同样，该通用模型在处理其他交通网络问题、大型区域水流分支引导等问题，也提供了相应的参考和支持，具有一定的实用价值指导作用。

参考文献

[1]朱文兴，贾磊，赵建玉，刘红波.城市交通网络路径优化建模与仿真，系统仿真学报，2005.06

[2]刘婷，王秋平，徐卫博.城市干线交通协调控制仿真优化，交通科技与经济，2009.03

[3]苏海滨，王继东.交通网络中多路径优化选择算法的研究，公路交通科技，2007.09

[4]李大友，彭波.数据结构，清华大学出版社，2002.03

[5]何迪，严余松，郭守儆，郝光.基于矩阵分析的公共交通网络最优路径算法，西南交通大学学报，2007.03

[6]胡运权，运筹学基础及应用，高等教育出版社，2004.04

推荐访问： 矩阵 算法 最小 模型 费用

---