第七章--网络优化模型.pptVIP

第七章 网络优化模型 图与网络的基本概念 最短路径问题 最大流问题 最小费用最大流问题 7.1 图与网络的基本概念 7.1 图与网络的基本概念 7.1 图与网络的基本概念 7.1 图与网络的基本概念 7.1 图与网络的基本概念 7.1 图与网络的基本概念 7.1 图与网络的基本概念 2、逐次逼近算法 可用于网络中有权数为负数的边 7.2 最短路问题 7.2 最短路问题 v1 v3 v4 v2 v5 vt vs w w 6 2 4 3 7 4 3 1 7 9 8 8 7.3 最大流问题 1、流量和容量 有向连通图G = ( V，E ),G的每条边（vi，vj）上有非负数cij称为边的容量，仅有一个入次=0的点vs称为发点，一个出次=0的点vt称为收点，其余点为中间点，这样的网络G称为容量网络，记为G（V,E,C）。 7.3.1 基本概念 7.3 最大流问题 2、可行流和最大流 可行流必须满足的两个条件 （1）容量限定条件： 0≤fij ≤cij （2）流量守恒条件：每一个节点流量平衡 7.3 最大流问题 vj vi fij=5 cij=5 饱和边、不饱和边、流量的间隙 （vi，vj）是饱和的 2、如果fijcij，流从vi到vj的方向是不饱和的 ( vi，vj )是不饱和的 间隙为δ12=c12-f12=5 – 3 = 2 1、如果cij=fij，流从vi到vj的方向是饱和的 vj vi fij=3 cij=5 3、增广链 容量网络G，若u为网络中从vs到vt的一条链，u上的边与u同向的称为前向边，与u反向的称为后向边 f是G的一个可行流， 如果满足： 则称u为从vs到vt的可增广链。 定理7.4 可行流f是最大流的充要条件是不存在从vs到vt的可增广链。 7.3 最大流问题 v1 v3 v4 v2 v5 vt vs w w 6 2 4 3 7 4 3 1 7 9 8 8 4、割集 S =(vs,v3) = (v1,v2,v4,v5,vt) 为G的割集 割集E’的容量=14 v1 v3 v4 v2 v5 vt vs w w 6 2 4 3 7 4 3 1 7 9 8 8 其中S =(vs,v1, v3,v4) = (v2,v5,vt) 为G的割集 (v1,v2), (v3,v4), (v3,v6)的容量和为割集E’的容量=13 其中割集容量最小的称为网络G的最小割集容量(最小割) 定理7.5：（流量—割集定理）设f为网络G=（V,E,C）的任一可行流，S是任一割集，则有W (f)≤ 定理7.6：(最大流-最小割定理)任一个网络G中，从vi到vj的最大流的流量等于分离vi，vj的最小割的容量 7.3 最大流问题 vs v2 v3 v1 v4 v5 vt v6 (5 , 0) (3 , 0) (4 , 0) (3 , 0) (2 , 0) (5 , 0) (3, 0) (4 , 0) (5 , 0) (3 , 0) (2, 0) f f 7.3.2 最大流算法 7.3 最大流问题 vs v2 v3 v1 v4 v5 vt v6 (5 , 0) (3 , 0) (4 , 0) (3 , 0) (2 , 0) (5 , 0) (3, 0) (4 , 0) (5 , 0) (3 , 0) (2, 0) f f 解：从零流开始，寻找增广链 vs→v1→v4→vt 最小容量min { 5，5，4 }=4 (5 , 4) (5 , 4) (4 , 4) vs→v1→v5→vt 最小容量min { 1，3，3 }=1 (5 , 5) (3 , 1) (3, 1) vs→v2→v5→vt 最小容量min { 4，3，2 }=2 (4 , 2) (3 , 2) (3, 3) vs→v2→v6→vt 最小容量min { 2，2，5 }=2 (4 , 4) (2, 2) (5 , 2) vs→v3→v6→vt 最小容量min { 3，2，3 }=2 (3 , 2) (2 , 2) (5 , 4) ∴网络最大流量=11，流量安排如上图 vs v2 v3 v1 v4 v5 vt v6 (5 , 5) (3 , 2) (4 , 2) (3 , 0) (2 , 2) (5 , 2) (3, 3) (4 , 2) (5 , 4) (3 , 3) (2, 2) 从任一可行流开始寻找最大流，采用标号法寻找增广链 (? ,+∞) 解：先给发点标号，即：vs标（ ? ，+∞ ） (vs，v1) fs1 = cs1 = 5 (vs，v2) fs2 =2 cs2 = 4 δs2= 2