运筹学课件--第七章 网络分析

管理运筹学--管理科学方法李军桂林电子科技大学商学院SubtitleOR:SM第7章图与网络分析内容提要2第一节第二节第三节第四节第五节图论的概念最小树问题最短路问题网络最大流最小费用流OR:SMOR:SM哥尼斯堡，原属波兰，现属俄罗斯，名为加里宁格勒3OR:SM18世纪，哥尼斯堡城（当时东普鲁士柯尼斯堡，今日俄罗斯加里宁格勒）中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来。茶余饭后，人们提出了这样的问题：一个散步者能否从某地出发，走遍七座桥且每座桥恰好经过一次，最后回到原地？4OR:SM第7章网络分析1736年瑞士数学家欧拉将两岸和小岛抽象为四个点，将桥抽象为七条边，此问题归结为一笔画问题。陆地AA岛D岛CDCB陆地B欧拉回答的根据是：若图是连通的，且图中奇点(和奇数条边相关联的点)的数目为0或2时，则图能“一笔画”。奇点的数目为零时，则图中任一点即是“一笔画”的起点又是终点。奇点的数目为2时，则两点中任一点为“一笔画”的起点，而另一点为终点。前图中奇点数目为4，不满足“一笔画”规则，因此是无解的。哥尼斯堡七桥问题，用图论的方法得到了简捷的证明，所以欧拉被人们公认为图论的创始人，人们称他为“图论之父”。5OR:SM••OR:SM第一节图论的概念一、图的内涵1、图的定义图论的图与一般几何图形或代数函数图形是完全不同的图论中的图:由一些点和连接点的线所组成的“图形”点和线的位置是任意的线的曲直、长短与实际无关，代表的只是点与点之间的相互关系例：表示苏州v1、杭州v2、上海v3、南京v4仓储网点之间的物流运输线路关系v2·e4e1e5·v1e2·v3e3e6·v4e2e3v2·e4v3·e5e6e5e2e1·v4e3·v16·v1e1·v2e4·v3e6·v4OR:SMOR:SM第一节图论的概念一、图的内涵2、图的分类不带箭头的连线称为“边”，如公路运输线路；带箭头的连线称为“弧”，如供排水的管道运输线路。1、无向图由点和边的集合所构成2、有向图由点和弧的集合所构成•链：无向网络中，前后相继点和边•路径：有向网络图中，前后相继并且7的交替序列称为一条链。•圈：闭合的链称为一个圈。方向一致的点弧序列称为一条路径。•回路：闭合的路径称为一个回路。OR:SMOR:SM8第一节图与网络的基本概念图及其分类3、简单图无环，且任意两点间不多于一条边图论的概念4、多重图有环，或有多重边OR:SMOR:SM第一节图与网络的基本概念母图、子图、支撑子图图论的概念9母图子图支撑子图（生成子图）OR:SMOR:SM第一节图论的概念图与网络的基本概念网络（赋权图）在实际问题中，只用图来描述所研究的对象间的关系往往是不够的，而常常还需要考虑与点或边有关的某些数量指标（即“权”），其可以代表诸如距离、费用、通过能力（容量）等等。网络——点或边带有某种数量指标的图22342234613761371055OR:SMOR:SM第一节图论的概念图与网络的基本概念连通图在众多各类图中有一类在实际应用中占有重要地位的图连通图——在图中，任意两点间至少存在着一条链。11连通图不连通图OR:SMOR:SM第二节最小树问题树及其性质无圈且连通的无向图称为树。例如，企业的组织结构，文件的目录管理等都可以用一个树状图来表示。性质：①树中任两点之间必有且只有一条链；②树中去掉任一条边，则成为不连通图；③树中不相邻两顶点之间添一条边，则得到一个圈；④顶点个数nv与边的个数ne的关系：ne=nv－1。12OR:SM[v,v]TijOR:SM第二节最小树问题支撑树：如果图G（V，E）的支撑子图T=（V，E/）是树，则称T为G的支撑树。权数总和为最小的那棵支撑树，称为最小树。w(T)wij求解方法：①破圈法；②避圈法例：一家企业分别要在6间办公室铺设网线接入口，网线的可行走线方式如下图所示，如何铺设网线才能使网线总长为最短？8v24v56v1356v626v38v4最短网线总长度为最小树权之和2+3+4+6+6=2113OR:SMOR:SM14第二节最小树问题方法一：破圈法：任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个不含圈的图为止，这时的图便是最小树。6v35v54v1173v654v22v4这就得到了该图的一个最小支撑树。142011-03-25OR:SMOR:SM15第二节最小树问题方法二：避圈法：开始选一条权最小的边（也可从一点开始），以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。6v35v54v1173v654v22v4这就得到了该图的一个最小支撑树。152011-03-25OR:SMOR:SM第三节一、最短路问题最短路问题－－ShortestRoute(Path)Problems路权：弧(vi,vj)的权为wij；路权是路p中各条弧权之和最短路：在所有从vs到vt的路p中，求一条路权最短的路狄克斯特拉(Dijkstra)算法算法说明：w(P*)minw(P)P1959年提出，目前公认的最短路算法适合于求解所有弧权wij≥0的最短路问题算法假设：有向图D是完备图图D中任意两点vi,vj之间，恰有两条弧(vi,vj)和(vj,vi)若vi→vj不存在弧,可设想一条从vi→vj的弧,权wij=+∞；若vi→vj有重复的弧，则保留弧权最小的弧16OR:SMOR:SM17OR:SMOR:SM第三节一、双标号算法最短路问题18基本思路:从始点vs出发，逐步探寻，给每个点标号；标号分永久标号P(vk)和临时标号T(vk)两种：•永久标号P(vk)是从点vs→vk的最短路权•临时标号T(vk)是从点vs→vk最短路权的上界算法的每一步从临时标号集中选最小者变为永久标号；经过逐次改变，就可以得到从点vs到各点的最短路。标号形式：单标号法是对每一点赋予一个路权标号双标号法是对每一点赋予两个标号：路标、路权OR:SMOR:SM第三节最短路问题一、双标号算法例：用双标号法求下图网络最短路v12v537418vs109v2413v4671vt19v32v6OR:SM2OR:SMvs第三节一、双标号算法最短路问题第一步：3(vs,3)v1724v51(vs,)8(vs,0)vs9v2(vs,9)1v4(vs,)7vt(vs,)10436120v3(vs,10)v6(vs,)OR:SM2OR:SM第三节一、双标号算法最短路问题第二步：(vs,3)(v1,5)v12v537418(vs,0)vs9v2(vs,9)1v4(v1,7)7vt(vs,)10436121v3(vs,10)v6(vs,)OR:SM2OR:SM第三节一、双标号算法最短路问题第三步：(vs,3)(v1,5)v12v537418(vs,0)vs9v2(vs,9)1v4(v5,6)7vt(v5,13)10436122v3(vs,10)v6(vs,)OR:SM2OR:SM第三节最短路问题一、双标号算法最终：依此类推，重复上述标号过程。得最短路。(vs,3)(v1,5)v12v537418(vs,0)vs9v2(vs,9)1v4(v5,6)7vt(v6,12)10436123v3(v4,9)v6(v3,11)OR:SMOR:SM即时练习：某一个配送中心要给一个快餐店送快餐原料，应按照什么路线送货才能使送货时间最短。(4,1)(18,3)(25,4)21647646112287(27,5)183(16,2)655(22,3)24OR:SMOR:SM第三节最短路问题二、最短路的应用1、网络的中心所谓网络的中心是指一个网络中，选择某一点，使之其余各点到该中心点的距离之和为最小。例：如果要在下表中6个销售点中选一个作为仓库所在地，应该建在哪个经销点，使其余各销售点都离它较近？25OR:SMOR:SM第三节最短路问题二、最短路的应用2、网络的重心引进点的权系数，将权系数与最短距离阵各列对应元素加权求和，再从中选择最小的即为网络重心。26OR:SMOR:SM27第三节最短路问题3、设备更新问题:制订一设备更新问题，使得总费用最小？第1年第2年第3年第4年第5年购买费使用年数维修费130-18141-210162-313193-418244-527[解]设以vi(i=1,2,3,4,5)表示“第i年初购进一台新设备”这种状态，以v6表示“第5年末”这种状态；以弧(vi,vj)表示“第i年初购置的一台设备一直使用到第j年初”这一方案，以wij表示这一方案所需购置费和维护费之和。于是，该问题就可归结为从图中找出一条从v1到v6的最短路问题。其网络模型如下：272011-03-25OR:SMOR:SM28设备更新的网络模型(21)v232(44)v463214422452737(0)v131896224(78)v6用Dijkstra标号法，求得最短路为:v1v3v6v3(31)4734v5(62)32282011-03-25OR:SMOR:SM*设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。表1：设备每年年初的价格表年份年初价格111211312412513表2：设备维修费如下表使用年数每年维修0-151-262-383-4114-518费用29OR:SMOR:SM解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。v1v2v3v4v5v6把所有弧的权数计算如下表：12312163221643022175413023659413130456172318OR:SM222318OR:SM(继上页)把权数赋到图中，再用Dijkstra算法求最短路。5922304123v116v216v317v417v518v62230233141最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1v3v6和v1v4v659V1（0,s）16（16,1）(22,1)4130(30,1)V216v317v430173123(41,1)v5v6(53,3)(53,4)4131OR:SMOR:SM第四节网络最大流－－MaximalflowsinNetworks许多系统包含了流量问题，例如铁、公路系统中的车辆流、工业流程中的物流、通风网络中的风流、供水系统中的水流、控制系统中的信息流和金融系统中的资金流等。对这些系统求最大流量的问题就转化为图论中求网络中一个相容的最大流问题，运输上称之为网络的最大通过能力。32OR:SMOR:SM引例：一个公路交通运输网络如图7-10所示，它联接了产地vs和销售地点vt。其中每一条弧（vi，vj）表示vi到vj的运输线，弧旁的数字表示该支线的最大通过能力。要求制定一个运输方案，使vs到vt的运输量达到最大。这就是一个求网络最大流的问题。可给出一个运输方案，用圆圈中的数字表示。它表明有8个单位的运量从vs运往vt。问题在于运量是否还能增加，或者说如何求最大运量？这是本节要解决的一类主要问题。9⑤v15②5①v38⑥vs4①4③vt2②337③v26③图7-10公路交通运输网络图v46②OR:SM••OR:SM第四节网络最大流一、相关概念与定理1、弧容量与容量网络对于有向图D=(V,A),，弧(vi,vj)的容量表示弧的最大流通能力。在V中指定一点称为发点(记为vs)，另一点称收点(记为vt)，其余点叫中间点，这样的赋权有向图就称为一个容量网络，记N=(V,A,B)2、弧的流量与可行流弧的实际通过量称为该弧的流量。弧集A上的流量集合fxij称为网络上的流。满足下述条件的流称为可行流。34①容量限制：对每条弧(vi,vj)A②平衡条件：中间点流出量=流入