趙禮峰，劉艷清

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210003)

定流值比例的最小雙費(fèi)用流算法研究

趙禮峰，劉艷清

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210003)

現(xiàn)有最小雙費(fèi)用流算法只能求解網(wǎng)絡(luò)的最大雙流問題，并不能得到定流值比例。為此，提出了一種定流值比例的最小雙費(fèi)用流新算法，在求解最小雙流和最小費(fèi)用的基礎(chǔ)上，在調(diào)整雙流值保證定流值比例的同時(shí)得到最小費(fèi)用流。所提出的新算法定義了余網(wǎng)絡(luò)和費(fèi)用差，以鄰接矩陣為網(wǎng)絡(luò)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，使用Ford算法分別得到兩費(fèi)用的最短增廣鏈，選擇費(fèi)用最小的增廣鏈增廣并求出其對應(yīng)的費(fèi)用差，從費(fèi)用差最小的開始調(diào)整流值就得到定流值比例下的最小費(fèi)用。應(yīng)用該新算法構(gòu)建定流值比例的最小雙費(fèi)用流算法的運(yùn)輸網(wǎng)絡(luò)模型，就可以獲得最優(yōu)運(yùn)輸方案。邏輯推理和仿真實(shí)驗(yàn)結(jié)果均表明，所提出的算法可行、有效，能較好地解決稀疏網(wǎng)絡(luò)以及復(fù)雜網(wǎng)絡(luò)中定流值比例的最小雙費(fèi)用流問題。

最小雙費(fèi)用流算法；余網(wǎng)絡(luò)；鄰接矩陣；Ford算法；費(fèi)用差

0 引 言

最小雙費(fèi)用流問題是網(wǎng)絡(luò)優(yōu)化中的一個(gè)核心問題，許多網(wǎng)絡(luò)優(yōu)化問題都可歸結(jié)為最小雙費(fèi)用流問題的特例，如最短路[1-2]、最大流[3-5]以及最小費(fèi)用最大流[6-8]問題，這些網(wǎng)絡(luò)優(yōu)化問題都可歸為單可行流算法研究。隨著物流運(yùn)輸?shù)陌l(fā)展，這些單可行流算法研究已經(jīng)滿足不了運(yùn)輸行業(yè)不斷發(fā)展的需要。由此，謝政和湯澤瀅根據(jù)一個(gè)實(shí)例建立了在容量—費(fèi)用雙流網(wǎng)絡(luò)中求最小費(fèi)用最大雙流的模型[9]，提出了最小費(fèi)用最大雙流和雙流增量網(wǎng)絡(luò)的充要條件，該算法證明了最小費(fèi)用最大雙流算法的正確性。謝政和肖予欽提出了在(vs,vt)平面雙流網(wǎng)絡(luò)中的最小費(fèi)用最大雙流[10]，利用(vs,vt)平面雙流網(wǎng)絡(luò)的平面性，找出并證明了該網(wǎng)絡(luò)中最小費(fèi)用雙流的充要條件，該算法更易于在計(jì)算機(jī)上實(shí)現(xiàn)。馬宇斌、謝政等提出了一種求解最小雙費(fèi)用流問題的算法[11]，通過實(shí)際應(yīng)用案例，抽象出一種帶容量限制的雙費(fèi)用權(quán)網(wǎng)絡(luò)模型，并由此提出了相應(yīng)的最小雙費(fèi)用流問題。借鑒網(wǎng)絡(luò)分層的思想，根據(jù)雙費(fèi)用權(quán)網(wǎng)絡(luò)的特點(diǎn)，設(shè)計(jì)出一個(gè)求解該問題的雙層原始對偶算法。文獻(xiàn)[9-11]都是關(guān)于雙可行流的算法研究，這些算法很好地解決了單可行流算法解決不了的問題。但是對運(yùn)輸?shù)膬煞N產(chǎn)品有定運(yùn)輸比例要求時(shí)，以上三種雙費(fèi)用流算法明顯就不再適用，由此在文獻(xiàn)[9-11]的理論基礎(chǔ)上，提出了一種定流值比例的最小雙費(fèi)用流算法。

在文獻(xiàn)[9-11]中得到了網(wǎng)絡(luò)中的最大雙流，由于每次都選擇費(fèi)用最小的增廣鏈增廣流值，這就造成了得到的比值往往不是兩流值的定流值比例?？梢酝ㄟ^調(diào)整雙流的流值得到定流值比例，而每調(diào)整一個(gè)單位可行流，總費(fèi)用就會(huì)增加，為此產(chǎn)生了如何調(diào)整雙流的比值才能使其總費(fèi)用最小，每調(diào)整一個(gè)流值總費(fèi)用會(huì)增加多少的問題。新算法是在求得的最大雙流和最小費(fèi)用的基礎(chǔ)上，每得到一個(gè)增廣鏈增廣流值時(shí)，求出其對應(yīng)的費(fèi)用差。每調(diào)整一個(gè)流值，總費(fèi)用就增加對應(yīng)的費(fèi)用差的值，所以從費(fèi)用差最小的開始調(diào)整流值就能實(shí)現(xiàn)既得到要求的流值比例又使得費(fèi)用最少。通過模型建立與求解以及仿真實(shí)驗(yàn)表明，新算法具有完全的可行性和有效性。

1 基本概念

定義3(余網(wǎng)絡(luò))[9]：設(shè)f是N上一個(gè)單可行流，按如下規(guī)則修改網(wǎng)絡(luò)N：對于N中任意一條弧aij=(vi,vj)∈A，若fij=cij，則刪掉弧aij；若0

2 定流值比例的最小雙費(fèi)用流算法

2.1 算法思想

2.2 算法步驟

Step1：令f1=0，f2=0。

Step2:構(gòu)造余網(wǎng)絡(luò)D(f1,f2),若D(f1,f2)中不存在關(guān)于費(fèi)用w1和w2的(vs,vt)路，轉(zhuǎn)Step4，否則，在D(f1,f2)中用Ford算法找一條關(guān)于w1的最小費(fèi)用路s1和關(guān)于w2的最小費(fèi)用路s2，σi是si的容量(i=1,2)。

Step3:當(dāng)w1(s1)≤w2(s2)時(shí)，沿路s1對f1增廣流值σ1，得到新可行流仍記為f1，轉(zhuǎn)Step1；當(dāng)w1(s1)≥w2(s2)時(shí)，沿路s2對f2增廣流值σ2，得到新可行流仍記為f2，轉(zhuǎn)Step2。

2.3 算法的可行性分析

該算法執(zhí)行時(shí)，每找到一條增廣鏈增廣流值，會(huì)重新構(gòu)造余網(wǎng)絡(luò)，在余網(wǎng)絡(luò)中繼續(xù)尋找增廣鏈直至找不到增廣鏈為止。由于先前對于余網(wǎng)絡(luò)的定義是對于N中任意一條弧aij=(vi,vj)∈A，若fij=cij，則刪掉弧aij；若0

2.4 算法的時(shí)間復(fù)雜度

設(shè)N的頂點(diǎn)數(shù)為n，有向弧數(shù)為m，v*為最大雙流的流值，并且假設(shè)N中所有弧容量以及v*均為整數(shù)，在算法執(zhí)行過程中，每次增廣的流值最多為1，因此最多經(jīng)過v*次增廣，所以Step2到Step3的循環(huán)次數(shù)不超過v*。Ford算法的復(fù)雜性為O(nm)，在Step2中需要分別求出兩費(fèi)用的最短路，所以Step2的復(fù)雜性為O(2nm)，Step3沿最小費(fèi)用路對流進(jìn)行增廣的計(jì)算量為O(n)。Step4調(diào)整流值最大為v*，最多調(diào)整v*次。由此可知，定流值比例的最小雙費(fèi)用流算法的復(fù)雜性為O(2nmv*)。

3 算法驗(yàn)證

3.1 建立網(wǎng)絡(luò)模型

某企業(yè)想要將兩種不同的產(chǎn)品從產(chǎn)地運(yùn)往倉庫，運(yùn)輸過程是通過一個(gè)單行的公路網(wǎng)，公路網(wǎng)中有若干條運(yùn)輸路線可供選擇，每條道路只能負(fù)擔(dān)有限重量的產(chǎn)品，不同的道路上單位產(chǎn)品的運(yùn)費(fèi)也不同，在同一條道路上，不同產(chǎn)品的運(yùn)費(fèi)也不同。那么給出一個(gè)模型使得該企業(yè)從產(chǎn)地運(yùn)往兩種不同產(chǎn)品到倉庫且兩種產(chǎn)品的運(yùn)輸比例為θ的方案，使得運(yùn)輸量最多而總費(fèi)用最小。不妨假設(shè)圖1為這個(gè)運(yùn)輸網(wǎng)絡(luò)的一部分，運(yùn)輸網(wǎng)絡(luò)有10個(gè)節(jié)點(diǎn)，為圖中圈起來的數(shù)字，每一條弧上第一個(gè)數(shù)字為每條運(yùn)輸?shù)缆返淖畲筘?fù)擔(dān)重量，第二個(gè)數(shù)字為第一種產(chǎn)品在每條運(yùn)輸?shù)缆返倪\(yùn)費(fèi)，第三個(gè)數(shù)字為第二種產(chǎn)品在每條運(yùn)輸?shù)缆返倪\(yùn)費(fèi)。

若將此運(yùn)輸系統(tǒng)看作是一個(gè)從始點(diǎn)(產(chǎn)地)為節(jié)點(diǎn)1，終點(diǎn)(倉庫)為節(jié)點(diǎn)10的容量網(wǎng)絡(luò)N=(V,A,c,w1,w2,θ)，其中，V表示節(jié)點(diǎn)1和節(jié)點(diǎn)10之間的兩條或者兩條以上道路的交匯點(diǎn)，A表示弧的集合，c表示每條運(yùn)輸?shù)缆返淖畲筘?fù)擔(dān)重量，w1和w2分別表示第一種產(chǎn)品和第二種產(chǎn)品在每條道路運(yùn)費(fèi)的集合，θ表示兩種產(chǎn)品的運(yùn)輸比值。

圖1 運(yùn)輸網(wǎng)絡(luò)

于是上述問題歸結(jié)為：求容量網(wǎng)絡(luò)N=(V,A,c,w1,w2,θ)的定流值比例的最小雙費(fèi)用流算法。

3.2 求解網(wǎng)絡(luò)模型

用編制的MATLAB程序求出圖1兩流值比例為1∶2的最小雙費(fèi)用流，如表1所示。其中，序號1～5表示有五條路徑，增廣路徑中列出從節(jié)點(diǎn)1到節(jié)點(diǎn)10的所有增廣路徑，f1為費(fèi)用1在每條增廣路徑的增廣流值，f2為費(fèi)用2在每條增廣路徑的增廣流值，w1(s1)和w2(s2)分別表示每一條增廣路徑關(guān)于費(fèi)用1和費(fèi)用2的費(fèi)用，費(fèi)用差ω是w1(s1)和w2(s2)的差的絕對值，w是圖1中的最小費(fèi)用。從表中可以看到，兩流值的比例為1∶2，最小費(fèi)用為275。

表1 網(wǎng)絡(luò)1中流值比為1∶2的最小雙費(fèi)用流

表2 網(wǎng)絡(luò)1中流值比為1∶1的最小雙費(fèi)用流

當(dāng)需要的兩流值比例為1∶1，也就是說最大雙流為(7.5,7.5)時(shí)，需要從f2調(diào)整2.5個(gè)單位可行流到f1，序號3、4以及5是f2的增廣路徑，每從f2調(diào)整一個(gè)單位可行流到f1，總費(fèi)用就會(huì)增加一個(gè)單位費(fèi)用差的值，所以從費(fèi)用差最小的4開始調(diào)整，調(diào)整2.5個(gè)單位的可行流如表2所示。最小費(fèi)用w在275的基礎(chǔ)上增加10為285。用編制的MATLAB程序檢驗(yàn)得到的結(jié)果和表2相同。

3.3 新算法在稀疏網(wǎng)絡(luò)中的運(yùn)行時(shí)間

The initial resistance is defined as , and was found to be R0 ~ 8.5 kΩ in our case.ρM can be calculated as a function of either time or the statevariable x.

生成規(guī)模為n*n的隨機(jī)稀疏網(wǎng)絡(luò)，每條弧的流值、費(fèi)用1以及費(fèi)用2都是隨機(jī)生成的整數(shù)。為了減少計(jì)算機(jī)穩(wěn)定性造成的誤差，以下所有實(shí)驗(yàn)都進(jìn)行10次仿真并取平均值。

當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)規(guī)模為500，流值比值設(shè)置為1∶2時(shí)的運(yùn)行時(shí)間如圖2所示。

圖2 流值比例為1∶2的稀疏網(wǎng)絡(luò)平均運(yùn)行時(shí)間(1)

從圖中可以得到，平均運(yùn)行時(shí)間隨著節(jié)點(diǎn)數(shù)的增大而增大。對于節(jié)點(diǎn)規(guī)模為1 000，流值比值設(shè)置為1∶2的網(wǎng)絡(luò)來說，由于新算法的時(shí)間復(fù)雜性為O(2nmv*)，隨著節(jié)點(diǎn)數(shù)、弧的個(gè)數(shù)以及總流值的增大運(yùn)行時(shí)間呈次方增長，所以從圖3可以看到，節(jié)點(diǎn)數(shù)從500增加到1 000時(shí)運(yùn)行時(shí)間直線上升。大量的仿真實(shí)驗(yàn)結(jié)果表明，算法對于網(wǎng)絡(luò)規(guī)模為500個(gè)節(jié)點(diǎn)的運(yùn)行時(shí)間比較穩(wěn)定，當(dāng)網(wǎng)絡(luò)規(guī)模超過500個(gè)節(jié)點(diǎn)時(shí)運(yùn)行時(shí)間呈次方增長，運(yùn)行時(shí)間稍長。

圖3 流值比例為1∶2的稀疏網(wǎng)絡(luò)平均運(yùn)行時(shí)間(2)

3.4 新算法在復(fù)雜網(wǎng)絡(luò)中的運(yùn)行時(shí)間

生成規(guī)模為n*n的隨機(jī)網(wǎng)絡(luò)，用round(10*rand(n))生成的隨機(jī)矩陣來構(gòu)成隨機(jī)網(wǎng)絡(luò)，發(fā)現(xiàn)round(10*rand(n))生成的矩陣中每個(gè)節(jié)點(diǎn)平均與n-2個(gè)節(jié)點(diǎn)相連，每條弧的流值、費(fèi)用1以及費(fèi)用2都是隨機(jī)生成的整數(shù)，為了減少計(jì)算機(jī)穩(wěn)定性造成的誤差，以下所有實(shí)驗(yàn)都進(jìn)行10次仿真并取平均值。

當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)規(guī)模為500，流值比值設(shè)置為1∶2時(shí)的運(yùn)行時(shí)間如圖4所示。當(dāng)節(jié)點(diǎn)規(guī)模為350時(shí)，運(yùn)行時(shí)間開始直線上升，這是由于算法的時(shí)間復(fù)雜度為O(2nmv*)，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)至少與n-2個(gè)節(jié)點(diǎn)相連，那么弧的個(gè)數(shù)m=(n-2)!，所以隨著節(jié)點(diǎn)數(shù)的增加，運(yùn)行時(shí)間快速增加。

圖4 流值比例為1∶2的復(fù)雜網(wǎng)絡(luò)平均運(yùn)行時(shí)間

通過圖2到圖4，比較和分析新算法在稀疏網(wǎng)絡(luò)以及復(fù)雜網(wǎng)絡(luò)運(yùn)行時(shí)間的長短，表明新算法更適合執(zhí)行較大規(guī)模的稀疏網(wǎng)絡(luò)，對于較小規(guī)模的較復(fù)雜網(wǎng)絡(luò)也很適用。

4 結(jié)束語

運(yùn)輸問題一直是網(wǎng)絡(luò)最優(yōu)化的重要研究方向，在運(yùn)輸如此發(fā)達(dá)的今天，急需提高運(yùn)輸物品的量同時(shí)降低運(yùn)輸成本。為此，提出了一種定流值比例的最小雙費(fèi)用流新算法，在構(gòu)建余網(wǎng)絡(luò)下求得網(wǎng)絡(luò)中的最小雙費(fèi)用流，在求解最小雙流和最小費(fèi)用的基礎(chǔ)上，通過調(diào)整雙流值保證定流值比例的同時(shí)得到最小費(fèi)用流算法。用MATLAB編制的程序能直接求出定流值比例，對于兩種商品運(yùn)輸問題有很大的研究意義。大量的仿真實(shí)驗(yàn)表明，算法對于稀疏網(wǎng)絡(luò)規(guī)模為500個(gè)節(jié)點(diǎn)的運(yùn)行時(shí)間比較穩(wěn)定，當(dāng)網(wǎng)絡(luò)規(guī)模超過500個(gè)節(jié)點(diǎn)時(shí)運(yùn)行時(shí)間呈次方增長，運(yùn)行時(shí)間稍長；對于復(fù)雜網(wǎng)絡(luò)，當(dāng)節(jié)點(diǎn)規(guī)模為350時(shí)運(yùn)行時(shí)間上升稍快。目前隨著網(wǎng)絡(luò)規(guī)模的不斷增大，網(wǎng)絡(luò)規(guī)模趨于復(fù)雜化，而新算法經(jīng)過邏輯推理以及仿真實(shí)驗(yàn)，證明了其能求出稀疏網(wǎng)絡(luò)以及復(fù)雜網(wǎng)絡(luò)的固定流值比以及最小費(fèi)用，具有較高的應(yīng)用價(jià)值。

[1]CaiX,KloksT，WongCK.Time-varyingshortestpathwithconstraints[J].Networks,1997,29(2):141-149.

[2]LoachimI.Adualprogrammingalgorithmfortheshortestpathproblem[J].Networks,1998,31(2):192-204.

[3]DinicEA.Algorithmsforsolutionofaproblemofmaximum

flowinnetworkswithpowerestimation[J].SovietMathematicalDoklady,1970,11(8):1277-1280.

[4] 謝金星，邢文訓(xùn)，王振波.網(wǎng)絡(luò)優(yōu)化[M].北京：清華大學(xué)出版社，2009:177-181.

[5]FordLR,FuldersonDR.AsimplealgorithmforfindingmaximalnetworkflowsandanapplicationtoHitchcockproblem[J].CanadianJournalofMathematics,1957,9:210-218.

[6]HamacherHW,PedersenCR,RuzikaS.Multipleobjectiveminimumcostflowproblems[J].EuropeanJournalofOperationalResearch,2007,176(3):1404-1422.

[7]ZhuXiaoyuan,YuanQi.Minimal-costnetworkflowproblemswithvariablelowerboundsonarcflows[J].Computers&OperationsResearch,2011,38(8):1210-1218.

[8] 趙禮峰，宋常城，白 睿.基于最小費(fèi)用最大流問題的“排序”算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2011,21(12):82-85.

[9] 謝 政,湯澤瀅.最小費(fèi)用最大雙流[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào),1996,11(1):97-104.

[10] 謝 政，肖予欽.(vs,vt)平面雙流網(wǎng)絡(luò)中的最小費(fèi)用最大雙流[J].數(shù)學(xué)理論與應(yīng)用，1999,19(3):112-116.

[11] 馬宇斌，謝 政，陳 摯.一種求解最小雙費(fèi)用流問題的算法[J].計(jì)算機(jī)工程與科學(xué)，2014,36(3)：446-451.

[12] 厙向陽.點(diǎn)和邊有容量約束的網(wǎng)絡(luò)最小費(fèi)用最大流算法[J].計(jì)算機(jī)應(yīng)用研究，2010,27(8)：3112-3114.

[13] 謝 政.網(wǎng)絡(luò)算法與復(fù)雜性理論[M].北京：國防科技大學(xué)出版社，2003.

Investigation on Minimum Double Cost Flow Algorithm with Constant Value Ratio

ZHAO Li-feng，LIU Yan-qing

(College of Mathematics and Physics,Nanjing University of Posts and Telecommunication,Nanjing 210003,China)

The minimum double cost flow algorithm can only get the maximum double flow of the network,but it cannot get the required flow value ratio.So,a new algorithm of the minimum double cost flow with constant value ratio is put forward.It adjusts the double value to get the constant value ratio and make the cost least based on the maximal double value and minimal cost has gotten.The algorithm defines the over network and cost difference in it,with adjacency matrix as the network data storage structure,and it uses Ford algorithm to obtain shortest augmenting chain for two expenses and chooses the minimum cost augmented links to get the cost difference of augmented chain.It adjusts the double flow ratio based on the size of the cost difference.The algorithm is used to build the transportation network model of minimum double cost flow of constant flow ratio to get the optimal transportation scheme about the model.The logical reasoning and simulation results show that the algorithm proposed is completely feasible and effective,and it can effectively solve the problem of minimum double cost flow in sparse network and complex network.

minimum double cost flow algorithm;over network;adjacency matrix;Ford algorithm;cost difference

2016-04-24

2016-08-17

時(shí)間：2017-03-07

國家自然科學(xué)基金資助項(xiàng)目(61304169)

趙禮峰(1959-)，男，教授，碩士研究生導(dǎo)師，研究方向?yàn)閳D論及其應(yīng)用、矩陣論等;劉艷清(1989-)，女，碩士研究生，研究方向?yàn)樽疃搪?、最大流以及最小雙費(fèi)用流等。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0920.006.html

TP301.6

A

1673-629X(2017)04-0094-04

10.3969/j.issn.1673-629X.2017.04.021