[管理学]运筹学第八章.ppt

第八章 图与网络分析 图与网络的基本概念 树 最短路径问题 最大流问题 最小费用流问题 A、B、C、D、E 某公司的 五支球队进行循环赛 组织机构设置图 图与网络的基本概念 v2 v3 v7 v1 v8 v4 v5 v6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 S={v1 ,v4 , v2 , v6 , v7 , v5} P(v3) =8 P(v5) =6 P(v7) =3 P(v6) =3 P(v1)=0 P(v4)=1 P(v2) =2 L23=8 L53=15 L58=10 L78=11 T(v3)=8 T(v8)=10 min {T(v3), T(v8)}=min {8, 10}=8 P(v3) =8 S={v1 ,v4 , v2 , v6 , v7 , v5 , v3} v2 v3 v7 v1 v8 v4 v5 v6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 S={v1 ,v4 , v2 , v6 , v7 , v5 , v3} P(v8) =10 P(v3) =8 P(v5) =6 P(v7) =3 P(v6) =3 P(v1)=0 P(v4)=1 P(v2) =2 L38=14 L58=10 L78=11 T(v8)=10 P(v8) =10 S={v1 ,v4 , v2 , v6 , v7 , v5 , v3 , v8} v2 v3 v7 v1 v8 v4 v5 v6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 S={v1 ,v4 , v2 , v6 , v7 , v5 , v3 , v8} v1到v8的最短路径为{v1 ,v4 , v7 , v5 , v8}，长度为10 P(v8) =10 P(v3) =8 P(v5) =6 P(v7) =3 P(v6) =3 P(v1)=0 P(v4)=1 P(v2) =2 狄克斯托算法（Dijkstra）的适用条件： 1、用于赋权有向图。 对于赋权无向图的处理 2、权数 wij ≥0 v1 v3 v4 v2 v5 vt vs w w 6 2 4 3 7 4 3 1 7 9 8 8 网络最大流问题 定义20：有向连通图G = ( V，E ),G的每条边（vi，vj）上有非负数cij称为边的容量，仅有一个入次=0的点vs称为发点，一个出次=0的点vt称为收点其余点为中间点，这样的网络G称为容量网络，记为G（V,E,C）。 边的流量、可行流 边的容量和流量 容量cij，流量fij 可行流:满足以下条件的流称为可行流 （1）容量限定条件： 0≤fij ≤cij （2）平衡条件：每一个节点流量平衡 一、基本概念 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 v1 v3 v4 v2 v5 vt vs w w 6 2 4 3 7 4 3 1 7 9 8 8 定义21：割集 割集容量 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的最小割集容量(最小割) 定理10:设f为网络G=（V,E,C）的任一可行流,流量为W, 是图G的任一割集,则有W ≤ 定理11：(最大流-最小割定理)任一个网络G中，从vi到vj的最大流的流量等于分离vi，vj的最小割的容量 定义22：容量网络G，若u为网络中从vs到vt的一条链，u上的边与u同向的称为前向边，与u反向的称为后向边 f是G的一个可行流， 如果满足： 则称u为从vs到vt的可增广链。 推论：可行流f是最大流的充要条件是不存在从vs到vt的可增广链。 二、求最大流的增广链法（标号法） vs v2 v3 v1 v4 v5 vt v6 (5 , 0) (3 , 0) (4 , 0) (3 ,