运筹学图与网络分析(新)a管理资料课件

1、运筹学图与网络分析(新)a管理资料课件作业：作业：P170171 6.3 6.4(c) 6.5 6.7(b) 第六章第六章 图与网络分析图与网络分析 哥尼斯堡七桥问题哥尼斯堡七桥问题 德国古城德国古城哥尼斯堡哥尼斯堡普雷格尔河普雷格尔河七七桥问题：从任一桥头出发，依次走过每座桥问题：从任一桥头出发，依次走过每座桥，每座桥只走一次，最后回到出发点。桥，每座桥只走一次，最后回到出发点。 一笔画问题一笔画问题运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件2. 中国邮递员问题中国邮递员问题 邮递员送信送报要走完全部所负责的街邮递员送信

2、送报要走完全部所负责的街道，最后回到邮局，如何走路程最短？道，最后回到邮局，如何走路程最短？运筹学图与网络分析(新)a管理资料课件第一节第一节 图的基本概念图的基本概念一、图的概念1. 图（无向图） 图是由点与边组成的集合，记为：G=(V,E)，其中V，表示图G中点的集合，E表示图G中边的集合。图中点的个数记为p，称为图的阶；图中边的条数记为q。 运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件2. 端点、关联边、相邻端点、关联边、相邻 若边若边e可以表示为可以表示为e=（vi，vj)，则称，则称vi和和vj是边是边e的端点；边的端点；边e称为点称为点vi和和vj的

3、关联边。的关联边。 若点若点vi、vj与同一条边关联，称点与同一条边关联，称点vi和和vj相相邻。邻。 若边若边ei、ej有公共的端点，称边有公共的端点，称边ei和和ej相邻。相邻。运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件3. 环，多重边，简单图环，多重边，简单图 如果边如果边e的两个端点相重，称该边为环。的两个端点相重，称该边为环。 如果两个端点之间的边多于一条，称为如果两个端点之间的边多于一条，称为多重边。无环、无多重边的图称为简单图。多重边。无环、无多重边的图称为简单图。4. 次，奇点，偶点，孤立点，悬挂点次，奇点，偶点，孤立点，悬挂点 与某一个点与某

4、一个点vi相关联的边的数目称为点相关联的边的数目称为点vi的次。记为的次。记为d(vi)。 次为奇数的点称为奇点，次为偶数的点次为奇数的点称为奇点，次为偶数的点称为偶点。称为偶点。 次为次为0的点称为孤立点。的点称为孤立点。 次为次为1的点称为的点称为悬挂点。悬挂点。 运筹学图与网络分析(新)a管理资料课件.v6运筹学图与网络分析(新)a管理资料课件5. 链，圈，连通图链，圈，连通图 图中由相邻的点和互不相同的边组成的图中由相邻的点和互不相同的边组成的交替序列交替序列称为链。称为链。 若链中的所有顶点也不相同，则该链称若链中的所有顶点也不相同，则该链称为路。为路。 起点与终点重合的链称为圈。起

5、点与终起点与终点重合的链称为圈。起点与终点重合的路称为回路。点重合的路称为回路。 若图中任意两个顶点之间都至少存在一若图中任意两个顶点之间都至少存在一条链，则称该图为连通图。条链，则称该图为连通图。运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件6. 完全图，偶图完全图，偶图 若一个简单图中任意两点之间均有边相连，若一个简单图中任意两点之间均有边相连，则称该图为完全图。则称该图为完全图。 对含有对含有n个顶点的完全图，其边数有个顶点的完全图，其边数有 条。条。 ) 1(212nnCn运筹学图与网络分析(新)a管理资料课件 如果图的顶点能分成两个互不相交的非空如果图的

6、顶点能分成两个互不相交的非空集合集合V1和和V2 ，使在同一集合中任意两个顶点，使在同一集合中任意两个顶点都不相邻，则称该图为偶图（或二分图）。都不相邻，则称该图为偶图（或二分图）。 若偶图的顶点集合若偶图的顶点集合V1、V2之间的每一对不之间的每一对不同顶点之间都有一条边相连，则称该图为完全同顶点之间都有一条边相连，则称该图为完全偶图。在完全偶图中，偶图。在完全偶图中， V1若有若有m个顶点，个顶点， V2有有n个顶点，则其边数共有个顶点，则其边数共有mn条。条。运筹学图与网络分析(新)a管理资料课件7. 子图，部分图子图，部分图 对图对图G1= V1，E1 和图和图G2= V2，E2 ，若

7、有，若有 ，则称，则称G1是是G2的一个子图。的一个子图。 若有若有 ，则称，则称G1是是G2的一个部分图。的一个部分图。2121EEVV和2121EEVV和运筹学图与网络分析(新)a管理资料课件定理定理 ：在图：在图G中，所有顶点次之和等于边数中，所有顶点次之和等于边数的两倍。即：的两倍。即：定理定理 ：在任一图中，奇点的个数必为偶数。：在任一图中，奇点的个数必为偶数。Vvqvd2)(运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件例：有八种化学药品，某些不能放入同一个仓例：有八种化学药品，某些不能放入同一个仓库，用连线表示。

8、见下图。库，用连线表示。见下图。 （v1) （ v2， v4，v7) （v3，v5) （v6，v8) 例：四色问题。例：四色问题。运筹学图与网络分析(新)a管理资料课件8. 同构同构 对图对图G1= V1，E1 和图和图G2= V2，E2 ，如果顶点集合，如果顶点集合V1与与V2之间以及边的集之间以及边的集合合E1与与E2之间都建立了一一对应关系，并且之间都建立了一一对应关系，并且图图G1的两顶点之间的边对应于图的两顶点之间的边对应于图G2对应顶点对应顶点的边，则称图的边，则称图G1与图与图G2是同构的。是同构的。运筹学图与网络分析(新)a管理资料课件9. 9. 赋权图：对一个无向图赋权图：对

9、一个无向图G的每一条边的每一条边（vi，vj) ，相应地有一个数，相应地有一个数wij，则称这样的图，则称这样的图G为为赋权图（也称网络图，记为赋权图（也称网络图，记为N)N)，wij称为边称为边（vi，vj) 上的权。上的权。运筹学图与网络分析(新)a管理资料课件10. 一笔画问题一笔画问题欧拉链：给定一个连通图欧拉链：给定一个连通图G,若存在一条链，过若存在一条链，过每边一次且仅一次，则称这条链为欧拉链。每边一次且仅一次，则称这条链为欧拉链。欧拉圈：若存在一个简单圈，过每边一次，则欧拉圈：若存在一个简单圈，过每边一次，则称这个圈为欧拉圈。称这个圈为欧拉圈。欧拉图：有欧拉圈的图称为欧拉图。欧

10、拉图：有欧拉圈的图称为欧拉图。 能一笔画的图一定是欧拉圈或含有欧拉链。能一笔画的图一定是欧拉圈或含有欧拉链。定理：连通的多重图定理：连通的多重图G是欧拉图的充要条件是是欧拉图的充要条件是G中无奇点。中无奇点。推论：连通的多重图推论：连通的多重图G有欧拉链的充要条件是有欧拉链的充要条件是G中恰有两个奇点。中恰有两个奇点。运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件第二节第二节 树图和图的最小部分树树图和图的最小部分树树图：无圈的连通图称为树图，记为树图：无圈的连通图称为树图，记为T(V,E)。 2-1 树的性质树的性质性质性质

11、1：任何树中必存在至少两个次为：任何树中必存在至少两个次为1的点（悬的点（悬挂点）。挂点）。性质性质2：具有：具有n个顶点的树的边数恰好为个顶点的树的边数恰好为(n-1)条。条。性质性质3：任何具有：任何具有n个顶点、（个顶点、（n-1)条边的连通图条边的连通图是树。是树。2-2 图的最小部分树（最短树）图的最小部分树（最短树） 如果如果G1是是G2的部分图，又是树图，则称的部分图，又是树图，则称G1是是G2的部分树（或支撑树）。的部分树（或支撑树）。 G2的树枝总长最的树枝总长最小的部分树称为该图的最小部分树。小的部分树称为该图的最小部分树。运筹学图与网络分析(新)a管理资料课件定理定理1.

12、 图中任一个点图中任一个点i，若，若j是与是与i相邻点中距离相邻点中距离最近的，则边最近的，则边(i, j)必含在该图的最小部分树内。必含在该图的最小部分树内。 推论：推论： 把图的所有点分成把图的所有点分成V和和 两个集合，两个集合，则两集合之间连线的最短边一定包含在最小部则两集合之间连线的最短边一定包含在最小部分树内。分树内。V运筹学图与网络分析(新)a管理资料课件2-3 求最小部分树的破圈法和避圈法求最小部分树的破圈法和避圈法1. 避圈法避圈法运筹学图与网络分析(新)a管理资料课件2.破圈法破圈法 从网络图从网络图N N中任取一回路，去掉这个中任取一回路，去掉这个回路中权数最大的一条边，

13、得一子网络图回路中权数最大的一条边，得一子网络图N1。在。在N1中再任取一回路，再去掉回路中再任取一回路，再去掉回路中权数最大的一条边，得中权数最大的一条边，得N2。如此继续。如此继续下去，一直到剩下的子图中不再含回路止。下去，一直到剩下的子图中不再含回路止。该子图就是该子图就是N N的最小部分树。的最小部分树。运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件例例: :某工厂内联结六某工厂内联结六个车间的道路网如图个车间的道路网如图所示，已知每条道路所示，已知每条道路的长，要求沿道架设的长，要求沿道架设联结六个车间的电话联结六个车间的电话线网，使电话线的线网，使电话

14、线的总长最小。总长最小。运筹学图与网络分析(新)a管理资料课件第三节第三节 最短路问题最短路问题3-1 狄克斯特拉（标号）算法（狄克斯特拉（标号）算法（dijkstra)：令：令： dij 为相邻两点为相邻两点 vi 与与 vj 的距离，若的距离，若vi 与与 vj不相邻，则令不相邻，则令dij = ，显然，显然，dii=0。 L1i 为从为从v1 到图中任一点到图中任一点vi 的最短距离。的最短距离。狄克斯特拉（标号）算法步骤：狄克斯特拉（标号）算法步骤：（1）从）从v1点出发，将点出发，将L11=0标在标在v1旁的小方框旁的小方框内，表示内，表示v1已经标号；已经标号； 运筹学图与网络分析

15、(新)a管理资料课件（2）找出与）找出与v1相邻的点中距离最小的一个，相邻的点中距离最小的一个，设为设为vr， 将将L1r= L11+ d1r的值标注在点的值标注在点vr旁的小方旁的小方框内，此时，框内，此时， vr也已经标号；也已经标号；（3）从已标号点出发，找出与已标号点相）从已标号点出发，找出与已标号点相邻的所有未标号点邻的所有未标号点vp，若有，若有则将则将L1p的值标在的值标在vp旁的小方框内，此时，点旁的小方框内，此时，点vp已得到标号；已得到标号；（4）重复第（）重复第（3）步，直到）步，直到vn得到标号。得到标号。rprpppdLdLL11111,min运筹学图与网络分析(新)

16、a管理资料课件作业：作业： P172 6.11 6.13运筹学图与网络分析(新)a管理资料课件修正狄克斯特拉（标号）算法：修正狄克斯特拉（标号）算法：步骤：步骤：1. 对起点对起点v1给予固定标号给予固定标号L(v1)=0，其余点为，其余点为临时标号，并记为：临时标号，并记为： (j=1,2.n) 2. 设设vi是刚刚得到固定标号的点是刚刚得到固定标号的点L(vi) ，修改与，修改与其相邻的临时标号点其相邻的临时标号点vj ：不相邻与相邻与jjjjvvvvdvT111)(ijijjjdvLvTvT）（）（,)(min运筹学图与网络分析(新)a管理资料课件3. 在与固定标号点相邻的临时标号点中选

17、取在与固定标号点相邻的临时标号点中选取具有最小标号的点具有最小标号的点vi给予固定标号，即给予固定标号，即: L(vi)=min T(vj) 返回第返回第2步。步。4. 当当vn得到固定标号时，计算结束。得到固定标号时，计算结束。 注：注： 固定标号固定标号L(vi)表示表示v1到到vi的最短距离，的最短距离，临时标号临时标号T(vj)表示表示v1到到vi距离的上界。距离的上界。运筹学图与网络分析(新)a管理资料课件 固定标号固定标号 临时标号临时标号v1（0） v2（5） v3（2） v4（） v5（） v6（） v7（）2. v1（0） v3（2） v2（5） v4（9） v5（） v6（

18、6） v7（）3. v1（0） v3（2） v2（5） v4（7） v5（12） v6（6） v7（）4. v1（0） v3（2） v2（5） v4（7） v5（7） v7（12） v6（6）5. v1（0） v3（2） v2（5） v5（7） v7（12） v6（6） v4（7） 6 v1（0） v3（2） v2（5） v7（10） v6（6） v4（7） v5（7）7. v1（0） v3（2） v2（5） v6（6） v4（7） v5（7） v7（10） 运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件v Dijkstra Dijkstra算法仅适合于所有的权算

19、法仅适合于所有的权w wijij00的情形。如果当赋权有向图中存在的情形。如果当赋权有向图中存在有负权弧时，则该算法失效。例如下图有负权弧时，则该算法失效。例如下图中，根据中，根据DijkstraDijkstra算法，可以得出从算法，可以得出从v v1 1到到v v2 2最短路权是最短路权是2 2，但是这显然不对，因，但是这显然不对，因为从为从v v1 1到到v v2 2的最短路是（的最短路是（v v1 1,v,v3 3,v,v2 2）, ,权是权是-1-1。2 2v v1 13 3v v3 3v v2 2-2-2运筹学图与网络分析(新)a管理资料课件 下面介绍当赋权有向图中，存在负权弧时，下

20、面介绍当赋权有向图中，存在负权弧时，寻求最短路的算法寻求最短路的算法(Ford):(Ford): 1. 1.若点若点v vi i到点到点v vj j之间有一条弧，则令权数为之间有一条弧，则令权数为d dijij，否则，令否则，令d dijij=+=+。 2.2.由于从由于从v vs s到到v vj j的最短路是从的最短路是从v vs s点点出发，沿着这出发，沿着这条路到某个点条路到某个点v vi i, ,再沿弧再沿弧( (v vi i, ,v vj j) )到点到点v vj j。显然，。显然，从从v vs s到到v vi i必定是从必定是从v vs s到到v vj j的最短路，否则从的最短路，

21、否则从v vs s到到v vj j的这条路将不是最短路。于是，的这条路将不是最短路。于是，从从v vs s到到v vj j的最的最短距离短距离L(L(v vs s,v,vj j) )满足以下条件满足以下条件， L(vL(vs s，v vj j)=minL(v)=minL(vs s，v vi i)+d)+dijij, i=1,p, i=1,p i i运筹学图与网络分析(新)a管理资料课件 这个关系式这个关系式L L( (v vs s，v v1 1)L L( (v vs s，v vp p) )可利用如可利用如下的下的递推公式递推公式求解求解 L L(1)(1)( (v vs s，v vj j)=)

22、=d dsj sj , ,j j=1=1p p L L(t)(t)( (v vs s,v,vj j)=min)=minL L(t-1)(t-1)( (v vs s，v vi i)+ )+ d dijij,t t=2,3=2,3 i i 3. 3.当计算到第当计算到第K K步时步时, ,若对一切的若对一切的j j=1=1p p, ,有有 L L(k)(k)( (v vs s，v vj j)=)=L L(k-1)(k-1)( (v vs s，v vj j) ) 则则L L(k)(k)( (v vs s，v vj j),),j j=1=1p p, ,就是从就是从v vs s到各点到各点v vj j的

23、最短路径的最短路径。运筹学图与网络分析(新)a管理资料课件v设设C C是赋权函数有向图是赋权函数有向图D D中的一个回路。如果回路中的一个回路。如果回路C C的的权权S S（C C）是负数那么称）是负数那么称C C是是D D中的一个负回路。中的一个负回路。 可以证明以下的结论：可以证明以下的结论： 1.1.如果赋权有向图如果赋权有向图D D不含有负回路，那么从不含有负回路，那么从v vs s到任到任一点的最短路至多包含一点的最短路至多包含P P-2-2个中间点，并且必可取为个中间点，并且必可取为简单路。简单路。 2.2.如果赋权有向图如果赋权有向图D D不含有负回路，那么上述递推不含有负回路，

24、那么上述递推算法至多经过算法至多经过P P-1-1次迭代必收敛，可以求出从次迭代必收敛，可以求出从v vs s到各到各个点的最短路权。个点的最短路权。 3.3.如果上述算法经过如果上述算法经过P P-1-1次迭代，还存在在着某个次迭代，还存在在着某个j j，使得，使得L L(p)(p)( (v vs s,v,vj j) ) L L(p-1)(p-1)( (v vs s,v,vj j),),那么那么D D中含有负回中含有负回路。这时，不存在从路。这时，不存在从v vs s到到v vj j的路（权无界）。的路（权无界）。结论结论运筹学图与网络分析(新)a管理资料课件例例: : 在如下图所示的赋权有

25、向图中求从在如下图所示的赋权有向图中求从v v1 1到各到各点的最短路。点的最短路。 解解: :利用上述递推公式，将求解结果列出如利用上述递推公式，将求解结果列出如下表所示。下表所示。 可以看出，当可以看出，当t t=4=4时，有：时，有： L L(t)(t)( (v vs s,v,vj j)=)=L L(t-1)(t-1)( (v vs s,v,vj j) ) j j=18=18。因此，表。因此，表中的最后一列，就是从中的最后一列，就是从v v1 1到到v v1 1,v,v2,.,2,.,v v8 8的最短的最短路权。路权。运筹学图与网络分析(新)a管理资料课件v8v2v4v7v5v1v3v

26、61 1111 11 11 12 23 33 35 55 52 22 23 36 67 78 8运筹学图与网络分析(新)a管理资料课件终终点点 起起点点V1V1V2V2V3V3V4V4V5V5V6V6V7V7V8V8t t=1=1t t=2=2t t=3=3t t=4=4V1V1 0 0-1-1-2-2 3 3 0 0 0 0 0 0 0 0V2V2 6 6 0 0 2 2 -1-1-5-5-5-5-5-5V3V3 -3-3 0 0-5-5 1 1 -2-2-2-2-2-2-2-2V4V4 8 8 0 0 2 2 3 3-7-7-7-7-7-7V5V5 -1-1 0 0 1 1-3-3-3-3

27、V6V6 1 1 0 0 1 1 7 7 -1-1-1-1-1-1V7V7 -1-1 0 0 5 5-5-5-5-5V8V8 -3-3 -5-5 0 0 6 6 6 6dij L(t)(vs,vj) 运筹学图与网络分析(新)a管理资料课件v 为了求出从为了求出从v v1 1到各个点的最短路，一般采到各个点的最短路，一般采用反向追踪的方法：如果已知用反向追踪的方法：如果已知L L( (v vs s,v,vj j),),那么寻那么寻求一个点求一个点v vk k, ,使得使得L L( (v vs s,v,vk k)+)+w wkjkj= =L L( (v vs s,v,vj j),),然后记然后记录

28、下录下( (v vk k,v,vj j) )。再看。再看L(L(v vs s,v,vk k),),寻求一个点寻求一个点v vi i, ,使使得得L L( (v vs s,v,vi i)+)+w wiKiK= =L L( (v vs s,v,vk k)依次类推，一直到依次类推，一直到达达L L( (v vs s,v,v1 1) )为止。这样，从为止。这样，从v vS S到到v vj j的最短路是的最短路是（v vs s,v,vi i,v,vk k,v,vj j）。）。v 在本例中在本例中, ,由表知，由表知，L(L(v v1 1,v,v8 8)=6,)=6,由于由于L(vL(v1 1,v,v6

29、6)+d)+d6 86 8=(-1)+7=(-1)+7记录下记录下v v6 6 , ,由于由于L(vL(v1 1,v,v3 3)+d)+d3636=L(v=L(v1 1,v,v6 6),),j j记录下记录下v v3 3 , ,由于由于L L( (v v1 1,v,v1 1)+d)+d1313=L(=L(v v1 1,v,v3 3),),于是，从于是，从v v1 1到到v v8 8的最短的最短路是路是( (v v1 1,v,v3 3,v,v6 6,v,v8 8) )。运筹学图与网络分析(新)a管理资料课件3-2 求任意两点间最短距离的矩阵算法求任意两点间最短距离的矩阵算法(Floyd) 设邻接

30、矩阵为设邻接矩阵为D,计算计算D1=D+D, D2= D1 +D , D3= D2 +D , 。若。若Dm+1= Dm ，则，则Dm中的元中的元素值即为各点间的最短距离。素值即为各点间的最短距离。 Dk+1= Dk +D算法：算法：例例4：运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件D1=D+D= + =rjkirrkijddd )1()(min运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件3-3 求中心求中心 在一个连通图在一个连通图G中，设中，设d(vi ,vj)为为vi至至vj的的最短距离，令：最短距离，令：为点为点vi至点至

31、点vj的最大距离的最大距离,若若G中的一点中的一点v*满足：满足：则称点则称点v*为图为图G的中心。的中心。),(max)(jiVvivvdvdj)(min)(iVvvdvdi运筹学图与网络分析(新)a管理资料课件求中心求中心 村庄之间的最短距离村庄之间的最短距离 dij * 村庄村庄 max v1 v2 v3 v4 v5 v6 v7 v11005277610 v285072548 v372706548 v477260326 v577553013 v66*6442104 v71010886340运筹学图与网络分析(新)a管理资料课件3-4 求重心求重心在一个连通图在一个连通图G中，设中，设w(

32、vi)为点为点vi的权重，令的权重，令表示将点表示将点vi的物资运到点的物资运到点vj的总运输量。的总运输量。若满足若满足则称点则称点 为图为图G的重心。的重心。),.,2 , 1(),()()(1njvvdvwvgnijiij)(min)(jVvvgvgj运筹学图与网络分析(新)a管理资料课件例：上例中，例：上例中， v1， v2， v3，v4， v5， v6， v7为七个村子，现决定要办一所小学，已知各村为七个村子，现决定要办一所小学，已知各村学生人数分别为：学生人数分别为： v130， v240， v325， v420， v550，v660, v760，问小学应建在那个村子，使学生上学走

33、的路程问小学应建在那个村子，使学生上学走的路程最短。最短。解：计算见表。解：计算见表。 小学应建在小学应建在v6村。村。运筹学图与网络分析(新)a管理资料课件求重心求重心 村庄之间的最短距离村庄之间的最短距离 dij * 村庄村庄 人数人数 v1 v2 v3 v4 v5 v6 v7 v2405072548 v3252706548 v4207260326 v5507553013 v6606442104 v76010886340 wi dij * 1700 1335 1430 1070 835770*1330运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a

34、管理资料课件例：下图为一大型企业区域交通网络图。设例：下图为一大型企业区域交通网络图。设点点v v1 1vv7 7为某公司的为某公司的7 7个分厂，边表示经过测个分厂，边表示经过测绘的交通路线，边旁的数字表示两点之间的绘的交通路线，边旁的数字表示两点之间的距离。现该企业欲修建正规道路使各分厂互距离。现该企业欲修建正规道路使各分厂互通，并欲在某一分厂建一俱乐部。问如何选通，并欲在某一分厂建一俱乐部。问如何选择交通路线来修建正规道路既保证各分厂畅择交通路线来修建正规道路既保证各分厂畅通，又使道路总长度最短？俱乐部应建在那通，又使道路总长度最短？俱乐部应建在那个分厂才能使离该俱乐部最远的分厂的职工个

35、分厂才能使离该俱乐部最远的分厂的职工所走的路程最短？所走的路程最短？运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件解：显然，第一个问题就是求最短树问题。第解：显然，第一个问题就是求最短树问题。第二个问题就是求中心问题。二个问题就是求中心问题。 用避圈法或破圈法求出最小部分树见图。用避圈法或破圈法求出最小部分树见图。运筹学图与网络分析(新)a管理资料课件先用公式先用公式 计算计算d(vi)，见下表：，见下表： 再用公式再用公式 计算计算d(v*)，由表，由表可知，应将俱乐部建在分厂可知，应将俱乐部建在分厂v2或或v6。),(max)(jiVvivvdvdj)(min

36、)(iVvvdvdi运筹学图与网络分析(新)a管理资料课件求中心的步骤：求中心的步骤：1. 求出网络中任意两点之间的最短距离；求出网络中任意两点之间的最短距离；2.求出各点到其它点的最远距离；求出各点到其它点的最远距离；3.从这些最远距离中找出最短的距离所在点从这些最远距离中找出最短的距离所在点即为中心。即为中心。运筹学图与网络分析(新)a管理资料课件例：仍以上例为例，现准备在该地区建一个中例：仍以上例为例，现准备在该地区建一个中心仓库以贮存分发给各分厂的原材料。已知各心仓库以贮存分发给各分厂的原材料。已知各分厂每月的原材料需求量见下图。问中心仓库分厂每月的原材料需求量见下图。问中心仓库应建在

37、那个分厂，能使每月总的运输量最小。应建在那个分厂，能使每月总的运输量最小。解：由计算重心的公式：解：由计算重心的公式： 既可算得应把中心仓库建在既可算得应把中心仓库建在v v6 6分厂，每月分厂，每月的最小运输量为的最小运输量为122000122000。),.,2 , 1(),()()(1njvvdvwvgnijiij)(min)(jVvvgvgj运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件补：补： 中国邮路问题中国邮路问题 首先判断是否欧拉图首先判断是否欧拉图,若是就可归结为一若是就可归结为一笔画问题；否则，将图中奇点两两相连，变笔画问题；否则，将图中奇点两两

38、相连，变为欧拉图，连线为邮递员重复走的路程。为欧拉图，连线为邮递员重复走的路程。邮递员重复所走路程最短的条件：邮递员重复所走路程最短的条件：奇点两两之间的连线最短。奇点两两之间的连线最短。（1） 每条边上最多重复一次；每条边上最多重复一次；（2） 在图的每个回路上，有重复的边的长在图的每个回路上，有重复的边的长度不超过总长的一半。度不超过总长的一半。运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件作业：作业：P173P174 6.15(c) 6.17 6.18 6.19(b) 6.21 第四

39、节第四节 网络最大流网络最大流4-1 网络最大流的有关概念网络最大流的有关概念1. 有向图与容量网络有向图与容量网络有向图：点与弧的集合，记作有向图：点与弧的集合，记作D(V，A)。 弧弧(vi，vj)标明方向是从点标明方向是从点vi指向点指向点vj。 弧弧(vj，vi)则相反。则相反。运筹学图与网络分析(新)a管理资料课件容量网络：对网络上的每条弧容量网络：对网络上的每条弧(vi，vj)都给出都给出一个最大的通过能力，称为该弧的容量，记一个最大的通过能力，称为该弧的容量，记为为c(vi，vj)或简记为或简记为cij。容量网络记为。容量网络记为D(V，A，C)容量网络的点通常分为三类：容量网络

40、的点通常分为三类：发点发点vs（始点）、收点（始点）、收点vt（终点）、中间点（终点）、中间点vi 。网络最大流：网络中从发点到收点之间允许网络最大流：网络中从发点到收点之间允许通过的最大流量。通过的最大流量。注：多发点和多收点的处理。注：多发点和多收点的处理。运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件2. 流与可行流流与可行流（网络）流：加在网络各条弧上的一组负载量。（网络）流：加在网络各条弧上的一组负载量。弧弧(vi，vj)上的流量记为上的流量记为f(vi，vj)或或fij。可行流：在容量网络可行流：在容量网络D(V，

41、A，C)上，满足下列上，满足下列条件的一组流称为可行流：条件的一组流称为可行流：（1）容量限制条件，对所有的弧有）容量限制条件，对所有的弧有（2）中间点平衡条件）中间点平衡条件若以若以v(f)表示网络从表示网络从vsvt的流量，则有：的流量，则有：jjtjjsvvfvvffv),(),()(),(0),(),(tsjvvfvvfijji),(),(0jijivvcvvf运筹学图与网络分析(新)a管理资料课件 最简单的可行流是零流。最简单的可行流是零流。网络最大流问题：在满足容量限制条件和中间点网络最大流问题：在满足容量限制条件和中间点平衡条件下，使网络流平衡条件下，使网络流v(f)值达到最大。

42、或求使值达到最大。或求使网络流网络流v(f)实现最大值的可行流。实现最大值的可行流。最大流问题的线性规划模型最大流问题的线性规划模型对所有弧对所有弧满足求0),(0),(),(),(),()(maxijijijijjitjjsfcftsjvvfvvfvvfvvffv运筹学图与网络分析(新)a管理资料课件4-2 割集和割量割集和割量割集（截集）：将网络图中的点分割成割集（截集）：将网络图中的点分割成V和和 两个集合，并且有两个集合，并且有sV, t ，则称弧集，则称弧集（V, )为网络的一个割集。割集中各弧的为网络的一个割集。割集中各弧的容量之和称为割量，记为容量之和称为割量，记为C(V, )。

43、VVV),(),(),(),(_jVVvvivvcVVCjiV运筹学图与网络分析(新)a管理资料课件例：图例：图6-16中的所有割集及其割量见下表。中的所有割集及其割量见下表。运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件4-3 最大流最小割定理最大流最小割定理增广链：在网络图中找出一条增广链：在网络图中找出一条从始点从始点s到终点到终点t的链的链，定义：定义： 所有从所有从s指向指向t(s t)的弧称作正向弧的弧称作正向弧(记作记作+)； 所有从所有从t指向指向s(t s)的弧称作反向弧的弧称作反向弧(记作记作-)。 若在该链中：若在该链中： 对所有的正向弧都有

44、对所有的正向弧都有f0（称为非零流弧），（称为非零流弧）， 则称该链为网络的一条增广链。则称该链为网络的一条增广链。运筹学图与网络分析(新)a管理资料课件在增广链中，令：在增广链中，令：显然，显然，0，再令：，再令： 此时，此时， 仍是一个可行流，但其流量比仍是一个可行流，但其流量比 增加了增加了。对非增广链上的弧对所有的对所有的ijijijffff对对ijijijffc),(minf f运筹学图与网络分析(新)a管理资料课件结论：只要网络图中存在增广链，就可使网络结论：只要网络图中存在增广链，就可使网络的流量增加。只有当网络中不存在增广链时，的流量增加。只有当网络中不存在增广链时，才得到网络

45、的最大流量。才得到网络的最大流量。定理定理2 （最大流最小割定理）网络的最大流等（最大流最小割定理）网络的最大流等于它的最小割集的容量。于它的最小割集的容量。运筹学图与网络分析(新)a管理资料课件4-4 求网络最大流的标号法求网络最大流的标号法（Ford-Fulkerson标号法）标号法）运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件运筹学图与网络分析(新)a管理资料课件例：求下列网络的最大流。例：求下列网络的最大流。解：给出一个初始的可行流解：给出一个初始的可行流xij=02354671f=0f=06(0)2(0)4(0)3(0)7(0)4(0)3(0)1(0)

46、7(0)9(0)8(0)8(0)运筹学图与网络分析(新)a管理资料课件2354671f=0f=06(0)2(0)4(0)3(0)7(0)4(0)3(0)1(0)7(0)9(0)8(0)8(0)找从找从1到到7的增广链的增广链=8=3=1=8调整量：调整量：1 = min8,3,1,8=1运筹学图与网络分析(新)a管理资料课件2354671f=1f=16(0)2(0)4(0)3(1)7(0)4(0)3(0)1(1)7(0)9(0)8(1)8(1)调整流量，调整流量，f=1。继续找从。继续找从1到到7的增广链的增广链=7=1=6=9调整量：调整量：2 = min7,1,6,9=1运筹学图与网络分析

47、(新)a管理资料课件调整流量，调整流量，f=1+1=2。继续找从。继续找从1到到7的增的增广链广链2354671f=2f=26(1)2(0)4(0)3(0)7(1)4(0)3(0)1(1)7(0)9(1)8(1)8(1)=7=5=8调整量：调整量：3 = min7,5,8=5运筹学图与网络分析(新)a管理资料课件调整流量，调整流量，f=1+1+5=7。继续找从。继续找从1到到7的的增广链增广链2354671f=7f=76(6)2(0)4(0)3(0)7(1)4(0)3(0)1(1)7(0)9(6)8(1)8(6)=6=3=4调整量：调整量：4 = min6,4,4,3=3=4运筹学图与网络分析

48、(新)a管理资料课件调整流量，调整流量，f=1+1+5+3=10。继续找从。继续找从1到到7的增广链的增广链2354671f=10f=106(6)2(0)4(3)3(0)7(4)4(3)3(0)1(1)7(0)9(9)8(1)8(6)=3=1=3调整量：调整量：5 = min3,1,3,7=1=7运筹学图与网络分析(新)a管理资料课件调整流量，调整流量，f=1+1+5+3+1=11。继续找从。继续找从1到到7的的增广链增广链已找不到从已找不到从1到到7的增广链，已求得最大流为的增广链，已求得最大流为f=11，最小割集为（最小割集为（2,5）（）（3,4）（）（3,6）。）。2354671f=1

49、1f=116(6)2(0)4(3)3(0)7(5)4(4)3(1)1(1)7(0)9(9)8(2)8(6)运筹学图与网络分析(新)a管理资料课件第五节第五节 最小费用流（最小费用最大流）最小费用流（最小费用最大流） 最小费用流可以这样描述：设网络有最小费用流可以这样描述：设网络有n个点，个点，fij为弧为弧(i，j)上的流量，上的流量，cij为该弧的容量，为该弧的容量，bij为在为在弧弧(i，j)上通过单位流量时的费用，上通过单位流量时的费用，si代表第代表第i点点的可供量或需求量，当的可供量或需求量，当i为发点时，为发点时， si 0，i为为收点时，收点时， si f)，相应费用为，相应费用

50、为b(f)，有：，有： 称比值称比值b(f)/最小，也即调整单位流量花费最小，也即调整单位流量花费最小的增广链为费用最小的增广链。最小的增广链为费用最小的增广链。( )()( )(b)()()()()(6.21)ijijijijijijijijijijijijijijijijb fb fb ffb fb fb fbffbffbb运筹学图与网络分析(新)a管理资料课件 若将每条弧可能作为正向弧或反向弧出现若将每条弧可能作为正向弧或反向弧出现时，通过该弧一单位流量的费用在该弧旁作为时，通过该弧一单位流量的费用在该弧旁作为权数标注，则寻找费用最小的增广链，又可转权数标注，则寻找费用最小的增广链，又可

51、转化为一个求发点至收点的最短路问题。化为一个求发点至收点的最短路问题。因此求最小费用流的步骤可归结为：因此求最小费用流的步骤可归结为：第一步第一步 从零流从零流f0开始。开始。f0是可行流，也是相应是可行流，也是相应的流量为零时费用最小的。的流量为零时费用最小的。运筹学图与网络分析(新)a管理资料课件第二步第二步 对可行流对可行流fk构造加权网络构造加权网络W(fk)，方法是：，方法是： (1)对对0fijfk)。第四步第四步 重复第重复第2、3两步，一直到在网络两步，一直到在网络W(fk+m)中找不到增广链中找不到增广链(也即找不出最短路也即找不出最短路)时，时，fk+m即为要寻找的最小费用最大流即为要寻找的最小