管理运筹学第10章图与网络规划

1、管理运筹学第10章 图与网络规划图论Graph Theory本身是应用数学的一部份，以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论的第一本专著是匈牙利数学家O.Konig著的“有限图与无限图的理论”，发表于1936年。从1936年欧拉的第一篇论文到这本专著的200多年的时间里，图论的发展是比较缓慢的。直到20世纪中叶，随着电子计算机的出现和离散数学的广泛应用，图论得到快速的发展，被广泛应用于管理科学、计算机科学、心理学及工程技术管理中，并取得了丰硕的成果。10

2、.1 图与网络的基本知识10.1.1 基本概念定义10.1 一个图是由点集V= 和V中元素的无序对的一个集合E= 所构成的二元组，记为 ,V中的元素 叫做顶点，E中的元素 叫做边。当V，E为有限集合时，G称为有限图，否则，称为无限图。本书只讨论有限图。【例10-1】 在图103中：V= ，E= ，10.1 图与网络的基本知识如果两个点vi和vj属于V，且边（vi，vj）属于E，则称两点vi和vj相邻。vi和vj称为边（vi，vj）的端点。如果两条边ei和ej属于E，且两条边有一个公共的端点v，则称两条边ei和ej相邻。边ei和ej称为点v的关联边。10.1图与网络的基本知识对于任一条边（vi，

3、vj）属于E，如果边（vi，vj）的端点无序，就称它是无向边，此时图G称为无向图。上图就是无向图。如果边（vi，vj）的端点有序，就称它是有向边（或称弧），此时图G称为有向图。如果一条边的两个端点相同，则称此边为环。如上图中的e1。如果两点之间的边数多于一条，就称其为多重边。如上图中的e4 和e5。对于有向图中两点之间存在的不同方向的边，不是多重边。对于无环和无多重边的图称为简单图。含有多重边的图，我称其为多重图。如果无向简单图中每一对顶点间都有边相连，就称其为无向完全图。并记为Kn。（如下图所示）n为图中顶点的个数。有向完全图则是指每一对顶点间有且只有一条有向边的简单图。10.1图与网络的基

4、本知识如果图 的点集可以分为两个非空子集X和Y，且满足 ，使得E中每条边的一个端点属于X，另一个端点属于Y，则称G为二分图（或偶图），如图104所示。10.1图与网络的基本知识【定义10.2】 以点v为端点的边数称为点v的次，记作deg（v）或简记为d（v）。如上图中点v1的次为d（v1）=4，因为边e1要计算两次。次为1的点称为悬挂点，连接悬挂点的边称为悬挂边。如上图中v4，e6。次为零的点称为孤立点。如上图中点v5。次为奇数的点称为奇点，次为偶数的点称为偶点。【定理10.1】 在任何图中，顶点次数的总和等于边数的2倍，且次为奇数的顶点必为偶数个。（证明略）【定义10.3】对于图 和 ，若V

5、1为V2的子集，E1为E2的子集，且E1中的边仅与V1中的顶点相关联，则称G1是G2的一个子图。当V1=V2，E1为E2的子集时，则称G1是G2的一个支撑子图。10.1图与网络的基本知识如果点边列中只有重复的点而无重复的边，则称其为简单链。若点边列中既没有重复的点也无重复的边时，称其为初等链。一条开的初等链称为通路；一条闭的初等链称为圈或回路。如果圈中只有重复点而无重复的边时，称其为简单圈。若既没有重复的点也无重复的边时，称其为初等圈。10.1图与网络的基本知识图10-5是一个简单图，其中 是一条链，但不是初等链； 是一条简单链，但不是初等链； 是一条初等链； 是一个圈。【定义10.6】 一个

6、图中任意两点间至少有一条链相连，则称此图为连通图。任何一个连通图都可以分为若干个连通子图，每一个连通子图都可以称为原图的一个分图。10.1图与网络的基本知识10.1.2 图的矩阵表示【定义10.7】 赋权图 ，其边是 有权 ，构造矩阵 其中， 称矩阵A为网络G的权矩阵。图10-6表示图的权矩阵为：10.1图与网络的基本知识【定义10.8】 对于图 ，其中 ，构造一个矩阵 ，其中，则称矩阵A为图G的邻接矩阵。图10-7所示图的邻接矩阵A为：当G为无向图时，邻接矩阵为对称矩阵。10.1图与网络的基本知识10.1.3 欧拉回路与中国邮路问题1. 欧拉回路与道路定义10.9 连通图G中，若存在一条链，

7、经过每边一次且仅一次，则称这条路为欧拉链。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图。定理10.2 无向连通图G中有欧拉链的充要条件是图G中当且仅当只有两个奇点；无向连通图G是欧拉图的充要条件是：当且仅当图G中没有次为奇数的点（无奇点）。（证明略）10.1图与网络的基本知识2. 中国邮路问题运筹学中的“中国邮递员问题”是由我国管梅谷先生于1962首先提出，其内容为：一个邮递员从邮局出发，要走遍他所负责的每条街道去送信后再返回邮局，问应如何选择适当的路线可使所走的总路程最短？这个问题用图论的语言可以描述为：给定一个连通图 ，每边有非负权 ，要求图中经

8、过每边至少一次的一条回路，且满足总权最小。对于邮路问题，要从两种情况进行讨论：（1）如果图G中没有奇点，则是一个欧拉图，显然按欧拉回路走就可以满足要求，即经过每边一次且总权最小。10.1图与网络的基本知识（2）如果图G中有奇点，在连续走过每边至少一次时，必然会重复走过一些边，这相当于在图G中对某些边增加一些重复边，使所得到的亲图中没有奇点且满足总路程最短。由于总路程的长短完全取决于所增加的重复边的长度，所以中国邮路问题也可以转为如下问题：在连通图 中，求一个边集 ，把G中属于 的边均变为二重边得到新图 ，使新图满足无奇点，且 最小。【定理10.3】 已知图 无奇点，则 最小的充要条件为：（1）

9、每条边最多重复一次；（2）对于图G中的每个初等圈，重复边的长度和不超过圈长的一半。10.2 树10.2.1 树的概念与性质树是一类特殊的图，是图论中结构最简单但又应用十分广泛的图。在1847年，克希霍夫在研究电网络时发展了有关树的理论，此后树在分子结构、电网络分析、计算机科学等领域得到广泛的应用。【定义10.10】 不含有圈的无向连通图称为树，一般用 来表示。树中次为1的点称为树叶，次大于1的点称为分枝点。10.2 树对于树 ，当 ， 时，具有如下性质：（1）树中任意两个顶点间有唯一链相联。（2）树无圈，且 。（3）树无圈，但每加一新边即可得唯一一个圈。（4）树是连通的，且 （5）树是连通的，

10、但每舍去一边就不连通。10.2 树10.2.2 图的支撑树定义10.11 如果图G的支撑子图是一棵树T，则称该树T为G的支撑树，或简称为图G 的树。图G中属于支撑树的边称为树枝，不在支撑树中的边称为弦。如图10-10中的（b）为（a）图的支撑树，边（ ）为树枝，（ ）为弦。【定理10.3】图 有支撑树的充分必要条件为G是连通图。（证明略）10.2 树10.2.3 最小树问题【定义10.11】 连通图 ，每条边上有非负权 。一棵支撑树所有树枝上权的总和，称为这个支撑树的权。具有最小权的支撑树称为最小支撑树，简称最小树。定理10.4 用Kruskal算法得到的子图是一棵最小树。（证明略）Krusk

11、al算法的基本步骤：每步从未选的边中选取边e，使它与已选边不构成圈，且e是未选边中的最小权边，直到选够p-1条边为止，p为图的顶点数。10.2 树【例10-2】 一个乡有9个自然村，其间道路如图10-11所示，各边上数字表示距离，要以v0村为中心建设电话网络，问如何拉线才能使用线最短。10.3 最短路问题最短路问题在实际生产中的应用非常广泛。如投资、设备更新、选择管道铺设的最优线路、厂区布局以及整数规划和动态规划的问题，都可以归结为求最短路的问题。最短路问题的一般表述：设 为一给定的赋权连通图，对每一边 ，相应地有权 ，图中有任意两点 ，设l是G中 到 的一条路，路 的权是 中所有边的权之和，

12、记为 。最短路问题就是求从 到 的路中一条权最小的路 ，即：10.2 树10.3.1 Dijkstra算法该算法是由Dijkstra于1959年提出，用于求解指定两点 、 之间的最短路，或从指定点 到其余各点的最短路，目前被认为是求无负权（ ）的赋权图中最短路问题的最好方法。【例10-3】 用Dijkstra算法求图10-12中从 的最短路。10.2 树10.3.2 逐次逼近算法当赋权有向图中存在负权时，则Dijkstra算法失效。例如在图1013所示的赋权有向图中，用Dijkstra算法得到 到 最短路的权是4，但这里显然不对；因为 到 的最短路是 ，权为2。 10.2 树【例10-4】 求

13、图10-14所示赋权有向图中从 到各点的最短路。 10.4 最大流问题最大流问题的应用极为广泛。如在交通运输网络中的物流；金融系统中有现金流；通讯系统中有信息流等。20世纪50年代Ford ，Fulkerson建立的“网络流理论”是网络应用的重要组成部分。10.4 最大流问题10.4.1 最大流的相关概念无论是交通运输网络还是通讯网络，它们每条边的最大通过能力都是有限的，且在实际应用中不一定能充分利用这些有限的能力，最大流问题就是研究如何最大限度地利用各边的通过能力，以使整体网络的流量最大。最大流问题研究的主要对象是容量网络，其定义如下：【定义10.12】在一个有向连通图 中，如果对于每一个弧

14、 ，都有一个非负数 与之对应，则称 称为弧的容量。由该图中唯一的入次为0的点 为发点，唯一的出次为0的点 为终点，其余的点叫中间点所构成的网络称为容量网络，记作 。10.4 最大流问题10.4.2 最大流量最小割定理最大流量最小割定理是图与网络流理论方面的一个重要定理，也是用标号法求网络最大流的理论依据。一般求最大流的方法很多，常见的有标号法（Ford，Fulkerson），标号法的基本思路是由可增广链的概念发展来的。从一个可行流 开始，寻求关于这个可行流的可增广链，若可行流中存在增广链，说明可行流还有潜力可挖，只须沿增广链调整流量，就可得到一个流量增大的新的可行流，重复这个过程，直到不存在该

15、可行流的可增广链时就得到了最大流。10.4 最大流问题标号法的计算过程主要分为2步：第1步是标号过程，通过标号来寻找可增广链；第2步是调整过程，沿增广链调整 以增加流量。其具体的步骤如下：标号过程每个标号点的标号包含两部分：第1个标号说明它的标号从哪一点得到，以便找出增广链；第2个标号是为确定增广链的调整量 用的。调整过程令 10.4 最大流问题【例10-5】 用标号法求图10-15所示网络的最大流。弧旁的数是 。10.4 最大流问题由上述可见，用标号法找增广链找到最大流的同时，得到一个最小截集。最小截集的容量大小影响网络最大流量。因此为提高总的输送量，必须首先考虑改善最小截集中各弧的输送能力

16、。另一方面，一旦最小截集中弧的通过能力被 降低，就会使总的输送量减少。10.4最大流问题10.4.3 最大匹配问题【定义10.16】 二部图（也叫二分图）【定义10.17】（匹配）对给定的二部图G=（X，Y，E），若有M E，且则称M为G的一个匹配（也称对集）。M中任意两条边都没有公共端点， 【定义10.18】（最大匹配） M表示G中所有的匹配集，即M =M| M为G的匹配集，|M|表示M的边数，若存在M0使任意的MM ，|M0|M|，则称M0是G的最大匹配。10.4最大流问题【例10-6】设有5位待业者，5项工作，他们各自能胜任工作情况如图10-19所示，要求设计一个新业方案，使尽量多的人能

17、就业。解：按前述方法增加虚拟的发、收的 ，用求最大流的标号法求解得到图5-49，在图中略去容量，只标出流量，。边 上的流量都是1，所以让 工作可得最大就业方案，即最多可以安排四个人就业。 图10-19 胜任工作情况10.5 最小费用流问题【例10-7】 如图10-20所示的可增广链 中， ， 边上权为费用 ，则链 的费用 =（3+4+1+6）-（5+7）=2。若 是从 到 所有可增广链中费用最小的链，则称 围最小费用可增广链。 图1020 可增广链 10.5最小费用流问题寻求最小费用流的有效算法一般采用对偶算法，“对偶算法”的基本步骤如下：（1）取零流为初始可行流，即 。（2）若有 ，流量为

18、，构造长度网络 。（3）在长度网络 中求 到 的最短路。若不存在最短路，则 已为最大流，不存在流量等于 的流，停止；否则转（4）。（4）在 中与这条最短路相应的可增广链 上，作 10.5最小费用流问题【例10-8】 在图1021（a）所示运输网络上，求流量 为10的最小费用流，边上括号内为 。图1021(a) 运输网络10.6 网络最优化问题的模型与求解10.6.1 最小费用流问题最小费用流问题的模型在网络最优化中扮演着重要的角色，适应性也很广，并且求解方法容易。通常最小费用流问题用于最优化货物从供应点到需求点的网络，目标是在通过网络配送货物时，以最小的成本满足需求。一种典型的应用就是使得配送

19、网络的运营最优。【例10-9】 某公司有两个工厂生产产品，这些产品需要运送到两个仓库中。配送网络如图1022所示。目标是确定一个运输方案(即每条路线运送多 的产品) ，使通过配送网络的运输成本最小。10.6 网络最优化问题的模型与求解在图1022中，F1和F2代表两个工厂，为供应点；W1和W2代表两个仓库，为需求点；DC表示配送中心，为转运点。工厂1生产80个单位，工厂2生产70个单位。仓库1需要60个单位，仓库2需要90个单位。括号中第一分量表示最大运输量，第二分量表示单位运输费用。10.6 网络最优化问题的模型与求解在运输问题中，常常涉及三个基本概念：网络表示，基本假设和解的情况。A.最小

20、费用流问题的网络表示：节点：包括供应点，需求点和转运点弧：可行的运输路线（最大容量的限制）B.最小费用流问题的基本假设：至少有一个供应点，至少有一个需求点，除此而外还有转运点，通过弧的最大流量取决于该弧的容量；网络中有足够的弧提供足够的容量，使得所有在供应点中产生的流都能够到达需求点。在流的单位成本已知的情况下，通过每一条弧的流成本和流量成正比。最小费用流问题的目标是在满足给定的需求条件下，使得通过网络供应的总成本最小或者总利润最大。10.6 网络最优化问题的模型与求解C.最小费用流问题的解的特征在以上的假设情况下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题才有可行解；只要所有的供应，需求和弧容量都是整数值，那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解，这点与运输问题和指派问题的解一样。因此，没有必要加上所有决策变量都是整数的约束条件。10.6 网络最优化问题的模型与求解10.6.2 最大流问题【例10-10】 某公司要从起始点 运送货物到目的点 (收点) ，其网络如图1023所示。图10-23中每条弧(节点i节点j)旁边的权 表示这段运输线路的最大通过能力(容量)。要求制定一个运输方案，使得从 到 的运物量达到最大，这个问题就是寻求网络系统的最大流问题。 图1