最小费用最大流问题

✍ dations ◷ 2025-08-02 21:12:18 #管理学,经济学,网络流,图论

最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下,此类问题的研究试图寻找出:流量从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} 的弧,额外汇点也执行类似的操作。完成这一步后,所得到的模型已与普通最小费用最大流无异。

相关

  • 让·皮亚杰让·皮亚杰(法语:Jean Piaget,1896年8月9日-1980年9月16日),全名让·威廉·弗里兹·皮亚杰(法语:Jean William Fritz Piaget),瑞士人,是近代最有名的发展心理学家,同时也是哲学家。他的
  • 硫酸镝硫酸镝是一种无机化合物,化学式为Dy2(SO4)3。用硫酸溶解氧化镝,可以得到硫酸镝。
  • 阿尔克墨涅阿尔克墨涅(英语:Alcmene,希腊文:Αλκμήνη)是希腊神话中的人物,是珀耳修斯的孙女、梯林斯和迈锡尼国王厄勒克特律翁之女、忒拜国王安菲特律翁之妻、大力神赫拉克勒斯之母。
  • 夹鼻眼镜夹鼻眼镜("Pince-nez",/ˈpænsneɪ/ or /ˈpɪnsneɪ/; 法语发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida S
  • 2005年九江地震5.7Ms(中国地震台网) 5.2Mw(美国地质调查局) 2005年九江地震,发生于北京时间(UTC+8)2005年11月26日(星期六)8时49分38.6秒,震中位于中国江西省九江市九江县,靠近瑞昌市,距离九江市区15千
  • 科迪纳尔科迪纳尔(Kodinar),是印度古吉拉特邦Junagadh县的一个城镇。总人口32606(2001年)。该地2001年总人口32606人,其中男性16871人,女性15735人;0—6岁人口4825人,其中男2510人,女2315人;识
  • 卡恩凯尔卡恩凯尔(Kanker),是印度恰蒂斯加尔邦Kanker县的一个城镇。总人口24485(2001年)。该地2001年总人口24485人,其中男性12238人,女性12247人;0—6岁人口2890人,其中男1417人,女1473人;识字
  • 埃达加纳萨莱埃达加纳萨莱(Edaganasalai),是印度泰米尔纳德邦Salem县的一个城镇。总人口29593(2001年)。该地2001年总人口29593人,其中男性15902人,女性13691人;0—6岁人口3656人,其中男2042人,女1
  • 浙江各地级市地区生产总值列表浙江省各地级市地区生产总值列表收录各主要年份浙江省地级行政区(仅有地级市)的地区生产总值(GDP)总量和人均GDP指标,当年数据参考次年底出版的《中国统计年鉴》和《浙江统计年鉴
  • 哲人言行录《哲人言行录》,或译作《名哲言行录》(古希腊语:Βίοι καὶ γνῶμαι τῶν ἐν φιλοσοφίᾳ εὐδοκιμησάντων)是第欧根尼·拉尔修撰写的关于古