第11章 图与网络模型 运筹学

1、1.第11章：图和网络模型，1:图和网络的基本概念2:最短路径问题3:最小生成树问题4:最大流问题5:最小成本和最大流问题，2: 1:图和网络的基本概念。图论中的图是由点和边组成的，它能反映一些对象之间的关系。例如，在人群中，我们可以用一个图表来表达相互理解的关系，图11-1是显示这种关系的图表。当然，图论不仅是为了描述对象之间的关系，也是为了研究具体关系的内在规律。一般来说，图中点的相对位置以及点之间连接线的长度和曲率对于反映对象之间的关系并不重要。例如，我们可以用图11-2来表达赵与其他七人之间的相互理解关系。可以看出，图论中的图形不同于几何图形和工程图。图形和网络的基本概念，如果我们把上

2、面例子中的“相互理解”关系变成“理解”关系，那么很难只用两点之间的连线来描述它们之间的关系。这是一条带有箭头的连接线，叫做弧线。图11-3是反映这七个人之间“认知”关系的图表。相互理解由两条相反的弧线表示。图和网络的基本概念，无向图：由点和边组成的图，表示为G=(V，e)。有向图：由点和弧组成的图，表示为D=(V，a)。连通图：对于无向图G，如果任意两个不同点之间至少有一条链，则G是连通图。循环：如果道路的第一个点和最后一个点是相同的，那么道路就是一个循环。加权图：对于无向图G的每条边(vi，vj)，都有一个数wij，那么图G称为加权图，wij称为边(vi，vj)上的权。网络：在加权有向图D中

3、，一个点被指定为起点，另一个点被指定为接收点，其他点被称为中间点，D中每个弧的加权数被称为弧容量，D被称为网络。6，2最短路径问题：在加权有向图D中，为两个指定点Vs和Vt找到从Vs到Vt的路径，使得该路径上所有弧的权重之和最小。这条路径被称为从Vs到Vt的最短路径。这条路上所有弧线的重量之和称为从Vs到Vt的距离。1.求解最短路径的Dijkstra算法(双重标号法)步骤：1 .给点V1一个标签(0，s)；2.找出标记点的集合I、未标记点的集合j和弧的集合；3.如果弧的集合是空集合，则计算结束。如果vt被标记(lt，kt)，从vs到vt的距离为lt，并且从vs到vt的最短路径可以通过从kt追溯

4、到起始点vs来获得。如果vt未被标记，则可以断言从vs到vt没有定向路径。如果上述弧集不是空集，请转到下一步。4.对于上述弧集中的每个弧，计算sij=li cij。在所有sij中，找到具有最小值的弧。让我们将这个弧设置为(Vc，Vd)，然后给这个弧的端点一个双标签(scd，c)，并返回到步骤2。7，2最短路径问题，例1找到从v1到v6的最短路径解决方案如下图：使用Dijkstra算法，我们可以得到v1v3v4v6最短路径的每个点的标签图如下：8，2最短路径问题，例2电信公司将沿着道路A和B建立一条光缆线路，询问如何建立最短光缆线路。下图为甲乙双方的交通图.重量表示两地之间的道路长度(单位：千米

5、)。解决方法：这是一个寻找无向图最短路径的问题。无向图的每条边(vi，vj)可以被两个方向相反的弧(vi，vj)和(vj，vi)代替，这两个弧可以被转换成有向图，这可以通过Dijkstra算法来求解。它也可以在无向图中用Dijkstra算法直接求解。只要在算法中从标记点到未标记点的弧集合被改变成从标记点到未标记点的边集合。9，2最短路径问题，最后在例2中解决：最短路径v1v3v5v6v7，每个点的标号如下图所示，(0，s)V1 (A)，15，17，6，2，4，3，10，6，5，(。一家公司使用一台设备。每年年初，公司将决定是购买新设备还是继续使用旧设备。如果你购买新设备，你必须支付一定的购买费

6、用，当然，新设备的维护费用很低。如果你继续使用旧设备，你可以节省购买成本，但维护成本会更高。请设计一个在五年内更新设备的计划，以便在五年内将采购成本和维护成本的总支付降至最低。众所周知，每年年初的设备价格表如下：11.2最短问题，示例3的解决方案：将问题转化为最短问题，如下图所示：vi表示“在第一个一年年初购买新设备”，而arc (vi，vj)表示在第一个一年年初购买的设备一直使用到第一个一年年初。计算下表中所有弧的权重：12，2最短路径问题。(上一页继续)给图分配权重，然后使用Dijkstra算法找到最短路径。最后，得到下图。可以看出，v1到v6的距离为53，有两条最短路径：v1v3v6和v

7、1v4v6、13、3、13、3。最小生成树问题是图论中的一个重要概念，所谓的树是一个无环连通图。在图11-11中，(a)是一棵树，(b)它不是树，因为图中有圈，(c)它不是树，因为它没有连接。14，3最小生成树问题，给出一个无向图G=(V，E)，我们保留G的所有点，并删除G的一些边或保留G的一些边，得到的图G称为G的生成子图。在图11-12中，(b)和(c)是(a)的生成子图。如果图G的生成子图仍然是树，那么这个生成子图被称为生成树。在图11-12中，(c)是(a)的生成树。最小生成树问题是在加权连通无向图G中找到一棵生成树，并使生成树所有边的权重之和最小。(a)，(b)，(c)，15，3最小

8、生成树问题，1。该算法求解最小生成树的步骤如下：1 .在给定的加权连通图上找出一个圈。2.在您要寻找的圆中，移除一条最大权重的边(如果两条或多条边是最大权重的边，请随意移除其中一条)。3.如果剩余图不包含循环，则计算结束，剩余图是最小生成树；否则，返回到步骤1。16，3最小生成树问题，示例4:在图(A)中使用破环算法找到最小生成树，图11-13，17，3最小生成树问题，示例5:一所大学将连接其七个学院办公室的计算机。连接该网络的可能方式如下，其中v1、v7代表七个学院办公室。请设计一个连接七个学院办公室的网络。解决方案：这个问题实际上是要找到图11-14中的最小生成树，这在示例4中已经找到，也

9、就是说，根据图11-13 (f)的设计，这个网络的总线路长度可以是最短的，即1900米。管理操作研究软件有专门的子程序来解决最小生成树问题。18，4最大流量问题：给定一个有发送点和接收点的网络，每个弧的权重称为容量，从发送点到接收点的最大流量可以在不超过每个弧容量的情况下获得。1.最大流量的数学模型示例6石油公司有一个管道网络，可以将石油从矿区运输到一些销售点。下图显示了该网络的一部分。由于管道直径的变化，管道(vi，vj)各段的流量cij(容量)也不同。cij的单位是每小时10，000加仑。如果该网络系统用于将石油从生产地点v1运输到销售地点v7，每小时可以运输多少加仑的石油？v5，19，4

10、最大流量问题，我们可以为这个例子建立一个线性规划数学模型：让弧(vi，vj)上的流量为fij，网络上的总流量为f，那么将会有：20，4最大流量问题，在这个线性规划模型中，其约束中的前六个方程表明网络中的流量必须满足守恒条件，并且起点处的流出量必须为。其余的点称为中间点，并且其总流入量必须等于总流出量。以下约束条件表明，每个弧(vi，vj)的流量fij应满足可行的流量条件，该条件应小于或等于弧(vi，vj)的容量cij，且大于或等于零，即0fijcij。我们把满足守恒条件和流的可行条件的一组网络流称为可行流(即线性规划的可行解)，把最大流(即发送点的最大总流出量)的一组可行流称为最大流(即线性规

11、划的最优解)。我们将示例6的数据代入上述线性规划模型，并使用“管理运营研究软件”立即获得以下结果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，F。最优值(最大流量)=10。21，4最大流量问题，2。网络图论中最大流问题的求解改进了网络上弧容量的表示。为了省略弧的方向，图：(a)中(a)和(b)、(c)和(d)的含义相同。通过上述方法改进了实施例6的图表的容量标签，并且获得了以下图表：V1、VJ、V1、VJ、CIJ、0、(a)、(b)、CIJ、CIJ、V1、VJ、(cji)、(c)、V1、VJ、CIJ等。如果没有这样的路

12、径，则已获得最大流量。(2)找出该道路上各弧段的最小下游容量pf，增加该道路的网络流量pf。(3)在该道路上，减少每个弧的下游容量pf，增加这些弧的上游容量pf，并返回步骤(1)。用这种方法解决例6:第一次迭代：选择路径为v1v4v7。arc (v4，v7)的下游容量为2，这决定了pf=2。改进后的网络流程图如下：23，4最大流问题，第二次迭代：选择的路径是v1v2v5v7。arc (v2，v5)的下游容量为3，这决定了pf=3。改进后的网络流量图如下：第三次迭代：选择的路径是v1v4v6v7。arc (v4，v6)的下游容量为1，这决定了pf=1。改进后的网络流量图如下：24。在第四次迭代中

13、，选择的路径是v1v4v3v6v7。arc (v3，v6)的下游容量为2，这决定了pf=2。改进后的网络流量图如下：第五次迭代：选择的路径为v1v2v3v5v7。弧(v2，v3)的下游容量为2，这决定了pf=2。改进后的网络流程图如下：4最大流量问题，25。在第五次迭代之后，图中没有从起点到终点的路径，并且路径上每个弧的下游容量大于零，因此操作停止。获得的最大流量为10。最大流程图如下：4。最大流量问题。管理操作研究软件中有专门的子程序来解决最大流量问题。26，5最小成本最大流量问题，最小成本最大流量问题：给定一个具有发送点和接收点的网络，对于每个弧(vi，vj)，除了容量cij之外，还给出了

14、该弧的单位流量成本bij，它要求最大流量f和最小化总运输成本。1.最小成本和最大流量的数学模型示例7由于石油管道的长度不同，在示例6中，每个管道(vi，vj)具有不同的流量限制cij，并且还具有不同的单位流量成本bij，其中cij为10，000加仑/小时，bij为100元/10，000加仑。数字。当从生产地点v1向销售地点v7运输石油时，我们如何运输最多的石油，并最大限度地降低总运输成本？找出最大流量和最小成本。(6，6)、(3，4)、(5，7)、(2，5)、(2，4)、(2，3)、(4，4)、(1，3)、(2，8)解：我们用线性规划来解决这个问题，它可以分为两步。第一步是在这个网络图中找到最

15、大流f，它在例6中建立了一个线性规划模型，结果是通过管理运筹学软件获得的。在第二步中，在最大流的所有解中找出一个代价最小的解。让我们在第二步中建立线性规划模型如下：让弧(vi，vj)上的流为fij，然后我们知道网络中的最大流为F。只要在例6的约束条件中加上总流必须等于F: f12=f14=F的约束条件，就可以得到该线性规划的约束条件。线性规划模型如下：28，5最小费用和最大流量问题，29，5最小费用和最大流量问题。利用管理运筹学软件，可以得到以下结果：F12=4，F14=6，F25=3，F23=1，F43=3，F57=5，F36=2，F46其最优值(最小成本)=145。与示例6的结果相比，我们

16、可以对最小成本和最大流量的概念有更深的理解。如果我们将示例7中的问题改为：从生产地点v1到销售地点v7每小时运输60，000加仑油的最低成本是多少？它应该如何运输？这成为最小成本流的问题。一般来说，所谓的最小费用流的问题是在给定接收点和发送点并且每个弧(vi，vj)被给定容量cij和单位成本bij的网络中找到具有给定值f的流的最小费用，否则没有解决方案。求解最小费用流问题的线性规划模型只需在最小费用最大流模型的约束条件下，将出发流F改为F。在例6中，我们只需要将f12 f14=F改为f12 f14=f=6，就可以得到最小成本流的线性规划模型。30，5，最小成本和最大流量问题，2。最小费用和最大

17、流量的网络图论解决方案如下改变网络上弧(vi，vj)的表示(cij，bij)，并使用(b)来表示(a)。使用上述方法改进示例7中的图，并获得以下页面：VI，VJ，VI，VJ，(CIJ，BiJ)，(0，-BiJ)，(a)，(b)，(CIJ，BiJ)，(CIJ，BiJ)，VI，VJ (c)，(d)，31，5在具有改进的弧标签的网络图中，寻找最小成本和最大流量的基本算法与寻找最大流量的基本算法完全相同，除了在步骤(1)中，应该选择具有最小单位总成本的路径，而不是具有最小单位成本的路径，32，5，最小费用和最大流量问题，用上述方法求解例7:第一次迭代：寻找最短路径v1v4v6v7。第一次迭代后，总流量为1，总成本为10。v5，33，5最小费用和最大流量问题，第二次迭代：寻找最短路径v1v4v7。第二次迭代后，总流量为3，总成本为32。34，5最小费用和最大流量问题，第三次迭代：寻找最短路径v1v4v3v6v7。第三次迭代后，总流量为5，总成本为56。35，5最小费用和最大流量问题，第四次迭代：寻找最短路径v1v4v3v5v7。第四次迭代后，总流量为6，总成本为72。36，5最小费用和最大流量问题，第五次迭代：找到最短路径v1v2v5v7。第五次迭代后，总流量为9，总成本为123。37，5最小费用最大流问题，第6次迭代：寻找最短路径v1v2v3v5v7。第六次迭代