基于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）為?。╲i，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。

①若有非飽和?。╲i，vj），則vj標號（vi，l（vj）），其中l（vj）

=min[l（vi），fij-cij]，vj成為已標號未檢查的點。