打开文本图片集
摘 要 随着大学扩招政策的深度实施，各高校生源明显增加，对高校的教学质量提出新要求。教育装备更新换代迅速使得教育装备保障问题凸显，然而由于运输系统运营能力的限制，在规定时间内运输大量的教育设备、制订合理的运输安排计划尤为关键。为了满足高校对教育装备规模的新要求，保障教学质量，建立教育装备保障问题数学模型，依据Ford-Fulkerson方法实现模型的求解，给出较优方案，为教育装备保障工作提供依据。
关键词 教育装备保障；最大流；Ford-Fulkerson方法
中图分类号：G657 文献标识码：B
文章编号：1671-489X（2017）05-0009-03
1 前言
2013年全国各类高等教育在校学生总规模达到3460万人，高等教育毛入学率达到34.5%，规模庞大的生源对高校能否保证教学质量提出挑战。教育装备现代化建设不断加快，尤其是高科技在教育领域的广泛应用，有助于开展丰富多彩的教学活动，保障并提升教学质量，使得高校对教育装备的需求增多。因此，教育装备保障部门如何合理安排工作，实现教育装备供应的最优决策，成为亟待解决的关键问题。
2 图论与网络流理论
1736年，瑞士著名数学家欧拉（L.Euler）发表的一篇解决“哥尼斯堡七桥问题”（Konigsberg Seven Bridges Problem）的论文，标志了图论的起源。经历长时间的发展，图论和网络流理论已成为一门有趣又有用、既成熟又活跃的学科分支，应用十分广泛。随着计算机网络技术的飞速发展，基于图论和网络流的思想解决问题的方法被普遍使用，在应用数学、计算机科学与技术、运筹学、物理学、生命科学、管理科学等学科领域都能找到其应用范例，是算法理论和设计的重要参照。
图论的基本概念
1）图（Graph），即点和边的集合，记作G（V，E）。其中，V是点的集合，E是边的集合。通常点代表事物，边代表事物间的关系。
2）连通图（Connected graph）：vi和vj为G中的两个点，若存在从vi到vj的可达路径，则称点vi和vj是连通的；若图G（V，E）中任意两个顶点都连通，图G即为连通图。
3）赋权图（Weighted graph），即有权值的图，图G（V，E）的任意一条边（vi，vj）均有一个数wij与之对应，wij称为边（vi，vj）的权。
4）有向图（Digraph）：若图G（V，E）的任意一条边（vi，
vj）都具有一个方向，图G即为有向图，表示为。
5）弧集（Arc set）：，，是非空顶点集，是V×V的一个子集，即有方向的边的集合，称为弧集，表示为A。
网络流理论 现实应用中经常需要考虑网络及网络上的流，比如公路货运或客运网络、输电网络、通信网络等。这些网络的共同点是：具有出发点、收点、中间点的有向图，每条弧都有传输能力的限制。
1）容量网络（Capacity network）。设一个赋权有向图G（V，A），对于G中的每一个弧（vi，vj），相应地给一个权值cij（cij>0），称为弧（vi，vj）的容量。其中，仅有一个点的入度为零，称为发点，记为vs；仅有一个点的出度为零，称为收点，记为vt；其余的点称为中间点。如此，图G就被称为容量网络，记作G（V，A，C）。
2）网络流（Network flow），是指定义在弧集A上的函数f={f（vi，vj）}，并称f（vi，vj）为弧（vi，vj）上的流量。
3）可行流（Furthest flow）：对G中每条边（vi，vj），满足0≤fij≤cij（容量约束），对中间点，满足∑jfij=∑kfki
平衡条件），对收点vt与发点vs，有∑ifsi=∑jfjt=W（流量守
恒），W是网络的总流量。
4）割集容量（Cutset capacity）：给定容量网络G（V，
A，C），若V被剖分为两个非空集合V1和V2，使vs∈V1，vt
∈V2，则将弧集（V1，V2）称为（分离vt和vs的）割集。割集（V1，V2）中所有起点在V1、终点在V2的边的容量之和称为割集容量，在容量网络的所有割集中，割集容量最小的割集称为最小割集。
5）增广链（Augmenting chain）。对于可行流f={fij}，
使fij=ciij的弧称为饱和弧，fij
6）最大流最小割定理：任意一个网络G（V，A，C）中，最大流的流量等于分离vs和vt的最小割集的容量。
Ford-Fulkerson方法 最大流最小割定理提供了一个寻求网络中最大流的方法。假设网络G中有一个可行流f，只要判断网络是否存在关于可行流f的增广链，如果沒有增广链，那么f一定是最大流；如有增广链，那么可以按照定理中的必要性，不断改进和增大可行流f的流量，最终得到网络G中的一个最大流。也就是说，求最大流问题就是找增广链问题。
Ford-Fulkerson方法的基本步骤如下。
1）给vs标号（0，+∞），即l（vs）=∞，vs成为已标未查顶点，其余都是未标未查顶点。
2）取一个已标未查顶点vi，检查其一切未标号邻点vj。
①若有非饱和弧（vi，vj），则vj标号（vi，l（vj）），其中l（vj）
=min[l（vi），fij-cij]，vj成为已标号未检查的点。
②若有非零弧（vi，vj），则vj标号（-vi，l（vj）），其中l（vj）
=min[l（vi），fji]，vj成为已标号未检查的点。检查完vi的所有邻点，vi成为已标号已检查的点。
3）重复步骤2），直到vt成为标号点或所有标号点都检查过。
①若vt成为标号点，表明得到一条vs到vt的增广链，转入调整过程。
②若所有标号点都检查过，表明这时的可行流就是最大流，算法结束。
调整过程：在增广链上，前向弧流量增加l（vt），后向弧流量减少l（vt），非增广链上的弧不变。
3 实例应用
某高校急需一种教育耗材，购买量较大，需要在指定时间内运至学校。该耗材由教育装备中心统一购买并发放，但由于运输系统运营能力的限制，需分批次将耗材运出。高校到教育装备中心的路线如图1所示，ABCD为可能需要经过的中转站，箭头为运输系统规定方向。弧（cij，fij）中，cij表示此运输系统中该路段所能承受的容量，fij表示运输的流量（单位：件千米）。请指定合理的运输安排方案，使耗材的运输量尽可能得多。
可将问题转化为求解容量网络中的最大流问题，转化为流量网络，如图2所示。
应用Ford-Fulkerson方法求解如下。
1）为vs标号“（0，+∞）”。
2）检查vs，为vs为起点的未饱和弧的未标号v1和v2标号，（vs，v1）和（vs，v2）均为正向非饱和弧，所以为v2和v1标号分别为（vs，l（v1））和（vs，l（v2）），其中：
l（v1）=min{l（vs），cs1-fs1}=min{+∞，9-6}=3，
l（v2）=min{l（vs），cs2-fs2}=min{+∞，15-8}=7，
3）检查v1，与其相邻的未标号有v2、v3、v4，而弧（v1，v3）是饱和弧，弧（v1，v2）是负向非零流弧，所以（v1，v2）和（v1，v4）标号分别为（-v1，l（v2））和（v1，l（v4）），其中：
l（v2）=min{l（v1），f21}=min{3，5}=3，
l（v4）=min{l（v1），c14-f14}=min{3，5-4}=1，
4）检查v2，与其相邻的未标号的有v4，而弧（v2，v4）是饱和弧，所以v2点的标号中断。
5）检查v4，与其相邻的未标号的有v3和vt，要优先选择收点vt，得到标号（v4，l（vt）），其中：
l（vt）=min{l（v4），c4t-f4t}=min{1，6-5}=1
由于收点vt得到了标号，即得到一条增广链，如图3所示。
6）在此增广链上，正向流量增加1，若存在负向流量减少1，本题不存在，见图4。去掉所有标号，从出发点重新进行标号，此时图中不存在增广链，算法结束，图3所示的可行流即为最大流，值为15。
因此，教育装备中心在运输耗材时，选择{（vs，v1），
（v1，v4），（v4，vt）}的运输线路，能够尽可能多地运送耗材，扩大运输能力，是较为合理的决策方案。
4 结语
一方面，随着高校对教学质量的要求不断提高，以及信息技术的发展，高科技新体验的教学装备层出不穷；另一方面，生源不斷扩大，高校教育装备有更新替换的需求，大规模的教育装备保障问题亟待解决。因此，要求教育装备中心等统一采购和发放部门合理安排运输方案，尤其是现代物流新兴行业的出现，对教育装备的运输问题加以规划不容小视。本文建立教育装备保障问题的数学模型，依据Ford-Fulkerson方法实现模型的求解，给出教育装备保障问题中设备运输的可行性优化方案，希望为教育装备保障部门工作提供依据。
参考文献
[1]中华人民共和国教育部.2013年全国教育事业发展统计公报[DB/OL].http：///publicfiles/business/htmlfiles/moe/moe_633/201407/171144.html.
[2]胡运权，郭耀煌.运筹学教程[M].2版.北京：清华大学出版社，2003.
[3]高随祥.图论与网络流理论[M].北京：高等教育出版社，2009.
[4]李慧.教育装备运筹规划[M].北京：北京大学出版社，2010.
[5]辛宇.基于运筹学图论的物流网络优化研究[J].中国外资，2011（6）：125-127.
[6]胡又农.教育装备学导论[M].2版.北京：北京大学出版社，2011.