管理决策第七讲网络分析与应用.pptx

《管理决策第七讲网络分析与应用.pptx》由会员分享，可在线阅读，更多相关《管理决策第七讲网络分析与应用.pptx（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、管理决策曹媛媛曹媛媛 22022-4-25第七讲 网络分析图论(Graph Theory) 是运筹学的一个分支，已广泛应用在物理学、化学、控制论、信息论、科学管理、计算机等各个领域中。网络分析（Network Analysis） 作为图论的一个重要内容，已成为对各种系统进行分析、研究和管理的重要工具。本章主要介绍运输问题、最短路问题、最小支撑树问题、最大流问题，以及网络计划评审与优化问题。第七讲 网络分析图与网络的基本概念图论中的图，是反映现实世界中具体事物及其相互关系的一种抽象工具,它比地图、分子结构图、电路图等更抽象。 图的定义：图的定义：简单的说，一个图是由一些点(Vertices)及点

2、间的连线(Edges)所组成的。点可以作为现实世界中事物的抽象，而点间的连线表示事物间的关系。无向图：如果一个图由点及边所构成，则称之为无向图 ，记为G=(V，E)。其中，V是一个有限非空的点集合，称为G的点集，一般表示为V=v1，v2，vn；E是一个边集合，称为G的边集，一条连接vi和vj的边一般表示为一个无序对e=（vi，vj）。有向图：如果一个图由点及弧所构成，则称之为有向图，记为D(V，A)。其中，V是点的集合；A是弧的集合，一条从vi连接到vj的弧一般表示为一个有序对a(vi，vj)。 第七讲 网络分析图与网络的基本概念 无向图无向图 例3-1 试用一个图来表示大连、北京、深圳、上海

3、四城市之间的民航客机通航情况。 解： 设v1，v2，v3，v4分别表示大连、北京、深圳、上海四市，则他们之间的通航情况可表示为一个无向图：G=(V，E) 。 V=v1，v2，v3，v4E=e1，e2，e3，e4，e5，e6e1=v1，v2，e2=v1，v3，e3=v1，v4，e4=v2，v3，e5=v2，v4，e6=v3，v4第七讲 网络分析图与网络的基本概念 有向图有向图 例3-2 有A、B、C、D四支篮球队，进行单循环比赛，比赛情况如表所示。试用一个图表示各队之间的胜负关系。 比赛球队比赛球队获胜球队获胜球队A AB BA AA AC CA AA AD DD DB BC CB BB BD

4、DD DC CD DC C解：设v1，v2，v3，v4分别表示球队A、B、C、D，其相互间的胜负关系可表示为一个有向图： D=(V，A)，从vi连接到vj的弧表示vi代表的球队胜vj代表的球队。其中V=v1，v2，v3，v4A=a1，a2，a3，a4，a5，a6a1=v1，v2，a2=v1，v3，a3=v4，v1，a4=v2，v3，a5=v4，v2，a6=v3，v4第七讲 网络分析图与网络的基本概念几个基本概念 若有e=（vi，vj），则称vi，vj是e的端点，也称点vi与vj相邻，称e是vi，vj的关联边。如图中，v1与v4是e5的端点，点v2与v3相邻，e6是v4与v5的关联边。 若一条边

5、的两个端点相同，则称该边为环。如e7。 若两个端点之间不止一条边，则称具有多重边；一个无环也无多重边的图称为简单图。第七讲 网络分析图与网络的基本概念几个基本概念图G=(V，E)中，设 ； ； ；则交替序列 称为一条从 到 的链，简记为若 则称为闭链，否则称 为开链。若 中的边均不相同，则称 为简单链；若 中所有结点也均不同，则称 为初等链。若一条闭链 中，除 外，任意两点均不相同，则称 为一个圈。若图G中，任意两点间至少存在一条链，则称图G为连通图，否则称为不连通图。Vvvvkiii.,10Eeeekjjj.,10),(1tttiijvve), 2 , 1(ktkkijjijiveevev,

6、21100ivkivkiiivvvL100ivkivkiv0iv第七讲 网络分析图与网络的基本概念几个基本概念如图， v4v7v5v6v7v8是简单链， v4v5v7v6v8是初等链， v4v5v6v8v7v4是一个圈，但 v4v7v6v8v7v5v4仅为一条闭链，而不是圈。左图是连通图，而右图是不连通图，因为v1与v4之间不存在链。1423第七讲 网络分析图与网络的基本概念几个基本概念设有图G=(V，E)和图G=(V，E)，若VV，E E，则称G是G的一个支撑子图或支撑图。图中 (a)，(b)，(c)均为(a)的支撑子图，但(d)不是(a)的支撑子图，因为(d)比(a)少一个点v1。第七讲

7、网络分析图与网络的基本概念几个基本概念若把一个有向图D中所有弧的方向去掉，即每一条弧都用相应的无向边代替，所得到一个无向图称为该有向图D的基础图，记为G(D)。如图中(b)为(a)的基础图。第七讲 网络分析图与网络的基本概念几个基本概念若交替序列 是有向图D(V，A)的一条链，并且有： ；则称 是图D的一条从 到 的路，简记为： ，若 ，则称是图D的一条回路，否则称为开路。对无向图G而言，链和路(闭链和回路)这两个概念是一致的。如图， v2v4v1v3是一条开路， v4v1v3v4是一条回路；但 v2v1v4v3 和 v2v4v1v2虽然分别是G(D)的开路和回路，却不是D的路，而仅是D的链和

8、圈。kkijjijivaavav,.,2110),(1tttiijvva),2, 1(kt0ivkivkiiivvv1034120ivkiv第七讲 网络分析图与网络的基本概念几个基本概念 若给一个图中的每一条边（或弧）都赋予一个实数 = (vi，vj)，所得的图称为一个赋权网络图。赋权无向图和赋权有向图统称为网络，记为N。这里， 称为边(vi，vj)的权数（或权）。 一般来讲，图论中所讨论的图，特别是在应用图论中所讨论的图多数是网络。ijij第七讲 网络分析运输问题 运输问题一般描述为：一种物资有m个产地 ，其产量分别为ai，有n个销地 ，其销量分别为bj；从Ai至Bj的运价为cij，问如何设

9、计调运方案才能使总运费最少？产销平衡问题 当总产量等于总销量，即： 时，称为产销平衡的运输问题，简称平衡问题。产销不平衡问题 当总产量大于总销量，即 时，称为产大于销的运输问题；当总产量小于总销量，即 时，称为产小于销的运输问题。产大于销的运输问题和产小于销的运输问题统称为产销不平衡问题。 ), 2 , 1(miAi), 2 , 1(njBjKnjjmiiba11njjmiiba11njjmiiba11第七讲 网络分析运输问题产销平衡问题 例3-3 有A1，A2，A3三个水泥厂，每天要把生产的水泥运往B1，B2两地。各厂的产量、各地的需求量（销量）以及各厂地间的运价见表3-2。问如何设计调运方

10、案才能使总运费最少？运价（元运价（元/吨）（吨）（cij）产量（产量（ai）B1B2A112015011A214513015A31351409销量（销量（bj）1421 解：因为 =11+15+9=35， = 14+21=35， 所以这是一个产销平衡问题。miia1njjb1njjmiiba11目标函数为： 其中xij为Ai至 Bj的运量，因为某产地运往各销地的运量之和应等于该产地的产量，所以有 : 。 又因各产地运往某销地的运量之和应等于该销地的销量（需求量），所以有: miijnjijxcz11min), 2 , 1( ,1miaxinjij), 2 , 1( ,1njbxjmiij第七讲

11、 网络分析运输问题产销平衡问题产销平衡运输问题的一般模型为：应用到本例中的实例模型为：经求解，最优解： ，可知，由A1运往 B1地11吨，A2运往 B2 地15吨，A3运往 B1 地3吨，A3运往 B2 地6吨，这样安排总运费最少，最少总运费为4515元。 ), 2 , 1, 2 , 1(0), 2 , 1(), 2 , 1(. t . smin1111njmixnjbxmiaxxczijjmiijinjijmiijnjijK?KKK)2 , 13 , 2 , 1(0211491511. t . s140135130145150120min322212312111323122211211323

12、122211211jixxxxxxxxxxxxxxxxxxxzij；TX) 6 , 3 ,15, 0 , 0 ,11(*4515*z第七讲 网络分析运输问题产销不平衡问题 例3-4 有A1，A2，A3三个水泥厂，每天要把生产的水泥运往B1，B2两地。各厂的产量、各地的需求量（销量）以及各厂地间的运价见表。问如何设计调运方案才能使总运费最少？运价（元运价（元/吨）（吨）（cij）产量（产量（ai）B1B2A112015011A214513015A31351409销量（销量（bj）1320 解：因为 =11+15+9=35， = 13+20=33， 所以这是一个产大于销的问题。miia1njjb1

13、目标函数为： 其中xij为Ai至 Bj的运量，因为某产地运往各销地的运量之和应不大于该产地的产量，所以有 : 。 又因各产地运往某销地的运量之和应等于该销地的销量（需求量），所以有: miijnjijxcz11min), 2 , 1( ,1miaxinjijK), 2 , 1( ,1njbxjmiij第七讲 网络分析运输问题产销不平衡问题产大于销运输问题的一般模型为：应用到本例中的实例模型为：经求解，最优解： ，可知，由A1运往 B1 地11吨，A2运往 B2 地15吨，A3运往 B1 地2吨，A3运往 B2 地5吨，这样安排总运费最少，最少总运费为4240元。 ), 2 , 1, 2 , 1

14、(0), 2 , 1(), 2 , 1(. t . smin1111njmixnjbxmiaxxczijjmiijinjijmiijnjijK?KKK)2 , 13 , 2 , 1(0201391511. t . s140135130145150120min322212312111323122211211323122211211jixxxxxxxxxxxxxxxxxxxzij；TX)5 , 2 ,15, 0 , 0 ,11(*4240*z第七讲 网络分析运输问题转运问题 前面介绍的运输问题，都是将物资直接由产地运往销地，但是，实际中很多的运输问题是先将物资由产地运往某个或某些转运站（转运站在现

15、实情况中往往表现为仓库），再由转运站运往销地，这类运输问题不仅要求总运费最少，而且要同时选出最优运输路线，这就是转运问题。 第七讲 网络分析运输问题转运问题例3-5 有A1，A2，A3三个水泥厂，每天要把生产的水泥先运往C1，C2两个仓库，再由仓库运往B1，B2两地。各厂至各仓库、各仓库至各销地的运价（单位：元/吨）见表3-4，每个产地的产量（单位：吨/天）和每个销地的销量（单位：吨/天）分别在左侧和右侧做了标注。问如何设计调运方案才能使总运费最少？ C1C211 A19010015 A2105929 A310283B1 14B2 21C17267C25864 解：该例中共有10条运输路线，分

16、别是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来表示。第七讲 网络分析运输问题转运问题目标函数为： minz=90 x14+100 x15+105x24+92x25+102x34 +83x35+72x46+67x47+58x56+64x57由于这是一个产销平和问题，对于产地，物资的运出量应等于产地的产量，因此 ，对A1有：

17、 对A2有： 对A3有： 对于转运站（仓库），物资的运入量应等于运出量，因此: 对C1有： 对C2有：对于销地，物资的运入量应等于销地的需求量，因此: 对B1有： 对B2有：111514 xx152524 xx93534 xx4746342414xxxxx5756352515xxxxx145646xx215747xx第七讲 网络分析运输问题转运问题综上，建立此例的数学模型为：经求解，最优解如下：0,211491511. t . s645867728310292105100 90 min 575647463534252415145747564657563525154746342414353425

18、24151457564746353425241514xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzTX)10,14,11,0,9 ,0,15,0,0,11(*5306*z第七讲 网络分析运输问题转运问题归纳出转运问题的一般线性规划模型这里xij表示从节点i到j的运量，cij表示从i到j的运价，ai表示产地i的产量，bj表示销地j的销量（需求量）。jiijjijijijijiijijijijxbxxxxaxxxcz和对于所有的销地节点转运节点起点节点运出弧运入弧运入弧运出弧运入弧运出弧所有弧0)(0)(. t . smin第七讲 网络分析最短路问题 最短路问题

19、一般描述为：在一网络中，给定两个点vs和vt，找到一条从vs到vt的路，使这条路上所有弧的权数之和最小，这条路就是vs到vt的最短路。这条路上所有弧的权数之和称为vs到vt的距离。 最短路线问题可以采用标号法等方法进行求解，也可借助相关的运筹学软件包进行求解。这里xij表示从节点i到j的运量，cij表示从i到j的运价，ai表示产地i的产量，bj表示销地j的销量（需求量）。例 某电信公司计划在甲、乙两地铺设通信电缆，图是甲、乙两地间的交通图，图中 v1，v2，v3，v4，v5，v6表示6个地名点，其中v1 表示甲地，v6表示乙地，点之间的连线（边）表示两地公路，边上的数值表示两地间公路的长度（单

20、位：千米），问如何铺设能使甲、乙两地的电缆长度最短？ 经标号法求解最短路是v1-v2-v6，最短距离是7+12=19千米，所以应在v1-v2，v2-v6间铺设线路。(0)14(14)7819(7)(8)(19)11(11)练习：最短路为提高运输效率，请找出公司（节点1）到零售店（节点11）之间的最短路径。第七讲 网络分析最小支撑树问题 一个连通无圈简单图称为树。若图G的一个支撑图T是树，则称T是图G的一棵支撑树。 如图示出了一个图G及其支撑树T1，T2，T3。 第七讲 网络分析最小支撑树问题 设Tk（V，Ek）是网络N(G， )的一个棵支撑树，则Tk的边集Ek中所有边的权数之和称为树Tk的权，

21、记为 。 即： 若支撑树T*的权 是N的所有支撑树的权中最小者，则称T*为网络N的最小支撑树，简称最小树。 即： 如何找出网络的最小树就是最小支撑树问题。最小支撑树问题可以采用避圈法和破圈法等方法进行求解，也可借助相关的运筹学软件包进行求解。kTkEeekT)( *T)(min)(*kTTTTk第七讲 网络分析最小支撑树问题 例某自然景区内设有6个服务站和一个网络中心，景区的管理部门决定铺设光纤网络，为各服务站点提供通信线路。管理部门希望这个通信线路的建设成本尽可能低。图表示了服务站和网络中心的分布情况，一个圆圈表示一个服务站（或网络中心），圆圈之间连线上的数字表示两个站点（或站点与网络中心）

22、之间铺设电缆的成本（单位：万元）。问应如何设计该通讯线路？ 经求解，结果如图所示，铺设总成本最小，为4+5+4+3+4+3=23（万元）。练习：最小支撑树为节约成本，请设计一个网络系统，使得城市1与乡镇2-10之间都有光纤连通，且铺设总长度最少。地点地点23456789101949151511161622281612810191420369117121115441611815175712614136103715779108111299第七讲 网络分析最大流问题 现实生活中，许多系统中都存在流量问题。如公路系统中存在车辆流，电力系统中存在电流，供水系统中存在水流，信息系统中存在信息流，金融系统中

23、存在现金流等。例 迅达通讯公司使用光缆网络在不同地方传递电话和其他信息。信息通过光缆线和转换点传递。该公司的传送网络如图所示。一个圆圈代表一个转换点，转换点之间的连线上的数字表示该条光缆线的最大信息传递能力。求该通讯网络的最大传输能力。 第七讲 网络分析最大流问题 (1) 容量网络与网络流 满足如下规定的网络称之为容量网络。 对于一个有向网络N(V，A)，各弧的方向就是流量通过的方向； 对网络中的每一弧（vi，vj）A，都赋予一个容量r（vi，vj）rij 0，表示容许通过该弧的最大流量； 网络有一个始点vs和一个终点vt。除vs和vt外的其余点称之为中间点。 所谓网络流，指某种流在网络中各弧

24、上的流量的集合。即： 其中， 表示流经弧 的流量。,|AvvxXjiij）（ijx）（jivv ,第七讲 网络分析最大流问题(2) 可行流 满足下述条件的流Xxij称为一个可行流： 容量限制条件 中间点平衡条件 上式意味着每个中间点的流入量必须等于其流出量。设以ff (x)表示可行流x从vs到vt的流量，则有： 由上式可以看出，可行流x的流量f (x)等于始点的净流出量，也等于终点的净流入量。可行流恒存在，令所有弧的流量均为0，即可得到一个可行流，称为零流，其流量 f (X) 0。 Avvrxjiijij),( ,0),(0tsixxjjijijtifsifxxjjijij当当第七讲 网络分析

25、最大流问题(3) 最大流 最大流问题就是求一个可行流，使其流量最大，并满足： 最大流问题是一个特殊的线性规划问题。由于其特殊性，用网络分析的方法求解它要比线性规划的一般方法更方便、更直观。最大流问题可以采用福特-富尔克逊标号等法进行求解，也可借助相关的运筹学软件包进行求解。 Avvrxtiftsisifxxfjiijijjjjiij),(,0, 0,s.t.max第七讲 网络分析最大流问题第七讲 网络分析最大流问题 经求解，各线路的实际传输情况如图所示（括号内第一个数字表示该线路的最大传输能力，第2个数字表示该线路的实际传输情况），该网络的最大传输能力为13个信息单位。练习：最大流求输油管道网地点1到地点6的最大流量。第七讲 网络分析小结图与网络的基本概念运输问题产销平衡问题产销不平衡问题转运问题最短路问题最小支撑树问题最大流问题第七讲 网络分析本节结束本节结束 谢谢！谢谢！Thank you for your attention! Any questions?Thank you for your attention! Any questions?