《chapter7图与网络》PPT课件.ppt

运筹学,第七章 图与网络 YU Junli,解决的问题：,图论解决运输系统设计、信息系统设计、工程项目进度安排等。 运输系统设计 运输理论中运输、配置、转载问题，也是网络问题，网络由点、弧组成。 最短路线问题、最小支撑树问题、最大流问题、项目安排。,一、图与网络的基本概念,从实例引出图： 5个人之间认识关系：1与2，3与4，2与4，1与3相互认识；3认识5，5认识2，5认识4。,1,2,3,4,5,相关概念：,图论中的图由点和点及之间的连线（带箭头、不带箭头）构成。 有向图：由点和弧（带箭头的连线）构成,关联边有方向. D=(V,A)，V表示有向图D的点的集合，A表示有向图D的弧的集合 路与回路,1,2,4,3,5,6,无向图：由点和边构成的图,关联边没有方向。 G=(V, E),V表示图G的点集合，E表示的图G的边集合。 链与圈,5,3,2,4,1,6,赋权图：边或弧相关有相应的指标（权重），例如距离、费用等等。（网络图） 悬挂点、孤立点、奇点、偶点 链、边、连通图（无向图中两点之间，至少存在一条链）、回路（路的第一点和最后一点相同）、网络（有起点和发点的赋权有向图，称为网络） 树（无圈的连通图）、图的生成树,链：由两两相邻的点及其相关联的边构成的点边序列。 圈：出起点和终点外链中所含的点均不相同的闭链。 路：若有从 u 到 v 不考虑方向的链，且各方向一致，则称之为从 u 到 v 的路。 回路：路的第一点和最后一点相同则称为闭链或回路，否则称该链为开链。 赋权图：边或弧相关有相应的指标（权重）。 奇点：与点连的边（弧）的个数为奇数； 偶点：d(v)=偶数； 悬挂点：d(v)=1；悬挂边：与悬挂点连接的边， 孤立点：d(v)=0；空图：E = ，无边图。 连通图：图中任意两点之间均至少有一条通路，否则称作不连通图。 网络：有起点和发点的赋权有向图，称为网络。 树：无圈连通图；无圈图又称为树林，子连通图是树。,定理一：所有顶点次数之和等于所有边数的2倍。 定理二：在任一图中，奇点的个数必为偶数。 定理三（树的性质）六种等价描述。 设：边数 q , 顶点数 p . 1、无圈连通图； 2、边数q = 顶点数p - 1； 3、连通，且 q = p - 1； 4、无圈，但加一边则得到唯一的圈； 5、连通，但若去一边则图不连通； 6、每对顶点之间有且仅有一条链。,二、图与网络的典型问题,欧拉回路与道路问题（1763年发表的图论问题的第一篇论文，解决了著名的哥尼斯堡七桥问题。 ） 最小生成树问题 最短路问题 最大流问题 最小费用（最大）流问题,1、欧拉回路与道路问题,一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。 欧拉归结为一笔画问题 每个点都只与奇数条线相关联,欧拉回路与一笔画： 连通图G中若存在一条道路（回路），过每边一次且仅一次，当且仅当该图无奇点或只有两个奇点。,2、最小生成树（支撑树）问题,一个乡有九个自然村，其间道路见下图：要以v0村为中心建有线电视网络，如何架线，费用最低？,v0,v1,v2,v3,v4,v5,v6,v7,v8,3,2,5,1,1,4,1,5,5,4,2,4,4,3,1,2,树：,如某单位的组织结构,树：无圈的连通图 得到图的生成子图 边数点数1 例：高速公路建设；光缆通讯线路铺设 最小生成树问题就是在一个赋权的连通的无向图上找出一个生成树，并使这个生成树的所有边的权数之和最小。,最小生成树的算法（贪心算法）,方法：避圈法 在不形成圈的前提下，按从小到大的顺序依次加入边。,进入顺序： 6：13 7：24 8：12 10：34 成圈，不进 11：25 完成,1,2,3,5,4,8,6,11,7,破圈法在原来图中，找到任意一个圈，去掉圈上最长的边。,顺序：去掉的边用红色标出 圈135， 去14 圈1352， 去12 圈1342， 去10,1,2,3,5,4,8,6,12,11,10,7,1,2,3,5,4,8,6,11,10,7,1,2,3,5,4,8,6,11,7,例1：,某大学准备对其所属的7个学院的办公室计算机联网，可能的连图如下，请设计一个网络能连通7个学院，并使总的线路长度最短。,7,8,2,5,4,3,3,3,4,1,7,2,5,4,3,3,3,4,1,7,2,4,3,3,3,4,1,7,2,3,3,3,4,1,7,2,3,3,3,1,总长度=19百米,破圈法举例,7,避圈法举例,7,3、最短路问题,对于赋权的有向图或无向图，求其中一点到另一点的最短路径。 “双标号法”（Dijkstra算法） 做法：对图中的点vj赋予两个标号（lj，kj），第一个标号lj表示起点vs至vj的最短路的长度，第二个标号kj表示在vs至vj的最短路上vj前面一个邻点的下标，从而找到vs到vt的最短路及vs到vt的距离。 0-1规划求解,Dijkstra算法： 1）起点S得到永久标号，值为0；其它点临时标号，值为无穷。 2）考虑从刚得到永久标号的点 k （标号值为 yk) 出发直接到达的尚未得到永久标号的点，如点 j （原有临时标号值为 xj），若 yk + ckj xj ，则调整临时标号为 xj yk + ckj 3）从所有得到临时标号的点中，选取标号值最小的一个，变成永久标号点。 4）若点T没有得到永久标号，返回2）；否则，T的永久标号值即最短路的长，追索标号的路径，得到最短路。,甲地,乙地,v1,v2,v3,v4,v5,v6,v7,15,10,3,4,6,17,5,4,2,6,例2：电信公司准备在甲、乙两地沿路架设光缆线，问如何架设使其光缆线路最短？,甲地,乙地,v1,v2,v3,v4,v5,v6,v7,15,10,3,4,6,17,5,4,2,6,0,s,10,1,13,3,14,3,18,5,16,5,22,6,19,2,15,1,30,2,甲地,乙地,v1,v2,v3,v4,v5,v6,v7,15,10,3,4,6,17,5,4,2,6,最短路径为 v1v3v5 v6 v7 ，距离22,求解最短路问题示例,例3：用Dijkstra算法求点1到点6的最短路,1,2,3,5,4,7,6,11,9,15,13,6,4,3,7,1,0,s,6,1,16,2,20,2,19,5,17,3,21,3,有向图用0-1规划求解。用01变量xij表示从i点到j点的弧（边）是否被采用，为1表示采用，为0表示不采用，则,可用0-1规划求解最短路问题,如例3: （有向图） min 7x12+6x13+13x24+9x25+15x34+11x35+4x46+3x56 st x12+x13=1 x46+x56=1 x24+x25-x12=0 x34+x35-x13=0 x46-x24-x34=0 x56-x25-x35=0 end int 8,OBJECTIVE FUNCTION VALUE 1) 19.00000 VARIABLE VALUE REDUCED COST X12 1.000000 7.000000 X13 0.000000 6.000000 X24 0.000000 13.000000 X25 1.000000 9.000000 X34 0.000000 15.000000 X35 0.000000 11.000000 X46 0.000000 4.000000 X56 1.000000 3.000000,无向图怎么办？,如例2： min 15f12+10f13 +3f23 +6f24+4f35+17f27+5f47+4f45+2f56+6f67+0k1+0k2+0k3+0k4+0k5 st f12+f13=1 f27+f47+f67=1 f13+f23+f35-2k1=0 f12+f23+f27+f24-2k2=0 f35+f45+f56-2k3=0 f24+f45+f47-2k4=0 f56+f67-2k5=0 end Int 15 注：k1,k2,k3,k4,k5为中间点是否为最短路的经过点。,注意：中间点 或者是0条最 短路，或者是 相加等于2条 最短路。,OBJECTIVE FUNCTION VALUE 1) 22.00000 VARIABLE VALUE REDUCED COST F12 0.000000 15.000000 F13 1.000000 10.000000 F23 0.000000 3.000000 F24 0.000000 6.000000 F35 1.000000 4.000000 F27 0.000000 17.000000 F47 0.000000 5.000000 F45 0.000000 4.000000 F56 1.000000 2.000000 F67 1.000000 6.000000 K1 1.000000 0.000000 K2 0.000000 0.000000 K3 1.000000 0.000000 K4 0.000000 0.000000 K5 1.000000 0.000000,无向图用0-1规划求解： 用01变量xij表示从i点到j点的弧（边）是否被采用， 为1表示采用，为0表示不采用，则,例题：,某台机器可连续工作4年，也可于每年末卖掉，换一台新的，已知于各年初购置一台新机器的价格及不同役龄机器年末的处理价格如下表所示。又新机器第一年运行及维修费为0.3万元，使用1至3年后的机器每年运行及维修费用分别为0.8，1.5，2万元。请确定该机器的最优更新策略，使4年内购买、更换、及运行维修的总费用为最少。,分析： 目标：四年总费用最小 注意：此问题机器台数已定，最优方案与多少台机器无关，可以假设只保持一台。 设X12为第一年初购置机器，到第二年初更新机器， 同理设变量X13,X14,X15;X23,X24,X25;X34,X35;X45; 如果更新，意味着卖旧机器，买新机器。 先计算机器使用1，2，3，4年总的运行维修费，得：0.3，1.1，2.6，4.6 X12对应的总费用购置费运行维修费处理价2.5+0.3-2=0.8, 如此计算出相应费用如下： 变量 X13 X14 X15 X23 X24 X25 X34 X35 X45; 费用 0.8 2.0 3.8 6.0 0.9 2.1 3.9 1.1 2.3 1.4 问题转化成为从点1到点5的最短路问题。,4、最大流问题,所谓最大流问题就是：给定一个带容量权重的赋权图，我们希望在不超过每条弧的容量的前提下，得到从起点到终点的最大流量。 图例：S=1,T=6,求点1到点6的最大流量,最大流最小截定理,截集：将图G的点分成两个非空集合，分别包含起点和终点，分别记为 V1, V2。从V1的点到V2的点的所有弧的集合称为图G的一个截集。(把某一截集中的弧从网络中丢失，则从始点到终点便不存在路。截集是可行流的必经之道) 最大流最小截定理：最大流的流量等于最小截的截量。,注意：最小截集的容量影响总的运输量的提高。因此，为提高总的运输量，必须首先考虑改善最小截集中各弧的输送状况，提高它们的通过能力。另一方面，一旦最小截集中各弧的通过能力被降低，就会使总的输送量减少。,网络最大流问题是一个线性规划问题，用fij表示从i点到j点的流量,例4：某石油公司拥有一个管道网络（如图），使用这个网络可以把石油从采地运送到一些销售地。弧上的数字为该管道的容量，问使用这个网络系统从采地向销地运送石油，问每小时能运送多少加仑石油？,v1,v2,v3,v5,v7,v4,v6,6,6,3,2,2,2,4,5,2,1,3,设弧（vi，vj）上的流量为fij，网络上的总流量为F，则有 目标函数: max f12 + f14 约束条件： f12 = f23 + f25 f14 = f43 + f46 + f47 f23 + f43 = f35 + f36 f25 + f35 = f57 f36 + f46 = f67 f57 + f67 + f47 = f12 + f14 fij =0 ,（i=1,2,6, j=1,2,7）,MAX V ST F12+F14-V=0 F47+F57+F67-V=0 F12-F23-F25=0 F23+F43-F35-F36=0 F14-F43-F46-F47=0 F25+F35-F57=0 F36+F46-F67=0 END SUB F12 6 SUB F14 6 SUB F23 2 SUB F25 3 SUB F35 2 SUB F36 2 SUB F43 3 SUB F46 1 SUB F47 2 SUB F57 5 SUB F67 4,注意：,守恒条件： 1、网络中的流量必须满足守恒条件，发点的总流出量等于收点的总流入量； 流量可行条件： 2、中间点的总流入量等于总流出量； 3、每一条弧的流量应小于等于弧的容量； 4、每一条弧的流量应大于等于零。 满足以上两个条件的一组网络流称为可行流； 可行流中最大的网络流称之为最大流（最优解）。,LP OPTIMUM FOUND AT STEP 6 OBJECTIVE FUNCTION VALUE 1) 10.00000 VARIABLE VALUE REDUCED COST V 10.000000 0.000000 F12 5.000000 0.000000 F14 5.000000 0.000000 F23 2.000000 0.000000 F25 3.000000 -1.000000 F43 2.000000 0.000000 F46 1.000000 -1.000000 F47 2.000000 -1.000000 F35 2.000000 -1.000000 F36 2.000000 -1.000000 F57 5.000000 0.000000 F67 3.000000 0.000000,5、最小费用最大流问题,在例4中加上问题：怎样运送才能运送的石油最多并使得总的运费最小？并求出其每小时的最大的流量及每小时的最大流量的最小费用。 因为最大流时可以通过不同费用的网络，故要考虑在得到最大流中还要使得总的费用最小。 这时问题不但给出每条弧的容量，还给出了每条弧单位流量的费用，要求最大流，并使运送费用最小。 方法1：分两步走，先求出最大流，然后再求最小费用。,v1,v2,v3,v5,v7,v4,v6,(6,6),(6,3),(3, 4),(2 ,5),(2, 4),(2, 3),(4, 4),(5, 7),(2, 8),(1, 3),(3, 2),红色数字为容量，蓝色数字为费用。,最大流等于10 仍然设弧（vi，vj）上的流量为fij，已知网络上的总流量为F，则有 目标函数:min fij bij =6f12 + 3f14 + 4f25 + 5f23 +2f43 + 4f35 + 7f57 + 3f36 + 3f46 + 8f47 +4f67 约束条件： f12 + f14 = F= 10 f12 = f23 + f25 f14 = f43 + f46 + f47 f23 + f43 = f35 + f36 f25 + f35 = f57 f36 + f46 = f67 f57 + f67 + f47 = f12 + f14 fij =0 ,（i=1,2,6, j=1,2,7）,LP OPTIMUM FOUND AT STEP 9 OBJECTIVE FUNCTION VALUE 1) 145.0000 VARIABLE VALUE REDUCED COST F12 4.000000 0.000000 F14 6.000000 -6.000000 F23 1.000000 0.000000 F25 3.000000 -5.000000 F35 2.000000 0.000000 F36 2.000000 -4.000000 F43 3.000000 0.000000 F46 1.000000 -6.000000 F47 2.000000 -5.000000 F57 5.000000 0.000000 F67 3.000000 0.000000,MIN W-V ST 6F12+3F14+5F23+4F25+4F35+3F36 +2F43+3F46+8F47+7F57+4F67-W=0 F12+F14-V=0 F47+F57+F67-V=0 F12-F23-F25=0 F23+F43-F35-F36=0 F14-F43-F46-F47=0 F25+F35-F57=0 F36+F46-F67=0 END SUB F12 6 SUB F14 6 SUB F23 2 SU