不可分流网络的最小费用流问题
曹卫锋+梅霞+张兴永
摘 要： 通常情况下单位流量费用最小的那条路径发送各个流总费用是最小的，但是往往单位流量费用最小的那条路径并不一定能满足所有流均可通过。针对不可分流的网络流最小费用问题，提出按流值排序寻求最优解的算法，并给出相关的理论证明及算法，最后通过具体实验测试了该算法的有效性。此算法可以快速求解所提的问题，并能够算出最优值。实例结果表明，该算法有效地解决了不可分流的网络流最小费用问题，可以应用于实际的网络优化中。
关键词： 节点； 最小费用流； 不可分流； 弧上限； 最小费用路径； 流值排序
中图分类号： 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：在网络中由一个节点向另一节点或其他几个节点发送等流值的若干个不可分流时，若逐个发出流，并沿每个流在当前可取到的最小费用路径发送，则所有流的总费用最小，且最小费用与要发送的等流值的若干个不可分流的发送次序无关。
结论是显然的（证明略）。
定理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
7） 若[k=K，]则停，输出[u=k=1Kukj0][（j0=tk，k=][1，2，…，K）]；否则（[k
对该算法的几点说明：
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.
[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.
摘 要： 通常情况下单位流量费用最小的那条路径发送各个流总费用是最小的，但是往往单位流量费用最小的那条路径并不一定能满足所有流均可通过。针对不可分流的网络流最小费用问题，提出按流值排序寻求最优解的算法，并给出相关的理论证明及算法，最后通过具体实验测试了该算法的有效性。此算法可以快速求解所提的问题，并能够算出最优值。实例结果表明，该算法有效地解决了不可分流的网络流最小费用问题，可以应用于实际的网络优化中。
关键词： 节点； 最小费用流； 不可分流； 弧上限； 最小费用路径； 流值排序
中图分类号： 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：在网络中由一个节点向另一节点或其他几个节点发送等流值的若干个不可分流时，若逐个发出流，并沿每个流在当前可取到的最小费用路径发送，则所有流的总费用最小，且最小费用与要发送的等流值的若干个不可分流的发送次序无关。
结论是显然的（证明略）。
定理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
7） 若[k=K，]则停，输出[u=k=1Kukj0][（j0=tk，k=][1，2，…，K）]；否则（[k
对该算法的几点说明：
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.
[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.
