《运筹学-图与网络模型以及最小费用最大流.ppt》由会员分享，可在线阅读，更多相关《运筹学-图与网络模型以及最小费用最大流.ppt（100页珍藏版）》请在三一办公上搜索。
1、Chapter11 图与网络分析(Graph Theory and Network Analysis),图与网络的基本概念与模型最短路问题最小生成树问题最大流问题最小费用最大流问题,本章主要内容：,图与网络的基本概念与模型,长,江,汉,江,武昌,汉口,汉阳,您能从武汉理工大学出发走过每座桥且只走一次然后回到学校吗?,近代图论的历史可追溯到18世纪的七桥问题穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不可能存在这样的路线。,图与网络的基本概念与模型,Knigsberg桥对应的图,图与网络的基本概念与模型,图论中
2、图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。,图的定义(P230)若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作：,其中:V点集 E边集,图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。,图与网络的基本概念与模型,可见图论中的图与几何图、工程图是不一样的。,例如：在一个人群中，对相互认识这个关系我们可以用图来表示。,1图与网络的基本概念,如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系
3、了，这是我们引入一个带箭头的联线，称为弧。图11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。,图与网络的基本概念与模型,定义:图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=v1,v1;e2=v1,v2;,端点,关联边,相邻,若有边e可表示为e=vi,vj，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。,图与网络的基本概念与模型,环,多重边,简单图,如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多
4、重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。,图与网络的基本概念与模型,链，圈，连通图(P231),图中某些点和边的交替序列，若其中各边互不相同，且对任意Vi-1,Vi 和vi+1均相邻称为链。用表示：,起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。,图与网络的基本概念与模型,网络（赋权图）(P232),设图G（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称
5、为有向网络。,图与网络的基本概念与模型,主要概念(p231-p232)无向图：由点和边构成的图，记作G=（V，E）。有向图：由点和弧构成的图，记作D=（V，A）。连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。回路：若路的第一个点和最后一个点相同，则该路为回路。赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。,最短路问题,如何用最短的线路将三部电话连起来？此问题
6、可抽象为设ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如ABAC）。,A,B,C,最短路问题,A,B,C,P,但若增加一个周转站（新点P），连接4点的新网络的最短路线为PAPBPC。最短新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。,最短路问题,问题描述：要求：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。,最短路问题,例 渡
7、河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。,最短路问题,定义：1）人M（Man），狼W（Wolf），羊G（Goat），草H（Hay）2）点 Vi 表示河岸的状态3）边 ek 表示由状态 vi 经一次渡河到状态 vj 4）权边 ek 上的权定为 1,我们可以得到下面的加权有向图：,最短路问题,状态说明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=
8、(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G),此游戏转化为在下面的二部图中求从 v1 到 u1 的最短路问题。,v1,v2,v3,v4,v5,u5,u4,u3,u2,u1,最短路问题,求最短路有两种算法:,狄克斯屈拉(Dijkstra)（双标号）算法 逐次逼近算法,最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。,最短路问题,狄克斯屈拉(Dijkstra)标号算法的基本思路：若序列 vs,v1.vn-1,v
9、n 是从vs到vt间的最短路，则序列 vs,v1.vn-1 必为从vs 到vn-1的最短路。,假定v1v2 v3 v4是v1 v4的最短路，则v1 v2 v3一定是v1 v3的最短路，v2 v3 v4也一定是v2 v4的最短路。,最短路问题,最短路的Dijkstra算法(双标号法）的步骤：1.给出点V1以标号(0,s)2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合3.如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则 vs到vt的距离为lt，而从 vs到vt的最短路径，则可以从kt 反向追踪到起点vs 而得到。如果vt 未标号，则可以断言不存在从 vs到vt的有向
10、路。如果上述的弧的集合不是空集，则转下一步。4.对上述弧的集合中的每一条弧，计算 sij=li+cij。在所有的 sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。,最短路问题,(P233)例1 求下图中v1到v6的最短路解：采用Dijkstra算法，可解得最短路径为v1 v3 v4 v6 各点的标号图如下：,最短路问题,(P234)例2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。解：这是一个求无向图的最短路的问题。可以把无向图的每一边（
11、vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。,最短路问题,（0,s）V1（甲地）,15,17,6,2,4,4,3,10,6,5,(13,3)v2,(22,6)V7（乙地）,V5(14,3),V6(16,5),V3(10,1),V4(18,5),最短路问题,例3 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费
12、，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表 设备维修费如下表,最短路问题,例3的解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。把所有弧的权数计算如下表：,最短路问题,(继上页)把权数赋到图中，再用Dijkstra算法求最短路。最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1 v3 v6和 v1 v4 v6,最短路问题,课堂练习：1.用Dijk
13、stra算法求下图从v1到v6的最短距离及路线。,v3,v5,4,v1到v6的最短路为：,最短路问题,2.求从v1到v8的最短路径,最短路问题,v1到v8的最短路径为v1v4v7v5v8，最短距离为10,最短路问题,3.求下图中v1点到另外任意一点的最短路径,v1,v2,v3,v4,v6,v5,3,2,2,7,6,2,1,3,3,最短路问题,v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,最短路问题,v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,最短路问题,算法适用条件：Dijkstra算法只适用
14、于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。,例6.7 如右图所示中按dijkstra算法可得P(v1)=5为从vsv1的最短路长显然是错误的，从vsv2v1路长只有3。,v2,vs,v1,5,-5,8,最小生成树问题,树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。,例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。,运动员,最小生成树问题,例 某企业的组织机构图也可用树图表示。,树与图的最小树,树：无圈的连通图即为树,性质1：任何树中必存在次为1的点。(一个点Vi的相关联边的数目称为点Vi的次)性质2：n 个顶点的树必有n-
15、1 条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。,最小生成树问题,树是图论中的重要概念，所谓树就是一个无圈的连通图。,图11-11中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。,最小生成树问题,图的最小部分树(支撑树),如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。,G1,G2,最小生成树问题,最小生成树
16、问题,最小生成树问题,最小生成树问题,最小生成树问题,最小生成树问题,给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子图。在图11-12中，(b)和(c)都是(a)的生成子图。如果图G的一个生成子图还是一个树，则称这个生成子图为生成树，在图11-12中，(c)就是(a)的生成树。最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。,(a),(b),(c),最小生成树问题,求树的方法：破圈法和避圈法,破圈法,最小生成树问题,部分树,最小生成树问题,避圈法,最小生成树问题,
17、赋权图中求最小树的方法：破圈法和避圈法,破圈法：任取一圈，去掉圈中最长边，直到无圈。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,边数n-1=5,最小生成树问题,得到最小树：,Min C(T)=15,最小生成树问题,避圈法:去掉G中所有边，得到n个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。,最小生成树问题,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min C(T)=15,最小生成树问题,练习：应用破圈法求最小树,最小生成树问题,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,20,15,9,16
18、,25,3,28,17,4,1,23,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,最小生成树问题,v
19、1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,min=1+4+9+3+17+23=57,最小生成树问题,练习：应用避圈法求最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25
20、,3,28,17,4,1,23,36,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,20,15,9,
21、16,25,3,28,17,4,1,23,36,最小生成树问题,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,min=1+4+9+3+17+23=57,最小生成树问题,课堂练习：,Min C(T)=12,Min C(T)=15,答案：,最小生成树问题,3,4,1,2,2,3,2,3,2,4,2,Min C(T)=12,Min C(T)=18,最小生成树问题,例5、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。
22、,解：此问题实际上是求图11-14的最小生成树，这在例4中已经求得，也即按照图11-13的(f)设计，可使此网络的总的线路长度为最短，为19百米。“管理运筹学软件”有专门的子程序可以解决最小生成树问题。,网络的最大流,如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。,网络的最大流,基本概念：1.容量网络：队网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。,s,t,4,8,4,4,1,2,2,6,7,9,网络的最大流,2.网络的
23、最大流是指网络中从发点到收点之间允许通过的最大流量。,3.流与可行流 流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。若fij=0，称为零流。满足以下条件的一组流称为可行流。,容量限制条件。容量网络上所有的弧满足：0fijcij 中间点平衡条件。,若以v(f)表示网络中从st的流量，则有：,网络的最大流,结论：任何网络上一定存在可行流。（零流即是可行流）,网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大。,网络的最大流,一、最大流的数学模型 例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分
24、如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？,v5,网络的最大流,我们可以为此例题建立线性规划数学模型：设弧(vi,vj)上流量为fij，网络上的总的流量为F，则有：,网络的最大流,在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等
25、于弧(vi,vj)的容量cij，并大于等于零，即0fij 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。,网络的最大流,二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图:(a)和(b)、(c)
26、和(d)的意义相同。用以上方法对例6的图的容量标号作改进，得下图,vi,vj,vi,vj,cij,0,（a）,（b）,cij,cij,vi,vj,（cji）,（c）,vi,vj,cij,cji,（d）,网络的最大流,求最大流的基本算法（1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。（3）在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的逆流容量pf，返回步骤（1）。用此方法对例6求解：第一次迭代：选择路为v1 v4 v7。弧（v4,v7）的顺流容
27、量为2，决定了pf=2，改进的网络流量图如下图：,网络的最大流,第二次迭代：选择路为v1 v2 v5 v7。弧（v2,v5）的顺流容量为3，决定了pf=3，改进的网络流量图如下图：第三次迭代：选择路为v1 v4 v6 v7。弧（v4,v6）的顺流容量为1，决定了pf=1，改进的网络流量图如下图：,网络的最大流,第四次迭代：选择路为v1 v4 v3 v6 v7。弧（v3,v6）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：第五次迭代：选择路为v1 v2 v3 v5 v7。弧（v2,v3）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：,网络的最大流,经过第五次迭代后在图中已经找
28、不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为10。最大流量图如下图：,“管理运筹学软件”中还有专门的子程序用于解决最大流问题。,最小费用最大流问题,最小费用最大流问题：给了一个带收发点的网络，对每一条弧（vi,vj），除了给出容量cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流F，并使得总运送费用最小。一、最小费用最大流的数学模型 例7 由于输油管道的长短不一，所以在例6中每段管道（vi,vj）除了有不同的流量限制cij外，还有不同的单位流量的费用bij，cij的单位为万加仑/小时，bij的单位为百元/万加仑。如图。从采地 v1向销地 v7运
29、送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。,最小费用最大流问题,这个最小费用最大流问题也是一个线性规划的问题。解：我们用线性规划来求解此题，可以分两步走。第一步，先求出此网络图中的最大流量F，这已在例6中建立了线性规划的模型，通过管理运筹学软件已经获得结果。第二步，在最大流量F的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下：仍然设弧（vi,vj）上的流量为fij，这时已知中最大流量为F，只要在例6的约束条件上，再加上总流量必须等于F的约束条件：f12=f14=F,即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费
30、用 fij.bij。由此得到线性规划模型如下：,最小费用最大流问题,最小费用最大流问题,用管理运筹学软件，可求得如下结果：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最优值(最小费用)=145。对照前面例6的结果，可对最小费用最大流的概念有一个深刻的理解。如果我们把例7的问题改为：每小时运送6万加仑的石油从采地v1到销地v7最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧(vi,vj)赋权以容量cij及单位费用bij的网络中，求一
31、个给定值f的流量的最小费用，这个给定值f的流量应小于等于最大流量F，否则无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量F改为f即可。在例6中只要把f12+f14=F改为f12+f14=f=6得到了最小费用流的线性规划的模型了。,最小费用最大流问题,二、最小费用最大流的网络图论解法对网络上弧（vi,vj）的（cij,bij）的表示作如下改动，用(b)来表示(a)。用上述方法对例7中的图形进行改进，得图如下页：,vi,vj,vi,vj,（cij,bij）,（0,-bij）,（a）,（b）,（cij,bij）,（cij,bij）,vi,vj,（cji,bji
32、）,（cij,bij）,vi,vj,（cji,bji）,（0,-bji),（0,-bji),（c）,（d）,最小费用最大流问题,求最小费用最大流的基本算法 在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求最大流的基本算法完全一样，不同的只是在步骤（1）中要选择一条总的单位费用最小的路，而不是包含边数最小的路。,最小费用最大流问题,用上述方法对例7求解：第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后总流量为1，总费用10。,v5,最小费用最大流问题,第二次迭代：找到最短路v1 v4 v7。第二次迭代后总流量为3，总费用32。,最小费用最大流问题,第三次迭代：找到最短路v1
33、 v4 v3 v6 v7。第三次迭代后总流量为5，总费用56。,最小费用最大流问题,第四次迭代：找到最短路v1 v4 v3 v5 v7。第四次迭代后总流量为6，总费用72。,最小费用最大流问题,第五次迭代：找到最短路v1 v2 v5 v7。第五次迭代后总流量为9，总费用123。,最小费用最大流问题,第六次迭代：找到最短路v1 v2 v3 v5 v7。第六次迭代后总流量为10，总费用145。已经找不到从v1到v7的每条弧容量都大于零的路了，故已求得最小费用最大流了。,最小费用最大流问题,如果对例7求一个最小费用流的问题：每小时运送6万加仑石油从v1到v7的最小费用是多少，或者每小时运送7万加仑呢？我们可以从第四次迭代及图11-32即可得到运送6万加仑最小费用72百元，其运送方式通过比较图11-28及图11-32即得图11-36所示。至于每小时运送7万加仑，我们可以在图11-36的基础上，再按第五次迭代所选的最短路运送1万加仑即得最小费用：72+1*17=89百元，其运送方式如图11-37所示。,最小费用最大流问题,注：“管理运筹学软件”有专门的子程序用于解决这类问题。,
