最小费用流理论在教育装备运输中的应用

摘 要 建立教育装备运输成本问题的数学模型，依据算法实现模型的求解，给出较优运输方案，使总的运输代价最小，为教育装备配送工作提供依据。

关键词 教育装备；最小费用流理论；Dijkstra算法

中图分类号：G48 文献标识码：B

文章编号：1671-489X（2016）20-0016-03

随着教育水平的提高，信息技术与教育的融合是必然趋势[1]，先进的教育技术装备给课堂带来新的视听觉体验，高科技在教育领域的广泛应用使得教育装备更新换代加速，因此，高校对教育装备保障部门提出新要求。教育装备的运输问题属于物资调运问题，是物资管理、教育装备中经常遇到的问题[2]，不同的交通工具和道路状况导致运输方案的交通费用存在明显差异，在满足运输总量的前提下，教育装备保障部门合理安排运输路线，以最小的代价将所需设备运到目的地尤为重要。

1 图论与网络流理论

图论起源于瑞士著名数学家欧拉（L.Euler）在1736年发表的一篇解决“哥尼斯堡七桥问题”（Konigsberg Seven Bridges Problem）的论文[3]，网络流的早期发展可以追溯到Kantorovich、Hitchcock以及Koopmans等人研究的运输问题[4]。随着计算机网络技术的飞速发展，图论和网络流理论已成为一门新的学科分支，基于图论和网络流的思想解决问题的方法应用广泛，在应用数学、计算机科学与技术、运筹学、物理学、生命科学等学科领域都能找到其范例[5]。

图论的基本概念

1）图（Graph），即点和边的集合，记作G（V，E）。其中，V是点的集合，E是边的集合。

2）赋权图（Weighted graph），即带权值的图，图G的任意一条边（vi，vj）都有一个数wij与之对应，wij称为边（vi，vj）的权。

3）有向图（Directed graph）：图G的任意一条边（vi，vj）都具有一个方向，即为有向图，表示为。

4）弧集（Arc set）：，是非空顶点集，是V×V的一个子集，即有方向的边的集合称为弧集，表示为A。

网络流理论

1）容量网络（Capacity network）和费用网络（cost network）：设一个赋权有向图G（V，E），对于G中的每一个弧（vi，vj），相应地给一个权值cij（cij≥0），称为弧（vi，vj）的容量；图G被称为容量网络，记作G（V，A，C）。对于G中的每一个弧（vi，vj），相应地赋予一个非负实数bij，称为弧（vi，vj）的费用，图G被称为费用网络，记作G（V，A，C，w），也可以记为N=（V，A，C，w）。其中仅有一个点的入度为零，记为vs；仅有一个点的出度为零，记为vt。

2）网络流（Network flow）：指定义在弧集A上的函数f={fij}并称f（vi，vj）为弧（vi，vj）上的流量。

3）可行流（Furthest flow）：对G中每条边（vi，vj），满足0≤fij≤cij（容量约束）；对中间点，满足∑jfij=∑kfki（平衡条件）；对收点vt与发点vs，有∑ifsi=∑jfjt=W（流量守恒），W是网络的总流量。对G上任意一可行流，B（f）=∑wijfij称为可行流的费用。

4）增广链（Augmenting chain）。对于可行流f={fij}，使fij=cij的弧称为饱和弧，fij0的弧称为非零流弧。若μ是连接发点vs和收点vt的一条链，规定链的方向是从vs到vt，边的方向与链的方向相同，即前向弧，记作u+；否则为后向弧，记作u-。若u+都为非饱和弧，u-都为非零流弧，则称μ是可行流f的一条增广链。

5）增广链的费用（Cost of augmenting chain）：当沿着一条关于可行流f的增广链μ，以δ调整f，得到新的可行流，可行流f和f′的费用只在增广链μ上有差异，其费用差为：

6）最小费用流（Minimum cost flow）：对于网络N=（V，A，C，w），要求B（f）最小且流量为某确定值f的可行流问题，即最小费用流问题；求B（f）最小且流量f为最大的问题称为最小费用最大流的问题[6]。

2 最小费用流问题的求解

解法分析 求解最小费用流问题的基本思想是在寻求最大流算法过程中考虑费用最小的流。首先选取一个最小费用流，找出其增广链并进行调整，直到找不到增广链为止，这时的可行流即为最小费用最大流。

1）最小费用增广链。寻找最小费用增广链是求解最小费用流问题的关键。构造一个费用网络图f（k），其顶点为原网络N的顶点，把N中的每条弧（vi，vj）变为两条相反方向的弧（vi，vj）和（vj，vi），规定f（k）中弧（vi，vj）的权wij为：

其中，长度为+∞的弧可略去。因此，求最小费用增广链等价于在f（k）中求vs到vt的最短路径。本文用Dijkstra算法完成最短路径的求解。

2）Dijkstra算法。Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959年提出的，用于解决有向图中最短路径问题。要求最短路径，首先给定赋权有向图G（V，A），将图G所有顶点分为两组，令V表示已标记最短路径的顶点集合，S表示未标记最短路径的顶点集合，定义dij为图的邻接矩阵中顶点i和j之间的距离，即：

求从vs到vt的最短路径的具体步骤如下。

①将vs标记为“0”，初始时，令vs∈V，其余各点均属于S。

②从vs出发，在S中找到与vs相邻且距离最短的顶点vi，标记为vs到vi弧上的权值wsi，即顶点vi已被标记。令（vs，vi）∈V，其余各点均属于S。