搜索
管理运筹学1第十一章图与网络模型§1图与网络的基本概念§2最短路问题§3最小生成树问题§4最大流问题§5最小费用最大流问题管理运筹学2§1图与网络的基本概念一、图的概念（一）图的定义图论中图是由点和边构成，可以反映一些对象之间的关系。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图11-1就是一个表示这种关系的图。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5图11-1管理运筹学3§1图与网络的基本概念当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图11-2来表示，可见图论中的图与几何图、工程图是不一样的。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5图11-2管理运筹学4§1图与网络的基本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图11-3如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。管理运筹学5§1图与网络的基本概念（二）无向图：由点和边构成的图，记作G=（V，E）。•（三）有向图：由点和弧构成的图，记作D=（V，A）。•（四）连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。•（五）回路：若路的第一个点和最后一个点相同，则该路为回路。•（六）赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。•（七）网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。管理运筹学6§2最短路问题•一、最短路问题•对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从Vs到Vt的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。•二、求解最短路的Dijkstra算法(双标号法）的步骤•1.给出点V1以标号(0,s)•2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合{(Vi,Vj)︱Vi∈I,Vj∈J}•3.如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则vs到vt的距离为lt，而从vs到vt的最短路径，则可以从kt反向追踪到起点vs而得到。如果vt未标号，则可以断言不存在从vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步。•4.对上述弧的集合中的每一条弧，计算sij=li+cij。在所有的sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。管理运筹学7§2最短路问题例1求下图中v1到v6的最短路v23527531512v1v6v5v3v4(3,1)v23527531512V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4解：采用Dijkstra算法，各点的标号图如下：由左图可知最短路径为v1→v3→v4→v6，最短路径的长度为8。管理运筹学8§2最短路问题例2电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。V1（甲地）15176244431065v2V7（乙地）v3v4v5v6管理运筹学9§2最短路问题解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。管理运筹学10§2最短路问题每点的标号见下图：（0,s）V1（甲地）1517624431065(13,3)v2(22,6)V7（乙地）V5(14,3)V6(16,5)V3(10,1)V4(18,5)例2最终解得：最短路径v1→v3→v5→v6→v7，最短光缆需要22公里。管理运筹学11§2最短路问题例3设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表如下：年份12345年初价格1111121213使用年数第1年第2年第3年第4年第5年每年维修费用5681118设备维修费如下表：管理运筹学12§2最短路问题解：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。将问题转化为最短路问题，如下图：v1v2v3v4v5v6123456116223041592162230413172331417235186把所有弧的权数计算如下表：管理运筹学13§2最短路问题(继上页)把权数赋到图中，再用Dijkstra算法求最短路。v1v2v3v4v5v6162230415916223041312317181723V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)可知，v1到v6的距离是53，最短路径有两条：v1→v3→v6和v1→v4→v6，即最少费用为53。各点的标号如下图所示：管理运筹学14§3最小生成树问题•一、树的概念•（一）树的定义•树是图论中的重要概念，所谓树就是一个无圈的连通图。图11-11中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)管理运筹学15§3最小生成树问题（二）生成子图给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图，称之为G的生成子图。在图11-12中，(b)和(c)都是(a)的生成子图。（三）生成树如果图G的一个生成子图还是一个树，则称这个生成子图为生成树，在图11-12中，(c)就是(a)的生成树。图11-12(a)(b)(c)管理运筹学16§3最小生成树问题二、最小生成树问题最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。三、求解最小生成树的破圈算法算法的步骤：（一）在给定的赋权的连通图上找一个含有最大边的圈。（二）在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。（三）如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。管理运筹学17§3最小生成树问题例4用破圈算法求图（a）中的一个最小生成树v1331728541034v7v6v5v4v2v13317285434v7v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)图11-13管理运筹学18§3最小生成树问题例5、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,…,v7表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。解：此问题实际上是求图11-14的最小生成树，这在例4中已经求得，也即按照图11-13的(f)设计，可使此网络的总的线路长度为最短，为19百米。“管理运筹学软件”有专门的子程序可以解决最小生成树问题。v1331728541034v7v6v5v4v2v3图11-14管理运筹学19§4最大流问题•一、最大流问题•给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。•二、最大流的数学模型•例6某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6图11-26v5管理运筹学20§4最大流问题我们可以为此例题建立线性规划数学模型：设弧(vi,vj)上流量为fij，网络上的总的流量为F，则有：1412232514434647234335362535573646675767471214,1,2,,6;1,2,70,1,2,,6;1,2,712ijijijmaxF=fffffffffffffffffffffffffcijfij目标函数：约束条件：管理运筹学21§4最大流问题在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等于弧(vi,vj)的容量cij，并大于等于零，即0≤fij≤cij。我们把满足守恒条件及流量可行条件的一组网络流{fij}称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。我们把例6的数据代入以上线性规划模型，用“管理运筹学软件”，马上得到以下的结果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。最优值（最大流量）=10。管理运筹学22§4最大流问题三、最大流问题网络图论的解法（一）对网络上弧的容量的表示作改进。为省去弧的方向，如下图:(a)和(b)、(c)和(d)的意义相同。vivjvivjcij0（a）（b）cijcijvivj（cji）（c）vivjcijcji（d）63522241263v1v2v5v7v4v3v600000000000用以上方法对例6的图的容量标号作改进，得下图：管理运筹学23§4最大流问题（二）求最大流的基本算法1、找出一条从发点到收点所含边数最少的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。2、找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。3、在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的逆流容量pf，返回步骤（1）。用此方法对例6求解：第一次迭代：选择路为v1→v4→v7。弧（v4,v7）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：63522241263v1v2v5v7v4v3v6000000000004202管理运筹学24§4最大流问题第二次迭代：选择路为v1→v2→v5→v7。弧（v2,v5）的顺流容量为3，决定了pf=3，改进的网络流量图如下图：635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v600