最小费用最大流问题.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