不可分流網絡的最小費用流問題

曹衛鋒+梅霞+張興永

摘 要： 通常情況下單位流量費用最小的那條路徑發送各個流總費用是最小的，但是往往單位流量費用最小的那條路徑并不一定能滿足所有流均可通過。針對不可分流的網絡流最小費用問題，提出按流值排序尋求最優解的算法，并給出相關的理論證明及算法，最后通過具體實驗測試了該算法的有效性。此算法可以快速求解所提的問題，并能夠算出最優值。實例結果表明，該算法有效地解決了不可分流的網絡流最小費用問題，可以應用于實際的網絡優化中。

關鍵詞： 節點； 最小費用流； 不可分流； 弧上限； 最小費用路徑； 流值排序

中圖分類號： TN911.1?34； O221 文獻標識碼： 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

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

本文針對不可分流的網絡流最小費用問題，提出按流值排序尋求最優解的方法，并給出了相關的理論證明及算法。實例顯示，該算法有效地解決了不可分流的網絡流最小費用問題。

1 問題的提出及建立的數學模型

在具有已知的弧上限和單位流量費用的網絡中，如何由一個節點向另一節點或其他幾個節點發送若干個不可分流，并使得所有流的總費用最小。假定所有的不可分流均是源源不斷地從發點流向對應的收點，中途沒有間斷；并且這些不可分流都是以同樣的速度勻速通過網絡上各條弧的。

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

[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]個不可分流[xk]的最小費用路徑上：當[xkij=vk]時，表示弧[（i，j）]位于流[xk]的最小費用路徑上：當[xkij=0]時，表示弧[（i，j）]不在流[xk]的最小費用路徑上。[tk]則表示第[k]個不可分流[xk]的收點，[tk]既可以相同也可以不同（[k=1，2，…，K]）。

2 問題的理論分析及研究

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

定理1：在網絡中由一個節點向另一節點或其他幾個節點發送等流值的若干個不可分流時，若逐個發出流，并沿每個流在當前可取到的最小費用路徑發送，則所有流的總費用最小，且最小費用與要發送的等流值的若干個不可分流的發送次序無關。endprint

結論是顯然的（證明略）。

定理2：在網絡中由一個節點向另一節點或其他幾個節點發送不等流值的若干個不可分流時，若按流值由大到小的次序逐個發出流，并沿每個流在當前可取到的最小費用路徑發送，則所有流的總費用最小。

證明：在網絡中發送不等流值的若干個流，不妨設發送兩個流[x1]和[x2，]其流值分別為[v1]和[v2]（[v1>v2]），當在網絡中只發送流[x1]時，其最小費用為[t1，]最小費用路徑為[P1；]當在網絡中只發送流[x2]時，其最小費用為[t2，]最小費用路徑為[P2。]當優先考慮發送流[x1，]后考慮發送流[x2]時，各自的最小費用分別為[t11]和[t22，]最小費用路徑分別為[P11]和[P22；]當優先考慮發送流[x2，]后考慮發送流[x1]時，各自的最小費用分別為[t21]和[t12，]最小費用路徑分別為[P21]和[P12]。這樣，在只有一個發點和若干個收點的網絡中，路徑[P11，][P12，][P22，][P21]與路徑[P1，][P2]僅有如下的關系：

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

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

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

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

3 算 法

在不可分流的網絡中，所有的弧上限[nij]都是剛性的，故可記為：

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

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

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

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

3） 由[vk]與[nij（i，j=1，2，…，n）]比較的結果，令費用[tij=cijvkfij（vk）]（若[i=j]，則認為[tii=0]；若[i]與[j] 間無弧，則認為[tij=∞]），[i，j=1，2，…，n]；同時，令與[vk]相對應的流[xk]的收點[tk=j0]；

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

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

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

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

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

對該算法的幾點說明：

1） 此算法結合了Bellman?Ford標號修正算法（迭代算法）和函數空間迭代法的思想[9]。

2） 算法步驟中[vk]的下標[k]的遞增序是與給定的流的流值的非遞增序相對應的，在不考慮等流值的流調換發送次序時，這種對應是一對一的。

3） 算法步驟中的[p（j）]是表示在最小費用路徑中節點[j]的前趨節點，即當前最小費用路徑中至節點[j]的最后一條弧（[p（i）， j]）的起點。

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

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

6） 若已知網絡的節點數為[n，]弧數為[m，]給定[K]個不可分流，則此流值排序算法的時間復雜度為[O（Knm），]這是一個復雜度比較低的強多項式時間算法。

4 算例分析

例1：設有如圖1所示的網絡。弧[（i， j）]的權[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]，則認為[cii=nii=0；]若[i]與[j]間無弧，則認為[cij=nij=∞，][i，j=1，2，…，6。]弧[（i，j）]上的指標函數[fij（v）=][1，v≤nij∞，v>nij]，若[i=j，]則認為[fii（v）=0；]若[i]與[j]間無弧，則認為[fij（v）=∞，][i，j=1，2，…，6]。

試求：給定流[x1]（[v1=20]），流[x2]（[v3=25]）和流[x3]（[v3=30]）時，從節點1發送所有流至節點6的最小費用和各個流的最小費用路徑。根據流值排序算法，計算過程如下：

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

第二步：依據得到的發送流的次序，順次計算各個流的最小費用和經過的最小費用路徑（具體計算過程略）；

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

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

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

第三步：將各個流的費用相加，得到所有流的費用之和為980。

故從節點1發送所有流至節點6的最小費用為980。

例2：網絡及弧[（i， j）]上的[cij，nij]和[fij（v）]均同例1。

試求：給定流[x1]（[v1=20，]對應的收、發點分別為4和1），流[x2]（[v2=35]對應的收、發點分別為5和1）和流[x3]（[v3=30，]對應的收、發點分別為6和1）時，從節點1發送所有流至對應收點的最小費用和各個流的最小費用路徑。根據流值排序算法，解題步驟類似于例1，有：

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

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

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

將各個流的費用相加，得到所有流的費用之和為900。

故從節點1發送所有流至對應收點的最小費用為900。

5 結 語

針對不可分流的網絡流最小費用問題，提出一種新的、行之有效的可求得最優解的方法——流值排序算法。該算法有效地解決了在一個發點、一個收點及一個發點、若干個收點的網絡中發送若干個不可分流的最小費用問題。同時，由于該算法是一種強多項式時間算法，其時間復雜度為[O（Knm），]因此可以很方便地編制程序利用計算機執行。利用本文給出的算法編制成C程序對多個實例進行驗算顯示，該算法可以快速地求解所給出的問題，不但能求得最優解的值，而且也能給出具體的發送流的方案。

參考文獻

[1] 黃凱，張曉旭，張曉濛，等.基于整數線性規劃的MPSoC通信優化策略[J].上海交通大學學報，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] 吳超，黃淋妃.安全運籌學的學科構建研究[J].中國安全科學學報，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] 王勤波，許成，段偉偉，等.動態最小費用流問題[J].青島大學學報（自然科學版），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] 謝政，湯澤瀅.帶模糊約束的最小費用流問題[J].模糊系統與數學，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] 董振寧.無容量限制的最小費用流問題[J].數學研究與評論，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] 吳相林，尹崢.應用最小費用流求解活動網絡時間?費用模型[J].華中科技大學學報（自然科學版），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] 董振寧，張畢西.遺傳算法求解帶容量限制的最小費用流問題[J].數學的實踐與認識，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] 張煜，吳露，田維.動態最小費用流啟發式算法求解多式聯運問題[J].武漢理工大學學報，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