最小费用最大流问题.ppt

最小费用最大流问题,最大流问题 最小费用最大流问题,最大流问题 引 例 基本概念 最大流算法 算 例,Back,continued,Back,引 例 假设某个公路网的每条公路只允许单向行驶，这样的公路网称为单行公路网为了保证畅通，交通部门对每条公路在单位时间内通过的车辆数目要作一个限制问单位时间内最多能有多少辆车从甲地出发经过该公路网到达乙地？ 网络与流 增广链,一、网络与流 一个有向图 称为一个网络其中， 为图的所有顶点集； 为弧集； 为各弧上容量集 在 中指定了两点 ，分别称为发点和收点，其余的点叫中间点定义弧集合 上的一个函数 为网络的一个流,并称 为弧 上的流量，简记为,continued,二、可行流与最大流 一个流称为一个可行流,如果满足以下条件: (1) 容量限制条件:对 (2) 平衡条件: 对中间点:流出量=流入量,即 对于发点 对于收点 式中 称为这个可行流的流量,即发点的净输出量(或收点的净输入量),最大流问题:,三、增广链 1 、给定一个可行流 称 2 、若 是网络中联结发点 和收点 的一条链,定义链的方向是从 到 ,则链上的弧被分为两类:一类是弧的方向与链的方向一致,称为前向弧,前向弧的全体记为 另一类弧与链的方向相反,称为后向弧,后向弧的全体记为 3 、设f是一个可行流, 是从到的一条链,称为一条增广链,如果,四、截集 1 、设 把始点在 ,终点在 中的所有弧构成的集合,记为 2 、给定网络 若点集 被剖分为两个非空集合 使 则弧集 称为分离 和 的截集. 3 、截集 中所有弧的容量之和称为此截集的容量,记为 即,定理 1 可行流f是最大流 不存在关于f的增广链. 定理2 任一个网络 中,从 到 的最大流的流量等于分离 的最小截集的容量.,Back,求最大流的标号法(Ford,Fulkerson) 1 、标号过程 开始:先给 标上 此时 是标号而未检查的点,其余都是未标号点.一般地,取一个标号而未检查的点 ,对一切未标号点 : (1)若在弧 上 则给 标号 ,这里 .此时,点 成为标号而未检查的点. (2)若在弧 上 则给 标号 这里 .此时,点 成为标号而未检查的点. 于是 成为标号且已检查过的点.重复上述步骤,一旦 被标上号,表明得到一条从 到 的增广链 ,转入调整过程. 若所有标号都已经检查过,而标号过程进行不下去时,则算法结束,此时的可行流就是最大流.,2 、调整过程 (1)寻找以 为终点的增广链-(反向追踪法): (2)调整量 (3)流的调整 令 去掉所有的标号,对新的可行流 重新进入标号过程.,Back,continued,Back,算 例 用标号法求右下图所示网络的最大流.弧旁的数是 解:(一)标号过程 1 、首先给 标上 2 、检查 在弧 上 不满足标号条件; 在弧 上 则 的标号为 . 其中,continued,Back,3 、检查 在弧 上 不满足标号条件; 在弧 上 则 的标号为 其中, 4 、检查 在弧 上 则 的标号为 . 其中, 在弧 上 则 的标号为 . 其中,continued,Back,5、在 中任选一个进行检查 . 例如 在弧 上 则 的标号为 其中, 因 有了标号,故转入调整过程.,continued,Back,(二)调整过程 (1)寻找以为终点的增广链-(反向追踪法) (2)调整量,continued,Back,(3)流的调整 去掉所有的标号,对新的可行流重新进入标号过程.,continued,Back,标号过程无法继续下去,算法结束. 此时的可行流即为所求的最大流.最大流量为 最小截集: 其中, 为标号点集合, 为未标号集合.,最小费用最大流问题 给定网络 每一弧 上,除了已给容量 外,还给了一个单位流量的费用 (简记为 ).所谓最小费用最大流问题就是要求一个最大流 ,使流的总输送费用最小,即求 ,使 怎么求解这个问题?,1、定义 增广链 的费用为 结论:若 是流量为 的所有可行流中费用最小者,而 是关于 的所有增广链中费用最小的增广链,则沿 去调整 ,得到的可行流 ,就是流量为 的所有可行流中的最小费用流.这样,当 是最大流时,它即为所求的最小费用最大流. 2、定义 网络D的一个可行流为 ,构造其赋权有向图,记为 如下： 1) 的顶点集是D的顶点集; 2)把D中的每一条弧 变成两个相反方向的弧 和 .定义 中弧的权为:,在网络D中求关于f的最小费用增广链等价于在 中求从 到 的最短路. 最小费用最大流算法 开始:取 为初始可行流. (1) 在第K-1步:最小费用流为 ,构造赋权有向图 并在 中,寻求从 到 的最短路. 1)若不存在最短路,则 就是最小费用最大流. 2)若存在最短路,则在原网络D中得相应的增广链 ,在增广链 上对 进行调整.调整量为 令 则得到新的可行流 .转(1).,算 例 以下图为例,求最小费用最大流.弧旁数字为 (1)取 为初始可行流. (2)构造赋权有向图 ,并求出从 到 的最短路 ,如图1所示(双箭头). (3)在原网络 中,与这条最短路相应的增广链 (4)在 上进行调整, 得 如图2所示.按照上述算法依次得 ,流量依次为5,7,10,11;构造相应的赋权有向图为 ,见图39.,图1,图2,图3,图4,图5,图6,图7,图8,图9,Back,