专题五-图与网络分析

1专题五图论与网络计划模型最小生成树模型最短路模型最大流模型最小费用流模型网络计划与优化模型2第一节图与网络基础概念图子图和生成子图网络图链、路、圈和回路连通图简单图3一、图

由有限个代表事物的点和表示事物间联系线构成，这些点称为顶点。为了反映7家企业的业务来往联系，用7个点表示7家企业，若某两家企业之间存在业务来往，则两点间联线。数学表达：顶点用V={v1,v2,…,vn}表示；顶点间的连线称为边，用E={e1,e2,…}表示，则图的表示方法为：G={V,E}4无向图：对象之间具有对称性，（甲对乙，乙对甲）。有向图：不具有对称性的事物。A认识B，B一定认识A?A到B的距离，一定等于B到A的距离？为了反映球队之间比赛胜负关系，则球队之间单纯用一条联线就难以表达。对策：带箭头的线，有向线－－－有向图。5边：两点间不带箭头联线称为边，若两点为vi,vj,则边记为：[vi,vj]；弧：两点间带箭头联线称弧,若有vi指向vj的弧，则弧记为：（vi,vj）。无向图定义：由点和边组成，表示G={V,E}；有向图定义：由点和弧组成，表示D={V,A}。6二、子图与生成子图子图：图G1中的点是图G2中点的一部分，图G1中的边是图G2中的一部分。生成图：图G1的点与图G2相同，边是其中的一部分。7三、网络图各边赋予一定的物理量，例如距离，则叫做网络图。所赋予的物理量叫做权。权可以是：距离、时间、成本、容量等。e11表示上海到北京的铁路长度。或，旅客从上海到北京的车票费用8四、链、路、圈、回路链：点和边的交错序列（vi1,ei1,vi2,…,eik-1,vik）,若有eit=[vit,vit+1]。初等链：顶点和边相互交替出现的点不重复序列。路：在有向图中，链中每条边的方向和链的走向一致的链。圈：起点和终点相同的链叫做圈。回路：起点和终点相同的路叫做回路。v4v1v2v5v3e1e2e3e4e5e6★任意举出一条链，初等链，路，圈和回路。9五、连通图和简单图连通图：在图中，任意两点之间都有一条链相连，叫做连通图。否则是非连通图。非连通图可以由几个连通图构成。环：某边的两个顶点相同；多重边：两个顶点之间多于一条边。简单图：没有环和多重边的图是简单图。10第二节树及最小生成树算法什么是树？构造生成树的方法最小生成树寻找最小生成树的方法11树：不含圈的连通图五个城市连通电话线问题什么是连通图：任意两点之间都有一条链相连。什么是圈：起点和终点相同的链叫做圈。已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话（允许通过其它城市），并且电话线的根数最少。一、树的基本概念12树的基本性质任意两点之间有且只有一条链；图是树的充要条件：任意两个顶点之间只有一条链；若树有p个顶点，则共有q=p-1条边；图是树的充要条件：连通图，边数=顶点数－1。五个城市连通电话线问题13生成树的概念生成图：图G1的点与图G2相同，边是其中的一部分。如果G1是树，则称为生成树。五个城市连通电话线问题14二、构造生成树的方法法1：破圈法：无圈的连通图，图中无圈。起点和终点相同的链叫做圈。从图中取圈，从圈中去掉一边，重复直到无圈。15避圈法：从图中某一点开始生长边，选取与入树边不构成圈的边。16三、最小生成树生成树不唯一架设电话线铺设水管连接边长度最短？17设有一个连通图，每一边都有一个非负权，w(e)=wij.树的权：树中所有边的权之和。最小生成树：图中，权最小的生成树。18将图中求最小生成树的问题归结为整数规划问题，列出数学模型。3568a12a13a24a34a36a67a47a45a78a5812471920四、寻找最小生成树的方法（1）避圈法：开始选一条最小权的边，以后总从与已选边不构成圈的那些未选边中，选一条权最小的（相同最小权的边，任选一条）。（2）破圈法：任取一圈，从圈中去掉一条权最大的边（相同权的边，任去一条），在余下图中，重复此步骤，直到得到一个不含圈的图，即得最小树。21分别用破圈法和避圈法

求图中的最小生成树3926331447392633144722(3)矩阵求解算法步骤1：构造一个矩阵，651572344v1v2v3v4v5v623T651572344v1v2v3v4v5v624步骤2：从矩阵中任一行开始，用T表明节点入树，划去该节点所在的列。T25步骤3：在标T的行中选取最小元素，用方框表示，将对应的边入树，将新得到节点标T，划去所在列。TT26步骤4：重复步骤3。TTT27矩阵计算方法TTTT28矩阵计算方法TTTTT29矩阵计算方法TTTTTT30矩阵计算结果3168357234832第三节最短路问题及算法什么是最短路问题？求解最短路问题的基本思路Dijstra算法：标号法33一、什么是最短路问题？91344372858始点终点v1v2v3v42v5v6v734二、求解最短路问题的基本思路

对于在始点到终点的总体最短路径上的任意一点，从始点到该点的最短路在总体最短路径上。动态规划的思路35三、Dijkstra算法对每个节点，用两种标号：T和P，表示从始点到该节点的距离，P是最短距离，T是目前路径的距离。通过不断改进T值，当其最小时，将其改为P标号。开始时，令始点有P=0，P标号，其它节点T=M（无穷大）。36P(V1)=0,T(V2)=M,…第一步：T(V2)=min(T(V2),P(V1)+W12)=0+8=8T(V3)=min(T(V3),P(V1)+W13)=0+6=6T(V4)=min(T(V4),P(V1)+W14)=0+2=2Min(T(V2),T(V3),T(V4))=2★断言：V1到V4的最短距离为2?P(V4)=237第二步：T(V3)=min(T(V3),P(V4)+W43)=min(6,2+3)=5T(V6)=min(T(V6),P(V4)+W46)=min(M,2+2)=4T(V2)=min(T(V2),P(V1)+W12)=0+8=8T(V3)=min(T(V3),P(V1)+W13)=0+6=6Min(T(V2),T(V3),T(V6))=4断言：V1到V6的距离最短：4。P(V6)=438第一步：假定vi是新产生的P标号点，考查以vi为开始点的所有弧段vivj。如果vj是P标号点，则对vj点不再进行标号；如果vj是T标号点，则计算第二步：产生新的P标号点，在现有所有的T标号中将值最小的T标号改为P标号。重复上述步骤,直到没有点可标号。39第三步：T(V5)=min(T(V5),P(V6)+W65)=min(M,4+3)=7T(V7)=min(T(V7),P(V6)+W67)=min(M,4+9)=13T(V2)=min(T(V2),P(V1)+W12)=0+8=8T(V3)=min(T(V3),P(V4)+W43)=min(6,2+3)=5Min(T(V2),T(V3),T(V5),T(V7))=5断言：V1到V3的距离最短：5。P(V3)=5404142问：从V1到V6的最短距离为多少？从V1到V3的距离为多少？从V3到V5的最短距离为多少？43练习：求V1到V9点的最短距离。v1v2v3v4v5v6v7v8v92349135115651246344无向图（取消箭头）计算方法?8623415192123456745v1v2v3v4v5v6v7v8v92349135115651246346四、Ford算法Dijkstra算法不适用于负权网络具有负权的网络，应当用Ford算法（修正标号法）修正标号法特点是：不但最小T标号应改为P标号，P标号也可修改，修改后P标号再次改为T标号。25-464472v1v3v4v98-588545St748五、寻找最短路径的方法使用双标号49已知有6个村庄，相互间道路距离如下图，拟建一所小学。A处有学生50人，B处有40人，C处有60人，D处有20人，E处有70人，F处有90人。问小学应建在哪个村庄，使学生上学走的路程最短？ABDCFE266418313750第四节最大流问题网络流的基本概念求解网络最大流的基本原理寻找网络最大流的标号法确定网络中最大流的方法51

如图是联接某石油销地和产地的交通网（管道），弧旁数字表示此运输管道的最大通过能力。产品从V1送到V7．现在要求制定一个运输方案，使从V1到V7的产品运输最多。91344372858始点终点v1v2v3v42v5v6v752一、网络流的基本概念流量：某时间内通过弧(vivj)的物质数量fij。容量：弧的最大允许流通量。始点（发点），终点（收点），中间点91344372858始点终点v1v2v3v42v5v6v753可行流f：节点和边的限制条件（1）容量限制条件：通过每条弧的流量不超过弧的容量。（2）平衡条件：网络中的总流量等于始点净输出量；网络中的总流量等于终点净输入量；流进中间点的流量等于流出该点的流量。41341231223始点终点v1v2v3v41v5v6v7网络中的总流量54如何判断流分配是否可行？41341231223始点终点v1v2v3v41v5v6v791344372858始点终点v1v2v3v42v5v6v755饱和弧：网络中流量等于容量的弧；非饱和弧：流量小于容量的弧；正向弧：定义从始点到终点的一条链，与链方向一致的弧，为正向弧，反之为反向弧。12345691344372858始点终点v1v2v3v42v5v6v7零流弧：流量=0的弧56增广链：对于一可行流，网络一条链满足BDCFE10，55，211，64，15，13，26，33，317，28，3非饱和弧非零流弧57二、求解网络最大流的基本原理数学模型58列出下述问题的数学模型：从三口油井1，2，3经管道将油输送到脱水处理厂7，8，中间经4，5，6三个泵站。图中弧旁数字为各管道通过的最大能力，求从油井每小时输送到处理厂的最大流量。2010101050203015205020123456783059定理：可行流f为最大流的充分必要条件是当且仅当网络不存在增广链。若f是最大流，则不存在增广链；若不存在增广链，则f是最大流。60给出一初始可行流，寻找增广链，若存在，则通过该增广链调整、增加网络流。若不存在增广链，则网络流不可再增加。求得最大流。流量调整多少？61三、寻找网络最大流的标号法Ford-Fulkson标号算法：寻增广链。给每个节点以一对标号，第一个标号表示箭尾节点，第二个标号表示可调整量，若终点有了标号，则找到一条增广链，否则不存在增广链。增广链判定：vivjvivj62调整过程：在增广链上，正向弧加上调整量，反向弧减去调整量。经过调整网络流v(f)增加一个调整量：4，43，05，33，36，4按上述调整，得网络流是否可行？流量是否增加了？4，43，15，23，36，363646566从三口油井1，2，3经管道将油输送到脱水处理厂7，8，中间经4，5，6三个泵站。图中弧旁数字为各管道通过的最大能力，求从油井每小时输送到处理厂的最大流量。2010101050203015205020123456783067第五节最小费用最大流问题什么是最小费用流问题？求解最小费用流的赋权图法68一、什么是最小费用流354123152最大流分配是否唯一？引入每条流的成本！69给定网络N=(V,A,c,b)和经过网络的流量v，求流在网络上的最佳分布，使总费用最小。70二、求解最小费用流的赋权图法增广链费用，最小费用增广链。当沿着一条关于可行流f的增广链，以调整f，得到的可行流f’，流量增加，费用变化：称之为增广链的费用。多条增广链,费用不同.71对于可行流，沿最小费用增广链调整流，可使流增加，并保持流费用最小。给定初始可行流（若该流量下费用最小），求最小费用增广链，若存在，则沿该增广链调整网络流；再寻求最小费用增广链，直到给定的网络流不存在增广链为止，即为最小费用最大流。72如何求最小费用增广链？增广链的条件73赋权网络：将饱和弧反向将非饱和、非零流弧加一反向弧零流弧不变所有正向弧的权为该弧的费用，反向弧的权为该弧费用的相反数如此变化后，有何特点？赋权图中，从始点到终点每条通路都是当前可行流的增广链。最小费用增广链对应赋权网络的最短路。74最小费用流的实例7576777879-28081赋权网络已不存在最短路（增广链）82第六节网络计划技术网络图的绘制与识别网络图的时间参数计算网络优化的基本方法83甘特图不易表现工程全貌不便于对各项工作的安排进行筹划和推敲不能识别影响进度的关键工作不能反映一项工作不能按进度完成时对工程进度影响项目有几项工作?能否体现工作之间先后关系?能否反映工作开工和完工的时间?84一、网络图网络图的构成作业（工作、工序、活动），箭头表示，箭头之上表示工作名称，之下表示工作时间。需要消耗一定的人力、物力，经过一定的时间完成。事项，节点表示，表示某个工作的结束和另一工作的开始。虚工作85一个基建项目网络图特点：工作数；先后时间。有了工作和事项，可按照作业的先后次序绘制网络图。86路线：从开始节点到结束节点的一条路经，一个网络图有多条路线，每条路线有一个总时间。关键路线：总时间最长的路线。工期：关键路线的总时间87网络图的路线路线有几条？关键路线是哪条？工期有多长？88以上网络图共有8条路线可以计算出这8条路线的总时间，最长的是16天。关键路线是当某些工作的时间调整后，可能引起关键路线的变化和工期的变化。例如将工作E的时间缩短为4天，则工期缩短为13天，关键路线将变为1346BEG5651356BFH55389二、网络图的画法作业的串联：先行作业；紧前作业；紧后作业作业的并联两事项间只能有一项作业90网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编号大于箭尾事项编号。网络图只能一个开始节点，一个终止节点。不能出现循环路线。尽量少交叉，采用暗桥；有层次性。始工作和结束工作绘制网络图的基本原则9192一项工作有两个紧后工作一项工作有两个紧前工作9394修改95三、网络图时间参数计算事项时间参数的计算作业时间参数的计算关键路线的寻找方法96作业时间的确定对具有标准的作业，采用单一时间估计法对一般性作业，采用三点时间估计法最乐观时间：a最可能时间：m最悲观时间：b计算时间期望值和方差97作业时间计算方法数学期望；方差98事项参数计算事项最早时间：以节点j为开始的各项作业最早可开工的时间。事项最迟时间：以此节点为结束的各项作业最迟必须完成时间。ijiiijj99图上计算法1）从始节点开始（始节点最早为零），用方括号表示某节点的最早时间。2）从终节点开始（终节点最迟为工期），用三角表示某节点最迟时间。12345ABCDEHFG67841078127540411141426313501441414263135100作业时间参数的计算作业最早开始时间作业最早结束时间作业最迟开始时间作业最迟结束时间总时差单时差101作业最早时间ijii最早开始最早结束102作业最迟时间ijj最迟开始最迟结束103作业时间参数计算12345ABCDEHFG67841078127540411141426313501441414263135作业D的时间参数作业G的时间参数104总时差：在不影响总工程完工工期情况下，作业完工期可推迟的时间。单时差：不影响下一作业最早开工的情况下，一项作业完工期可推迟的时间。最早开始，最早结束最迟开始，最迟结束ijEF105时差12345ABCDEHFG67841078127540411141426313501441414263135106最早时间：由上到下；先定开始作业A的最早开始时间（0），加上作业时间得到作业的最早结束时间。凡是先行作业（B，C）只有一个为A，则，作业A的最早结束时间为该作业（B，C）的最早开始时间。若有多项先行作业，则为先行作业最早结束时间最长的为该作业的最早开始时间。107最迟时间：由下到上；最后一个作业的最早结束时间为最迟结束时间，减去作业时间为最迟开始时间；查看该作业的先行作业，先行作业的最迟结束时间为该作业的最迟开始时间。若某作业是两个以上作业的先行作业，取小的为该作业的最迟开始时间。108关键路线的确定方法总时差为零的作业即是关键作业；关键作业构成关键路线。109已知下表所列资料：要求(1)绘制网络图；(2)计算各工序的最早开工、最早完工，最迟开工，最迟完工时间，总时差，并指出关键工序；(3)若要求工程完工时间缩短2天，缩短哪些工序的时间为好。工序紧前工序工序时间工序紧前工序工序时间工序紧前工序工序时间ag,m3ec5ia,l2bh4fa,e5kf,i1c-7gb,c2lb,c7dl3h-5mc3110四、网络优化工程进度计划编制：工期，费用，资源从工程进度角度编制，考虑工作时间关系；考虑资源条件限制，包括人员和物质条件，如设备工时，器材，工具，厂房，运输工具，原材料，动力，燃料。111工期限定，资源需要平衡问题：多项工作同时展开，可能导致资源使用不均衡，延误关键工作，不能保证工期。解决措施：工期不变，就是关键工作时间不能调整。调整非关键路线上工作的开始时间，使资源实现平衡。112箭线下面的数字