最小費用流理論在教育裝備運輸中的應用

劉穎+李慧

摘 要 建立教育裝備運輸成本問題的數學模型，依據算法實現模型的求解，給出較優運輸方案，使總的運輸代價最小，為教育裝備配送工作提供依據。

關鍵詞 教育裝備；最小費用流理論；Dijkstra算法

中圖分類號：G48 文獻標識碼：B

文章編號：1671-489X（2016）20-0016-03

隨著教育水平的提高，信息技術與教育的融合是必然趨勢[1]，先進的教育技術裝備給課堂帶來新的視聽覺體驗，高科技在教育領域的廣泛應用使得教育裝備更新換代加速，因此，高校對教育裝備保障部門提出新要求。教育裝備的運輸問題屬于物資調運問題，是物資管理、教育裝備中經常遇到的問題[2]，不同的交通工具和道路狀況導致運輸方案的交通費用存在明顯差異，在滿足運輸總量的前提下，教育裝備保障部門合理安排運輸路線，以最小的代價將所需設備運到目的地尤為重要。

1 圖論與網絡流理論

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

圖論的基本概念

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

2）賦權圖（Weighted graph），即帶權值的圖，圖G的任意一條邊（vi，vj）都有一個數wij與之對應，wij稱為邊（vi，vj）的權。

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

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

網絡流理論

1）容量網絡（Capacity network）和費用網絡（cost network）：設一個賦權有向圖G（V，E），對于G中的每一個弧（vi，vj），相應地給一個權值cij（cij≥0），稱為弧（vi，vj）的容量；圖G被稱為容量網絡，記作G（V，A，C）。對于G中的每一個弧（vi，vj），相應地賦予一個非負實數bij，稱為弧（vi，vj）的費用，圖G被稱為費用網絡，記作G（V，A，C，w），也可以記為N=（V，A，C，w）。其中僅有一個點的入度為零，記為vs；僅有一個點的出度為零，記為vt。

2）網絡流（Network flow）：指定義在弧集A上的函數f={fij}并稱f（vi，vj）為弧（vi，vj）上的流量。

3）可行流（Furthest flow）：對G中每條邊（vi，vj），滿足0≤fij≤cij（容量約束）；對中間點，滿足∑jfij=∑kfki（平衡條件）；對收點vt與發點vs，有∑ifsi=∑jfjt=W（流量守恒），W是網絡的總流量。對G上任意一可行流，B（f）=∑wijfij稱為可行流的費用。

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

5）增廣鏈的費用（Cost of augmenting chain）：當沿著一條關于可行流f的增廣鏈μ，以δ調整f，得到新的可行流，可行流f和f′的費用只在增廣鏈μ上有差異，其費用差為：

6）最小費用流（Minimum cost flow）：對于網絡N=（V，A，C，w），要求B（f）最小且流量為某確定值f的可行流問題，即最小費用流問題；求B（f）最小且流量f為最大的問題稱為最小費用最大流的問題[6]。

2 最小費用流問題的求解

解法分析 求解最小費用流問題的基本思想是在尋求最大流算法過程中考慮費用最小的流。首先選取一個最小費用流，找出其增廣鏈并進行調整，直到找不到增廣鏈為止，這時的可行流即為最小費用最大流。

1）最小費用增廣鏈。尋找最小費用增廣鏈是求解最小費用流問題的關鍵。構造一個費用網絡圖f（k），其頂點為原網絡N的頂點，把N中的每條弧（vi，vj）變為兩條相反方向的弧（vi，vj）和（vj，vi），規定f（k）中弧（vi，vj）的權wij為：

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

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

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

①將vs標記為“0”，初始時，令vs∈V，其余各點均屬于S。

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

③找出S中與V中各點相鄰的未標記的頂點（廣度優先搜索），若S中的頂點vi經過已標記頂點到vs的總距離之和最短，則vj被標記。令（vs，vi，vj）∈V，其余各點均屬于S。

④重復第三步，直到終點vt被標記，至集合S為空為止，算法結束。

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

具體步驟

1）取f（0）=0為初始可行流，依據其對應的費用網絡w（f（0）），應用Dijkstra算法求從vs到vt的最短路徑，即最短路徑的增廣鏈u0，并沿u0調整流量，在新的可行流f（1）上構造新的費用網絡w（f（1）），重新尋找最小費用增廣鏈。其中，構造增廣費用網絡的規則為：零流弧上保持原弧-wij不變；非飽和弧上，后加弧為-wij；飽和弧上，去掉原有弧，后加弧為-wij。

2）如第k步得到最小費用流f（k），構造對應費用網絡w（f（k）），尋找最短路徑。若不存在最短路徑，則f（k）即為網絡的最小費用最大流；若存在，則在原網絡中得到相應的最小費用增廣鏈，調整f（k）為：

3 實例應用

某高校計劃引進一批新型教育裝備，需從某教育裝備配備中心訂購，該教育裝備中心到學校存在多條運輸路線（如圖1所示），其中ABCD為主要經過的幾個中轉站，箭頭為運輸系統規定的方向，弧（bij，cij）中bij為運輸單位費用（單位：千元），cij表示此路段所能承受的容量。請設定合理的運輸路線，在保證運輸總量的前提下，使運輸成本最小。

本例中的運輸問題是典型的最小費用最大流問題。求解時首先將費用流網絡圖分解為費用網絡圖w（f（0））和流量網絡圖D（f（1））。

1）取f（0）=0為初始可行流，構造相應的費用網絡圖w（f（0）），如圖2（a）所示。

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

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

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

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

6）構造與D（f（3））相應的費用網絡w（f（3）），如圖5所示。由于w（f（3））中無法找到vs到vt的最短路徑，說明D（f（3））已不存在增廣鏈，求解終止，D（f（3））所示的流即為所求的最小費用最大流。此時，流值v（f（3））=12，最小費用為：

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

4 結語

在信息技術與教育深度融合的時代，先進的教育裝備使傳統課堂變得有趣豐富，多媒體教學的普及既保證了教學質量，也促進了教育裝備行業的發展。教育裝備運輸問題是物資管理、教育裝備管理中經常遇到的問題，合理安排運輸方案、追求運輸成本最小化，是教育機構和教育裝備部門共同的目標。本文結合實際的教育裝備運輸問題，依據最小費用最大流理論及Dijkstra算法實現模型求解，給出教育裝備運輸問題的一種解決方案，為教育裝備保障部門工作提供了依據。

參考文獻

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

[2]胡又農.教育裝備學導論[M].2版.北京：北京大學出版社，2011：163-177.

[3]胡運權，郭耀煌.運籌學教程[M].2版.北京：清華大學出版社，2003.

[4]魯海燕.最小費用網絡流的若干新問題研究[D].杭州：浙江大學理學院，2007.

[5]高隨祥.圖論與網絡流理論[M].北京：高等教育出版社，2009.

[6]辛宇.基于運籌學圖論的物流網絡優化研究[J].中國外資，2011（6）：125-127.

[7]李慧.教育裝備運籌規劃[M].北京：北京大學出版社，2010：122-126.