运筹学第三之图与网络分析.pptx

BDACABCD哥尼斯堡“七桥”难题一笔画问题问题：一个游者怎样才问题：一个游者怎样才能一次连续走过这七座能一次连续走过这七座桥且每座桥只走一次，桥且每座桥只走一次，回到原出发点。回到原出发点。欧拉欧拉用用A,B,C,DA,B,C,D四点表示河的四点表示河的两岸和小岛，用两点间的联两岸和小岛，用两点间的联线表示桥。七桥问题变为：线表示桥。七桥问题变为：从从A,B,C,DA,B,C,D任一点出发，能否任一点出发，能否通过每条边一次且仅一次，通过每条边一次且仅一次，再回到该点再回到该点?第1页/共100页 一、图与网络的基本知识（一）、图与网络的基本概念EADCB第2页/共100页v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10图1第3页/共100页v4v6v1v2v3v5图2第4页/共100页4.一条边的两个端点如果相同,称此边为环。6.不含环和多重边的图称为简单图，含有多重边的图称为多重图。8.有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。5.5.两个点之间多于一条边的，称为多重边两个点之间多于一条边的，称为多重边.7.每一对顶点间都有边相连的无向简单图称为完全图。有有n n个顶点的无向完全图记作个顶点的无向完全图记作K Kn n第5页/共100页 次为零的点称为弧立点，次为1的点称为悬挂点。连结悬挂点的边称为悬挂边。次为奇数的点称为奇点，次为偶数的点称为偶点。第6页/共100页定理定理2 2 任何图中，次为奇数的顶点必为偶数个。有向图中,所有顶点的入次之和等于所有顶点的出次之和定理1 任何图中，顶点次数的总和等于边数的2倍。第7页/共100页v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图第8页/共100页第9页/共100页e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10图图3 3一个图中任意两点间至少有一条链相连，则称此图一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连为连通图。任何一个不连通图都可以分为若干个连通子图，每一个子图称为原图的一个分图。通子图，每一个子图称为原图的一个分图。v4v6v1v2v3v5e e2 2e e1 1e e3 3e e4 4e e5 5e e6 6e e7 7e e8 8e e9 9e e1010图图4 4第10页/共100页第11页/共100页例权矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437第12页/共100页 二、树及最小树问题 已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。v1v2v3v4v5v6第13页/共100页1、连通且不含圈的无向图称为树。树中次为1的点称为树叶，次大于1的点称为分支点。第14页/共100页第15页/共100页第16页/共100页第17页/共100页一个图G 有生成树的充要条件是G是连通图。v1v2v3v4v5v1v2v3v4v5第18页/共100页用破圈法求出下图的一个生成树。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8第19页/共100页（一）破圈法第20页/共100页（二）避圈法第21页/共100页v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5第22页/共100页 某六个城市之间的道路网如下图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v612344第23页/共100页求最小树的方法：求最小树的方法：一、破圈法：在给定连通图一、破圈法：在给定连通图G G中，任取一圈，去掉一条中，任取一圈，去掉一条最大权边（若有两条或两条以上的权均是最大权边，则最大权边（若有两条或两条以上的权均是最大权边，则任意去掉其中一条），在余图中任取一圈，去掉一条最任意去掉其中一条），在余图中任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即得到图大权边，重复下去，直到余图中无圈为止，即得到图G G的最小树。的最小树。二、避圈法：在给定连通图二、避圈法：在给定连通图G G中，任取权值最小的一条中，任取权值最小的一条边，在未选边中选一条权值最小的边，要求所选边与已边，在未选边中选一条权值最小的边，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止，已选边与顶点构成的图圈的边为止，已选边与顶点构成的图T T即为所求的最小即为所求的最小树。树。第24页/共100页v1v2v3v4v514231352破圈法求最小树：破圈法求最小树：v1v2v3v4v514231352第25页/共100页v1v2v3v4v514231352避圈法求最小树：避圈法求最小树：v1v2v3v4v514231352第26页/共100页三、最短路问题三、最短路问题最短路问题是重要的优化问题之一，它不仅可以直接应最短路问题是重要的优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局、设备更新等，而且经常被作为一个基本工具，厂区布局、设备更新等，而且经常被作为一个基本工具，用于解决其他的优化问题。用于解决其他的优化问题。DijkstraDijkstra标号法标号法第27页/共100页第28页/共100页第29页/共100页例：如图所示是某地区交通运输示意图，问从例：如图所示是某地区交通运输示意图，问从v v1 1出发，出发，经那条路线到达经那条路线到达v v8 8,才能使总行程最短才能使总行程最短?v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8 83 35 56 67 74 42 23 35 56 69 95 52 21 11 11 1第30页/共100页3 35 56 67 74 41 1第31页/共100页2 21 1第32页/共100页3 35 52 21 19 9第33页/共100页5 5第34页/共100页第35页/共100页例2、用Dijkstra算法求下图从v1到v6的最短路。v1v2v3v4v6v5352242421解（1）首先给v1以P标号，给其余所有点T标号。（2）（3）（4）第36页/共100页v1v2v3v4v6v5352242421（5）（6）（7）（8）（9）（10）反向追踪得v1到v6的最短路为：第37页/共100页237184566134105275934682求从1到8的最短路径第38页/共100页237184566134105275934682X=1,w1=0minc12,c14,c16=min0+2,0+1,0+3=min2,1,3=1X=1,4,p4=1p4=1p1=0第39页/共100页237184566134105275934682X=1,4minc12,c16,c42,c47=min0+2,0+3,1+10,1+2=min2,3,11,3=2X=1,2,4,p2=2p1=0p4=1p2=2第40页/共100页237184566134105275934682X=1,2,4minc13,c23,c25,c47=min0+3,2+6,2+5,1+2=min3,8,7,3=3X=1,2,4,6,p6=3p2=2p4=1p1=0p6=3第41页/共100页237184566134105275934682X=1,2,4,6minc23,c25,c47,c67=min2+6,2+5,1+2,3+4=min8,7,3,7=3X=1,2,4,6,7,p7=3p2=2p4=1p1=0p6=3p7=3第42页/共100页237184566134105275934682X=1,2,4,6,7minc23,c25,c75,c78=min2+6,2+5,3+3,3+8=min8,7,6,11=6X=1,2,4,5,6,7,p5=6p2=2p4=1p1=0p6=3p7=3p5=6第43页/共100页237184566134105275934682X=1,2,4,6,7minc23,c53,c58,c78=min2+6,6+9,6+4,3+8=min8,15,10,11=8X=1,2,3,4,5,6,7,p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8第44页/共100页237184566134105275934682X=1,2,3,4,6,7minc38,c58,c78=min8+6,6+4,3+7=min14,10,11=10X=1,2,3,4,5,6,7,8,p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10第45页/共100页237184566134105275934682X=1,2,3,4,6,7,81到8的最短路径为1，4，7，5，8，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10第46页/共100页求从V1 到 V8 的最短路线。第47页/共100页第48页/共100页v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8 83 35 56 67 74 42 23 35 56 69 95 52 21 11 11 1第49页/共100页第50页/共100页第51页/共100页第52页/共100页V1V2V3V4V5V6V7V8P=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;minL()=10P=T=10第53页/共100页由此看到，此方法不仅求出了从V1到V8的最短路长，同时也求出了从V1到任意一点的最短路长。将从V1到任一点的最短路权标在图上，即可求出从V1到任一点的最短路线。本例中V1到V8的最短路线是：v1v2v5v6v8第54页/共100页623121641036234210第55页/共100页（二）、逐次逼近法算法的基本思路与步骤：首先设任一点vi到任一点vj都有一条弧。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：开始时，令即用v1到vj的直接距离做初始解。从第二步起，使用递推公式：求，当进行到第t步，若出现则停止计算，即为v1到各点的最短路长。第56页/共100页例2、18v1v2v3v4v52635135211211v6v7v837v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8 8P P(1)(1)P P(2)(2)P P(3)(3)P P(4)(4)v v1 10 0-1-1-2-23 3 0 00 00 00 0v v2 26 60 0 2 2 -1-1-5-5-5-5-5-5v v3 3-3-30 0-5-5 1 1 -2-2-2-2-2-2-2-2v v4 48 8 0 0 2 2 3 3-7-7-7-7-7-7v v5 5-1-1 0 0 1 1-3-3-3-3v v6 6 1 10 01 17 7-1-1-1-1-1-1v v7 7 -1-1 0 0 5 5-5-5-5-5v v8 8 -3-3-5-50 0 6 66 6求图中v1到各点的最短路第57页/共100页18v1v2v3v4v52635135211211v6v7v837（0，0）（v3，-5）（v1，-2）（v3，-7）（v2，-3）（v4，-5）（v3，-1）（v6，6）第58页/共100页例3、求：5年内，哪些年初购置新设备，使5年内的总费用最小。解：（1）分析：可行的购置方案（更新计划）是很多的，如：1）每年购置一台新的，则对应的费用为：11+11+12+12+13+5+5+5+5+5=84 2)第一年购置新的，一直用到第五年年底，则总费用为：11+5+6+8+11+18=59 显然不同的方案对应不同的费用。第i年度 12345购置费1111121213设备役龄0-11-22-33-44-5维修费用 5681118第59页/共100页（2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。求解步骤：1）画赋权有向图：设 Vi 表示第i年初，(Vi,Vj)表示第i 年初购买新设备用到第j年初（j-1年底），而Wi j 表示相应费用，则5年的一个更新计划相当于从V1 到V6的一条路。2）求解 （标号法）第60页/共100页WW1212=11+5=16=11+5=16WW1313=11+5+6=22=11+5+6=22WW1414=11+5+6+8=30=11+5+6+8=30WW1515=11+5+6+8+11=41=11+5+6+8+11=41WW1616=11+5+6+8+11+18=59 =11+5+6+8+11+18=59 W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41W45=12+5=17W46=12+5+6=23W56=13+5=18W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31第61页/共100页 例4、某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。年份年份年份年份1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 5购置费购置费购置费购置费1818181820202020212121212323232324242424使用年数使用年数使用年数使用年数0 0 0 0 1 1 1 11 1 1 1 2 2 2 22 2 2 2 3 3 3 33 3 3 3 4 4 4 44 4 4 4 5 5 5 5维修费维修费维修费维修费5 5 5 57 7 7 7121212121818181825252525第62页/共100页年份年份年份年份1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 5购置费购置费购置费购置费1818181820202020212121212323232324242424使用年数使用年数使用年数使用年数0 0 0 0 1 1 1 11 1 1 1 2 2 2 22 2 2 2 3 3 3 33 3 3 3 4 4 4 44 4 4 4 5 5 5 5维修费维修费维修费维修费5 5 5 57 7 7 712121212181818182525252528v1v2v3v4v5v62325262930426085324462334530第63页/共100页四、最大流问题四、最大流问题第64页/共100页13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)第65页/共100页第66页/共100页第67页/共100页第68页/共100页13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)是一个增广链显然图中增广链不止一条第69页/共100页第70页/共100页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第71页/共100页13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)设，则截集为容量为20第72页/共100页第73页/共100页第74页/共100页在此过程中，网络中的点或为标号点或为未标号点，每在此过程中，网络中的点或为标号点或为未标号点，每个标号点的标号包含两部分：第一个标号表明它的标号个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链，第二个标号是为是从哪一点得到的，以便找出增广链，第二个标号是为确定增广链的调整量确定增广链的调整量用的。用的。第75页/共100页第76页/共100页例：用标号法求下图所示的网络最大流例：用标号法求下图所示的网络最大流13(7)9(9)4(4)5(5)6(6)5(0)5(2)5(5)4(4)4(0)9(7)10(5)第77页/共100页第78页/共100页13(7)9(9)4(4)5(5)6(6)5(0)5(2)5(5)4(4)4(0)9(7)10(5)第79页/共100页13(11)9(9)4(0)5(5)6(6)5(4)5(2)5(5)4(4)4(4)9(9)10(9)第80页/共100页求下图所示网络中的最大流，弧旁数为(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)第81页/共100页(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)(3,0)(5,3)(2,2)（0，+）（+vs,3）最小截集第82页/共100页13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)第83页/共100页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=20第84页/共100页70（70）70（50）130（100）150（130）150（150）50（20）50（50）120（30）100（100）（120）（230）（150）（200）第85页/共100页第五节最小费用最大流问题定义8.17已知网络G=（V，E，C，d），f是G上的一个可行流，为一条从vs到vt的增广链，称为链的费用。若*是从vs到vt的增广链中费用最小的增广链，则称*是最小费用增广链。结论：如果可行流f在流量为W(f)的所有可行流中的费用最小，并且*是关于f 的所有增广链中的费用最小的增广链，那么沿增广链*调整可行流f，得到的新可行流f*也是流量为W(f*)的所有可行流中的最小费用流。当f*是最大流时，就是最小费用最大流。第86页/共100页寻找关于f 的最小费用增广链：构造一个关于f 的赋权有向图L(f)，其顶点是原网络G的顶点，而将G中的每一条弧(vi,vj)变成两个相反方向的弧（vi，vj）和(vj,vi)，并且定义图中弧的权lij为：1.当，令2.当（vj，vi）为原来网络G中（vi，vj）的反向弧，令在网络G中寻找关于f 的最小费用增广链等价于在L(f)中寻求从vs 到vt 的最短路。第87页/共100页步骤：（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)进行调整，调整量为：第88页/共100页令得到新可行流f(k)。对f(k)重复上面步骤，返回（2）。例8.11求网络的最小费用最大流，弧旁权是（bij,cij）(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)第89页/共100页3vsv2v1vtv3164122(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)23vsv2v1vtv31641212第90页/共100页1vsv2v1vtv3400343(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)3vsv2v1vtv314122231661vsv2v1vtv3401453(6)f(3)3=1W(f(3)=5第91页/共100页(7)L(f(3)vsv2v1vtv33141-223161vsv2v1vtv3434450(8)f(4)4=3W(f(4)=80vsv2v1vtv34455505=1W(f(5)=9(10)f(5)1-231vsv2v1vtv334126(9)L(f(4)-4-6第92页/共100页31214(11)L(f(5)1264vsv2v1vtv36第93页/共100页第六节中国邮递员问题一、欧拉回路与道路定义8.18连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图。定理8.7一个多重连通图G是欧拉图的充分必要条件是G中无奇点。推论一个多重连通图G有欧拉道路的充分必要条件是G有且仅有两个奇点。第94页/共100页ABCD第95页/共100页二、奇偶点图上作业法（1）找出图G中的所有的奇顶点，把它们两两配成对，而每对奇点之间必有一条通路，把这条通路上的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点。（2）如果边e=（u,v）上的重复边多于一条，则可从重复边中去掉偶数条，使得其重复边至多为一条，图中的顶点仍全部都是偶顶点。（3）检查图中的每一个圈，如果每一个圈的重复边的总长不大于该圈总长的一半，则已经求得最优方案。如果存在一个圈，重复边的总长大于该圈总长的一半时，则将这个圈中的重复边去掉，再将该圈中原来没有重复边的各边加上重复边，其它各圈的边不变，返回步骤（2）。第96页/共100页判定标准1:在最优邮递路线上，图中的每一条边至多有一条重复边。判定标准2:在最优邮递路线上，图中每一个圈的重复边总权小于或等于该圈总权的一半。例8.12求解下图所示网络的中国邮路问题，图中数字为该边的长。v1v2v3v4v5v6v7v8v9243449556434第97页/共100页v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v9243449643455l12+2l23+2l36+2l89+2l78+l69+l14+2l47=51v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v9243449556434第98页/共100页v1v2v3v4v5v6v7v8v9243449556434第99页/共100页感谢您的观看！第100页/共100页