最小费用最大流问题

✍ dations ◷ 2025-08-24 19:34:17 #管理学,经济学,网络流,图论

最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下,此类问题的研究试图寻找出:流量从A到B,如何选择路径、分配经过路径的流量,可以达到所用的费用最小的要求。


有足够多辆卡车要将数量无限的某种物品从一个地点运输到另外一个地点,现在有有限条单向行驶道路直接或者间接地连接了这两地。但是每一条道路都有运输通过总数量的限制,称为容量,同时携带物品通过该路段时,都会按照携带物品数量多少被收取一定的费用。如何合理地安排每辆车的行驶路线,使得在运输的货物总量尽可能大的情况下,交付的总费用尽可能少?

注意,在此问题中总费用仅包括携带物品通过路段时被收取的费用,车辆和路线安排上没有限制,但通过某一路段的物品数量总和不得超过它的容量,收取的费用与携带物品的多少成正比。

最小费用最大流建立在最大流和网络流问题的基础之上。

带权有向图 G = ( V , E ) {\displaystyle G=(V,E)} 。如果将费用看作两点之间的距离,那么这就转换为了一个最短路问题。

在最短路问题中,我们利用队列优化的Bellman-Ford算法(以下简称 SPFA) 求单源最短路,进而得到两个结点之间的最短路径 d i s u v {\displaystyle dis_{u\to v}} . 使用类似的思想,将两点之间的距离转换为两点之间的费用,然后运行 SPFA 算法,同时维护可以从源点到达每个点的最大流量,得到从源点到汇点一条费用最小的增广路,使用这条路径进行增广,然后重复这个过程。直到找不到增广路,此时的总流量和总费用即为所求答案。

具体而言,记源点为 s {\displaystyle s} ,汇点为 t {\displaystyle t} . 设 u V ,   d ( u ) {\displaystyle u\in V,\ d(u)} 代表从 s {\displaystyle s} u {\displaystyle u} 每单位流量花费的最小费用, f ( u ) {\displaystyle f(u)} 代表使用上述每单位流量花费费用最小的路径能够让多少流量从源点流到 u {\displaystyle u} . 在 SPFA 每一轮循环过程中,从队列中取出一个结点 u {\displaystyle u} , 并枚举每一条边 ( u , v ) E {\displaystyle (u,v)\in E} , 如果满足 d ( v ) > d ( u ) + w ( u , v ) {\displaystyle d(v)>d(u)+w(u,v)} 则更新相应的 d ( v ) = d ( u ) + w ( u , v ) {\displaystyle d(v)=d(u)+w(u,v)} f ( v ) = min { f ( u ) , f ( u , v ) } {\displaystyle f(v)=\min\{f(u),f(u,v)\}} ,同时记录 l a s t ( v ) {\displaystyle last(v)} 代表来到结点 v {\displaystyle v} 使用了哪一条弧. 求出单源最短路后,就等同于找到了一条增广路,花费 f ( t ) × d ( t ) {\displaystyle f(t)\times d(t)} 将流量增大 f ( t ) {\displaystyle f(t)} . 增广结束后,我们需要更新这条增广路上弧和反向弧的流量。

需要注意的是,与求解单源最短路问题时类似,虽然SPFA能够处理带有负权的边(也就是费用为负的弧),但是如果出现了负环,则会让算法陷入死循环。

利用这种算法,不仅可以解决前面提到的类似问题,经过变换也可以通过建立相应模型间接地解决许多问题。

二分图的最佳带权匹配问题在经过变形之后,可以使用最小费用最大流相关算法进行求解。首先对于二分图中的每一条边,视其容量为1,它的权值也就是费用,由于最佳带权匹配需要所有匹配边权值之和最大,所以视其费用为权值的相反数。正确地求得最小费用 C {\displaystyle C} 之后,最佳带权匹配的总权值之和 T {\displaystyle T} 就是最小费用的相反数 T = C {\displaystyle T=-C} .

需要注意的是,二分图匹配问题中有许多个源点和许多个汇点,一条可行流可以从其中任何一个源点出发到达任何一个汇点结束,对于这种情况,我们可以建立一个额外的源点何一个额外的汇点,将额外源点与所有源点连容量为 {\displaystyle \infty } 费用为 0 {\displaystyle 0} 的弧,额外汇点也执行类似的操作。完成这一步后,所得到的模型已与普通最小费用最大流无异。

相关

  • 肝病毒科正肝去氧核糖核酸病毒属 Orthohepadnavirus 鸟类肝去氧核糖核酸病毒属 Avihepadnavirus肝病毒科(hepadnaviridae)又译肝去氧核糖核酸病毒科,DNA逆转录病毒的一类,主要感染对象为
  • 乙酰乙酰基(英语:Acetyl),化学式为
  • 新北市新北市文化资产是位于台湾新北市的古迹与历史建筑等文化资产,以下的文化资产均收录在中华民国行政院文化部文化资产局的网站里。改修碑:1926年
  • 伦敦规划伦敦计划(London Plan)是大伦敦地区的空间发展战略,由伦敦城长编写,大伦敦管理局出版。最新的一份伦敦计划在2016年3月制定,2017年1月出版。现在的计划将截止至2036年。
  • 阿拉斯加狭地阿拉斯加狭地(Alaska Panhandle),是指阿拉斯加的东南隅的狭长地带,位于加拿大卑诗省的北半部的西边,但北部亚库塔特湾部分邻育空地方,是长达1,040公里的北面直线边界(西经141度)
  • 卫德明赫尔穆特·威廉(德语:Hellmut Wilhelm,1905年12月10日-1990年7月5日),汉名卫德明,生于德属胶澳青岛,德国著名汉学家,专长于中国文学与中国历史。他也是国际知名的易经专家,曾任教于北
  • 包斯卡自治市包斯卡自治市(拉脱维亚语:Bauskas novads),是拉脱维亚的一个自治市,设立于2009年。位于该国南部,人口27052人,面积784.9平方公里,人口密度约34人/km2。
  • 清凉寺街道清凉寺街道,是中华人民共和国河北省保定市涿州市下辖的一个乡镇级行政单位。清凉寺街道下辖以下地区:槐林社区、长空路社区、建设路社区、华阳社区、学园社区、阳光社区、马坊
  • Poppin'PartyPoppin'Party是由五位声优组成的乐团型声优组合,组建于2015年,是日本跨媒体制作《BanG Dream!》的一部分。成员各自对应《BanG Dream!》中同名虚拟乐团的五位角色,并与角色演奏
  • 农嫩巴赫河 (阿尔河支流)坐标:50°25′27.13″N 6°40′14.00″E / 50.4242028°N 6.6705556°E / 50.4242028; 6.6705556农嫩巴赫河(德语:Nonnenbach),是德国的河流,位于该国西部,处于北莱茵-威斯特法伦州