14-图与网络规划.ppt

第十章图与网络优化 主要内容 图论的基本概念最小支撑树问题最短路问题最大流问题最小费用最大流问题 一 基本概念与定理 1 容量网络与流 定义给定一个有向图D V A 在V中指定一个发点vs 和一个收点vt 其余点称中间点 对任意弧 vi vj A 有权Cij 0 称为弧的容量 称D为一个容量网络 记为 D V A C 如 a 图是一个容量网络 弧旁数字 容量 第四节网络最大流问题 网络D中的任一条弧 vi vj 的流量记为f vi vj 简记fij 显然 fij Cij 一系列流量的集合f f vi vj 构成网络D上的流 运输方案 弧旁数字 流量 例连接某产品产地v1和销地v6的交通网如下 弧 vi vj 从vi到vj的运输路线 弧旁数字 这条运输路线的最大通过能力 第四节网络最大流问题 目标 制定一个运输方案 使从v1到v6的产品运量最大 2 可行流与最大流 满足下述条件的流f称为可行流 1 容量限制条件 对每一弧 vi vj A0 fij Cij 2 平衡条件 对中间点vj j s t 有 V f 称为可行流f的流量 即发点的净输出量 对发点 对收点 0 0 如 b 图是网络上的一个可行流 运输方案 弧旁数字 流量 可行流总是存在的 例如所有弧的流量fij 0 零流 所谓最大流问题就是寻找流量最大的可行流 3 增广链 对可行流f fij 的弧有 非饱和弧 0 fij Cij 饱和弧 fij Cij 非零流弧 0 fij Cij 零流弧 fij 0 链的方向 若 是联结vs和vt的一条链 定义链的方向是从vs到vt 前向弧 与链的方向一致的弧 前向弧全体记为 后向弧 与链的方向相反的弧 后向弧全体记为 v1 v2 v3 v4 v5 v6 v1 v2 v2 v3 v3 v4 v5 v6 v5 v4 定义3设f是一个可行流 是从vs到vt的一条链 若 满足下列条件 称之为 关于可行流f的 一条增广链 vi vj 0 fij Cij vi vj 0 fij Cij 前向弧是非饱和弧 后向弧是非零流弧 4 截集与截量 1 v4 v5 v6 截集为红色弧集 由图可见 截集不是唯一的 每个截集相当于从发点vs到收点vt的必经之路 去掉截集所有的弧 就不存在从发点vs到收点vt的路 C V1 V1 5 3 5 6 19 不难证明 任何一个可行流的流量V f 都不会超过任一截集的容量 即 定理1最大流最小截定理 任一个网络D中 从vs到vt的最大流的流量等于分离vs vt的最小截集的容量 最小截集的容量是网络中的瓶颈容量 1 从一个可行流f开始 寻找关于f的增广链 2 如果不存在关于f的增广链 可行流f就是最大流f 3 如果存在关于f的增广链 则以适当的调整量 对可行流f进行调整 得到一个流量更大的可行流 不断重复调整过程 直到不再存在增广链时 就得到了最大流 由定理2可得到寻找最大流的方法 定理2可行流f 是最大流不存在关于f 的增广链 二 寻求最大流的标号法 从任一个可行流f出发 若网络中没有给定f 则从零流开始 一 标号过程 通过标号来寻找增广链 每个标号点vj的标号包含两部分 vi l vj 第一个标号vi表示标号点的前一点 以便找出增广链 第二个标号l vj 是为了确定增广链 的调整量 用的 标号过程首先给vs标号 0 此时vs是未检查的标号点 其余各点都是未标号点 取一个未检查的标号点vi进行检查 给与vi相邻的所有未标号点vj标号 1 如果在前向弧 vi vj 上 有fij0 则给vj标号 vi l vj 其中l vj min l vi fji 此时新标号点vj成为未检查的标号点 至此 点vi成为已检查过的标号点 重复标号过程 一旦vt被标号 即得到一条从vs到vt的增广链 转入调整过程 二 调整过程 找出增广链 并沿增广链 调整流量 1 找增广链 从vt开始 反向追踪 找出增广链 如vt的第一个标号为k 或 k 则得到前向弧 vk vt 或后向弧 vt vk 检查vk的第一个标号 若为i 或 i 又得到前向弧 vi vk 或后向弧 vk vi 再检查vi的第一个标号 依此找下去 直到vs 被找出的弧构成了增广链 2 调整流量 令调整量 l vt 沿增广链 构造新的可行流f 去掉所有的标号 对新的可行流f f ij 重新进行标号 重复标号过程和调整过程 直到标号过程进行不下去且vt未获得标号为止 说明当前可行流不存在增广链 即得到了最大的可行流 例用标号法求下图网络的最大流 弧旁的数字是 Cij fij 解 一 标号过程 1 给vs标号 0 2 检查vs 在vs的前向弧 vs v1 上 fs1 1 Cs1 5 fs1 Cs1 给v1标号 s l v1 其中 0 未检查的标号点为vs s 4 继续检查vs 在vs的前向弧 vs v2 上 fs2 Cs2 3 不满足标号条件 此时 未检查的标号点为v1 3 检查v1 在v1的后向弧 v2 v1 上 f21 0 给v2标号 1 l v2 这里 继续检查v1 在v1的前向弧 v1 v3 上 f13 C13 2 不满足标号条件 此时 未检查的标号点为v2 1 1 4 检查v2 在v2的后向弧 v3 v2 上 f32 1 0 给v3标号 2 l v3 这里 2 1 2 1 继续检查v2 在v2的前向弧 v2 v4 上 f24 C24 给v4标号 2 l v4 这里 此时 未检查的标号点为v3和v4 在v3和v4中可任选一点进行检查 不妨检查v3 2 1 5 检查v3 在v3的前向弧 v3 vt 上 f3t 1 C3t 2 f3t C3t 给vt标号 3 l vt 这里 至此 vt得到标号 转入调整过程 3 1 2 1 二 调整过程 从vt开始逆向追踪 找到增广链 vs v1 v2 v3 vt l vt 1 在 上进行流量 1的调整 得可行流f 如右图所示 去掉各点标号 从vs开始 重新标号 点v1 标号过程无法进行 所以f 即为最大流 vs的净输出量 最大流量V f 3 2 5 vt的净输入量与此同时 可找到最小截集 V1 V1 截集 V1 V1 vs v2 v1 v3 最大流量V f 最小截量C V1 V1 5 标号点集V1 vs v1 未标号点集V1 v2 v3 v4 vt 第五节最小费用最大流问题 网络D V A C 每一弧 vi vj A 给出 vi vj 上单位流量的费用b vi vj 0 简记bij 一 求解原理 设对可行流f存在增广链 当沿 以 1调整f 得新的可行流f 时 显然V f V f 1 两流的费用之差 b f b f 为增广链 的费用 b f b f 例 vs v1 v2 v3 v4 v5 vt 3 5 4 1 7 6 增广链 的费用 3 4 1 6 5 7 2 不同的增广链的费用是不同的 求最小费用最大流的原理 在网络D中 若f是流量为V f 的费用最小的可行流 而 是关于f的所有增广链中费用最小的增广链 则沿费用最小的增广链 以 去调整f 得到新可行流f f 就是流量为V f 的费用最小的可行流 当f 是最大流时 f 就是流量最大的最小费用流 即最小费用最大流 由于单位流量的费用bij 0 所以流量 0的可行流f必是费用最小的可行流 这样剩下的问题就是去寻找关于f的费用最小的增广链 为此 需要根据网络D构造一个赋权有向图W f 构造赋权有向图W f 方法如下 它的顶点就是网络D的顶点 W f 中弧及其权wij按弧 vi vj 在D中的情形分为 则构造同向弧 vi vj 且wij bij 则构造反向弧 vj vi 且wji bij 若弧 vi vj 的最小费用流量fij 0 零流弧 若弧 vi vj 的最小费用流量fij cij 饱和弧 费用 若弧 vi vj 的最小费用流量0 fij cij 非饱和弧 则同时构造同向弧 vi vj 且wij bij 及反向弧 vj vi 且wji bij 赋权有向图W f 的权是单位流量的费用 故W f 成为流f的费用网络图 如果把费用理解为长度 可知这实际是一个在赋权有向图W f 中求最短路的问题 寻求关于费用最小的可行流f的费用最小的增广链 等价于在赋权有向图W f 中寻求从vs到vt的一个最小费用链 二 最小费用最大流算法 第2步 构造赋权有向图W fk 第3步 在W fk 中 寻找vs到vt的最短路 1 若不存在最短路 即最短路路长是 则fk就是最小费用最大流 2 若存在最短路 则此最短路即为原网络D中相应的最小费用增广链 转入第4步 第4步 在增广链 上对可行流fk进行调整 调整量 为 min 令 得新的可行流fk 1 令k k 1 返回第2步 例求下图所示网络的最小费用最大流 弧旁数字为 bij cij 解 1 取初始可行流f0 0 2 按算法要求构造长度网络W f0 求出从vs到vt的最短路 3 在原网络D中 与这条最短路对应的增广链为 vs v2 v1 vt 3 在原网络D中