不可分流網(wǎng)絡(luò)的最小費(fèi)用流問題

曹衛(wèi)鋒+梅霞+張興永

摘 要： 通常情況下單位流量費(fèi)用最小的那條路徑發(fā)送各個(gè)流總費(fèi)用是最小的，但是往往單位流量費(fèi)用最小的那條路徑并不一定能滿足所有流均可通過。針對不可分流的網(wǎng)絡(luò)流最小費(fèi)用問題，提出按流值排序?qū)で笞顑?yōu)解的算法，并給出相關(guān)的理論證明及算法，最后通過具體實(shí)驗(yàn)測試了該算法的有效性。此算法可以快速求解所提的問題，并能夠算出最優(yōu)值。實(shí)例結(jié)果表明，該算法有效地解決了不可分流的網(wǎng)絡(luò)流最小費(fèi)用問題，可以應(yīng)用于實(shí)際的網(wǎng)絡(luò)優(yōu)化中。

關(guān)鍵詞： 節(jié)點(diǎn)； 最小費(fèi)用流； 不可分流； 弧上限； 最小費(fèi)用路徑； 流值排序

中圖分類號： TN911.1?34； O221 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2018）01?0097?04

Abstract： The total flow cost is minimum when each flow is sent through the path with minimum unit flow cost. But the path with minimum unit flow cost doesn′t necessarily meet that all flows can be passed. Aiming at the minimum cost flow problem of the indecomposable flow network， an algorithm for optimal solution seeking by means of flow value ranking is proposed， and its relative theoretical proof and algorithm are given. The validity of the algorithm was tested with the specific experiment. THe algorithm can solve the proposed problem quickly， and get the optimal value. The results of the practical example show that the algorithm can solve the minimum cost flow problem of the indecomposable flow network effectively， and is applied to the actual network optimization.

Keywords： node； minimum cost flow； indecomposable flow； upper limit of arc； minimum cost path； flow value ranking

目前，對網(wǎng)絡(luò)優(yōu)化中可分解流在剛性弧上限的網(wǎng)絡(luò)中的最小費(fèi)用問題，其研究已日趨完善，有了許多能夠求得最小費(fèi)用流最優(yōu)解的算法[1?3]。但是，對于不可分流的網(wǎng)絡(luò)流的最小費(fèi)用問題，目前相關(guān)的研究還較少[4?5]；同時(shí)，解決的方法還缺少一般性的最優(yōu)性證明[6]。

本文針對不可分流的網(wǎng)絡(luò)流最小費(fèi)用問題，提出按流值排序?qū)で笞顑?yōu)解的方法，并給出了相關(guān)的理論證明及算法。實(shí)例顯示，該算法有效地解決了不可分流的網(wǎng)絡(luò)流最小費(fèi)用問題。

1 問題的提出及建立的數(shù)學(xué)模型

在具有已知的弧上限和單位流量費(fèi)用的網(wǎng)絡(luò)中，如何由一個(gè)節(jié)點(diǎn)向另一節(jié)點(diǎn)或其他幾個(gè)節(jié)點(diǎn)發(fā)送若干個(gè)不可分流，并使得所有流的總費(fèi)用最小。假定所有的不可分流均是源源不斷地從發(fā)點(diǎn)流向?qū)?yīng)的收點(diǎn)，中途沒有間斷；并且這些不可分流都是以同樣的速度勻速通過網(wǎng)絡(luò)上各條弧的。

在已知的網(wǎng)絡(luò)中，[V]表示所有節(jié)點(diǎn)的集合，[A]表示所有弧的集合，節(jié)點(diǎn)數(shù)為[n，]弧數(shù)為[m。]對[?（i，j）∈A，][cij]表示弧[（i， j）]上單位流量的費(fèi)用，[nij]表示弧[（i， j）]的弧上限，[xij]表示通過弧[（i， j）]的流的流量（流值），而[vk]則表示第[k]個(gè)不可分流[xk（ ）]的流值[7?8]。用數(shù)學(xué)規(guī)劃的方法描述存在若干個(gè)不可分流的網(wǎng)絡(luò)中最小費(fèi)用流問題如下：

[mink=1K（i，j）∈Acijxkijs.t. j：（i，j）∈Axkij-j：（j，i）∈Axkji=vk，i=s-vk，i=tk，0，i≠s，tk ?i∈V0≤xkij≤n， ?（i，j）∈A ] （1）

式中：決策變量（流量）[xkij]表示弧[（i，j）]是否位于第[k]個(gè)不可分流[xk]的最小費(fèi)用路徑上：當(dāng)[xkij=vk]時(shí)，表示弧[（i，j）]位于流[xk]的最小費(fèi)用路徑上：當(dāng)[xkij=0]時(shí)，表示弧[（i，j）]不在流[xk]的最小費(fèi)用路徑上。[tk]則表示第[k]個(gè)不可分流[xk]的收點(diǎn)，[tk]既可以相同也可以不同（[k=1，2，…，K]）。

2 問題的理論分析及研究

由于在網(wǎng)絡(luò)中沿不同的路徑發(fā)送各個(gè)流，其費(fèi)用是不同的，如何選擇路徑發(fā)送這些不可分流才能使得總費(fèi)用最小，顯然，可以的話，沿單位流量費(fèi)用最小的那條路徑發(fā)送各個(gè)流，總費(fèi)用是最小的，但是，往往單位流量費(fèi)用最小的那條路徑并不一定能滿足所有流均可通過。這時(shí)，就要考慮應(yīng)讓哪些流占用單位流量費(fèi)用最小的那條路徑，哪些流的發(fā)送路徑應(yīng)重新考慮，才能使得所有不可分流的總費(fèi)用最小。容易想到的是，將所有可行的方案一一考慮，并逐個(gè)對比、選擇，最終可獲得（TCP）的最優(yōu)解。但是，這種方法的計(jì)算量一般是非常龐大的，同時(shí)也不太現(xiàn)實(shí)。研究表明，不可分流的網(wǎng)絡(luò)流總費(fèi)用與各個(gè)流的優(yōu)先安排發(fā)送次序有關(guān)，且具有如下的性質(zhì)。

定理1：在網(wǎng)絡(luò)中由一個(gè)節(jié)點(diǎn)向另一節(jié)點(diǎn)或其他幾個(gè)節(jié)點(diǎn)發(fā)送等流值的若干個(gè)不可分流時(shí)，若逐個(gè)發(fā)出流，并沿每個(gè)流在當(dāng)前可取到的最小費(fèi)用路徑發(fā)送，則所有流的總費(fèi)用最小，且最小費(fèi)用與要發(fā)送的等流值的若干個(gè)不可分流的發(fā)送次序無關(guān)。endprint

結(jié)論是顯然的（證明略）。

定理2：在網(wǎng)絡(luò)中由一個(gè)節(jié)點(diǎn)向另一節(jié)點(diǎn)或其他幾個(gè)節(jié)點(diǎn)發(fā)送不等流值的若干個(gè)不可分流時(shí)，若按流值由大到小的次序逐個(gè)發(fā)出流，并沿每個(gè)流在當(dāng)前可取到的最小費(fèi)用路徑發(fā)送，則所有流的總費(fèi)用最小。

證明：在網(wǎng)絡(luò)中發(fā)送不等流值的若干個(gè)流，不妨設(shè)發(fā)送兩個(gè)流[x1]和[x2，]其流值分別為[v1]和[v2]（[v1>v2]），當(dāng)在網(wǎng)絡(luò)中只發(fā)送流[x1]時(shí)，其最小費(fèi)用為[t1，]最小費(fèi)用路徑為[P1；]當(dāng)在網(wǎng)絡(luò)中只發(fā)送流[x2]時(shí)，其最小費(fèi)用為[t2，]最小費(fèi)用路徑為[P2。]當(dāng)優(yōu)先考慮發(fā)送流[x1，]后考慮發(fā)送流[x2]時(shí)，各自的最小費(fèi)用分別為[t11]和[t22，]最小費(fèi)用路徑分別為[P11]和[P22；]當(dāng)優(yōu)先考慮發(fā)送流[x2，]后考慮發(fā)送流[x1]時(shí)，各自的最小費(fèi)用分別為[t21]和[t12，]最小費(fèi)用路徑分別為[P21]和[P12]。這樣，在只有一個(gè)發(fā)點(diǎn)和若干個(gè)收點(diǎn)的網(wǎng)絡(luò)中，路徑[P11，][P12，][P22，][P21]與路徑[P1，][P2]僅有如下的關(guān)系：

1） 當(dāng)[P11=P1，][P22=P2]時(shí)，顯然，此時(shí)有[P21]=[P2]和[P12]=[P1]（此兩種情況可相互推出）。所以，[t11]=[t12]=[t1]且[t21]=[t22]=[t2]，故[t11]+[t22]=[t21]+[t12]。

2） 當(dāng)[P11]=[P1]，[P22][≠][P2]時(shí)，顯然，此時(shí)有[P21]=[P2]和[P12][≠][P1]（此兩種情況可相互推出）。所以，[t11=t1，][t21=t2；]根據(jù)所要求的是最小費(fèi)用路徑，從[P22][≠][P2]知一定有[t22≥t2，]從[P12][≠][P1]知一定有[t12≥t1]。又，在相同的路徑上，大流值流的費(fèi)用比小流值流的費(fèi)用多，且大流值流可經(jīng)過的路徑小流值流一定能過，但反之不成立。故[t22-t2≤t12-t1，]所以，[t11+t22≤t11+t12-t1+t2=t11+][t12-t11+t21=t21+t12，]即[t11+t22≤t21+t12。]

因此，當(dāng)發(fā)送兩個(gè)不等流值的流時(shí)，大流值的流后發(fā)送所增加的費(fèi)用與小流值的流后發(fā)送所增加的費(fèi)用相比是非遞減的。同樣，當(dāng)發(fā)送多個(gè)不等流值的流時(shí)，其情況可以類似地如上分析，或者是依次選取兩個(gè)流相互比較。

綜上所述，在只有一個(gè)發(fā)點(diǎn)和若干個(gè)收點(diǎn)的網(wǎng)絡(luò)中發(fā)送不等流值的多個(gè)不可分流，大流值的流后發(fā)送所增加的費(fèi)用與小流值的流后發(fā)送所增加的費(fèi)用相比是非遞減的。也就是說，若按流值由大到小的次序逐個(gè)發(fā)出流，并沿每個(gè)流在當(dāng)前可取到的最小費(fèi)用路徑發(fā)送，則所有流的總費(fèi)用最小。

3 算 法

在不可分流的網(wǎng)絡(luò)中，所有的弧上限[nij]都是剛性的，故可記為：

[fij（v）=1，v≤nij∞，v>nij， ?（i，j）∈A] （2）

稱[fij（v）]為指標(biāo)函數(shù)，引入指標(biāo)函數(shù)的目的是為了計(jì)算的簡便及算法步驟的清晰。根據(jù)以上分析和定理1和2，建立流值排序算法，具體步驟為：

1） 輸入[cij，nij]和[fij（v）]（若[i=j，]則認(rèn)為[cij=nij=fij（v）=0；]若[i]與[j]間無弧，則認(rèn)為[cij=nij=fij（v）=]∞）；

2） 按流值的非遞增序輸入給定的不可分流，令按此順序輸入的流的流值為[vk]（[k=1，2，…，K]）（[k]的遞增序與流值的非遞增序一一對應(yīng)），再令[k=1，]發(fā)點(diǎn)[s=i0；]

3） 由[vk]與[nij（i，j=1，2，…，n）]比較的結(jié)果，令費(fèi)用[tij=cijvkfij（vk）]（若[i=j]，則認(rèn)為[tii=0]；若[i]與[j] 間無弧，則認(rèn)為[tij=∞]），[i，j=1，2，…，n]；同時(shí)，令與[vk]相對應(yīng)的流[xk]的收點(diǎn)[tk=j0]；

4） 令[u（1）i0=0，][u（1）j=ti0j（j=1，2，…，n，j≠i0）]，同時(shí)令[l=1，][p（i0）=0，][p（j）=i0]（若弧[（i0，j）∈A]）；

5） 對所有的節(jié)點(diǎn)[i，j∈V，]若[u（l）j≥u（l）i+tij，]則令[u（l+1）j=u（l）i+tij，][p（j）=i，]轉(zhuǎn)到步驟6）；否則（[u（l）j

6） 若[u（l+1）j=u（l）j（?j∈V），]則輸出[ukj0=u（l）j0]和[p（j）][（j=1，2，…，n）]，轉(zhuǎn)到步驟7）；否則（[u（l+1）j≠u（l）j（?j∈V）]），則令[l←l+1]，轉(zhuǎn)到步驟5）；

7） 若[k=K，]則停，輸出[u=k=1Kukj0][（j0=tk，k=][1，2，…，K）]；否則（[k

8） 由[p（j）]確定出與[vk]相對應(yīng)的流[xk]的最小費(fèi)用路徑[Pk：][s→jk1=p（jk2）→jk2=p（jk3）→…→tk]，令弧[（ik，jk）∈Pk]上[nikjk←nikjk-vk，]再令[k←k+1]，轉(zhuǎn)到步驟3）。

對該算法的幾點(diǎn)說明：

1） 此算法結(jié)合了Bellman?Ford標(biāo)號修正算法（迭代算法）和函數(shù)空間迭代法的思想[9]。

2） 算法步驟中[vk]的下標(biāo)[k]的遞增序是與給定的流的流值的非遞增序相對應(yīng)的，在不考慮等流值的流調(diào)換發(fā)送次序時(shí)，這種對應(yīng)是一對一的。

3） 算法步驟中的[p（j）]是表示在最小費(fèi)用路徑中節(jié)點(diǎn)[j]的前趨節(jié)點(diǎn)，即當(dāng)前最小費(fèi)用路徑中至節(jié)點(diǎn)[j]的最后一條弧（[p（i）， j]）的起點(diǎn)。

4） 算法迭代過程結(jié)束后，至節(jié)點(diǎn)[j]的最小費(fèi)用路徑可通過[p（j）]經(jīng)反向查找得出[10]。而算法步驟中的[ukj0]為與[vk]相對應(yīng)的流[xk]經(jīng)過其最小費(fèi)用路徑[Pk：][s→jk1=p（jk2）→jk2=p（jk3）→…→tk]時(shí)的費(fèi)用，[u]是所有流的最小費(fèi)用之和，即總費(fèi)用。

5） 按此算法求得的解[u]即為問題（TCP）最優(yōu)解的值。

6） 若已知網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)為[n，]弧數(shù)為[m，]給定[K]個(gè)不可分流，則此流值排序算法的時(shí)間復(fù)雜度為[O（Knm），]這是一個(gè)復(fù)雜度比較低的強(qiáng)多項(xiàng)式時(shí)間算法。

4 算例分析

例1：設(shè)有如圖1所示的網(wǎng)絡(luò)?；（i， j）]的權(quán)[cij，nij]以矩陣形式[C]和[N]記錄如下：

[C=0349∞∞∞0∞26∞∞20∞18∞∞5024∞∞∞∞03∞∞∞∞∞0] （3）

[N=0402520∞∞∞0∞5027∞∞300∞4025∞∞4002527∞∞∞∞045∞∞∞∞∞0] （4）

若[i=j]，則認(rèn)為[cii=nii=0；]若[i]與[j]間無弧，則認(rèn)為[cij=nij=∞，][i，j=1，2，…，6。]弧[（i，j）]上的指標(biāo)函數(shù)[fij（v）=][1，v≤nij∞，v>nij]，若[i=j，]則認(rèn)為[fii（v）=0；]若[i]與[j]間無弧，則認(rèn)為[fij（v）=∞，][i，j=1，2，…，6]。

試求：給定流[x1]（[v1=20]），流[x2]（[v3=25]）和流[x3]（[v3=30]）時(shí)，從節(jié)點(diǎn)1發(fā)送所有流至節(jié)點(diǎn)6的最小費(fèi)用和各個(gè)流的最小費(fèi)用路徑。根據(jù)流值排序算法，計(jì)算過程如下：

第一步：根據(jù)給定的流，按流值的非遞增序排列得到發(fā)送流的次序：[v1=30]（流[x3]），[v2=25]（流[x2]），[v3=20]（流[x1]）；

第二步：依據(jù)得到的發(fā)送流的次序，順次計(jì)算各個(gè)流的最小費(fèi)用和經(jīng)過的最小費(fèi)用路徑（具體計(jì)算過程略）；

① 首先發(fā)送流[x3]（[v1=30]），費(fèi)用[u（1）6=u（5）6=420，]最小費(fèi)用路徑為：[1→2→4→3→5→6]。

② 其次發(fā)送流[x2]（[v2=25]），費(fèi)用[u（2）6=u（3）6=300，]最小費(fèi)用路徑為：[1→3→6]。

③ 最后發(fā)送流[x1]（[v3=20]），費(fèi)用[u（3）6=u（2）6=260，]最小費(fèi)用路徑為：[1→4→6]。

第三步：將各個(gè)流的費(fèi)用相加，得到所有流的費(fèi)用之和為980。

故從節(jié)點(diǎn)1發(fā)送所有流至節(jié)點(diǎn)6的最小費(fèi)用為980。

例2：網(wǎng)絡(luò)及弧[（i， j）]上的[cij，nij]和[fij（v）]均同例1。

試求：給定流[x1]（[v1=20，]對應(yīng)的收、發(fā)點(diǎn)分別為4和1），流[x2]（[v2=35]對應(yīng)的收、發(fā)點(diǎn)分別為5和1）和流[x3]（[v3=30，]對應(yīng)的收、發(fā)點(diǎn)分別為6和1）時(shí)，從節(jié)點(diǎn)1發(fā)送所有流至對應(yīng)收點(diǎn)的最小費(fèi)用和各個(gè)流的最小費(fèi)用路徑。根據(jù)流值排序算法，解題步驟類似于例1，有：

① 首先發(fā)送流[x3]（[v1=30]），費(fèi)用[u（1）6=u（5）6=420，]最小費(fèi)用路徑為：[1→2→4→3→5→6]。

② 其次發(fā)送流[x2]（[v2=25]），費(fèi)用[u（2）5=u（3）5=300]，最小費(fèi)用路徑為：[1→3→2→5]。

③ 最后發(fā)送流[x1]（[v3=20]），費(fèi)用 [u（3）4=u（2）4=180，]最小費(fèi)用路徑為：[1→4]。

將各個(gè)流的費(fèi)用相加，得到所有流的費(fèi)用之和為900。

故從節(jié)點(diǎn)1發(fā)送所有流至對應(yīng)收點(diǎn)的最小費(fèi)用為900。

5 結(jié) 語

針對不可分流的網(wǎng)絡(luò)流最小費(fèi)用問題，提出一種新的、行之有效的可求得最優(yōu)解的方法——流值排序算法。該算法有效地解決了在一個(gè)發(fā)點(diǎn)、一個(gè)收點(diǎn)及一個(gè)發(fā)點(diǎn)、若干個(gè)收點(diǎn)的網(wǎng)絡(luò)中發(fā)送若干個(gè)不可分流的最小費(fèi)用問題。同時(shí)，由于該算法是一種強(qiáng)多項(xiàng)式時(shí)間算法，其時(shí)間復(fù)雜度為[O（Knm），]因此可以很方便地編制程序利用計(jì)算機(jī)執(zhí)行。利用本文給出的算法編制成C程序?qū)Χ鄠€(gè)實(shí)例進(jìn)行驗(yàn)算顯示，該算法可以快速地求解所給出的問題，不但能求得最優(yōu)解的值，而且也能給出具體的發(fā)送流的方案。

參考文獻(xiàn)

[1] 黃凱，張曉旭，張曉濛，等.基于整數(shù)線性規(guī)劃的MPSoC通信優(yōu)化策略[J].上海交通大學(xué)學(xué)報(bào)，2015，49（2）：184?190.

HUANG Kai， ZHANG Xiaoxu， ZHANG Xiaomeng， et al. MPSoC communication optimization strategy based on integer linear programming [J]. Journal of Shanghai Jiaotong University， 2015， 49（2）： 184?190.

[2] 吳超，黃淋妃.安全運(yùn)籌學(xué)的學(xué)科構(gòu)建研究[J].中國安全科學(xué)學(xué)報(bào)，2017（6）：37?42.

WU Chao， HUANG Linfei. Discipline construction of safety operations research [J]. China safety science journal， 2017（6）： 37?42.

[3] CAI X， SHA D， WONG C K. Time?varying minimum cost flow problems [J]. European journal of operational research， 2001， 131（2）： 352?374.

[4] 王勤波，許成，段偉偉，等.動態(tài)最小費(fèi)用流問題[J].青島大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，21（4）：39?41.

WANG Qinbo， XU Cheng， DUAN Weiwei， et al. Dynamic minimum cost flow problems [J]. Journal of Qingdao University （natural science edition）， 2008， 21（4）： 39?41.endprint

[5] 謝政，湯澤瀅.帶模糊約束的最小費(fèi)用流問題[J].模糊系統(tǒng)與數(shù)學(xué)，1999，13（2）：90?94.

XIE Zheng， TANG Zeying. The minimum?cost flow problem with fuzzy constraint [J]. Fuzzy systems and mathematics， 1999， 13（2）： 90?94.

[6] 董振寧.無容量限制的最小費(fèi)用流問題[J].數(shù)學(xué)研究與評論，2004，24（4）：751?757.

DONG Zhenning. Uncapacitated minimum cost flow problem [J]. Journal of mathematical research and exposition， 2004， 24（4）： 751?757.

[7] CALVETE H I. Network simplex algorithm for the general equal flow problem [J]. European journal of operational research， 2003， 150（3）： 585?600.

[8] 吳相林，尹崢.應(yīng)用最小費(fèi)用流求解活動網(wǎng)絡(luò)時(shí)間?費(fèi)用模型[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2007，35（1）：42?45.

WU Xianglin， YIN Zheng. Solving time?cost trade?off model for activity network by minimum cost flow principle [J]. Journal of Huazhong University of Science and Technology （nature science edition）， 2007， 35（1）： 42?45.

[9] 董振寧，張畢西.遺傳算法求解帶容量限制的最小費(fèi)用流問題[J].數(shù)學(xué)的實(shí)踐與認(rèn)識，2007，37（2）：30?36.

DONG Zhenning， ZHANG Bixi. Study on capacitated minimum cost flow problem with genetic algorithm [J]. Mathematics in practice and theory， 2007， 37（2）： 30?36.

[10] 張煜，吳露，田維.動態(tài)最小費(fèi)用流啟發(fā)式算法求解多式聯(lián)運(yùn)問題[J].武漢理工大學(xué)學(xué)報(bào)，2016，38（2）：103?110.

ZHANG Yu， WU Lu， TIAN Wei. Dynamic minimum cost flow?based heuristics solving problem of multimodal transport [J]. Journal of Wuhan University of Technology， 2016， 38（2）： 103?110.endprint