基于Ford—Fulkerson方法的教育装备保障问题分析

刘颖+李慧

摘 要 随着大学扩招政策的深度实施，各高校生源明显增加，对高校的教学质量提出新要求。教育装备更新换代迅速使得教育装备保障问题凸显，然而由于运输系统运营能力的限制，在规定时间内运输大量的教育设备、制订合理的运输安排计划尤为关键。为了满足高校对教育装备规模的新要求，保障教学质量，建立教育装备保障问题数学模型，依据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的弧称为饱和弧，fij0的弧称为非零流弧。若?是连接发点vs和收点vt的一条链，规定链的方向是从vs到vt，边的方向与链的方向相同，即前向弧，否则为后向弧。若?满足前向弧都是非饱和弧，后向弧都是非零流弧，则称?是可行流f的一条增广链。

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成为已标号未检查的点。