网络优化-第6章_最葱麦流问题.pptVIP

网 络 优 化 ;;;定义6.2 对于流网络N=（V，A，L，U，D），其上的一个流(flow) x是指从N的弧集A到实数集合R的一个函数x：A? R, 即对每条弧(i,j) 赋予一个实数 (称为弧(i,j)上的流). 如果流x满足 ;运输网络的特点是只有源或汇，没有中间转运点. 显然，此问题有解的一个必要条件是 ;网络中的流;网络中的流;网络中的流;;当找到一个路流时, 重新定义使得某个节点的供需量从非零成为零, 或者使得某条弧的流量从非零成为零. 当找到一个圈流时, 重新定义使得某条弧的流量从非零成为零. ;;;增广路;;;STEP5. 转STEP3. ;最大流流值为4 ;最大流流值为2*106;该算法是否一定在有限步内终止呢？ 如果弧上的容量可以是无理数，可以举出例子说明标号算法不一定在有限步内终止；并且，这一增广路算法的极限过程得到的流的流值即使收敛，也不一定收敛到最大流 ;;;;; (Capacity-Scaling Algorithm);;布 置 作 业（第1讲）;网 络 优 化 ; - 概论;;;;STEP0. (预处理) 置初始可行流x为零流; 计算精确的距离函数d；令当前节点i=s. ;6.3.2 最短增广路算法 – 性质 ;6.3.2 最短增广路算法 – 性质 ;1;最短增广路算法 – ;最短增广路算法 – ;6.3.3 最短增广路算法 –复杂度分析 ;6.3.3 最短增广路算法 –复杂度分析 ;6.3.3 最短增广路算法 –复杂度分析 ; 容量 全为1 ;定义6.9 流网络N=（s，t, V，A，U）上的一个预流 x 是指从N 的弧集A到实数集合R的一个函数,使得对每个顶点 i 都满足如下条件: ;STEP1.如果残量网络中不存在活跃节点, 结束, 已经得到最优解; 否则继续. ;6.4.1 一般的预流推进算法;6.4.1 一般的预流推进算法;6.4.1 一般的预流推进算法;一般的预流推进算法 – ;一般的预流推进算法 – ;一般的预流推进算法 – ;一般的预流推进算法 – ;一般的预流推进算法 – ;一般的预流推进算法 – ;布 置 作 业;网 络 优 化 ; - 6.5.1 算法; - 6.5.1 算法;最高标号预流推进算法执行非饱和推进的总次数是关键： 标号的修改次数不超过2n2次 ； 每两次相邻的标号修改操作之间对所有节点的检查不超过n次(如算法连续对n个节点的检查而中间没有对任何节点进行距离标号修改,则赢余一定已经达到s或t点,算法求到最大流终止); 每个节点检查执行非饱和推进的次数不超过1次；; ;权函数法 记当前森林中最大活跃点的集合为H,并令?=?i?H ?(i),其中?(i)=max{0,K+1-|D(i)|}, K为一个待定参数. 显然, 0??(i)?K.;(2) 对最大活跃点i，沿当前(允许)弧（i，j）执行一次饱和推进: 推进后，当前弧（i，j）不再是允许弧(因为残留容量为0)，所以从当前森林中退出. 但节点i仍为最大活跃点，同时节点j成为活跃点，因此也可能成为新的最大活跃点. 所以此时?可能增加最多K个单位. ;(4) 在当前森林中增加一条新的当前(允许)弧: 此时, 不会产生任何新的最大活跃节点,而只可能使一些节点的后代集合扩大, 因此可能使某些最大活跃点变成非最大活跃点. 无论如何, ?的值不可能增加. ;最多执行2n/K次非饱和推进的阶段: 所有这类阶段中的非饱和推进的次数之和最多为O(n3/K)次;定义6.10 每条弧上的容量(上界)都是1个单位的网络称为单位容量网络（unit capacity network）. 如果在这种单位容量网络中, 除了源点和汇点以外, 所有其它节点上要么最多只有一条入弧, 要么最多只有一条出弧, 则称这种网络为单位容量简单网络（unit capacity simple network）. ;6.6.1 单位容量网络上的最大流算法;布 置 作 业