最小费用最大流问题算法研究汇总

1、最大流问题最大流问题 引例：引例：图图1是联结某产地是联结某产地 和销地和销地 的的交通网交通网,产品经过交通网从产品经过交通网从 输送到输送到 。现要制定一个运输。现要制定一个运输1v6v1v6v方案使从方案使从 运到运到 的产品数量最多。的产品数量最多。1v6v1v2v3v4v6v5v(17,2)(5,1)(11,6)(3,3)(4,1)(5,2)(3, 2 )(8 , 3 )(6, 3)(10,5)图图1 引例：引例：图图2是联结某产地是联结某产地 和销地和销地 的的交通网络费用图交通网络费用图,产品经过交通网从产品经过交通网从 输送到输送到 。现要制定一个运输。现要制定一个运输1v6v

2、1v6v方案使从方案使从 运到运到 的产品数量最多，的产品数量最多，而总费用最小。而总费用最小。1v6v1v2v3v4v6v5v(17,2,7)(5,1, 5)(11,6,2)(3,3,4)(4,1, 5)(5,2,3)(3, 2, 4 )(8 , 3, 8 )(6, 3, 4)(10,5,10)图图2最小费用最大流问题最小费用最大流问题),(CAVD vijijxbvb)(ijc),(jivvijbijx),(jivv),(jivv 其中，其中， 表示弧表示弧 上的容量，上的容量， 表示弧表示弧 上上通过单位流量所花费的费用，通过单位流量所花费的费用， 表示弧表示弧 上的流量。上的流量。 对

3、每一条弧都给出对每一条弧都给出的的容量网络容量网络 中，求取中，求取最大流最大流 ，使输送流量的，使输送流量的总费用总费用 为最小为最小的一类优化问题。的一类优化问题。vivj),(ijijijbxcvivj(,)ijijc bijc),(jivvijb),(jivv 其中，其中， 表示弧表示弧 上的容量，上的容量， 表示弧表示弧 上上通过单位流量所花费的费用通过单位流量所花费的费用 。 当沿着一条关于可行流当沿着一条关于可行流 的增广链（流量修的增广链（流量修正路线）正路线） ，以修正量，以修正量 进行调整进行调整，得到新的，得到新的可行流可行流 ，则称，则称 为为( )( )b xb xx

4、P1xP 在网络费用图上只要在网络费用图上只要找到找到其上的其上的最小费用增广最小费用增广链链，在该链上，在该链上调整流量调整流量，就得到，就得到增加流量后的最小增加流量后的最小费用流费用流。循环往复就可以求出最小费用最大流。循环往复就可以求出最小费用最大流。四、网络图的构造四、网络图的构造 顶点是原网络费用图顶点是原网络费用图 的顶点，而把的顶点，而把 中的中的每一每一DD条弧条弧 变成变成两个相反方向两个相反方向的弧的弧 和和 。定义。定义),(jivv),(jivv(,)jiv v弧的权为弧的权为:ijw00ijijijjiijijijijijijxxbwcxcxbw若若若若ivjviv

5、jvijwjiw vsvtv2v3v1(10,4)(7,1)(8,1)(10,3)(4,2)(5,2)(2,6)3vsvtv2v3v1411226tsvvvv12vsvtv2v3v1(10,0,4)(7,0,1)(8,0,1)(10,0,3)(4,0,2)(5,0,2)(2,0,6)vsvtv2v3v1(10,0,4)(7,1,1)(8,1,1)(10,0,3)(4,0,2)(5,1,2)(2,0,6)31-12-2vsvtv2v3v1426-11tsvvvv12vsvtv2v3v1(10,0,4)(7,5,1)(8,5,1)(10,0,3)(4,0,2)(5,5,2)(2,0,6)3vsv2

6、v3v14-1126-1-21vt1stvvv vsvtv2v3v1(10,2,4)(7,7,1)(8,5,1)(10,0,3)(4,0,2)(5,5,2)(2,0,6)3vsv2v3v14-1126-1-2vt-423stvvvvvsvtv2v3v1(10,2,4)(7,7,1)(8,8,1)(10,3,3)(4,3,2)(5,5,2)(2,0,6)3vsv2v3v14-126-1-2vt-4-3-213stvvvv 123stvvvvv vsvtv2v3v1(10,3,4)(7,7,1)(8,8,1)(10,4,3)(4,4,2)(5,4,2)(2,0,6)-33vsv2v3v14-1-1

7、-2vt-4-262总总 结结最短路算法与最大流算法的结合运用最短路算法与最大流算法的结合运用 1 1）构造构造初始可行流的初始可行流的增广费用网络图增广费用网络图，用，用最短路算法最短路算法求出最小费用增广链。求出最小费用增广链。 2 2）将最小费用增广链）将最小费用增广链还原还原到容量流量网络到容量流量网络图中的增广链，图中的增广链，调整调整流量流量得到新的得到新的可行流，继可行流，继续进行，续进行，直到直到用最短路算法用最短路算法找不到找不到最小费用增最小费用增广链。广链。 练习：练习：图图2是联结某产地是联结某产地 和销地和销地 的的交通网络费用图交通网络费用图,产品经过交通网从产品经过交通网从 输送到输送到 。现要制定一个运输。现要制定一个运输1v6v1v6v方案使从方案使从 运到运到 的产品数量最多，而总费用最小。的产