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

管理决策曹媛媛[e-mail]22019/8/18第七讲网络分析图论(GraphTheory)是运筹学的一个分支，已广泛应用在物理学、化学、控制论、信息论、科学管理、计算机等各个领域中。网络分析（NetworkAnalysis）作为图论的一个重要内容，已成为对各种系统进行分析、研究和管理的重要工具。本章主要介绍运输问题、最短路问题、最小支撑树问题、最大流问题，以及网络计划评审与优化问题。第七讲网络分析图与网络的基本概念图论中的图，是反映现实世界中具体事物及其相互关系的一种抽象工具,它比地图、分子结构图、电路图等更抽象。图的定义：简单的说，一个图是由一些点(Vertices)及点间的连线(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试用一个图来表示大连、北京、深圳、上海四城市之间的民航客机通航情况。解：设v1，v2，v3，v4分别表示大连、北京、深圳、上海四市，则他们之间的通航情况可表示为一个无向图：G=(V，E)。v1v2v3v4e1e5e2e6e4e3V={v1，v2，v3，v4}E={e1，e2，e3，e4，e5，e6}e1={v1，v2}，e2={v1，v3}，e3={v1，v4}，e4={v2，v3}，e5={v2，v4}，e6={v3，v4}第七讲网络分析图与网络的基本概念——有向图例3-2有A、B、C、D四支篮球队，进行单循环比赛，比赛情况如表所示。试用一个图表示各队之间的胜负关系。比赛球队获胜球队A——BAA——CAA——DDB——CBB——DDC——DC解：设v1，v2，v3，v4分别表示球队A、B、C、D，其相互间的胜负关系可表示为一个有向图：D=(V，A)，从vi连接到vj的弧表示vi代表的球队胜vj代表的球队。v1v2v3v4a5a2a1a6a3a4其中V={v1，v2，v3，v4}A={a1，a2，a3，a4，a5，a6}a1={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的关联边。若一条边的两个端点相同，则称该边为环。如e7。若两个端点之间不止一条边，则称具有多重边；一个无环也无多重边的图称为简单图。v5v1v2e1e8e3e2e4e6e5e7v3v4第七讲网络分析图与网络的基本概念几个基本概念图G=(V，E)中，设；；；则交替序列称为一条从到的链，简记为若＝则称为闭链，否则称为开链。若中的边均不相同，则称为简单链；若中所有结点也均不同，则称为初等链。若一条闭链中，除＝外，任意两点均不相同，则称为一个圈。若图G中，任意两点间至少存在一条链，则称图G为连通图，否则称为不连通图。Vvvvkiii...,10Eeeekjjj...,10),(1tttiijvve),,2,1(ktkkijjijiveevev,,,,,,21100ivkivkiiivvvL100ivkivkiv0iv第七讲网络分析图与网络的基本概念几个基本概念如图，＝v4v7v5v6v7v8是简单链，＝v4v5v7v6v8是初等链，＝v4v5v6v8v7v4是一个圈，但＝v4v7v6v8v7v5v4仅为一条闭链，而不是圈。左图是连通图，而右图是不连通图，因为v1与v4之间不存在链。1423v1v2v3v4v5v6v7v8e1e2e3e4e5e7e6e8e10e9v5v1v2e1e8e3e2e4e6e5e7v3v4第七讲网络分析图与网络的基本概念几个基本概念设有图G=(V，E)和图G’=(V’，E’)，若V’＝V，E’E，则称G’是G的一个支撑子图或支撑图。图中(a)，(b)，(c)均为(a)的支撑子图，但(d)不是(a)的支撑子图，因为(d)比(a)少一个点v1。●●●v1v2v3v4e4e1e2e3e1v1e4v4e3v2v3v4v2v3e5e5v2v3e3v4(a)(b)(c)(d)v1第七讲网络分析图与网络的基本概念几个基本概念若把一个有向图D中所有弧的方向去掉，即每一条弧都用相应的无向边代替，所得到一个无向图称为该有向图D的基础图，记为G(D)。如图中(b)为(a)的基础图。v1v3v2v1v2v4v3a1a3a4a5e1e2a2e3e4e5（a）图D（b）基础图G（D）v4第七讲网络分析图与网络的基本概念几个基本概念若交替序列是有向图D＝(V，A)的一条链，并且有：；则称是图D的一条从到的路，简记为：，若＝，则称是图D的一条回路，否则称为开路。对无向图G而言，链和路(闭链和回路)这两个概念是一致的。如图，＝v2v4v1v3是一条开路，＝v4v1v3v4是一条回路；但＝v2v1v4v3和＝v2v4v1v2虽然分别是G(D)的开路和回路，却不是D的路，而仅是D的链和圈。kkijjijivaavav,...,,,2110),(1tttiijvva),,2,1(kt0ivkivkiiivvv103412v1v3v2v1v2v4v3a1a3a4a5e1e2a2e3e4e5（a）图D（b）基础图G（D）v40ivkiv第七讲网络分析图与网络的基本概念几个基本概念若给一个图中的每一条边（或弧）都赋予一个实数=(vi，vj)，所得的图称为一个赋权网络图。赋权无向图和赋权有向图统称为网络，记为N。这里，称为边(vi，vj)的权数（或权）。一般来讲，图论中所讨论的图，特别是在应用图论中所讨论的图多数是网络。ijij第七讲网络分析运输问题运输问题一般描述为：一种物资有m个产地，其产量分别为ai，有n个销地，其销量分别为bj；从Ai至Bj的运价为cij，问如何设计调运方案才能使总运费最少？产销平衡问题当总产量等于总销量，即：时，称为产销平衡的运输问题，简称平衡问题。产销不平衡问题当总产量大于总销量，即时，称为产大于销的运输问题；当总产量小于总销量，即时，称为产小于销的运输问题。产大于销的运输问题和产小于销的运输问题统称为产销不平衡问题。),,2,1(miAi),,2,1(njBjKnjjmiiba11njjmiiba11njjmiiba11第七讲网络分析运输问题——产销平衡问题例3-3有A1，A2，A3三个水泥厂，每天要把生产的水泥运往B1，B2两地。各厂的产量、各地的需求量（销量）以及各厂地间的运价见表3-2。问如何设计调运方案才能使总运费最少？运价（元/吨）（cij）产量（ai）B1B2A112015011A214513015A31351409销量（bj）1421解：因为=11+15+9=35，=14+21=35，所以这是一个产销平衡问题。miia1njjb1njjmiiba11目标函数为：其中xij为Ai至Bj的运量，因为某产地运往各销地的运量之和应等于该产地的产量，所以有:。又因各产地运往某销地的运量之和应等于该销地的销量（需求量），所以有:miijnjijxcz11min),2,1(,1miaxinjij),2,1(,1njbxjmiij第七讲网络分析运输问题——产销平衡问题产销平衡运输问题的一般模型为：应用到本例中的实例模型为：经求解，最优解：，可知，由A1运往B1地11吨，A2运往B2地15吨，A3运往B1地3吨，A3运往B2地6吨，这样安排总运费最少，最少总运费为4515元。),2,1,2,1(0),2,1(),2,1(.t.smin1111njmixnjbxmiaxxczijjmiijinjijmiijnjijKKKK)2,13,2,1(0211491511.t.s140135130145150120min322212312111323122211211323122211211jixxxxxxxxxxxxxxxxxxxzij；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，所以这是一个产大于销的问题。miia1njjb1目标函数为：其中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(0),2,1(),2,1(.t.smin1111njmixnjbxmiaxxczijjmiijinjijmiijnjijKKKK)2,13,2,1(0201391511.t.s140135130145150120min322212312111323122211211323122211211jixxxxxxxxxxxxxxxxxxxzij；TX)5,2,15,0,0,11(*4240*z第七讲网络分析运输问题——转运问题前面介绍的运输问题，都是将物资直接由产地运往销地，但是，实际中很多的运输问题是先将物资由产地运往某个或某些转运站（转运站在现实情况中往往表现为仓库），再由转运站运往销地，这类运输问题不仅要求总运费最少，而且要同时选出最优运输路线，这就是转运问题。第七讲网络分析运输问题——转运问题例3-5有A1，A2，A3三个水泥厂，每天要把生产的水泥先运往C1，C2两个仓库，再由仓库运往B1，B2两地。各厂至各仓库、各仓库至各销地的运价（单位：元/吨）见表3-4，每个产地的产量（单位：吨/天）和每个销地的销量（单位：吨/天）分别在左侧和右侧做了标注。问如何设计调运方案才能使总运费最少？C1C211A19010015A2105929A310283B114B221C17267C25864解：该例中共有10条运输路线，分别是A1-C1，A1-C2，A2-C1，A2-C2，A3-C1，A3-C2，C1-B1，C1-B2，C2-B1，C2-B2，我们分别用数字1~7来表示A1、A2、A3、C1、C2、B1、B2，则这十条运输路线上的运量可分别用x14，x15，x24，x25，x34，x35，x46，x47，x56，x57来表示。第七讲网络分析运输问题