图与网络分析物流运筹学ppt课件

1、图与网络分析在物流系统中的运用 (Graph Theory and Network Analysis)图与网络的根本知识最短路问题 树及最小树问题BDACABCD哥尼斯堡七空桥一笔画问题运用及处理的问题配送运输规划问题物流车辆规划调度系统物流园区规划一、 图与网络的根本知识一、图与网络的根本概念 EADCB 1、一个图是由点和连线组成。连线可带箭头，也可不带，前者叫弧，后者叫边一个图是由点集 和 中元素的无序对的一个集合 构成的二元组，记为G =(V，E)，其中 V 中的元素 叫做顶点，V 表示图 G 的点集合；E 中的元素 叫做边，E 表示图 G 的边集合。v1v2v3v4v5v6e1e2e

2、3e4e5e6e7e8e9e10例图1 2、假设一个图是由点和边所构成的，那么称其为无向图，记作G = (V，E)，衔接点的边记作vi , vj，或者vj , vi。 3、假设一个图是由点和弧所构成的，那么称它为有向图，记作D=(V, A)，其中V 表示有向图D 的点集合，A 表示有向图D 的弧集合。一条方向从vi指向vj 的弧，记作(vi , vj)。v4v6v1v2v3v5V = v1 , v2 , v3 , v4 , v5 , v6 ，A = (v1 , v3 ) , (v2 , v1) , (v2 , v3 ) ,(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 )

3、 , (v5 , v4 ) , (v5 , v6 ) 图2 4、一条边的两个端点是一样的,那么称为这条边是环。 5、假设两个端点之间有两条以上的边，那么称为它们为多重边。 6、一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。 7、每一对顶点间都有边相连的无向简单图称为完全图。 有向完全图那么是指恣意两个顶点之间有且仅有一条有向边的简单图。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10 度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。 8、以点v为端点的边的个数称为点v 的度次，记作 。图中

4、 d(v1)= 4，d(v6)= 4环计两度 定理1 一切顶点度数之和等于一切边数的2倍。 定理2 在任一图中，奇点的个数必为偶数。 一切顶点的入次之和等于一切顶点的出次之和。 有向图中，以 vi 为始点的边数称为点vi的出次，用 表示 ；以 vi 为终点的边数称为点vi 的入次，用 表示；vi 点的出次和入次之和就是该点的次。 9、设 G1= V1 , E1 ，G2 = V2 ,E2 假设 V2 V1 , E2 E1 称 G2 是G1 的子图；假设 V2 = V1 , E2 E1 称 G2 是 G1 的部分图或支撑子图。 v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10

5、e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图 在实践运用中，给定一个图G=V，E或有向图D=V，A，在V中指定两个点，一个称为始点或发点，记作v1 ，一个称为终点或收点，记作vn ，其他的点称为中间点。对每一条弧 ，对应一个数 ，称为弧上的“权。通常把这种赋权的图称为网络。 10、由两两相邻的点及其相关联的边构成的点边序列称为链。 如:v0 ，e1，v1，e2，v2，e3 ， v3 ,vn-1 , en ， vn，记作 v0 ， v1 ， v2， v3 , , vn-1 ， vn ， e3v1v2v3v4v

6、5v6e7e8e1e2e4e5e6e9e10 11、图中恣意两点之间均至少有一条通路，那么称此图为连通图，否那么称为不连通图。 其链长为 n ，其中 v0 ，vn 分别称为链的起点和终点 。假设链中所含的边均不一样，那么称此链为简单链；所含的点均不一样的链称为初等链 , 也称通路。二、 图的矩阵表示对于网络赋权图G=V，E，其中边有权 ，构造矩阵 ，其中：称矩阵A为网络G的权矩阵。 设图G=V，E中顶点的个数为n，构造一个矩阵 ，其中： 称矩阵A为网络G的邻接矩阵。 例权矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437问题图顶点、边、有限图、无限图无向图、有向图、环、多重边多重

7、图、简单图、完全图、有向完全图、二部图顶点的次、出次、入次、悬挂点、孤立点、奇点、偶点子图、生成子图支撑图、网络赋权图链、初等链、圈、初等圈、回路、连通图图的矩阵表示、邻接矩阵欧拉道路、欧拉回路、中国邮路问题树的概念树、树叶、分枝点数的性质生成子图、生成树、树枝、弦最小生成树避圈法、破圈法有向树、根树、叶、分枝点、叉树 二、 树及最小树问题 知有六个城市，它们之间 要架设线，要求恣意两个城市均可以相互通话，并且线的总长度最短。 v1v2v3v4v5v6 1、一个连通的无圈的无向图叫做树。 树中次为1的点称为树叶，次大于1的点称为分支点。 树 的性质： 1树必连通，但无回路圈。 2n 个顶点的树

8、必有n-1 条边。 3树 中恣意两个顶点之间，恰有且仅有一条链初等链。 4树 连通，但去掉任一条边， 必变为不连通。 5 树 无回路圈，但不相邻的两个点之间加一条边，恰得到一个回路圈。v1v2v3v4v5v6 2、 设图 是图G=(V , E )的一支撑子图，假设图 是一个树,那么称K 是G 的一个生成树支撑树，或简称为图G 的树。图G中属于生成树的边称为树枝，不在生成树中的边称为弦。一个图G 有生成树的充要条件是G 是连通图。 v1v2v3v4v5v1v2v3v4v5用避圈法求出以下图的一个生成树。 v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1

9、v2v3v4v5e1e2e3e4e5e6e7e8一破圈法二避圈法 在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与e1，e2不构成圈的边e3。普通设已有e1，e2，ek，找一条与e1，e2，ek中任何一些边不构成圈的边ek+1，反复这个过程，直到不能进展为止。v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v53、最小生成树问题 假设图 是图G的一个生成树，那么称E1上一切边的权的和为生成树T 的权，记作S(T)。假设图G的生成树T* 的权S(T*)，在G 的一切生成树T 中的权最小，即那么称T*是G 的最小生成树。 某六个城市

10、之间的道路网如图 所示，要求沿着知长度的道路结合六个城市的线网，使线的总长度最短。 v1v2v3v4v5v66515723445v1v2v3v4v5v612344v1v2v3v4v514231352 最短路的普通提法为：设 为连通图，图中各边 有权 表示 之间没有边，为图中恣意两点，求一条路 ，使它为从 到 的一切路中总权最短。即： 最小。(一)、 狄克斯屈拉(Dijkstra)算法适用于wij0，给出了从vs到恣意一个点vj的最短路。三 、最短路问题算法步骤：1.给始点vs以P标号 ，这表示从vs到 vs的最短间隔为0，其他节点均给T标号， 。2.设节点 vi 为刚得到P标号的点，思索点vj

11、，其中 ，且vj为T标号。对vj的T标号进展如下修正：3.比较一切具有T标号的节点，把最小者改为P标号，即： 当存在两个以上最小者时，可同时改为P标号。假设全部节点均为P标号，那么停顿，否那么用vk替代vi，前往步骤2。例一、 用Dijkstra算法求以下图从v1到v6的最短路。 v1v2v3v4v6v5352242421 解 1首先给v1以P标号，给其他一切点T标号。234v1v2v3v4v6v53522424215678910反向追踪得v1到v6的最短路为：237184566134105275934682求从1到8的最短途径237184566134105275934682X=1, w1=0

12、min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4, p4=1p4=1p1=0237184566134105275934682X=1,4min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4, p2=2p1=0p4=1p2=2237184566134105275934682X=1,2,4min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6, p6=3p2=2p4=1p1=0p6=323718456613410

13、5275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7, p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X=1,2,4,6,7min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7, p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X=1,2,4,6,7min c23,c53,c58,c78=min

14、2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7, p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X=1,2,3,4,6,7min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8, p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X=1,2,3,4,6,7,81到8的最短途径为1，4，7，5，8，长度为10。p2=2p4=1p1=0p6

15、=3p7=3p5=6p3=8p8=10求从V1 到 V8 的最短道路。 V1V2V3V4V5V6V7V8 P=0T=+T=+T=+T=+T=+T=+T=+P=T=3T=+T=7T=+T=+T=+T=+T=6T=7P=T=5T=+T=+T=+P=T=6T=6T=8T=+T=+P=T=6T=8T=9T=12P=T=8T=10T=10P=T=9T=11再无其它T 标号，所以 T(V8)=P(V8)=10; min L()=10P=T=10 由此看到，此方法不仅求出了从V1 到 V8 的最短路长，同时也求出了从V1 到 恣意一点 的最短路长。将从V1 到 任一点的最短路权标在图上，即可求出从V1 到

16、任一点的最短道路。本例中V1 到 V8 的最短道路是： v1 v2 v5 v6 v8 623121641036234210二、 逐次逼近法算法的根本思绪与步骤：首先设任一点vi到任一点vj都有一条弧。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。那么v1到vi的这条路必然也是v1到vi的一切路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，那么有以下方程： 开场时，令 即用v1到vj的直接间隔做初始解。从第二步起，运用递推公式：求 ，当进展到第t步，假设出现那么停顿计算， 即为v1到各点的最短路长。例二、18v1v2

17、v3v4v52635135211211v6v7v837v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v48023-7-7-7v5-101-3-3v61017-1-1-1v7-105-5-5v8-3-5066求图中v1到各点的最短路18v1v2v3v4v52635135211211v6v7v8370，0 v3 ，-5 v1 ，-2 v3 ，-7 v2 ，-3 v4 ，-5 v3 ，-1 v6 ，6例三、求：5年内，哪些年初购置新设备，使5年内的总费用最小。 解：1分析：可行的购置方案更新方案是很多

18、的， 如： 1 每年购置一台新的，那么对应的费用为： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年购置新的，不断用到第五年年底，那么总费用为： 11+5+6+8+11+18 = 59 显然不同的方案对应不同的费用。 第i年度 1 2 3 4 5购置费 11 11 12 12 13设备役龄0-1 1-2 2-3 3-4 4-5维修费用 5 6 8 11 18 2方法：将此问题用一个赋权有向图来描画，然后求这个赋权有向图的最短路。 求解步骤： 1画赋权有向图： 设 Vi 表示第i年初，(Vi ,Vj )表示第i 年初购买新设备用到第j年初j-1年底，而Wi j 表示相

19、应费用，那么5年的一个更新方案相当于从V1 到V6的一条路。 2求解 标号法 W12 =11+5=16W13 =11+5+6=22W14 =11+5+6+8=30W15 =11+5+6+8+11=41W16 =11+5+6+8+11+18=59 W23 =11+5=16 W24 =11+5+6=22W25 =11+5+6+8=30 W26 =11+5+6+8+11=41 W45 =12+5=17 W46 =12+5+6=23W56 =13+5=18 W34 =12+5=17W35 =12+5+6=23W36 =12+5+6+8=31 例四、 某工厂运用一种设备，这种设备在一定的年限内随着时间的

20、推移逐渐损坏。所以工厂在每年年初都要决议设备能否更新。假设购置设备，每年需支付购置费用；假设继续运用旧设备，需求支付维修与运转费用，而且随着设备的老化会逐年添加。方案期五年内中每年的购置费、维修费与运转费如表所示，工厂要制定今后五年设备更新方案，问采用何种方案才干使包括购置费、维修费与运转费在内的总费用最小。 年份12345购置费1820212324使用年数0112233445维修费57121825年份12345购置费1820212324使用年数0112233445维修费5712182528v1v2v3v4v5v62325262930426085324462334530四、 最大流问题一、 根

21、本概念1、设一个赋权有向图D=V, E,在V中指定一个发点vs和一个收点vt ,其它的点叫做中间点。对于D中的每一个弧vi , vjE ,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=V，E，C。网络D上的流，是指定义在弧集合E上的一个函数其中f(vi ,vj) =fij 叫做弧(vi，vj)上的流量。 2、称满足以下条件的流为可行流：1容量条件：对于每一个弧vi ,vjE有 0 fij cij 。 2平衡条件：对于发点vs，有对于收点vt ，有对于中间点，有可行流中 fijcij 的弧叫做饱和弧，fijcij的弧叫做非饱和弧。fij0 的弧为非零流弧

22、，fij0 的弧叫做零流弧。 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1) 图中 为零流弧，其他为非饱和弧。 3、容量网络G，假设 为网络中从vs到vt的一条链，给 定向为从vs到vt， 上的弧凡与 方向一样的称为前向弧，凡与 方向相反的称为后向弧，其集合分别用 和 表示。f 是一个可行流，假设满足： 那么称 为从vs到vt 的关于f 的一条增广链。 推论 可行流f 是最大流的充分必要条件是不存在从vs到vt 的关于f 的一条可增广链。 即 中的每一条弧都是非饱和弧即 中的每一条弧都是非零流弧 13 (5)9 (3)

23、4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)是一个增广链显然图中增广链不止一条 4、容量网络G =V，E，C，vs为始点，vt为终点。假设把V分成两个非空集合 使 ，那么一切始点属于S，而终点属于 的弧的集合，称为由S决议的截集,记作 。截集 中一切弧的容量之和，称为这个截集的容量，记为 。 vsv1v2v4v3vt374556378S 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)设 ，那么截集为容量为24 13 (5)9 (3)4 (1)5 (3)6(3)5

24、(2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)设 ，那么截集为容量为20二 求最大流的标号法 标号过程：1 给发点vs 标号0，+。2 取一个已标号的点vi，对于vi一切未标号的邻接点vj 按以下规那么处置：1假设边 ，且 ，那么给vj 标号 ，其中：2假设边 ，且 ，那么给vj 标号 ，其中： 3反复步骤2，直到vt被标号或标号过程无法进展下去，那么标号终了。假设vt被标号，那么存在一条增广链，转调整过程；假设vt未被标号，而标号过程无法进展下去，这时的可行流就是最大流。调整过程设1令 2去掉一切标号，回到第一步，对可行流重新标号。 求以下图所示网络中的最大流，弧旁数为

25、(1 ,1)v2v1v4v3vsvt(3 , 3)(5 , 1)(1 , 1)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,1)(1 ,1)v2v1v4v3vsvt(3 , 3)(5 , 1)(1 , 1)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,1)0，+-v1, 1+ vs , 4-v2 ，1+v2，1(+ v3 ，1)(1 ,0)v2v1v4v3vsvt(3 , 3)(5 , 2)(1 , 0)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,2)(1 ,0)v2v1v4v3vsvt(3 , 3)(5 , 2)(1 , 0)(4 ,3)(2 , 2)(

26、3 ,0)(5 ,3)(2 ,2)0，+ vs , 3最小截集 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1) 13 (11)9 (9)4 (0)5 (5)6(6)5 (5)5 (4)5 (4)4 (4)4 (3)9 (9)10 (7)截集1截集2最小截量为：9+6+5=20707070501301001501301501505020505012030100100 120 230 150 200 第五节 最小费用最大流问题定义8.17 知网络G =V，E，C，d，f是G上的一个可行流， 为一条从vs到vt的增广链， 称

27、为链的费用。 假设 * 是从vs到vt的增广链中费用最小的增广链，那么称 * 是最小费用增广链。结论：假设可行流 f在流量为W(f )的一切可行流中的费用最小，并且 *是关于f 的一切增广链中的费用最小的增广链，那么沿增广链 *调整可行流f，得到的新可行流f *也是流量为W(f*)的一切可行流中的最小费用流。当f * 是最大流时，就是最小费用最大流。 寻觅关于f 的最小费用增广链： 构造一个关于f 的赋权有向图L(f ) ，其顶点是原网络G的顶点，而将G中的每一条弧 ( vi, vj )变成两个相反方向的弧vi， vj和(vj , vi)，并且定义图中弧的权lij为：1.当 ，令 2.当vj，

28、vi为原来网络G中vi， vj的反向弧，令 在网络G中寻觅关于f 的最小费用增广链等价于在L(f )中寻求从vs 到vt 的最短路。 步骤：1取零流为初始可行流 ，f (0) =0。2普通地，假设在第k-1步得到最小费用流 f (k-1)，那么构造图 L( f (k-1) )。3在L( f (k-1) )中，寻求从vs到vt的最短路。假设不存在最短路，那么f (k-1)就是最小费用最大流；否那么转(4)。4假设存在最短路，那么在可行流f (k1)的图中得到与此最短路相对应的增广链，在增广链上，对f (k1)进展调整，调整量为：令得到新可行流f (k) 。对f (k)反复上面步骤，前往2。例8.

29、11 求网络的最小费用最大流，弧旁权是bij , cij (3 ,2)vsv2v1vtv3(1 ,4)(6 ,7)(4 ,8)(1 ,6)(2 ,5)(2 ,3)3 vsv2v1vtv31 64 12 2 (1) L(f (0)(3 ,2)vsv2v1vtv3(1 ,4)(6 ,7)(4 ,8)(1 ,6)(2 ,5)(2 ,3)0vsv2v1vtv3300333(2) f ( 1)1=3W(f(1)=31(3) L(f (1)2 3 vsv2v1vtv31 64 12 121vsv2v1vtv3400343 (4 ) f ( 2)2=1W(f(2)=4(3 ,2)vsv2v1vtv3(1 ,4)(6 ,7)(4 ,8)(1 ,6)(2 ,5)(2 ,3)(5) L(f (2)3 vsv2v1vtv31 4 12 2 231661vsv2v1vtv3401453 (6 ) f ( 3)3=1W(f(3)=5