基于Ford—Fulkerson方法的教育裝備保障問題分析

劉穎+李慧

摘 要 隨著大學(xué)擴招政策的深度實施，各高校生源明顯增加，對高校的教學(xué)質(zhì)量提出新要求。教育裝備更新?lián)Q代迅速使得教育裝備保障問題凸顯，然而由于運輸系統(tǒng)運營能力的限制，在規(guī)定時間內(nèi)運輸大量的教育設(shè)備、制訂合理的運輸安排計劃尤為關(guān)鍵。為了滿足高校對教育裝備規(guī)模的新要求，保障教學(xué)質(zhì)量，建立教育裝備保障問題數(shù)學(xué)模型，依據(jù)Ford-Fulkerson方法實現(xiàn)模型的求解，給出較優(yōu)方案，為教育裝備保障工作提供依據(jù)。

關(guān)鍵詞 教育裝備保障；最大流；Ford-Fulkerson方法

中圖分類號：G657 文獻標(biāo)識碼：B

文章編號：1671-489X（2017）05-0009-03

1 前言

2013年全國各類高等教育在校學(xué)生總規(guī)模達到3460萬人，高等教育毛入學(xué)率達到34.5%，規(guī)模龐大的生源對高校能否保證教學(xué)質(zhì)量提出挑戰(zhàn)。教育裝備現(xiàn)代化建設(shè)不斷加快，尤其是高科技在教育領(lǐng)域的廣泛應(yīng)用，有助于開展豐富多彩的教學(xué)活動，保障并提升教學(xué)質(zhì)量，使得高校對教育裝備的需求增多。因此，教育裝備保障部門如何合理安排工作，實現(xiàn)教育裝備供應(yīng)的最優(yōu)決策，成為亟待解決的關(guān)鍵問題。

2 圖論與網(wǎng)絡(luò)流理論

1736年，瑞士著名數(shù)學(xué)家歐拉（L.Euler）發(fā)表的一篇解決“哥尼斯堡七橋問題”（Konigsberg Seven Bridges Problem）的論文，標(biāo)志了圖論的起源。經(jīng)歷長時間的發(fā)展，圖論和網(wǎng)絡(luò)流理論已成為一門有趣又有用、既成熟又活躍的學(xué)科分支，應(yīng)用十分廣泛。隨著計算機網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，基于圖論和網(wǎng)絡(luò)流的思想解決問題的方法被普遍使用，在應(yīng)用數(shù)學(xué)、計算機科學(xué)與技術(shù)、運籌學(xué)、物理學(xué)、生命科學(xué)、管理科學(xué)等學(xué)科領(lǐng)域都能找到其應(yīng)用范例，是算法理論和設(shè)計的重要參照。

圖論的基本概念

1）圖（Graph），即點和邊的集合，記作G（V，E）。其中，V是點的集合，E是邊的集合。通常點代表事物，邊代表事物間的關(guān)系。

2）連通圖（Connected graph）：vi和vj為G中的兩個點，若存在從vi到vj的可達路徑，則稱點vi和vj是連通的；若圖G（V，E）中任意兩個頂點都連通，圖G即為連通圖。

3）賦權(quán)圖（Weighted graph），即有權(quán)值的圖，圖G（V，E）的任意一條邊（vi，vj）均有一個數(shù)wij與之對應(yīng)，wij稱為邊（vi，vj）的權(quán)。

4）有向圖（Digraph）：若圖G（V，E）的任意一條邊（vi，

vj）都具有一個方向，圖G即為有向圖，表示為。

5）弧集（Arc set）：，，是非空頂點集，是V×V的一個子集，即有方向的邊的集合，稱為弧集，表示為A。

網(wǎng)絡(luò)流理論 現(xiàn)實應(yīng)用中經(jīng)常需要考慮網(wǎng)絡(luò)及網(wǎng)絡(luò)上的流，比如公路貨運或客運網(wǎng)絡(luò)、輸電網(wǎng)絡(luò)、通信網(wǎng)絡(luò)等。這些網(wǎng)絡(luò)的共同點是：具有出發(fā)點、收點、中間點的有向圖，每條弧都有傳輸能力的限制。

1）容量網(wǎng)絡(luò)（Capacity network）。設(shè)一個賦權(quán)有向圖G（V，A），對于G中的每一個弧（vi，vj），相應(yīng)地給一個權(quán)值cij（cij>0），稱為弧（vi，vj）的容量。其中，僅有一個點的入度為零，稱為發(fā)點，記為vs；僅有一個點的出度為零，稱為收點，記為vt；其余的點稱為中間點。如此，圖G就被稱為容量網(wǎng)絡(luò)，記作G（V，A，C）。

2）網(wǎng)絡(luò)流（Network flow），是指定義在弧集A上的函數(shù)f={f（vi，vj）}，并稱f（vi，vj）為弧（vi，vj）上的流量。

3）可行流（Furthest flow）：對G中每條邊（vi，vj），滿足0≤fij≤cij（容量約束），對中間點，滿足∑jfij=∑kfki

平衡條件），對收點vt與發(fā)點vs，有∑ifsi=∑jfjt=W（流量守

恒），W是網(wǎng)絡(luò)的總流量。

4）割集容量（Cutset capacity）：給定容量網(wǎng)絡(luò)G（V，

A，C），若V被剖分為兩個非空集合V1和V2，使vs∈V1，vt

∈V2，則將弧集（V1，V2）稱為（分離vt和vs的）割集。割集（V1，V2）中所有起點在V1、終點在V2的邊的容量之和稱為割集容量，在容量網(wǎng)絡(luò)的所有割集中，割集容量最小的割集稱為最小割集。

5）增廣鏈（Augmenting chain）。對于可行流f={fij}，

使fij=ciij的弧稱為飽和弧，fij0的弧稱為非零流弧。若?是連接發(fā)點vs和收點vt的一條鏈，規(guī)定鏈的方向是從vs到vt，邊的方向與鏈的方向相同，即前向弧，否則為后向弧。若?滿足前向弧都是非飽和弧，后向弧都是非零流弧，則稱?是可行流f的一條增廣鏈。

6）最大流最小割定理：任意一個網(wǎng)絡(luò)G（V，A，C）中，最大流的流量等于分離vs和vt的最小割集的容量。

Ford-Fulkerson方法 最大流最小割定理提供了一個尋求網(wǎng)絡(luò)中最大流的方法。假設(shè)網(wǎng)絡(luò)G中有一個可行流f，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流f的增廣鏈，如果沒有增廣鏈，那么f一定是最大流；如有增廣鏈，那么可以按照定理中的必要性，不斷改進和增大可行流f的流量，最終得到網(wǎng)絡(luò)G中的一個最大流。也就是說，求最大流問題就是找增廣鏈問題。

Ford-Fulkerson方法的基本步驟如下。

1）給vs標(biāo)號（0，+∞），即l（vs）=∞，vs成為已標(biāo)未查頂點，其余都是未標(biāo)未查頂點。

2）取一個已標(biāo)未查頂點vi，檢查其一切未標(biāo)號鄰點vj。

①若有非飽和弧（vi，vj），則vj標(biāo)號（vi，l（vj）），其中l(wèi)（vj）

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