最小费用最大流问题算法研究绪论.pptVIP

最大流问题 引例：图1是联结某产地 和销地 的交通网, 最小费用最大流问题 引例：图2是联结某产地 和销地 的交通网络费用图, 一、什么是最小费用最大流问题？ 四、网络图的构造 顶点是原网络费用图 的顶点，而把 中的每一 练习：图2是联结某产地 和销地 的交通网络费用图, * * 产品经过交通网从 输送到 。现要制定一个运输 方案使从 运到 的产品数量最多。 图1 产品经过交通网从 输送到 。现要制定一个运输 方案使从 运到 的产品数量最多，而总费用最小。。 图2 其中， 表示弧 上的容量， 表示弧 上 通过单位流量所花费的费用， 表示弧 上的流量。 对每一条弧都给出单位流量费用的容量网络 中，求取最大流 ，使输送流量的总费用 为最小的一类优化问题。 vi vj vi vj 其中， 表示弧 上的容量， 表示弧 上 通过单位流量所花费的费用 。 二、增广链的费用 当沿着一条关于可行流 的增广链（流量修正路线） ，以修正量 进行调整，得到新的可行流 ，则称 为增广链 的费用。 三、实现思路 在网络费用图上只要找到其上的最小费用增广链，在该链上调整流量，就得到增加流量后的最小费用流。循环往复就可以求出最小费用最大流。 实施中的关键——寻找最小费用增广链 条弧 变成两个相反方向的弧 和 。定义 弧的权为 举例：以下图为例，求最小费用最大流，弧旁的数字为(cij,bij)。 vs vt v2 v3 v1 (10,4) (7,1) (8,1) (10,3) (4,2) (5,2) (2,6) 3 vs vt v2 v3 v1 4 1 1 2 2 6 vs vt v2 v3 v1 (10,0,4) (7,0,1) (8,0,1) (10,0,3) (4,0,2) (5,0,2) (2,0,6) vs vt v2 v3 v1 (10,0,4) (7,1,1) (8,1,1) (10,0,3) (4,0,2) (5,1,2) (2,0,6) 3 1 -1 2 -2 vs vt v2 v3 v1 4 2 6 -1 1 vs vt v2 v3 v1 (10,0,4) (7,5,1) (8,5,1) (10,0,3) (4,0,2) (5,5,2) (2,0,6) 3 vs v2 v3 v1 4 -1 1 2 6 -1 -2 1 vt vs vt v2 v3 v1 (10,2,4) (7,7,1) (8,5,1) (10,0,3) (4,0,2) (5,5,2) (2,0,6) 3 vs v2 v3 v1 4 -1 1 2 6 -1 -2 vt -4 vs vt v2 v3 v1 (10,2,4) (7,7,1) (8,8,1) (10,3,3) (4,3,2) (5,5,2) (2,0,6) 3 vs v2 v3 v1 4 -1 2 6 -1 -2 vt -4 -3 -2 vs vt v2 v3 v1 (10,3,4) (7,7,1) (8,8,1) (10,4,3) (4,4,2) (5,4,2) (2,0,6) -3 3 vs v2 v3 v1 4 -1 -1 -2 vt -4 -2 6 2 总 结 最短路算法与最大流算法的结合运用 1）构造初始可行流的增广费用网络图，用最短路算法求出最小费用增广链。 2）将最小费用增广链还原到容量流量网络图中的增广链，调整流量得到新的可行流，继续进行，直到用最短路算法找不到最小费用增广链。 产品经过交通网从 输送到 。现要制定一个运输 方案使从 运到 的产品数量最多，而总费用最小。