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

刘颖+李慧

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

关键词 教育装备；最小费用流理论；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。

③找出S中与V中各点相邻的未标记的顶点（广度优先搜索），若S中的顶点vi经过已标记顶点到vs的总距离之和最短，则vj被标记。令（vs，vi，vj）∈V，其余各点均属于S。

④重复第三步，直到终点vt被标记，至集合S为空为止，算法结束。

⑤逆推可得vs到vt的最短路径。

具体步骤

1）取f（0）=0为初始可行流，依据其对应的费用网络w（f（0）），应用Dijkstra算法求从vs到vt的最短路径，即最短路径的增广链u0，并沿u0调整流量，在新的可行流f（1）上构造新的费用网络w（f（1）），重新寻找最小费用增广链。其中，构造增广费用网络的规则为：零流弧上保持原弧-wij不变；非饱和弧上，后加弧为-wij；饱和弧上，去掉原有弧，后加弧为-wij。

2）如第k步得到最小费用流f（k），构造对应费用网络w（f（k）），寻找最短路径。若不存在最短路径，则f（k）即为网络的最小费用最大流；若存在，则在原网络中得到相应的最小费用增广链，调整f（k）为：

3 实例应用

某高校计划引进一批新型教育装备，需从某教育装备配备中心订购，该教育装备中心到学校存在多条运输路线（如图1所示），其中ABCD为主要经过的几个中转站，箭头为运输系统规定的方向，弧（bij，cij）中bij为运输单位费用（单位：千元），cij表示此路段所能承受的容量。请设定合理的运输路线，在保证运输总量的前提下，使运输成本最小。

本例中的运输问题是典型的最小费用最大流问题。求解时首先将费用流网络图分解为费用网络图w（f（0））和流量网络图D（f（1））。

1）取f（0）=0为初始可行流，构造相应的费用网络图w（f（0）），如图2（a）所示。

2）在w（f（0））上应用Dijkstra算法求解vs到vt的最短路径，即最小费用增广链为vs→v1→v4→vt，如图2（a）中标粗路线。

3）在原网络图D（f（0））中与这条最短路径相应的增广链为u=（vs，v1，v4，vt）。沿着该增广链调整流量，δ=min（8，4，6）=4，得到新的可行流f（1），其流值v（f（1））=4，如图2（b）所示。

4）构造与D（f（1））相应的费用网络w（f（1）），如图3（a）中的粗线条所示。同样，求出vs到vt的最短路径为vs→v1→v3→vt，在流量网络原网络图D（f（1））中与这条最短路径相应的增广链为u=（vs，v1，v3，vt）。沿着该增广链调整流量，δ=min（4，7，4）=4，得到新的可行流f（2），其流值v（f（2））=8，如图3（b）所示。

5）构造与D（f（2））相应的费用网络w（f（2）），如图4（a）中的粗线条所示。同样，求出vs到vt的最短路径为vs→v2→v4→vt，在流量网络原网络图D（f（2））中与这条最短路径相应的增广链为u=（vs，v2，v4，vt）。沿着该增广链调整流量，δ=min（5，3，2）=2，得到新的可行流f（3），其流值v（f（3））=12，如图4（b）所示。

6）构造与D（f（3））相应的费用网络w（f（3）），如图5所示。由于w（f（3））中无法找到vs到vt的最短路径，说明D（f（3））已不存在增广链，求解终止，D（f（3））所示的流即为所求的最小费用最大流。此时，流值v（f（3））=12，最小费用为：

因此，此次运输方案应选择的路线是vs→v2→v4→vt，能够在满足运输总量的前提下将运输成本最小化。应用最小费用最大流定理，对教育装备的运输问题做出合理决策。

4 结语

在信息技术与教育深度融合的时代，先进的教育装备使传统课堂变得有趣丰富，多媒体教学的普及既保证了教学质量，也促进了教育装备行业的发展。教育装备运输问题是物资管理、教育装备管理中经常遇到的问题，合理安排运输方案、追求运输成本最小化，是教育机构和教育装备部门共同的目标。本文结合实际的教育装备运输问题，依据最小费用最大流理论及Dijkstra算法实现模型求解，给出教育装备运输问题的一种解决方案，为教育装备保障部门工作提供了依据。

参考文献

[1]邵林海，曲铁华.信息技术与教育“深度融合”背景下师范教育的未来发展[J].黑龙江高教研究院，2015（5）.

[2]胡又农.教育装备学导论[M].2版.北京：北京大学出版社，2011：163-177.

[3]胡运权，郭耀煌.运筹学教程[M].2版.北京：清华大学出版社，2003.

[4]鲁海燕.最小费用网络流的若干新问题研究[D].杭州：浙江大学理学院，2007.

[5]高随祥.图论与网络流理论[M].北京：高等教育出版社，2009.

[6]辛宇.基于运筹学图论的物流网络优化研究[J].中国外资，2011（6）：125-127.

[7]李慧.教育装备运筹规划[M].北京：北京大学出版社，2010：122-126.