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

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

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

中圖分類號(hào)： TN911.1?34； O221 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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

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

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

1 問(wèn)題的提出及建立的數(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)，中途沒(méi)有間斷；并且這些不可分流都是以同樣的速度勻速通過(guò)網(wǎng)絡(luò)上各條弧的。

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

[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èn)題的理論分析及研究

由于在網(wǎng)絡(luò)中沿不同的路徑發(fā)送各個(gè)流，其費(fèi)用是不同的，如何選擇路徑發(fā)送這些不可分流才能使得總費(fèi)用最小，顯然，可以的話，沿單位流量費(fèi)用最小的那條路徑發(fā)送各個(gè)流，總費(fèi)用是最小的，但是，往往單位流量費(fèi)用最小的那條路徑并不一定能滿足所有流均可通過(guò)。這時(shí)，就要考慮應(yīng)讓哪些流占用單位流量費(fèi)用最小的那條路徑，哪些流的發(fā)送路徑應(yīng)重新考慮，才能使得所有不可分流的總費(fèi)用最小。容易想到的是，將所有可行的方案一一考慮，并逐個(gè)對(duì)比、選擇，最終可獲得（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ā)送次序無(wú)關(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)過(guò)的路徑小流值流一定能過(guò)，但反之不成立。故[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)用相比是非遞減的。也就是說(shuō)，若按流值由大到小的次序逐個(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ì)算的簡(jiǎn)便及算法步驟的清晰。根據(jù)以上分析和定理1和2，建立流值排序算法，具體步驟為：

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

2） 按流值的非遞增序輸入給定的不可分流，令按此順序輸入的流的流值為[vk]（[k=1，2，…，K]）（[k]的遞增序與流值的非遞增序一一對(duì)應(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] 間無(wú)弧，則認(rèn)為[tij=∞]），[i，j=1，2，…，n]；同時(shí)，令與[vk]相對(duì)應(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） 對(duì)所有的節(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]相對(duì)應(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）。

對(duì)該算法的幾點(diǎn)說(shuō)明：

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

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

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

5） 按此算法求得的解[u]即為問(wèn)題（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]間無(wú)弧，則認(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]間無(wú)弧，則認(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ì)算過(guò)程如下：

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

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

① 首先發(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，]對(duì)應(yīng)的收、發(fā)點(diǎn)分別為4和1），流[x2]（[v2=35]對(duì)應(yīng)的收、發(fā)點(diǎn)分別為5和1）和流[x3]（[v3=30，]對(duì)應(yīng)的收、發(fā)點(diǎn)分別為6和1）時(shí)，從節(jié)點(diǎn)1發(fā)送所有流至對(duì)應(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ā)送所有流至對(duì)應(yīng)收點(diǎn)的最小費(fèi)用為900。

5 結(jié) 語(yǔ)

針對(duì)不可分流的網(wǎng)絡(luò)流最小費(fèi)用問(wèn)題，提出一種新的、行之有效的可求得最優(yōu)解的方法——流值排序算法。該算法有效地解決了在一個(gè)發(fā)點(diǎn)、一個(gè)收點(diǎn)及一個(gè)發(fā)點(diǎn)、若干個(gè)收點(diǎn)的網(wǎng)絡(luò)中發(fā)送若干個(gè)不可分流的最小費(fèi)用問(wèn)題。同時(shí)，由于該算法是一種強(qiáng)多項(xiàng)式時(shí)間算法，其時(shí)間復(fù)雜度為[O（Knm），]因此可以很方便地編制程序利用計(jì)算機(jī)執(zhí)行。利用本文給出的算法編制成C程序?qū)Χ鄠€(gè)實(shí)例進(jìn)行驗(yàn)算顯示，該算法可以快速地求解所給出的問(wè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].中國(guó)安全科學(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] 王勤波，許成，段偉偉，等.動(dòng)態(tài)最小費(fèi)用流問(wèn)題[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)用流問(wèn)題[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] 董振寧.無(wú)容量限制的最小費(fèi)用流問(wèn)題[J].數(shù)學(xué)研究與評(píng)論，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)用流求解活動(dòng)網(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)用流問(wèn)題[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，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] 張煜，吳露，田維.動(dòng)態(tài)最小費(fèi)用流啟發(fā)式算法求解多式聯(lián)運(yùn)問(wè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