工具之家 > 现代电子技术 > 不可分流网络的最小费用流问题

不可分流网络的最小费用流问题

发布时间:2019-07-04 02:15:00 文章来源:工具之家    

 推荐工具:金融理财app工具实用工具

曹卫锋+梅霞+zhang兴永

摘 要 通chang情况下单weiliu量feiyongzuixiaodena条lujingfa送gegeliu总feiyong是zuixiaode但是往往单位liu量费用zuixiaodena条lujing并bu一ding能满足所youliu均ke通过。针对不可fenliudewangluoliuzuixiaofei用wenti提chu按liuzhi排xu寻求最youjiedesuanfa并geichuxiang关de理论zhengming及suanfa最后通过ju体实验测试了gai算法deyou效性。此算法可yi快速求解所提de问ti并能够算出最优zhi。实例结果表明该算法有效地解决了不可fenliudewang络流最小费用问ti可以应用于实际的网络优化zhong

关jianci jiedian 最小费用流; 不可分流; 弧上限; 最小费用lu径; 流zhipaixu

zhong图分leihao: TN911.1?34; O221 文獻biao识码: A 文章编号: 14?373X2181?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

目前,对网络优化中可分解流在刚性弧上限的网络中dezui小费用问ti,qiyan究已日趋完善,有了许多能够求得最小费用流最优解的算法[1?3]。但是,对于不可分流的网络流的最小费用问题,目前相关的研究还jiaoshao[4?5];tongshi,解决的fangfa还缺少一般性的最优性证明[6]。

本文针对不可分流的网络流最小费用问题,提出按流值排序寻求最优解的方法,并给出了相关的理论证明及算法。实例显示,该算法有效地解决了不可分流的网络流最小费用问题。

1 问题的提出及建立的数xue模型

在juyouyizhi的弧上限he单位流量费用的网络中,如何由一ge节dian向另一节点或其他几ge节点fasongruo干个不可分liu并使得所有流的总费用最小。假ding所有的不可分流均是源源不断地从fa点流向对应deshou点,中途没有间断;并且这些不可分流都是以同样的速度匀速通过网络上ge条弧的。

在已知的网络中,[V]biaoshi所有节点的集合,[A]表示所有弧的集合,节点数wei[n]弧数为[m。]对[?i,jA,][cij]表示弧[i, j]上单位流量的费用,[nij]表示弧[i, j)]的弧上限,[xij]表示通过弧[i, j)]deliu的流量(流值),而[vk]ze表示第[k]个不可分流[xk( )]的流值[7?8]。用数学规划的方法描述存在若干个不可分流的网络中最小费用流问题如下

[mink=1K(i,j)∈Acijxkijs.t. j:(i,j)∈Axkij-j:j,i)∈Axkji=vk,i=s-vk,i=tk,0i≠s,tk ?i∈V0≤xkij≤n ?(i,j)∈A ] (1

式中:决cebian量(流量)[xkij]表示弧[(i,j)]是fou位于第[k]个不可分流[xk]的最小费用路径上:当[xkij=vk]时,表示弧[(i,j)]位于流[xk]的最小费用路径上:当[xkij=0]时,表示弧[(i,j)]不在流[xk]的最小费用路径上。[tk]则表示第[k]个不可分流[xk]的收点,[tk]既可以相同也可以不同([k=1,2,…,K])。

2 问题的理论分析及研究

由于在网络中沿不同的路径发送各个流,其费用是不同的,如何选择路径发送这些不可分流才能使得总费用最小,显ran,可以的话,沿单位流量费用最小的那条路径发送各个流,总费用是最小的,但是,往往单位流量费用最小的那条路径并不一定能满足所有流均可通过。这时,就要kaolv应让哪些流占用单位流量费用最小的那条路径,哪些流的发送路径应重新考虑,才能使得所有不可分流的总费用最小。容易想dao的是,jiang所有可行的方an一一考虑,并逐个对比、选择,最终可获得(TCP)的最优解。但是,这zhong方法的ji算量一般是fei常庞da的,同时也不太现实。研究表明,不可分流的网络流总费用与各个流的优先安排发送次序有关,且具有如下的性质。

定理1:在网络中由一个节点向另一节点或其他几个节点发送等流值的若干个不可分流时,若逐个发出流,并沿每个流在当前可取到的最小费用路径发送,则所有流的总费用最小,且最小费用与要发送的等流值的若干个不可分流的发送次序wu关。endprint

jielun是显然的(证明略)。

定理2:在网络中由一个节点向另一节点或其他几个节点发送不等流值的若干个不可分流时,若按流值由dadao小的次序逐个发出流,并沿每个流在当前可取到的最小费用路径发送,则所有流的总费用最小。

证明:在网络中发送不等流值的若干个流,不妨设发送liang个流[x1]和[x2,]其流值fenbie为[v1]和[v2]([v1>v2]),当在网络中只发送流[x1]时,qizui小费用为[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]时,显ran此时有[P21]=[P2]和[P12]=[P1](此两种情况可xianghu推出)。所以,[t11]=[t12]=[t1]且[t21]=[t22]=[t2],故[t11]+[t22]=[t21]+[t12]。

2 当[P11]=[P1],[P22][≠][P2]时,显然,此时有[P21]=[P2]和[P12][≠][P1](此两种情况可相互推出)。所以,[t11=t1,][t21=t2;]根ju所要求的是最小费用路径,从[P22][≠][P2]知一定有[t22≥t2,]从[P12][≠][P1]知一定有[t12≥t1]。又,在相同的路径上,大流值流的费用比小流值流的费用多,且大流值流可经过的路径小流值流一定能过,但反之不成立。故[t22-t2≤t12-t1,]所以,[t11+t22≤t11+t12-t1+t2=t11+][t12-t11+t21=t21+t12,]ji[t11+t22≤t21+t12。]

因此,当发送两个不等流值的流时,大流值的流后发送所zengjia的费用与小流值的流后发送所增加的费用相比是非递减的。同样,当发送多个不等流值的流时,其情况可以类似地如上分析,或者是依次选取两个流相互比jiao。

综上所述,在只有一个发点和若干个收点的网络中发送不等流值的多个不可分流,大流值的流后发送所增加的费用与小流值的流后发送所增加的费用相比是非递减的。也就是说,若按流值由大到小的次序逐个发出流,并沿每个流在当前可取到的最小费用路径发送,则所有流的总费用最小。

3 算 法

在不可分流的网络中,所有的弧上限[nij]都是刚性的,故可记为:

[fij(v)=1v≤nij,v>nij, ?(i,j)∈A] (2)

称[fij(v)]为指标han数,引入指标函数的目的是为了计算的简便及算法buzhou的清晰。根据以上分析和定理1和2,建立流值排序算法,具体步骤为:

1) 输入[cij,nij]和[fij(v)](若[i=j,]则认为[cij=nij=fij(v)=0;]若[i]与[j]间无弧,则认为[cij=nij=fij(v)=]);

2) 按流值的非递增序输入给定的不可分流,ling按此顺序输入的流的流值为[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) 令[u1)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,]若[ul)j≥u(l)i+tij,]则令[u(l+1)j=u(l)i+tij,][p(j)=i,]zhuandaobu骤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)]),则令[ll+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标号修正算法(迭代算法)和函数空间迭代法的si想[9]。

2) 算法步骤中[vk]的下标[k]的递增序是与给定的流的流值的非递增序相对应的,在不考虑等流值的流调换发送次序时,这种对应是一对一的。

3) 算法步骤中的[p(j)]是表示在最小费用路径中节点[j]的前趋节点,即当前最小费用路径中至节点[j]的最后一条弧([p(i), j])的起点。

4) 算法迭代过cheng结束后,至节点[j]的最小费用路径可通过[p(j)]经反向查找得出[10]。而算法步骤中的[ukj0]为与[vk]相对应的流[xk]经过其最小费用路径[Pk:][s→jk1=p(jk2)→jk2=p(jk3)→…→tk]时的费用,[u]是所有流的最小费用zhihe,即总费用。

5) 按此算法求得的解[u]即为问题(TCP)最优解的值。

6) 若已知网络的节点数为[n,]弧数为[m,]给定[K]个不可分流,则此流值排序算法的时间复杂度为[O(Knm),]这是一个复杂度比较低的qiang多项shishi间算法。

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]。

shiqiu:给定流[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 结 语

针对不可分流的网络流最小费用问题,提出一种新的、行之有效的可求得最优解的方法——流值排序算法。该算法有效地解决了在一个发点、一个收dianji一个发点、若干个收点的网络中发送若干个不可分流的最小费用问题。同时,由于该算法是一种强多项式时间算法,其时间复杂度为[O(Knm),]因此可以很方便地编制程序利用计算机执行。利用本文给出的算法编制成C程序对多个实例进行验算显示,该算法可以快速地求解所给出的问题,不但能求得最优解的值,而且也能给出具体的发送流的方案。

参考文献

[1] 黄凯,张晓xu张晓濛,等.基于整数线性规划的MPSoC通信优化celue[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] 吴超,黄淋妃.安全yun筹学的学科构建研究[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] 董zhen宁.无容量限制的最小费用流问题[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] wuxiang林,尹峥.应用最小费用流求解活动网络时间?费用模型[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,382):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

现代电子技术 2018年1期

现代电子技术的其它文章 基于联合迭代检测译码的多中继RA编码协zuo系统 差分GPS实时数据解调算法研究与实现 基于匹配追踪算法值改进的MIMO?OFDM信道估计研究 卫星天线过顶盲区时机分析 智能电网双层无线接入架构及信道仿真研究 一种EHOPPPA算法改进LTE切换性能的研究
转载请注明来源。原文地址:https://www.5420.com.cn/view/2019/0704/18390/
 与本篇相关的热门内容: