最大流问题数学建模资料

《最大流问题数学建模资料》由会员分享，可在线阅读，更多相关《最大流问题数学建模资料（65页珍藏版）》请在金锄头文库上搜索。

1、1 网络优化 NetworkOptimization 清华大学数学科学系谢金星办公室 理科楼1308 电话 62787812 Email jxie 清华大学课号 40420213 本 70420133 研 第6章最大流问题 MaximumFlowProblem 第1讲 2 许多实际问题都可以转化为最大流问题 S T 最大流问题的例子 公路交通网络 车流流量 3 定义6 1在有向图G V A 上定义如下的权函数 1 L A R为弧上的权函数 弧 i j 对应的权L i j 记为lij 称为弧 i j 的容量下界 lowerbound 2 U A R为弧上的权函数 弧 i j 对应的权U i j

2、记为uij 称为弧 i j 的容量上界 或直接称为容量 capacity 3 D V R为顶点上的权函数 节点i对应的权D i 记为di 称为顶点i的供需量 supply demand 此时网络可称为流网络 FlowNetwork 一般仍简称为网络 记为N V A L U D 6 1 1网络中的流 di 0 供应点 supplynode 或源 source 起始点或发货点di 0 需求点 demandnode 或汇 sink 终止点或吸收点di 0 转运点 transshipmentnode 或平衡点 中间点 4 定义6 2对于流网络N V A L U D 其上的一个流 flow x是指从N的

3、弧集A到实数集合R的一个函数x A R 即对每条弧 i j 赋予一个实数 称为弧 i j 上的流 如果流x满足 存在可行流的必要条件 则称x为可行流 feasibleflow 至少存在一个可行流的流网络称为可行网络 feasiblenetwork 如果流x只满足容量约束 6 2 但不一定满足流量守恒条件 6 1 则称x为伪流 pseudoflow 或容量可行流 流量守恒 平衡条件 容量约束 可行条件 网络中的流 一般可以把L 0的流网络转化为L 0的流网络进行研究 思考 除非特别说明 以后我们总是假设L 0 网络简记为N V A U D 5 运输网络的特点是只有源或汇 没有中间转运点 显然 此

4、问题有解的一个必要条件是 网络中的流 例 运输网络和运输计划 有一批货物从货源地运往目的地 假设货源集合为S 目的地集合为T 货源i可提供的货物数量为ai个单位 目的地j对货物的需求量为bj个单位 以 S T 为节点集作完全二部图 以ai bj为节点上的供需量 通过每条弧的运输量没有限制 非负即可 一个运输计划就相当于该网络中的一个流 6 网络中的流 例6 1有向网络中 令所有弧上的容量下界为0 容量 上界 为1 并令节点s的供需量为1 节点t的供需量为 1 从s到t的一条有向路正好对应于网络中的一个可行流x 当xij 1时 表示弧 i j 位于s t路上 当xij 0时 表示弧 i j 不在

5、s t路上 思考 网络中的任意一个可行流是否一定对应于一条有向路 7 网络中的流 定义6 3在流网络N V A U D 中 对于流x 如果某条弧 i j 上的流量等于其容量 则称该弧为饱和弧 saturatedarc 如果某条弧 i j 上的流量为0 则称该弧为空弧 voidarc 如果所有弧均为空弧 即则称x为零流 否则为非零流 8 网络中的流 定义6 4对于给定流网络N V A U D 中的流x A R 如果N中存在一条有向路P 使得 则称x为路流 Pathflow v称为该路流的流值 流量 v 0时 称该路流为零路流 否则称为非零路流 如果N中存在一个有向圈W 使得 则称x为圈流 Cyc

6、leflow v称为该圈流的流值 流量 v 0时 称该圈流为零圈流 否则称为非零圈流 5 9 定理6 1在网络N V A U D 中 任何一个可行流可以表示为若干个路流和若干个圈流之和 且这些路流和圈流满足下列性质 1 非零路流对应的有向路从一个源点指向一个汇点 2 至多有m n个路流和圈流为非零流 且其中至多有m个圈流为非零流 流的分解定理 FlowDecompositionTheorem 证明 构造性 记可行流为x 设i0是网络中的一个源点 则存在弧 i0 i1 使得 0 在一个无源无汇的流网络中 一个可行流称为可行循环流 推论一个可行循环流一定可以表示为至多m个非零圈流之和 如果i1是一

7、个汇点 则找到了从源点指向汇点的一条有向路 否则从i1出发重复上述过程 直到找到一个汇点或再次遇到前面经过的某个顶点时为止 即直到下列两种情况之一出现为止 10 当找到一个路流时 重新定义使得某个节点的供需量从非零成为零 或者使得某条弧的流量从非零成为零 当找到一个圈流时 重新定义使得某条弧的流量从非零成为零 对新网络 重复上述过程 直到所有顶点变成为转运点 平衡点 然后 找到一个至少有一条出弧上的流量为正的顶点 继续重复上述过程 这时只有情形 b 会出现 即一定获得一个非零圈流 重复上述过程 直到重新定义的流x成为零流为止 b 找到一个有向圈W 此时 定义 a 找到一条从一个源点i0指向一个

8、汇点ik的有向路P 定义 上述过程找到路流和圈流的次数之和不会多于m n次 且其中找到圈流的次数不会多于m次 11 单源单汇的网络 可行流x的流量 或流值 为v v x ds dt如果我们并不给定ds和dt 则网络一般记为N s t V A U 容量可行且转运点流量守恒的流称为s t可行流 有时为了方便也称为可行流 最大流问题 MaximumFlowProblem 就是在N s t V A U 中找到流值最大的s t可行流 即最大流 6 1 2最大流问题的数学描述 定理6 2 整流定理 最大流问题所对应的约束矩阵是全么模矩阵 若所有弧容量均为正整数 则问题存在最优整数解 12 引理6 1任意一

9、个s t可行流流值不超过任意一个s t割容量 6 1 3增广路定理 定义6 5设 S T 是网络N s t V A U 中给定的一个割 且s S t T 则称割 S T 为s t割 s t割 S T 中的弧 i j i S j T 称为割的前向弧 弧 i j j S i T 称为割的反向弧 s t割 S T 的容量定义为前向弧的容量之和 记为一个网络中容量最小的s t割称为最小割 13 增广路 引理6 2如果对于一个可行流存在增广路 则该可行流不是最大流 定义6 6设x是流网络N s t V A U 中给定的可行流 P是一条s t路 则P中满足下列两个条件之一的弧 i j 称为增广弧 augm

10、entingarc 1 弧 i j 是P的前向弧且为不饱和弧 或 2 弧 i j 是P的反向弧且为非空弧 如果P中的弧都是增广弧 则称P为关于流x的增广路 简称增广路 augmentingpath 这一过程称为x关于P的增广 augmentation 14 证明必要性可以由前面的引理直接得到 下面证明充分性 定理6 3 增广路定理 一个可行流为最大流的充要条件是不存在增广路 增广路定理 假设流网络N s t V A U 中不存在关于可行流x的增广路 记网络中从s出发沿增广弧可以到达的节点集合为S 令T V S 则s S t T 即 S T 为s t割 并且 对于A中的任意弧 i j 如果它是该

11、s t割的前向弧 则 如果它是该s t割的后向弧 则 0 引理6 1证明中的中间结果 因此 S T 为最小割 x为最大流 定理6 4 最大流最小割定理 最大流的流值等于最小割的容量 15 6 2增广路算法 6 2 1Ford Fulkerson标号算法 基本思想 从任何一个可行流开始 沿增广路对流进行增广 直到网络中不存在增广路为止 问题的关键在于如何有效地找到增广路 并保证算法在有限次增广后一定终止 基本思想 标号过程来寻找网络中的增广路pred j 节点j在可能的增广路中的前一个节点 maxf j 沿该可能的增广路到该节点为止可以增广的最大流量 LIST 记录可能的增广路上的节点 16 S

12、TEP5 转STEP3 STEP3 如果LIST 且maxf t 0 继续下一步 否则 3a 如果t已经有标号 即maxf t 0 则找到了一条增广路 沿该增广路对流x进行增广 增广的流量为maxf t 增广路可以根据pred回溯方便地得到 转STEP1 3b 如果t没有标号 即LIST 且maxf t 0 转STEP1 STEP4 从LIST中移走一个节点i 寻找从节点i出发的所有可能的增广弧 4a 对非饱和前向弧 i j 若节点j没有标号 即pred j 0 则对j进行标号 即令maxf j min maxf i uij xij pred j i 并将j加入LIST中 4b 对非空反向弧

13、j i 若节点j没有标号 即pred j 0 则对j进行标号 令maxf j min maxf i xji pred j i 并将j加入LIST中 STEP1 若maxf t 0 继续下一步 否则结束 STEP0 置初始可行流x 如零流 对节点t标号 即令maxf t 任意正值 如1 STEP2 取消所有节点j V的标号 即令maxf j 0 pred j 0 令LIST s 对节点s标号 即令maxf s 充分大的正值 17 最大流流值为4 Ford Fulkerson标号算法 例 uij xij 18 最大流流值为2 106 Ford Fulkerson标号算法 例 uij xij 19

14、该算法是否一定在有限步内终止呢 如果弧上的容量可以是无理数 可以举出例子说明标号算法不一定在有限步内终止 并且 这一增广路算法的极限过程得到的流的流值即使收敛 也不一定收敛到最大流 Ford Fulkerson标号算法 标号算法终止时 网络中一定不再含有增广路 如果所有弧上的容量都是正整数 根据整流定理 最大流v也是整数 实际上 由于割 s V s 中前向弧的条数最多为n条 因此最大流v的上界为nU U表示网络中弧上的最大容量 由于每次增广至少使得流值增加1个单位 因此增广的次数不会超过v次 算法一定在有限步内终止 此外 由于每次增广最多需要对所有弧检查一遍 因此算法的复杂度为O mv 或表示

15、为O mnU 伪多项式时间算法 而不是多项式时间算法 20 定义6 7对网络N s t V A U 中给定的s t可行流x 网络N关于流x的残量网络N x s t V A x U x 其中A x U x 定义如下 residualnetwork 又常称为增量网络或辅助网络 6 2 2残量网络 讨论算法复杂度时 假定 弧 i j A时 弧 j i A 并假定在残量网络中A x A 也就是说弧的条数和弧集合都不变 这只要允许容量为0的弧仍然保留在网络中就可以了 命题 若v 是原网络的最大流 则残量网络N x 中最大流为v v x 其中称 uij x 为弧 i j 上的残留容量 residualca

16、pacity 21 残量网络 例 uij xij N x 中的s t有向路P 对应于原网络N中的一条增广路 直接称残量网络中的s t有向路为增广路 沿P可以增广的最大流量称为P的残留容量 22 Ford Fulkerson标号算法每次只是在所有增广路中随便地找一条进行增广 因此增广的次数可能很多 一个自然的想法是 如果每次都找一条增广容量最大的增广路 则总的增广次数应当减少 这样的算法称为最大容量增广路算法 6 2 3最大容量增广路算法 23 最大容量增广路算法 复杂性分析 证明 根据流的分解定理 N x 中可以找到不超过m条从源点到汇点的有向路 增广路 使得其残留容量之和为v v x 现在考虑从可行流x开始的连续2m次最大容量增广 1 如果每次增广的流量都不小于 v v x 2m 则2m次增广后一定已经达到了最大流 2 某次增广的流量小于 v v x 2m 即每经过连续2m次最大容量增广 残量网络中的最大容量增广路的残留容量至少下降一半 命题 N x 中最大容量增广路的残留容量不小于 v v x m 可见 最大容量增广路算法将总的增广次数从Ford Fulkerson标号算法的O n