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

《管理决策 第七讲 网络分析与应用》由会员分享，可在线阅读，更多相关《管理决策 第七讲 网络分析与应用（38页珍藏版）》请在金锄头文库上搜索。

1、管理决策,曹媛媛 ,2,2018/10/15,第七讲 网络分析,图论(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，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四支篮球队，进行单循环比赛，比赛情况如表所示。试用一个图表示各队之间的胜负关系。,解：设v1，v2，v3，v4分别表示球队A、B、C、D，其相互间的胜负关系可表示为一个有向图： D=(V，A)

4、，从vi连接到vj的弧表示vi代表的球队胜vj代表的球队。,其中 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。若两个端点之间不止一条边，则称具有多重边；一个无环也无多重边的图称为简单图。,第七讲

5、 网络分析,图与网络的基本概念 几个基本概念 图G=(V，E)中，设 ； ；则交替序列 称为一条从 到 的链，简记为 若 则称为闭链，否则称 为开链。 若 中的边均不相同，则称 为简单链； 若 中所有结点也均不同，则称 为初等链。 若一条闭链 中，除 外，任意两点均不相同，则称 为一个圈。 若图G中，任意两点间至少存在一条链，则称图G为连通图，否则称为不连通图。,第七讲 网络分析,图与网络的基本概念 几个基本概念 如图， v4v7v5v6v7v8是简单链，v4v5v7v6v8是初等链， v4v5v6v8v7v4是一个圈， 但 v4v7v6v8v7v5v4仅为一条闭链，而不是圈。 左图是连通图，

6、而右图是不连通图，因为v1与v4之间不存在链。,第七讲 网络分析,图与网络的基本概念 几个基本概念 设有图G=(V，E)和图G=(V，E)，若VV，E E，则称G是G的一个支撑子图或支撑图。图中 (a)，(b)，(c)均为(a)的支撑子图，但(d)不是(a)的支撑子图，因为(d)比(a)少一个点v1。,第七讲 网络分析,图与网络的基本概念 几个基本概念 若把一个有向图D中所有弧的方向去掉，即每一条弧都用相应的无向边代替，所得到一个无向图称为该有向图D的基础图，记为G(D)。 如图中(b)为(a)的基础图。,第七讲 网络分析,图与网络的基本概念 几个基本概念 若交替序列 是有向图D(V，A)的一

7、条链，并且有： ；则称 是图D的一条从 到 的路，简记为： ，若 ，则称是图D的一条回路，否则称为开路。 对无向图G而言，链和路(闭链和回路)这两个概念是一致的。 如图， v2v4v1v3是一条开路， v4v1v3v4是一条回路；但 v2v1v4v3 和 v2v4v1v2虽然分别是G(D)的开路和回路，却不是D的路，而仅是D的链和圈。,第七讲 网络分析,图与网络的基本概念 几个基本概念若给一个图中的每一条边（或弧）都赋予一个实数 = (vi，vj)，所得的图称为一个赋权网络图。赋权无向图和赋权有向图统称为网络，记为N。这里， 称为边(vi，vj)的权数（或权）。 一般来讲，图论中所讨论的图，特

8、别是在应用图论中所讨论的图多数是网络。,第七讲 网络分析,运输问题运输问题一般描述为：一种物资有m个产地 ，其产量分别为ai，有n个销地 ，其销量分别为bj；从Ai至Bj的运价为cij，问如何设计调运方案才能使总运费最少？ 产销平衡问题当总产量等于总销量，即： 时，称为产销平衡的运输问题，简称平衡问题。 产销不平衡问题当总产量大于总销量，即 时，称为产大于销的运输问题；当总产量小于总销量，即 时，称为产小于销的运输问题。产大于销的运输问题和产小于销的运输问题统称为产销不平衡问题。,第七讲 网络分析,运输问题产销平衡问题例3-3 有A1，A2，A3三个水泥厂，每天要把生产的水泥运往B1，B2两地

9、。各厂的产量、各地的需求量（销量）以及各厂地间的运价见表3-2。问如何设计调运方案才能使总运费最少？,解：因为 =11+15+9=35，= 14+21=35，所以这是一个产销平衡问题。,目标函数为：其中xij为Ai至 Bj的运量，因为某产地运往各销地的运量之和应等于该产地的产量，所以有 : 。又因各产地运往某销地的运量之和应等于该销地的销量（需求量），所以有:,第七讲 网络分析,运输问题产销平衡问题 产销平衡运输问题的一般模型为： 应用到本例中的实例模型为：经求解，最优解： ，可知，由A1运往 B1地11吨，A2运往 B2 地15吨，A3运往 B1 地3吨，A3运往 B2 地6吨，这样安排总运

10、费最少，最少总运费为4515元。,第七讲 网络分析,运输问题产销不平衡问题例3-4 有A1，A2，A3三个水泥厂，每天要把生产的水泥运往B1，B2两地。各厂的产量、各地的需求量（销量）以及各厂地间的运价见表。问如何设计调运方案才能使总运费最少？,解：因为 =11+15+9=35，= 13+20=33，所以这是一个产大于销的问题。,目标函数为：其中xij为Ai至 Bj的运量，因为某产地运往各销地的运量之和应不大于该产地的产量，所以有 : 。又因各产地运往某销地的运量之和应等于该销地的销量（需求量），所以有:,第七讲 网络分析,运输问题产销不平衡问题 产大于销运输问题的一般模型为： 应用到本例中的

11、实例模型为：经求解，最优解： ，可知，由A1运往 B1 地11吨，A2运往 B2 地15吨，A3运往 B1 地2吨，A3运往 B2 地5吨，这样安排总运费最少，最少总运费为4240元。,第七讲 网络分析,运输问题转运问题前面介绍的运输问题，都是将物资直接由产地运往销地，但是，实际中很多的运输问题是先将物资由产地运往某个或某些转运站（转运站在现实情况中往往表现为仓库），再由转运站运往销地，这类运输问题不仅要求总运费最少，而且要同时选出最优运输路线，这就是转运问题。,第七讲 网络分析,运输问题转运问题 例3-5 有A1，A2，A3三个水泥厂，每天要把生产的水泥先运往C1，C2两个仓库，再由仓库运往

12、B1，B2两地。各厂至各仓库、各仓库至各销地的运价（单位：元/吨）见表3-4，每个产地的产量（单位：吨/天）和每个销地的销量（单位：吨/天）分别在左侧和右侧做了标注。问如何设计调运方案才能使总运费最少？,解：该例中共有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来表示。,第七讲 网络分析,运输问题转运问

13、题 目标函数为：minz=90x14+100x15+105x24+92x25+102x34 +83x35+72x46+67x47+58x56+64x57 由于这是一个产销平和问题，对于产地，物资的运出量应等于产地的产量，因此 ，对A1有：对A2有：对A3有： 对于转运站（仓库），物资的运入量应等于运出量，因此:对C1有：对C2有： 对于销地，物资的运入量应等于销地的需求量，因此:对B1有：对B2有：,第七讲 网络分析,运输问题转运问题 综上，建立此例的数学模型为：经求解，最优解如下：,第七讲 网络分析,运输问题转运问题 归纳出转运问题的一般线性规划模型这里xij表示从节点i到j的运量，cij表

14、示从i到j的运价，ai表示产地i的产量，bj表示销地j的销量（需求量）。,第七讲 网络分析,最短路问题最短路问题一般描述为：在一网络中，给定两个点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表示乙地，点之间的连线（边）表示两地公路，边上的数值表示两地间公路的长度（单位：千米），问如何铺设能使甲、乙两地的电缆长度最短？,