运筹学-图与网络模型以及最小费用最大流

Chapter11图与网络分析(GraphTheoryandNetworkAnalysis)图与网络的基本概念与模型最短路问题最小生成树问题最大流问题最小费用最大流问题本章主要内容：图与网络的基本概念与模型长江汉江武昌汉口汉阳您能从武汉理工大学出发走过每座桥且只走一次然后回到学校吗?近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡7桥”难题。Euler1736年证明了不可能存在这样的路线。图与网络的基本概念与模型Königsberg桥对应的图图与网络的基本概念与模型•图论中图是由点和边构成，可以反映一些对象之间的关系。•一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。图的定义(P230)若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作：},{EVG其中:V——点集E——边集※图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。图与网络的基本概念与模型(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。§1图与网络的基本概念6a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图11-3如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。图与网络的基本概念与模型•定义:图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=[v1,v1];e2=[v1,v2];v3e7e4e8e5e6e1e2e3v1v2v4v5端点,关联边,相邻若有边e可表示为e=[vi,vj]，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。图与网络的基本概念与模型环,多重边,简单图如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5图与网络的基本概念与模型链，圈，连通图(P231)图中某些点和边的交替序列，若其中各边互不相同，且对任意Vi-1,Vi和vi+1均相邻称为链。用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5},,,,,{110kkvevev起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。图与网络的基本概念与模型网络（赋权图）(P232)设图G＝（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。①②③④⑤⑥910201571419256图与网络的基本概念与模型主要概念(p231-p232)无向图：由点和边构成的图，记作G=（V，E）。•有向图：由点和弧构成的图，记作D=（V，A）。•连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。•回路：若路的第一个点和最后一个点相同，则该路为回路。•赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。•网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。11最短路问题•如何用最短的线路将三部电话连起来？•此问题可抽象为设△ABC为等边三角形，，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。ABC最短路问题ABCP•但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。最短新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。最短路问题•问题描述：•要求：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.•有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。最短路问题例渡河游戏•一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。最短路问题•定义：•1）人—M（Man），狼—W（Wolf），羊—G（Goat），草—H（Hay）•2）点——Vi表示河岸的状态•3）边——ek表示由状态vi经一次渡河到状态vj•4）权——边ek上的权定为1我们可以得到下面的加权有向图：最短路问题•状态说明：•v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);•v4,u4=(M,G,H);v5,u5=(M,G)此游戏转化为在下面的二部图中求从v1到u1的最短路问题。v1v2v3v4v5u5u4u3u2u1最短路问题•求最短路有两种算法:狄克斯屈拉(Dijkstra)（双标号）算法逐次逼近算法最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从Vs到Vt的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。最短路问题•狄克斯屈拉(Dijkstra)标号算法的基本思路：•若序列{vs,v1…..vn-1,vn}是从vs到vt间的最短路，则序列{vs,v1…..vn-1}必为从vs到vn-1的最短路。假定v1→v2→v3→v4是v1→v4的最短路，则v1→v2→v3一定是v1→v3的最短路，v2→v3→v4也一定是v2→v4的最短路。v1v2v3v4v5最短路问题最短路的Dijkstra算法(双标号法）的步骤：1.给出点V1以标号(0,s)2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合3.如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则vs到vt的距离为lt，而从vs到vt的最短路径，则可以从kt反向追踪到起点vs而得到。如果vt未标号，则可以断言不存在从vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步。4.对上述弧的集合中的每一条弧，计算sij=li+cij。在所有的sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。{(,)|,}ijijvvvIvJ最短路问题(P233)例1求下图中v1到v6的最短路解：采用Dijkstra算法，可解得最短路径为v1v3v4v6各点的标号图如下：v23527531512v1v6v5v3v4(3,1)v23527531512V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4最短路问题(P234)例2电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。V1（甲地）15176244431065v2V7（乙地）v3v4v5v6最短路问题（0,s）V1（甲地）1517624431065(13,3)v2(22,6)V7（乙地）V5(14,3)V6(16,5)V3(10,1)V4(18,5)最短路问题例3设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表设备维修费如下表年份12345年初价格1111121213使用年数0-11-22-33-44-5每年维修费用5681118最短路问题例3的解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。把所有弧的权数计算如下表：v1v2v3v4v5v6123456116223041592162230413172331417235186最短路问题(继上页)把权数赋到图中，再用Dijkstra算法求最短路。最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1v3v6和v1v4v6v1v2v3v4v5v6162230415916223041312317181723V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)最短路问题•课堂练习：•1.用Dijkstra算法求下图从v1到v6的最短距离及路线。v3v54v1v2v4v635222421v1到v6的最短路为：6521vvvv最短路问题•2.求从v1到v8的最短路径237184566134105275934682最短路问题237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10•v1到v8的最短路径为v1→v4→v7→v5→v8，最短距离为10最短路问题•3.求下图中v1点到另外任意一点的最短路径v1v2v3v4v6v5322762133最短路问题v1V2V3V4V6V5322762133024714最短路问题v1V2V3V4V6V5322762133024714最短路问题•算法适用条件：•Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。•例6.7如右图所示中按dijkstra算法可得P(v1)=5为从vs→v1的最短路长显然是错误的，从vs→v2→v1路长只有3。v2vsv15-58最小生成树问题•树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。•例6.2乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。ABCDEFGH运动员最小生成树问题•例某企业的组织机构图也可用树图表示。厂长人事科财务科总工程师生产副厂长经营副厂长开发科技术科生产科设备科供应科销售科检验科动力科树与图的最小树树：无圈的连通图即为树性质1：任何树中必存在次为1的点。(一个点Vi的相关联边的数目称为点Vi的次)性质2：n个顶点的树必有n-1条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。v1v2v3v4v5v6最小生成树问题•树是图论中的重要概念，所谓树就是一个无圈的连通图。37图11-11中，(a)就是一个树，而(b