基于Ford—Fulkerson方法的教育裝備保障問(wèn)題分析

劉穎+李慧

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

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

中圖分類號(hào)：G657 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1671-489X（2017）05-0009-03

1 前言

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

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

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

圖論的基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）取一個(gè)已標(biāo)未查頂點(diǎn)vi，檢查其一切未標(biāo)號(hào)鄰點(diǎn)vj。

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

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