《最小费用最大流问题》.pptVIP

最小费用最大流问题; 最大流问题 引 例 基本概念 最大流算法 算 例 ;continued;一、网络与流 　　　一个有向图　　　　　 称为一个网络．其中， 为图的所有顶点集； 为弧集； 为各弧上容量集 　　　在　中指定了两点　 ，分别称为发点和收点，其余的点叫中间点．定义弧集合　上的一个函数 为网络的一个流,并称　　 为弧 上的流量，简记为　;二、可行流与最大流 一个流称为一个可行流,如果满足以下条件: 　　(1) 容量限制条件:对 (2) 平衡条件: 对中间点:流出量=流入量,即 对于发点 对于收点 式中 称为这个可行流的流量,即发点的净输出量(或收点的净输入量);最大流问题: ;三、增广链 1 、给定一个可行流 称 2 、若 是网络中联结发点 和收点 的一条链,定义链的方向是从 到 ,则链上的弧被分为两类:一类是弧的方向与链的方向一致,称为前向弧,前向弧的全体记为 另一类弧与链的方向相反,称为后向弧,后向弧的全体记为 3 、设f是一个可行流, 是从到的一条链,称为一条增广链,如果 ;四、截集 1 、设 把始点在 ,终点在 中的所有弧构成的集合,记为 2 、给定网络 若点集 被剖分为两个非空集合 使 则弧集 称为分离 和 的截集. 3 、截集 中所有弧的容量之和称为此截集的容量,记为 即; 定理 1 可行流f是最大流 不存在关于f的增广链. 定理2 任一个网络 中,从 到 的最大流的流量等于分离 的最小截集的容量.;求最大流的标号法(Ford,Fulkerson) 1 、标号过程 开始:先给 标上 此时 是标号而未检查的点,其余都是未标号点.一般地,取一个标号而未检查的点 ,对一切未标号点 : (1)若在弧 上 则给 标号 ,这里 .此时,点 成为标号而未检查的点. (2)若在弧 上 则给 标号 这里 .此时,点 成为标号而未检查的点. 于是 成为标号且已检查过的点.重复上述步骤,一旦 被标上号,表明得到一条从 到 的增广链 ,转入调整过程. 若所有标号都已经检查过,而标号过程进行不下去时,则算法结束,此时的可行流就是最大流.;2 、调整过程 (1)寻找以 为终点的增广链----(反向追踪法): (2)调整量 (3)流的调整 令 去掉所有的标号,对新的可行流 重新进入标号过程. ;continued;continued;continued;continued;continued;continued;最小费用最大流问题 给定网络 每一弧 上,除了已给容量 外,还给了一个单位流量的费用 (简记为 ).所谓最小费用最大流问题就是要求一个最大流 ,使流的总输送费用最小,即求 ,使