三网络分析PPT课件

1,2020/5/28,1.某公司在三个地方有I、II、III三个分厂，生产同一种产品，其产量分别为400吨、500吨、700吨。需要供应甲、乙、丙、丁四个地方销售，这四地的产品需求分别为300吨、200吨、600吨、500吨。三个分厂到四个销售地的单位运价如表3-13所示。,第3章作业,（1）应如何安排调运方案，才能使得总运费最小？（2）如果II分厂的产量从500吨提高到700吨，那么应如何安排运输方案，才能使总运费为最小？（3）如果销地丙的需求从600吨提高到700吨，而其他情况都同（1），那该如何安排调运方案，才能使得总运费最小？,2,2020/5/28,2.某地区共由1个城市和8个乡镇组成，该地区不久将用光纤网络，其中城市1设有终端服务器。现要设计一个网络系统，使得城市1与乡镇29都有光纤连通，并且使铺设光纤的总长度尽可能地少。城镇之间的距离如表3-14所示。,第3章作业,3,2020/5/28,3.1项管道施工工程由AF六项活动组成，有关数据资料如表3-17所示。,第3章作业,（1）画出项目网络图；（2）设计活动的时间安排表；（3）判断关键路径，并求出项目的期望完成时间；（4）承包商希望在25天内完成这项管道施工项目，请判断该工程按计划完工的可能性有多大。,第3章网络分析,引言,图论(GraphTheory)是运筹学的一个分支，已广泛应用在物理学、化学、控制论、信息论、科学管理、计算机等各个领域中。网络分析（NetworkAnalysis）作为图论的一个重要内容，已成为对各种系统进行分析、研究和管理的重要工具。本章主要介绍运输问题、最短路问题、最小支撑树问题、最大流问题，以及网络计划评审与优化问题。,3.1图与网络的基本概念,图论中的图，是反映现实世界中具体事物及其相互关系的一种抽象工具,它比地图、分子结构图、电路图等更抽象。图的定义：简单的说，一个图是由一些点(Vertices)及点间的连线(Edges)所组成的。点可以作为现实世界中事物的抽象，而点间的连线表示事物间的关系。,3.1图与网络的基本概念,无向图：如果一个图由点及边所构成，则称之为无向图，记为G=(V，E)。其中，V是一个有限非空的点集合，称为G的点集，一般表示为V=v1，v2，vn；E是一个边集合，称为G的边集，一条连接vi和vj的边一般表示为一个无序对e=（vi，vj）。,3.1图与网络的基本概念,例3-1试用一个图来表示大连、北京、深圳、上海四城市之间的民航客机通航情况。解：设v1，v2，v3，v4分别表示大连、北京、深圳、上海四市，则他们之间的通航情况可表示为一个无向图：G=(V，E)。,3.1图与网络的基本概念,图3-1V=v1，v2，v3，v4E=e1，e2，e3，e4，e5，e6e1=v1，v2，e2=v1，v3，e3=v1，v4e4=v2，v3，e5=v2，v4，e6=v3，v4,3.1图与网络的基本概念,如果一个图由点及弧所构成，则称之为有向图，记为D(V，A)。其中，V是点的集合；A是弧的集合，一条从vi连接到vj的弧一般表示为一个有序对a(vi，vj)。,3.1图与网络的基本概念,例3-2有A、B、C、D四支篮球队，进行单循环比赛，比赛情况如表3-1所示。试用一个图表示各队之间的胜负关系。,表3-1,3.1图与网络的基本概念,设v1，v2，v3，v4分别表示球队A、B、C、D，其相互间的胜负关系可表示为一个有向图：D=(V，A)，从vi连接到vj的弧表示vi代表的球队胜vj代表的球队。,图3-2,3.1图与网络的基本概念,其中V=v1，v2，v3，v4A=a1，a2，a3，a4，a5，a6a1=v1，v2，a2=v1，v3，a3=v4，v1a4=v2，v3，a5=v4，v2，a6=v3，v4,3.1图与网络的基本概念,几个基本概念若有e=（vi，vj），则称vi，vj是e的端点，也称点vi与vj相邻，称e是vi，vj的关联边。如图3-3中，v1与v4是e5的端点，点v2与v3相邻，e6是v4与v5的关联边。若一条边的两个端点相同，则称该边为环。如e7。若两个端点之间不止一条边，则称具有多重边；一个无环也无多重边的图称为简单图。,3.1图与网络的基本概念,图3-3,3.1图与网络的基本概念,图G=(V，E)中，设；则交替序列称为一条从到的链，简记为,；,，,若则称为闭链，否则称为开链。若中的边均不相同，则称为简单链；若中所有结点也均不同，则称为初等链。若一条闭链中，除外，任意两点均不相同，则称为一个圈。若图G中，任意两点间至少存在一条链，则称图G为连通图，否则称为不连通图。,3.1图与网络的基本概念,如图3-4中，v4v7v5v6v7v8是简单链，v4v5v7v6v8是初等链，v4v5v6v8v7v4是一个圈，但v4v7v6v8v7v5v4仅为一条闭链，而不是圈。如图3-3是连通图，而图3-4是不连通图，因为v1与v4之间不存在链。,3.1图与网络的基本概念,图3-4,3.1图与网络的基本概念,设有图G=(V，E)和图G=(V，E)，若VV，EE，则称G是G的一个支撑子图或支撑图。,例如在图3-5中，(a)，(b)，(c)均为(a)的支撑子图，但(d)不是(a)的支撑子图，因为(d)比(a)少一个点v1。,图3-5,3.1图与网络的基本概念,若把一个有向图D中所有弧的方向去掉，即每一条弧都用相应的无向边代替，所得到一个无向图称为该有向图D的基础图，记为G(D)。如图3-6中(b)为(a)的基础图。,图3-6,3.1图与网络的基本概念,把基础图G(D)的链和圈定义为有向图D的链和圈。如图3-6中，v2v1v4v3是G(D)的一条初等链，因而也是D的一条初等链；v2v4v1v2是G(D)的一个圈，因而也是D的一个圈。,3.1图与网络的基本概念,若交替序列是有向图D(V，A)的一条链，并且有：则称是图D的一条从到的路，简记为：若，则称是图D的一条回路，否则称为开路。,，,3.1图与网络的基本概念,对无向图G而言，链和路(闭链和回路)这两个概念是一致的。如图3-6中，v2v4v1v3是一条开路，v4v1v3v4是一条回路；但v2v1v4v3和v2v4v1v2虽然分别是G(D)的开路和回路，却不是D的路，而仅是D的链和圈。,3.1图与网络的基本概念,若给一个图中的每一条边（或弧）都赋予一个实数=(vi，vj)，所得的图称为一个赋权网络图。赋权无向图和赋权有向图统称为网络，记为N。这里，称为边(vi，vj)的权数（或权）。一般来讲，图论中所讨论的图，特别是在应用图论中所讨论的图多数是网络。,3.2运输问题,运输问题一般描述为：一种物资有m个产地，其产量分别为ai，有n个销地，其销量分别为bj；从Ai至Bj的运价为cij，问如何设计调运方案才能使总运费最少？运输问题可以采用表上作业法进行求解，也可借助相关的运筹学软件包进行求解。,3.2运输问题,3.2.1产销平衡问题当总产量等于总销量，即：时，称为产销平衡的运输问题，简称平衡问题。,3.2运输问题,例3-3有A1，A2，A3三个水泥厂，每天要把生产的水泥运往B1，B2两地。各厂的产量、各地的需求量（销量）以及各厂地间的运价见表3-2。问如何设计调运方案才能使总运费最少？,表3-2,3.2运输问题,解：因为=11+15+9=35，=14+21=35，所以这是一个产销平衡问题。,3.2运输问题,目标函数为：其中xij为Ai至Bj的运量，因为某产地运往各销地的运量之和应等于该产地的产量，所以有:。又因各产地运往某销地的运量之和应等于该销地的销量（需求量），所以有:,3.2运输问题,综上，得到产销平衡运输问题的一般模型为：,3.2运输问题,应用到本例中的实例模型为：,3.2运输问题,经求解，最优解如下：由结果可知，由A1运往B1地11吨，A2运往B2地15吨，A3运往B1地3吨，A3运往B2地6吨，这样安排总运费最少，最少总运费为4515元。,，,3.2运输问题,3.2.2产销不平衡问题当总产量大于总销量即时，称为产大于销的运输问题；当总产量小于总销量即时，称为产小于销的运输问题。产大于销的运输问题和产小于销的运输问题统称为产销不平衡问题。,3.2运输问题,例3-4有A1，A2，A3三个水泥厂，每天要把生产的水泥运往B1，B2两地。各厂的产量、各地的需求量（销量）以及各厂地间的运价见表3-3。问如何设计调运方案才能使总运费最少？表3-3,3.2运输问题,解:因为=11+15+9=35，=13+20=33，所以这是一个产大于销的运输问题。因为某产地运往各销地的运量之和不大于该产地的产量，所以有。又因各产地运往某销地的运量之和应等于该销地的销量（需求量），所以有：,3.2运输问题,综上，得到产大于销运输问题的一般模型为：,3.2运输问题,应用到本例中的实例模型为：,3.2运输问题,经求解，最优解如下：由结果可知，由A1运往B1地11吨，A2运往B2地15吨，A3运往B1地2吨，A3运往B2地5吨，这样安排总运费最少，最少总运费为4240元。,3.2运输问题,3.2.3转运问题前面介绍的运输问题，都是将物资直接由产地运往销地，但是，实际中很多的运输问题是先将物资由产地运往某个或某些转运站（转运站在现实情况中往往表现为仓库），再由转运站运往销地，这类运输问题不仅要求总运费最少，而且要同时选出最优运输路线，这就是转运问题。,3.2运输问题,例3-5有A1，A2，A3三个水泥厂，每天要把生产的水泥先运往C1，C2两个仓库，再由仓库运往B1，B2两地。各厂至各仓库、各仓库至各销地的运价（单位：元/吨）见表3-4，每个产地的产量（单位：吨/天）和每个销地的销量（单位：吨/天）分别在左侧和右侧做了标注。问如何设计调运方案才能使总运费最少？,3.2运输问题,表3-4,3.2运输问题,解：该例中共有10条运输路线，分别是A1-C1，A1-C2，A2-C1，A2-C2，A3-C1，A3-C2，C1-B1，C1-B2，C2-B1，C2-B2，我们分别用数字17来表示A1、A2、A3、C1、C2、B1、B2，则这十条运输路线上的运量可分别用x14，x15，x24，x25，x34，x35，x46，x47，x56，x57来表示。,3.2运输问题,目标函数为：minz=90 x14+100 x15+105x24+92x25+102x34+83x35+72x46+67x47+58x56+64x57由于这是一个产销平和问题，对于产地，物资的运出量应等于产地的产量，因此对A1有：对A2有：对A3有：,3.2运输问题,对于转运站（仓库），物资的运入量应等于运出量，因此:对C1有：对C2有：对于销地，物资的运入量应等于销地的需求量，因此:对B1有：对B2有：,3.2运输问题,综上，建立此例的数学模型为：,3.2运输问题,经求解，最优解如下：,最优调度方案如下图:,图3-7,3.2运输问题,归纳出转运问题的一般线性规划模型,这里xij表示从节点i到j的运量，cij表示从i到j的运价，ai表示产地i的产量，bj表示销地j的销量（需求量）。,3.3最短路问题,最短路问题一般描述为：在一网络中，给定两个点vs和vt，找到一条从vs到vt的路，使这条路上所有弧的权数之和最小，这条路就是vs到vt的最短路。这条路上所有弧的权数之和称为vs到vt的距离。最短路线问题可以采用狄克斯特拉标号法、距离矩阵摹乘法等方法进行求解，也可借助相关的运筹学软件包进行求解。,3.3最短路问题,例3-6某电信公司计划在甲、乙两地铺设通信电缆，图3-7是甲、乙两地间的交通图，图中v1，v2，v3，v4，v5，v6表示6个地名点，其中v1表示甲地，v6表示乙地，点之间的连线（边）表示两地公路，边上的数值表示两地间公路的长度（单位：千米），问如何铺设能使甲、乙两地的电缆长度最短？,3.3最短路问题,图3-7Dijkstra标号法经求解最短路是v1-v2-v6，最短距离是7+12=19千米，所以应在v1-v2，v2-v6间铺设线路。,(0),14,(14),7,8,19,(7),(8),(19),11,(11),3.3最短路问题,例3-7某汽车厂使用一台设备，每年年初，部门领导都要决定是继续使用这台旧设备还是购置新设备。如果购置新设备的问题，每年年初就要支付一定的购置费用，如果继续使用旧设备，则需要支付一定的维护费用。现在要设计一套5年内更新该设备的实施方案，使5年内的总支付费用最少。该设备在每年年初的购买价格如表3-5所示，该设备各年累计维护费用如表3-6所示。,3.3最短路问题,表3-5设备各年年初购买价格（万元）,表3-6该设备累计维护费用（万元）,3.3最短路问题,解：构建该问题的网络模型，如图3-12所示,图3-12,V1,V2,V5,V4,V6,V3,11+12=23,12+12=24,13+12=25,15+5=20,12+12=24,33,17,33,44,18,17,43,61,32,11+5=16,3.3最短路问题,设vi表示“第i年年初购入设备”，如v1表示在第1年年初购买设备；由vi指向vj的箭头表示第“i”年年初购买的设备使用到“j”年年初报废，则该设备的使用年限为j-i。如从v1指向v2表示设备在第1年年初购置，在第2年年初报废，使用年限为1年；vi与vj之间的费用取值为在第i年的购买价格与该设备使用年限内的维护费用总和。例如v1与v2之间的费用为11+5=16，其中11为第1年的采购价格，5为一年使用期限内的维护费用。经求解，最佳解决方案是第1年购置新设备，第3年更换设备，这样5年内的费用最少，费用为56万元。,3.4最小支撑树问题,首先介绍一下树、图的支撑树概念，然后引出最小支撑树问题，最后以线路铺设问题为例介绍最小支撑树问题的建模思路与求解分析。最小支撑树问题可以采用避圈法和破圈法等方法进行求解，也可借助相关的运筹学软件包进行求解。,3.4最小支撑树问题,一个连通无圈简单图称为树。若图G的一个支撑图T是树，则称T是图G的一棵支撑树。如图3-8示出了一个图G及其支撑树T1，T2，T3。图3-8,3.4最小支撑树问题,设Tk（V，Ek）是网络N(G，)的一个棵支撑树，则Tk的边集Ek中所有边的权数之和称为树Tk的权，记为。即：,3.4最小支撑树问题,若支撑树T*的权是N的所有支撑树的权中最小者，则称T*为网络N的最小支撑树，简称最小树。即：,如何找出网络的最小树就是最小支撑树问题。,3.4最小支撑树问题,例3-7某自然景区内设有6个服务站和一个网络中心，景区的管理部门决定铺设光纤网络，为各服务站点提供通信线路。管理部门希望这个通信线路的建设成本尽可能低。图3-9表示了服务站和网络中心的分布情况，一个圆圈表示一个服务站（或网络中心），圆圈之间连线上的数字表示两个站点（或站点与网络中心）之间铺设电缆的成本（单位：万元）。请问应如何设计该通讯线路？,3.4最小支撑树问题,图3-9破圈法,3.4最小支撑树问题,图3-10经求解，结果如图3-10所示。此时，铺设总成本最小，为4+5+4+3+4+3=23（万元）。,3.5最大流问题,现实生活中，许多系统中都存在流量问题。如公路系统中存在车辆流，电力系统中存在电流，供水系统中存在水流，信息系统中存在信息流，金融系统中存在现金流等。本节首先介绍网络流、可行流的基本概念，然后引出最大流问题，最后以通讯网络为例介绍最大流问题的建模思路与求解分析。最大流问题可以采用福特-富尔克逊标号等法进行求解，也可借助相关的运筹学软件包进行求解。,3.5最大流问题,(1)容量网络与网络流满足如下规定的网络称之为容量网络。对于一个有向网络N(V，A)，各弧的方向就是流量通过的方向；对网络中的每一弧（vi，vj）A，都赋予一个容量r（vi，vj）rij0，表示容许通过该弧的最大流量；网络有一个始点vs和一个终点vt。除vs和vt外的其余点称之为中间点。,3.5最大流问题,本节所讨论的均为容量网络，以下简称网络。所谓网络流，是指某种流在网络中各弧上的流量的集合。即：其中，表示流经弧的流量。,3.5最大流问题,(2)可行流满足下述条件的流Xxij称为一个可行流：容量限制条件中间点平衡条件上式意味着每个中间点的流入量必须等于其流出量，二者必须平衡。,3.5最大流问题,设以ff(x)表示可行流x从vs到vt的流量，则有：由上式可以看出，可行流x的流量f(x)等于始点的净流出量，也等于终点的净流入量。可行流恒存在，令所有弧的流量均为0，即可得到一个可行流，称为零流，其流量f(X)0。,3.5最大流问题,(3)最大流最大流问题就是求一个可行流，使其流量最大，并满足：最大流问题是一个特殊的线性规划问题。由于其特殊性，用网络分析的方法求解它要比线性规划的一般方法更方便、更直观。,3.5最大流问题,(4)通讯网络的最大流问题例3-8迅达通讯公司使用光缆网络在不同地方传递电话和其他信息。信息通过光缆线和转换点传递。该公司的传送网络如图3-11所示。一个圆圈代表一个转换点，转换点之间的连线上的数字表示该条光缆线的最大信息传递能力。求该通讯网络的最大传输能力。,3.5最大流问题,图3-11Ford-Fulkerson标号法,3.5最大流问题,经求解，各线路的实际传输情况如图3-12所示（括号内第一个数字表示该线路的最大传输能力，第2个数字表示该线路的实际传输情况），该网络的最大传输能力为13个信息单位。,图3-12,3.6网络的计划评审与优化问题,计划评审方法（programevaluationandreviewtechnique，简写为PERT）和关键路线法（criticalpathmethod,简称为CPM）是网络分析的重要组成部分。通常，人们用计划评审法来解决活动时间不确定的项目，用关键路径法来处理活动时间已确定的项目。,3.6网络的计划评审与优化问题,计划评审与关键路径法可以用来解决下述问题：（1）该项目总共是由多少活动组成的，总共需要多少时间？（2）每一个活动的开始和完成日期？（3）哪些活动是“极其重要的”，其完成情况影响整个项目进度，必须严格按计划完成？（4）“不重要”的活动最多可延时多长时间完成，而不致影响整个项目的完成时间？,3.6网络的计划评审与优化问题,3.6.1活动时间确定的项目例3-9某公司决定启动一项可行性研究项目，对某一新设计出来的产品的可行性进行研究。该项目的活动清单表3-5所示。负责人该如何控制项目进度，才能使项目在最短的时间内完成？,3.6网络的计划评审与优化问题,表3-5,3.6网络的计划评审与优化问题,表3-5注明了各项活动的紧前活动和活动时间。对于给定的活动，只有在其紧前活动都已经完成后，该活动才能开始进行。最后一栏列出了完成每项活动需要的时间。例如活动A需要12天，活动B需要8天等等。按照简单的时间相加，估计完成所有活动需要168天。为了更加直观的了解项目的情况，可以构造一个项目网络图。网络图中的每个节点表示每项活动，箭头代表活动之间进行的优先顺序，项目网络图如图3-13所示。,3.6网络的计划评审与优化问题,图3-13,3.6网络的计划评审与优化问题,网络图中所谓路径，就是从起点到终点之间相连节点的序列。为了完成整个项目，网络中将存在多条路径，因此我们需要找出其中最长的路径。关键路径上的活动称为项目的关键活动，是整个项目中的环节。该条路径中的持续时间决定了完成整个项目所必须的最少时间。作为项目管理者需要安排充裕的人力物力等，保证该路径上的活动按期完工。,3.6网络的计划评审与优化问题,确定关键路径:要找出网络图中活动的最早开始时间和最早完成时间。ES一项活动的最早开始时间；EF一项活动的最早完成时间；t活动时间。对于任何活动，最早完成时间为：EF=ES+t,3.6网络的计划评审与优化问题,例如项目A是从项目开始时开始进行，则我们设活动A的最早开始时间为0。而完成项目A需要12天，所以活动A的最早完成时间为EF=ES+t=0+12=12。我们将在每个节点上注明完成活动需要的时间、最早开始时间和最早完成时间。以活动A为例。,3.6网络的计划评审与优化问题,由于每一活动在其紧前活动没有完成的情况下是不能开始的，按照以下规则，我们可以确定每项活动的最早开始时间。每项活动的最早开始时间等于所有紧前活动最早完成时间的最大值。经计算可以得到图中所有的活动的最早开始时间和最早完成时间。项目的最后一项活动K的最早完成时间是89，因此我们知道整个项目的最早完成时间是89天。,3.6网络的计划评审与优化问题,具体计算可见图3-14,图3-14,开始,完成,3.6网络的计划评审与优化问题,现在我们通过从后向前逆推项目网络图找出关键路径。经过前面的推导，已知该项目的最早完成时间是89天，我们就应该从最后结束的活动K开始向前逆推。首先要先明确几个变量，设LS每项活动的最晚开始时间LF每项活动的最晚完成时间t活动时间。对于任何活动，最晚开始时间为：LS=LFt,3.6网络的计划评审与优化问题,以活动K为例，可知活动K的最晚完成时间与最早完成时间相等，LF=EF=89，活动时间是t=19。因此活动K的最晚开始时间就应该为LS=LF-t=89-19=70。将最晚开始时间LS与最晚完成时间LF写在节点K最早开始时间（ES）和最早完成时间（EF）下边的空格处有。,3.6网络的计划评审与优化问题,按照以下规则，可以确定每项活动的最晚完成时间。每项活动的最晚完成时间等于其所有紧后活动最晚开始时间的最小值。依据上述规则，可依次计算各个活动的最晚开始时间和最晚完成时间。如图3-15所示。,3.6网络的计划评审与优化问题,图3-15,开始,完成,7089,6670,6070,5560,4366,4355,1543,815,1555,315,08,3.6网络的计划评审与优化问题,在进行接下来的工作之前，我们先引入一个新的概念松弛变量。松弛变量是指延迟某项活动的活动时间而又不影响整个项目整体完工时间。每项活动的松弛变量计算公式如下：松弛变量=LS-ES=LF-EF例3-9的活动松弛变量计算结果如表3-6所示：,3.6网络的计划评审与优化问题,表3-6,3.6网络的计划评审与优化问题,3.6.2活动时间不确定的项目现实生活中的许多项目，如新产品的研发，在项目的进行过程中会有很多不可预测的事情发生，所以在此类活动的安排中，项目负责人必须将这些不确定的因素考虑进去。依然上节中可行性研究项目为例，若项目中的每个活动的时间，只能够用一个适当的值域来描述，而不是一个具体的预计值。但公司希望能将项目从开始到完成的时间控制在90天之内，请问是否有这样的可能性？若有，可能性为多少？,3.6网络的计划评审与优化问题,下面我们对活动时间不确定的项目进行计划安排，把时间不确定的因素考虑在内，得到一些基本信息：乐观时间a在最佳状态下完成某项活动的时间。悲观时间b在最不利的条件下完成某项活动的时间。最大可能时间m一般情况下完成某项活动的时间。由这些信息组成的网络图称为概率型网络图。该项目的各项活动的三种时间估算如表3-7所示：,3.6网络的计划评审与优化问题,表3-7,3.6网络的计划评审与优化问题,以活动A对表3-9中所列出的时间进行说明。对于A，乐观时间a=10，最大可能时间m=12,悲观时间b=14，则完成该活动的平均时间和方差的计算公式如下：,3.6网络的计划评审与优化问题,由上述两个式子可以看出来，乐观时间和悲观时间的差值，是影响偏差的主要原因。两者的差值越大，说明该活动的不确定性越大。对活动A，平均时间和方差经计算得：,3.6网络的计划评审与优化问题,利用上述方法得项目中的所有活动的平均时间和方差，如表3-8所示。,表3-8,3.6网络的计划评审与优化问题,在活动时间不确定的情况下，对于关键路径的计算只是确定了项目平均完成时间，这与实际的项目所需时间会有偏差。活动的方差越大说明不确定性越大，项目负责人应该对方差较大的活动进行严密监测。利用上一节所提到的从前到后顺推方法，我们可以求出每项活动的最早开始时间ES、最早完成时间EF、最晚开始时间LS和最晚完成时间LF。具体数值如图3-16所示。,3.6网络的计划评审与优化问题,图3-16,开始,完成,6988,6569,5969,5459,4265,4254,1542,815,1454,214,08,3.6网络的计划评审与优化问题,根据现有的信息，为这个项目制定具体的安排。将有关活动的所有信息以表格的形式列出，如表3-8所示。,表3-8,3.6网络的计划评审与优化问题,由表3-8可知，该