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

§2最短路问题*§2最短路问题*§2最短路问题*§2最短路问题*§2最短路问题**§2最短路问题V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)标号如下图所示：§2最短路问题因此，v1到v6的距离是53，最短路径有两条：v1→v3→v6或v1→v4→v6。也就是说第一个方案为第1年初购置新设备使用到第2年底（第3年初），第3年初再购置新设备使用到第5年底（第6年初）。第二个方案为第1年初购置新设备使用到第3年底（第4年初），第4年初再购置新设备使用到第5年底（第6年初）。这两个方案使得总费用最小，均为53。**§3最小生成树问题树是图论中的重要概念，所谓树就是一个无圈的连通图。图11-11中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)*§3最小生成树问题给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子图。在图11-12中，(b)和(c)都是(a)的生成子图。如果图G的一个生成子图是一个树，则称这个生成子图为生成树，在图11-12中，(c)就是(a)的生成树。最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。图11-12(a)(b)(c)*§3最小生成树问题一、求解最小生成树的破圈算法算法的步骤：1、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。*§3最小生成树问题例4用破圈算法求图（a）中的一个最小生成树v1331728541034v7v6v5v4v2v13317285434v7v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)图11-13*§3最小生成树问题例5、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,…,v7表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。解：此问题实际上是求图11-14的最小生成树，这在例4中已经求得，也即按照图11-13的(f)设计，可使此网络的总的线路长度为最短，为19百米。“管理运筹学软件”有专门的子程序可以解决最小生成树问题。v1331728541034v7v6v5v4v2v3图11-14最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。*§4最大流问题*一、最大流的数学模型例6某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运送多少加仑石油？§4最大流问题*§4最大流问题我们可以为此例题建立线性规划数学模型：设弧(vi,vj)上流量为fij，网络上的总的流量为F，则有：*§4最大流问题在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表