最小費(fèi)用流理論在教育裝備運(yùn)輸中的應(yīng)用

劉穎+李慧

摘 要 建立教育裝備運(yùn)輸成本問(wèn)題的數(shù)學(xué)模型，依據(jù)算法實(shí)現(xiàn)模型的求解，給出較優(yōu)運(yùn)輸方案，使總的運(yùn)輸代價(jià)最小，為教育裝備配送工作提供依據(jù)。

關(guān)鍵詞 教育裝備；最小費(fèi)用流理論；Dijkstra算法

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

文章編號(hào)：1671-489X（2016）20-0016-03

隨著教育水平的提高，信息技術(shù)與教育的融合是必然趨勢(shì)[1]，先進(jìn)的教育技術(shù)裝備給課堂帶來(lái)新的視聽(tīng)覺(jué)體驗(yàn)，高科技在教育領(lǐng)域的廣泛應(yīng)用使得教育裝備更新?lián)Q代加速，因此，高校對(duì)教育裝備保障部門(mén)提出新要求。教育裝備的運(yùn)輸問(wèn)題屬于物資調(diào)運(yùn)問(wèn)題，是物資管理、教育裝備中經(jīng)常遇到的問(wèn)題[2]，不同的交通工具和道路狀況導(dǎo)致運(yùn)輸方案的交通費(fèi)用存在明顯差異，在滿足運(yùn)輸總量的前提下，教育裝備保障部門(mén)合理安排運(yùn)輸路線，以最小的代價(jià)將所需設(shè)備運(yùn)到目的地尤為重要。

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

圖論起源于瑞士著名數(shù)學(xué)家歐拉（L.Euler）在1736年發(fā)表的一篇解決“哥尼斯堡七橋問(wèn)題”（Konigsberg Seven Bridges Problem）的論文[3]，網(wǎng)絡(luò)流的早期發(fā)展可以追溯到Kantorovich、Hitchcock以及Koopmans等人研究的運(yùn)輸問(wèn)題[4]。隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，圖論和網(wǎng)絡(luò)流理論已成為一門(mén)新的學(xué)科分支，基于圖論和網(wǎng)絡(luò)流的思想解決問(wèn)題的方法應(yīng)用廣泛，在應(yīng)用數(shù)學(xué)、計(jì)算機(jī)科學(xué)與技術(shù)、運(yùn)籌學(xué)、物理學(xué)、生命科學(xué)等學(xué)科領(lǐng)域都能找到其范例[5]。

圖論的基本概念

1）圖（Graph），即點(diǎn)和邊的集合，記作G（V，E）。其中，V是點(diǎn)的集合，E是邊的集合。

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

3）有向圖（Directed graph）：圖G的任意一條邊（vi，vj）都具有一個(gè)方向，即為有向圖，表示為。

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

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

1）容量網(wǎng)絡(luò)（Capacity network）和費(fèi)用網(wǎng)絡(luò)（cost network）：設(shè)一個(gè)賦權(quán)有向圖G（V，E），對(duì)于G中的每一個(gè)?。╲i，vj），相應(yīng)地給一個(gè)權(quán)值cij（cij≥0），稱(chēng)為?。╲i，vj）的容量；圖G被稱(chēng)為容量網(wǎng)絡(luò)，記作G（V，A，C）。對(duì)于G中的每一個(gè)弧（vi，vj），相應(yīng)地賦予一個(gè)非負(fù)實(shí)數(shù)bij，稱(chēng)為弧（vi，vj）的費(fèi)用，圖G被稱(chēng)為費(fèi)用網(wǎng)絡(luò)，記作G（V，A，C，w），也可以記為N=（V，A，C，w）。其中僅有一個(gè)點(diǎn)的入度為零，記為vs；僅有一個(gè)點(diǎn)的出度為零，記為vt。

2）網(wǎng)絡(luò)流（Network flow）：指定義在弧集A上的函數(shù)f={fij}并稱(chēng)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ò)的總流量。對(duì)G上任意一可行流，B（f）=∑wijfij稱(chēng)為可行流的費(fèi)用。

4）增廣鏈（Augmenting chain）。對(duì)于可行流f={fij}，使fij=cij的弧稱(chēng)為飽和弧，fij0的弧稱(chēng)為非零流弧。若μ是連接發(fā)點(diǎn)vs和收點(diǎn)vt的一條鏈，規(guī)定鏈的方向是從vs到vt，邊的方向與鏈的方向相同，即前向弧，記作u+；否則為后向弧，記作u-。若u+都為非飽和弧，u-都為非零流弧，則稱(chēng)μ是可行流f的一條增廣鏈。

5）增廣鏈的費(fèi)用（Cost of augmenting chain）：當(dāng)沿著一條關(guān)于可行流f的增廣鏈μ，以δ調(diào)整f，得到新的可行流，可行流f和f′的費(fèi)用只在增廣鏈μ上有差異，其費(fèi)用差為：

6）最小費(fèi)用流（Minimum cost flow）：對(duì)于網(wǎng)絡(luò)N=（V，A，C，w），要求B（f）最小且流量為某確定值f的可行流問(wèn)題，即最小費(fèi)用流問(wèn)題；求B（f）最小且流量f為最大的問(wèn)題稱(chēng)為最小費(fèi)用最大流的問(wèn)題[6]。

2 最小費(fèi)用流問(wèn)題的求解

解法分析 求解最小費(fèi)用流問(wèn)題的基本思想是在尋求最大流算法過(guò)程中考慮費(fèi)用最小的流。首先選取一個(gè)最小費(fèi)用流，找出其增廣鏈并進(jìn)行調(diào)整，直到找不到增廣鏈為止，這時(shí)的可行流即為最小費(fèi)用最大流。

1）最小費(fèi)用增廣鏈。尋找最小費(fèi)用增廣鏈?zhǔn)乔蠼庾钚≠M(fèi)用流問(wèn)題的關(guān)鍵。構(gòu)造一個(gè)費(fèi)用網(wǎng)絡(luò)圖f（k），其頂點(diǎn)為原網(wǎng)絡(luò)N的頂點(diǎn)，把N中的每條?。╲i，vj）變?yōu)閮蓷l相反方向的弧（vi，vj）和（vj，vi），規(guī)定f（k）中?。╲i，vj）的權(quán)wij為：

其中，長(zhǎng)度為+∞的弧可略去。因此，求最小費(fèi)用增廣鏈等價(jià)于在f（k）中求vs到vt的最短路徑。本文用Dijkstra算法完成最短路徑的求解。

2）Dijkstra算法。Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959年提出的，用于解決有向圖中最短路徑問(wèn)題。要求最短路徑，首先給定賦權(quán)有向圖G（V，A），將圖G所有頂點(diǎn)分為兩組，令V表示已標(biāo)記最短路徑的頂點(diǎn)集合，S表示未標(biāo)記最短路徑的頂點(diǎn)集合，定義dij為圖的鄰接矩陣中頂點(diǎn)i和j之間的距離，即：

求從vs到vt的最短路徑的具體步驟如下。

①將vs標(biāo)記為“0”，初始時(shí)，令vs∈V，其余各點(diǎn)均屬于S。

②從vs出發(fā)，在S中找到與vs相鄰且距離最短的頂點(diǎn)vi，標(biāo)記為vs到vi弧上的權(quán)值wsi，即頂點(diǎn)vi已被標(biāo)記。令（vs，vi）∈V，其余各點(diǎn)均屬于S。

③找出S中與V中各點(diǎn)相鄰的未標(biāo)記的頂點(diǎn)（廣度優(yōu)先搜索），若S中的頂點(diǎn)vi經(jīng)過(guò)已標(biāo)記頂點(diǎn)到vs的總距離之和最短，則vj被標(biāo)記。令（vs，vi，vj）∈V，其余各點(diǎn)均屬于S。

④重復(fù)第三步，直到終點(diǎn)vt被標(biāo)記，至集合S為空為止，算法結(jié)束。

⑤逆推可得vs到vt的最短路徑。

具體步驟

1）取f（0）=0為初始可行流，依據(jù)其對(duì)應(yīng)的費(fèi)用網(wǎng)絡(luò)w（f（0）），應(yīng)用Dijkstra算法求從vs到vt的最短路徑，即最短路徑的增廣鏈u0，并沿u0調(diào)整流量，在新的可行流f（1）上構(gòu)造新的費(fèi)用網(wǎng)絡(luò)w（f（1）），重新尋找最小費(fèi)用增廣鏈。其中，構(gòu)造增廣費(fèi)用網(wǎng)絡(luò)的規(guī)則為：零流弧上保持原弧-wij不變；非飽和弧上，后加弧為-wij；飽和弧上，去掉原有弧，后加弧為-wij。

2）如第k步得到最小費(fèi)用流f（k），構(gòu)造對(duì)應(yīng)費(fèi)用網(wǎng)絡(luò)w（f（k）），尋找最短路徑。若不存在最短路徑，則f（k）即為網(wǎng)絡(luò)的最小費(fèi)用最大流；若存在，則在原網(wǎng)絡(luò)中得到相應(yīng)的最小費(fèi)用增廣鏈，調(diào)整f（k）為：

3 實(shí)例應(yīng)用

某高校計(jì)劃引進(jìn)一批新型教育裝備，需從某教育裝備配備中心訂購(gòu)，該教育裝備中心到學(xué)校存在多條運(yùn)輸路線（如圖1所示），其中ABCD為主要經(jīng)過(guò)的幾個(gè)中轉(zhuǎn)站，箭頭為運(yùn)輸系統(tǒng)規(guī)定的方向，?。╞ij，cij）中bij為運(yùn)輸單位費(fèi)用（單位：千元），cij表示此路段所能承受的容量。請(qǐng)?jiān)O(shè)定合理的運(yùn)輸路線，在保證運(yùn)輸總量的前提下，使運(yùn)輸成本最小。

本例中的運(yùn)輸問(wèn)題是典型的最小費(fèi)用最大流問(wèn)題。求解時(shí)首先將費(fèi)用流網(wǎng)絡(luò)圖分解為費(fèi)用網(wǎng)絡(luò)圖w（f（0））和流量網(wǎng)絡(luò)圖D（f（1））。

1）取f（0）=0為初始可行流，構(gòu)造相應(yīng)的費(fèi)用網(wǎng)絡(luò)圖w（f（0）），如圖2（a）所示。

2）在w（f（0））上應(yīng)用Dijkstra算法求解vs到vt的最短路徑，即最小費(fèi)用增廣鏈為vs→v1→v4→vt，如圖2（a）中標(biāo)粗路線。

3）在原網(wǎng)絡(luò)圖D（f（0））中與這條最短路徑相應(yīng)的增廣鏈為u=（vs，v1，v4，vt）。沿著該增廣鏈調(diào)整流量，δ=min（8，4，6）=4，得到新的可行流f（1），其流值v（f（1））=4，如圖2（b）所示。

4）構(gòu)造與D（f（1））相應(yīng)的費(fèi)用網(wǎng)絡(luò)w（f（1）），如圖3（a）中的粗線條所示。同樣，求出vs到vt的最短路徑為vs→v1→v3→vt，在流量網(wǎng)絡(luò)原網(wǎng)絡(luò)圖D（f（1））中與這條最短路徑相應(yīng)的增廣鏈為u=（vs，v1，v3，vt）。沿著該增廣鏈調(diào)整流量，δ=min（4，7，4）=4，得到新的可行流f（2），其流值v（f（2））=8，如圖3（b）所示。

5）構(gòu)造與D（f（2））相應(yīng)的費(fèi)用網(wǎng)絡(luò)w（f（2）），如圖4（a）中的粗線條所示。同樣，求出vs到vt的最短路徑為vs→v2→v4→vt，在流量網(wǎng)絡(luò)原網(wǎng)絡(luò)圖D（f（2））中與這條最短路徑相應(yīng)的增廣鏈為u=（vs，v2，v4，vt）。沿著該增廣鏈調(diào)整流量，δ=min（5，3，2）=2，得到新的可行流f（3），其流值v（f（3））=12，如圖4（b）所示。

6）構(gòu)造與D（f（3））相應(yīng)的費(fèi)用網(wǎng)絡(luò)w（f（3）），如圖5所示。由于w（f（3））中無(wú)法找到vs到vt的最短路徑，說(shuō)明D（f（3））已不存在增廣鏈，求解終止，D（f（3））所示的流即為所求的最小費(fèi)用最大流。此時(shí)，流值v（f（3））=12，最小費(fèi)用為：

因此，此次運(yùn)輸方案應(yīng)選擇的路線是vs→v2→v4→vt，能夠在滿足運(yùn)輸總量的前提下將運(yùn)輸成本最小化。應(yīng)用最小費(fèi)用最大流定理，對(duì)教育裝備的運(yùn)輸問(wèn)題做出合理決策。

4 結(jié)語(yǔ)

在信息技術(shù)與教育深度融合的時(shí)代，先進(jìn)的教育裝備使傳統(tǒng)課堂變得有趣豐富，多媒體教學(xué)的普及既保證了教學(xué)質(zhì)量，也促進(jìn)了教育裝備行業(yè)的發(fā)展。教育裝備運(yùn)輸問(wèn)題是物資管理、教育裝備管理中經(jīng)常遇到的問(wèn)題，合理安排運(yùn)輸方案、追求運(yùn)輸成本最小化，是教育機(jī)構(gòu)和教育裝備部門(mén)共同的目標(biāo)。本文結(jié)合實(shí)際的教育裝備運(yùn)輸問(wèn)題，依據(jù)最小費(fèi)用最大流理論及Dijkstra算法實(shí)現(xiàn)模型求解，給出教育裝備運(yùn)輸問(wèn)題的一種解決方案，為教育裝備保障部門(mén)工作提供了依據(jù)。

參考文獻(xiàn)

[1]邵林海，曲鐵華.信息技術(shù)與教育“深度融合”背景下師范教育的未來(lái)發(fā)展[J].黑龍江高教研究院，2015（5）.

[2]胡又農(nóng).教育裝備學(xué)導(dǎo)論[M].2版.北京：北京大學(xué)出版社，2011：163-177.

[3]胡運(yùn)權(quán)，郭耀煌.運(yùn)籌學(xué)教程[M].2版.北京：清華大學(xué)出版社，2003.

[4]魯海燕.最小費(fèi)用網(wǎng)絡(luò)流的若干新問(wèn)題研究[D].杭州：浙江大學(xué)理學(xué)院，2007.

[5]高隨祥.圖論與網(wǎng)絡(luò)流理論[M].北京：高等教育出版社，2009.

[6]辛宇.基于運(yùn)籌學(xué)圖論的物流網(wǎng)絡(luò)優(yōu)化研究[J].中國(guó)外資，2011（6）：125-127.

[7]李慧.教育裝備運(yùn)籌規(guī)劃[M].北京：北京大學(xué)出版社，2010：122-126.