最小流费用问题课件.ppt

《最小流费用问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、大家知道，法求最短路只适应于权≥0的情况，当网络中出现负权时，此法失效，如：一。带负权的最短路问题：求到的最短路。下面通过例子来说明带负权的网络的最短路求法：逐次逼近法：1．给标号（0）。画弧。①①①给划成彩线。③划第二个弧。②给标号（-3）。②①①给划成彩线。③划第三个弧。②给标号（1）。②③①①给划成彩线。③划第四个弧。②给标号（2）。②③④①①给划成彩线。④划第五个弧。②给再次标号（0）。②③④⑤③去掉彩线。①①分别给划成彩线。③划第六个弧。②分别给标号（6）。②③④⑤⑥①①给划成彩线。③划第七个弧。②给标号（10）。②③④⑤⑥

2、⑦①①给划成彩线。到达已经无负权，路程不可能再减少。②给标号（9）。②③④⑤⑥⑦①②③④⑤⑥⑦最短路径为：距离：10。前几节主要讲了两个问题：最短路问题和最大流问题。下面介绍网络中二者的结合问题：最小费用流的问题。问题的提出是这样的：在一个关于流的网络中，人们不仅需要流达到一定的数量，（甚至达到最大，即最大流）而且每一个流量要有一定的费用，流所走的路线不一样，单位费用不一样。同样数量的流量，可能走的路线不一样，总的费用不一样。从而在限定网络流的基础上，让流沿那些边走，能使总的费用最小（这里的最小费用问题又看成最短路问题）。§8.5最小

3、费用流问题特别的，当最大流不惟一时，在所有最大流中求一个流f,使总费用最低。流量的费用，记为用规划语言可以这样描述：若给定容量网络G=（V，E，C）除给定每个边上的容量外，还给定G=（V，E，C，D）若给定G的一个可行流,在总的流量（常数）下使求最费用最大流的基本思想是：从零流开始，以费用作为边的长度，用求最短路的方法，求出可增广链，调整流量，使其流量逐步达到要求的数量。下通过例子来说明。例：在下图所示的网络中，求流量为10的最小费用流。边上括号内为。先假设此网络是空架子，即0-流。然后，逐步调整流量到10，在什么路线上增加流量？在费

4、用最小的路线上调流量。为简单，把费用网络先拿出来。借费用最短路作为可行流的可增广链，从而在保证流量的同时，又保证费用最低。看下图：①②①②③③上图为0流图，边上的括号内为在此可增广链上，取容量最小的值min｛8,5,7｝=5,调整量为5。调整后图为此时，网络流量为=5≺10，此流的费用为：返回到费用网络中，继续找最短路，进而继续调整。在下面流量的调整中，注意到图（c)有些边的流量已饱和，只能降低，不能再升，如。而有些边可降，可升。如。下次调整为了表达上面的意思，我们在费用流网络中，可升、可降的边用两个箭头表示，如下图：下用逐次逼近法求

5、到的费用最短路。①标（0），画第一个弧。②标（1），画第二个弧。①②①②③分别标（4）、（4），画第三个弧。③④标号（5）。画第四个弧。经检查，已没有修改的必要。④显然，流的调整量为2。调整后为此时，网络流量为=7≺10，此流的费用为：在已用过的链上，可增可降的双箭头，只增不降的单箭头。下用逐次逼近发求最短路（可增广链）：①②③显然，流的调整量为3。调整后为此时，网络流量为=10，最小费用为：