运筹学chap6网络优化模型ppt课件

本章主要讨论图论根本概念、实际和方法以及最短路问题、最本章主要讨论图论根本概念、实际和方法以及最短路问题、最大流问题和最小费用流问题等网络优化模型及其根本算法。大流问题和最小费用流问题等网络优化模型及其根本算法。第六章第六章 图与网络优化模型图与网络优化模型 第一节第一节 图与网络图与网络运筹学的重要分支运筹学的重要分支主要运用领域：物理学、化学、控制论、信主要运用领域：物理学、化学、控制论、信息论、科学管理、电子计算机等息论、科学管理、电子计算机等图论实际和方法运用实例：图论实际和方法运用实例：在组织消费中，为完成某项消费义务，各工在组织消费中，为完成某项消费义务，各工序之间怎样衔接，才干使消费义务完成得序之间怎样衔接，才干使消费义务完成得既快又好。既快又好。一个邮递员送信，要走完他担任投递的全部一个邮递员送信，要走完他担任投递的全部街道，完成义务后回到邮局，应该按照怎街道，完成义务后回到邮局，应该按照怎样的道路走，所走的路程最短。样的道路走，所走的路程最短。各种通讯网络的合理架设，交通网络的合理各种通讯网络的合理架设，交通网络的合理分布等问题，运用图论的方法求解都很简分布等问题，运用图论的方法求解都很简便。便。p图论的来源与开展图论的来源与开展p七桥问题：哥尼斯堡城中有一条河叫普雷格尔河，该河中有七桥问题：哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥。当时那里的居民热衷于这样的问题：两个岛，河上有七座桥。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。图到出发点。图8-1(a)图6-1n欧拉在欧拉在1736年发表了图论方面的第一篇论文，处理了著名的哥尼斯年发表了图论方面的第一篇论文，处理了著名的哥尼斯堡七桥问题。堡七桥问题。n欧拉将此问题归结为如图欧拉将此问题归结为如图6-1(b)所示图形的一笔画问题。即能否从所示图形的一笔画问题。即能否从某一点开场，不反复地一笔画出这个图形，最后回到出发点。欧拉证某一点开场，不反复地一笔画出这个图形，最后回到出发点。欧拉证明了这是不能够的，由于图明了这是不能够的，由于图6-1(b)中的每个点都只与奇数条线相关中的每个点都只与奇数条线相关联，不能够将这个图不反复地一笔画成。联，不能够将这个图不反复地一笔画成。一、一、图的根本概念图的根本概念p人们为反映一些对象之间关系时，常会用表示图。p例1 右图是我国北京、上海等十个城市间的铁路交通图，反映了这十个城市间的铁路分布情况。这里用点代表城市，用点和点之间的连线代表这两个城市之间的铁道路。p其他表示图的例子p线分布图、煤气管道图、航空线图等。铁路交通表示图铁路交通表示图图6-2图是由点和边构成，可以反映一图是由点和边构成，可以反映一些对象之间的关系。些对象之间的关系。p例例2 有甲、乙、丙、丁、戊五个球队，它们之间竞赛的情有甲、乙、丙、丁、戊五个球队，它们之间竞赛的情况用图表示出来。况用图表示出来。p知甲队和其他各队都竞赛过一次，乙队和甲、丙队竞赛过，知甲队和其他各队都竞赛过一次，乙队和甲、丙队竞赛过，丙队和甲、乙、丁队竞赛过，丁队和甲、丙、戊队竞赛过，丙队和甲、乙、丁队竞赛过，丁队和甲、丙、戊队竞赛过，戊队和甲、丁队竞赛过。为了反映这个情况，可以用点分别戊队和甲、丁队竞赛过。为了反映这个情况，可以用点分别代表这五个队，某两个队之间竞赛过，就在这两个队所相应代表这五个队，某两个队之间竞赛过，就在这两个队所相应的点之间联一条线，这条线不过其他的点，如图的点之间联一条线，这条线不过其他的点，如图6-3所示。所示。竞赛情况图竞赛情况图图6-3p关系的对称性和非对称性：关系的对称性和非对称性：p几个例子中涉及到的对象之间的几个例子中涉及到的对象之间的“关系具有关系具有“对称性，就是说，假设甲对称性，就是说，假设甲与乙有这种关系，那么同时乙与甲也有这种关系。与乙有这种关系，那么同时乙与甲也有这种关系。p实践生活中，有许多关系不具有这种对称性。实践生活中，有许多关系不具有这种对称性。p如例如例2，假设人们关怀的是五个球队竞赛的胜负情况，那么从图，假设人们关怀的是五个球队竞赛的胜负情况，那么从图5-3中就看不中就看不出来了。为了反映这一类关系，可以用一条带箭头的连线表示。出来了。为了反映这一类关系，可以用一条带箭头的连线表示。p例如，假设球队例如，假设球队v1胜了球队胜了球队v2，可以从，可以从v1引一条带箭头的连线到引一条带箭头的连线到v2p类似胜负这种非对称性的关系，在消费和生活中是常见的，如交通运输中的类似胜负这种非对称性的关系，在消费和生活中是常见的，如交通运输中的“单行线，部门之间的指点与被指点的关系，一项工程中各工序之间的先单行线，部门之间的指点与被指点的关系，一项工程中各工序之间的先后关系等。后关系等。竞赛胜负图竞赛胜负图6-4术语术语顶点结点、弧、边取消弧的方向、有顶点结点、弧、边取消弧的方向、有向图、无向图、链、道路、环、连通图、连通向图、无向图、链、道路、环、连通图、连通子图、次子图、次1234123412345213次道路顶点无向图链有向图弧环连通图 弧是由一对有序的顶点组成，表示了两个顶点之间能够运动的方向 连通子图 由顶点集和弧 组成的图称为有向图 由顶点集和边组成的图称为无向图 链有一序列弧，假设链有一序列弧，假设每一个弧与前一个弧每一个弧与前一个弧恰有一个公共顶点，恰有一个公共顶点，那么称这一序列弧为那么称这一序列弧为一个链。一个链。道路道路 假设链中每一假设链中每一个弧的终点是下面一个弧的终点是下面一个弧的起点，那么这个弧的起点，那么这个链称为一个道路。个链称为一个道路。环环 衔接衔接a点与点与b点的点的一条链，假设一条链，假设a与与b是同一个点时，称此是同一个点时，称此链为环。链为环。连通图连通图 一个图中恣一个图中恣意两点间至少有一个意两点间至少有一个链相连，那么称此图链相连，那么称此图为连通图。为连通图。任何一个不连通图都任何一个不连通图都可以分为假设干个连可以分为假设干个连通子图，每一个子图通子图，每一个子图称为原图的一个分图。称为原图的一个分图。次次:以以a点为顶点的点为顶点的边的条数称为顶点的边的条数称为顶点的次次 图6-5例：例：设设V=v1,v2,v3,v4,E=V=v1,v2,v3,v4,E=v1v2,v1v3,v1v4,v2v3,v2v4,v1v2,v1v3,v1v4,v2v3,v2v4,v3v4,v3v4,画出画出G=(V,E)G=(V,E)的图。的图。或或二、网络二、网络l 点或边带有某种数量目的的图叫网络图，简称网络。l 与点或边有关的某些数量目的，我们经常称之为权，权可以代表如间隔、费用、容量等。左图可以看作：左图可以看作：从发电厂节点从发电厂节点1向某城市节向某城市节点点6保送电力，必需经过中转站保送电力，必需经过中转站节点节点2，3，4，5转送，边上转送，边上数字代表两节点间的间隔。电力公数字代表两节点间的间隔。电力公司希望选择适宜的中转站，使从电司希望选择适宜的中转站，使从电厂到城市的传输道路最短。厂到城市的传输道路最短。一个输油管道网。节点一个输油管道网。节点1表示管道表示管道的起点，节点的起点，节点6表示管道的终点，表示管道的终点，节点节点2到到5表示中转站，旁边的数表示中转站，旁边的数字表示该段管道能经过的最大保送字表示该段管道能经过的最大保送量。应怎样安排输油线路，使从节量。应怎样安排输油线路，使从节点点1到节点到节点6的总保送量最大？的总保送量最大？一张城市分布图。如今要在各城一张城市分布图。如今要在各城市之间架设线，应如何架设，使各市之间架设线，应如何架设，使各城市之间既能通话，又使总的架设城市之间既能通话，又使总的架设道路最短？道路最短？13254643323221325464332322第二节第二节 树树p定义定义1树的定义树的定义p连通且不含环的无向图称为树。连通且不含环的无向图称为树。p例例1 某工厂的组织机构如下所示某工厂的组织机构如下所示 树的性质：恣意两顶点之间必有一条且仅有一条链。去掉任一条边，那么树成为不连通图。不相邻的两个顶点间添上一条边，恰好得到一个环。部分图、生成子图、部分树部分图、生成子图、部分树 部分图部分图部分图、生成子图、部分树部分图、生成子图、部分树 部分图部分图生成子图生成子图,|),(111VvVuEvuE部分图、生成子图、部分树部分图、生成子图、部分树 部分图部分图生成子图生成子图部分树部分树,|),(111VvVuEvuE1325464332322最小生成树不一定独一最小生成树不一定独一最小生成树：最小生成树：设有一连通图设有一连通图G=(V,L),对于每一边对于每一边e=(vi,vj)，有一个权，有一个权wij0。一棵生成树一切树枝上权的总和，称为这个生成树的权。具一棵生成树一切树枝上权的总和，称为这个生成树的权。具有最小权的生成树称为最小生成树最小树。有最小权的生成树称为最小生成树最小树。例：某大学预备对其所属的例：某大学预备对其所属的7个学院办公室计算机联网，这个网络的能够联通的途径如以个学院办公室计算机联网，这个网络的能够联通的途径如以下图，图中下图，图中v1,v7 表示表示7个学院办公室，请设计一个网络能联通个学院办公室，请设计一个网络能联通7个学院办公室，并使个学院办公室，并使总的线路长度为最短。总的线路长度为最短。v1331728541034v7v6v5v4v2v3图图6-11方法一：破圈法方法一：破圈法步骤：步骤：1、在给定的赋权的连通图上任找一个圈。、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边假、在所找的圈中去掉一个权数最大的边假设有两条或两条以上的边都是权数最大的边，设有两条或两条以上的边都是权数最大的边，那么恣意去掉其中一条。那么恣意去掉其中一条。3、假设所余下的图已不包含圈，那么计算终、假设所余下的图已不包含圈，那么计算终了，所余下的图即为最小生成树，否那么前了，所余下的图即为最小生成树，否那么前往第往第1步。步。v1331728541034v7v6v5v4v2v13317285434v7v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)解：按照图解：按照图16-1116-11的的(f)(f)设计，可使此网络的总的线路长度为最短，为设计，可使此网络的总的线路长度为最短，为19001900米。米。p方法二：(加边)避圈法Kruskalp开场选一条最小权的边，以后每一步中，总从未被选中的边中选一条最小权的边，使之与已选的边不构成圈，直到一切的边都检验完，即可得最小树。每步中，假设有两条或两条以上的边都是权最小的边，那么从中任选一条。例：右图例：右图,用避圈用避圈法求其最小生成法求其最小生成树。树。类似地类似地,可定义连通可定义连通图图G G 的最大生成树的最大生成树.练习：房屋开发商正规划设计某居住新区的下水管练习：房屋开发商正规划设计某居住新区的下水管道，图中各数字表示各栋楼房之间铺设管道的工程道，图中各数字表示各栋楼房之间铺设管道的工程费用。房屋开发商应怎样设计最正确的管道铺设方费用。房屋开发商应怎样设计最正确的管道铺设方案，使总工程费用最少。案，使总工程费用最少。2873965657单位：十万元6V1V2V3V5V4V6从一特殊的节点出发，找出从该节点到网络中任何其它节点的最短途径问题从一特殊的节点出发，找出从该节点到网络中任何其它节点的最短途径问题某人买了一辆价值12000美圆的新车，一辆车每年的维护费用依赖于年初时的车龄，详细费用见下表。为了防止旧车的高维护费用，他决议卖掉旧车买新车。旧车的价钱依赖于买卖时的车龄，见右表。为计算简单起见，假设任何时间新车的价钱不变均为12000美圆。他希望在今后5年内的净费用最小即：净费用=购买价+维护价-售出价。车龄车龄每年的维护费用每年的维护费用售出价钱售出价钱123456200040005000900012000700060002000100001234562177777121212213131441221第三节第三节 最短路问题最短路问题 节点i表示第i年年初，当ij时，弧i,j表示第i年年初买一辆新车并不断用到第j年年初。弧i,j的长度为cij，cij表示假设第i年年初买车并在第j年年初卖掉改换新车，从第i年年初到第j年年初期间总费用。Cij=(i,i+1,j-1年的维护费)+第i年年初买新车的费用-第j年年初该车的售出价钱C12=2+12-7=7C13+c35+c56是1到6的最小费用，第3年年初与第五年初买卖，今后5年的净费用最小。算法算法Dijkstra(迪杰斯特拉迪杰斯特拉)1959年提出的年提出的1325464332322 第0步：P(1)=0,T(i)=+；第1步：与1相连的标号为2,3，均是T标号，修正2,3的标号，T(2)=minT(2),P(1)+w12=min+,P(1)+w12=4,T(3)=3；在一切的T标号中，3的标号最小，改3的标号为P(3)=3；第2步：修正与3相连的T标号；在一切剩下的T标号中，2的标号最小，改为P(2)=4；第3步：修正与2相连的T标号；在一切剩下的T标号中，5的标号最小，改为P(5)=6；第4步：修正与5相连的T标号；在一切剩下的T标号中，4的标号最小，改为P(4)=7；第5步：修正与4相连的T标号；只剩下节点6是T标号，修正6的标号，P(6)=8。从节点6开场回退，得到最短路。P(1)=0T(3)=+T(2)=+T(3)=3T(5)=+P(3)=3T(5)=6T(2)=4T(4)=+T(6)=+P(2)=4T(4)=7P(5)=6T(6)=8P(4)=7P(6)=8P(6)=8P(5)=6P(3)=3P(1)=0pDijkstra方法的根本思想：方法的根本思想：p从从vs出发，逐渐向外探寻最短路。执行过程中，与出发，逐渐向外探寻最短路。执行过程中，与每个点对应，记录下一个数每个点对应，记录下一个数(称为这个点的标号称为这个点的标号)，它或者表示从它或者表示从vs到该点的最短路的权到该点的最短路的权(称为称为P标号标号)，或者是从或者是从vs到该点的最短路的权的上界到该点的最短路的权的上界(称为称为T标号标号)，方法的每一步是去修正方法的每一步是去修正T标号，并且把某一个具标号，并且把某一个具T标号的点改动为具标号的点改动为具P标号的点，从而使标号的点，从而使D中具中具P标号标号的顶点数多一个，这样，至多经过的顶点数多一个，这样，至多经过p1步，就可以步，就可以求出从求出从vs到各点的最短路。到各点的最短路。p例：用例：用Dijkstra方法求图方法求图8-4所示的赋权图中，从所示的赋权图中，从v1到一切点的最短路。到一切点的最短路。图8-4p解：解：计算的最后结果为计算的最后结果为pP(v1)=0，P(v4)=1，P(v3)=3，P(v2)=5，P(v5)=6，P(v9)=8，P(v7)=9，P(v6)=10，P(v8)=11。p这样从这样从v1到到v8的最短链为的最短链为(v1，v3，v2，v5，v9，v8)，总，总权为权为11。p练习：练习：设备更新问题。某企业运用一台设备，在每年年初，设备更新问题。某企业运用一台设备，在每年年初，企业指点部门就要决议是购置新的，还是继续运用旧的。假企业指点部门就要决议是购置新的，还是继续运用旧的。假设购置新设备，就要支付一定的购置费用；假设继续运用旧设购置新设备，就要支付一定的购置费用；假设继续运用旧设备，那么需支付一定的维修费用。如今的问题是如何制定设备，那么需支付一定的维修费用。如今的问题是如何制定一个几年之内的设备更新方案，使得总的支付费用最少。我一个几年之内的设备更新方案，使得总的支付费用最少。我们用一个五年之内要更新某种设备的方案为例，假设知该种们用一个五年之内要更新某种设备的方案为例，假设知该种设备在各年年初的价钱为：设备在各年年初的价钱为：第第1年年第第2年年第第3年年第第4年年第第5年年1111121213v还知运用不同时间还知运用不同时间(年年)的设备所需求的维修费用为：的设备所需求的维修费用为：运用年数运用年数0112233445维修费用维修费用5681118v可供选择的设备更新方案显然是很多的。可供选择的设备更新方案显然是很多的。v例如，每年都购置一台新设备，那么其购置费例如，每年都购置一台新设备，那么其购置费用为用为11+11+12+12+13=59，而每年支付的维修费，而每年支付的维修费用为用为5，五年合计为，五年合计为25。于是五年总的支付费用。于是五年总的支付费用为为59+25=84。v又如决议在第一、三、五年各购进一台，这个又如决议在第一、三、五年各购进一台，这个方案的设备购置费为方案的设备购置费为11+12+13=36，维修费为，维修费为5+6+5+6+5=27。五年总的支付费用为。五年总的支付费用为63。p解：如何制定使得总的支付费用最少的设备更新方案解：如何制定使得总的支付费用最少的设备更新方案呢呢?可以把这个问题化为最短路问题，见图可以把这个问题化为最短路问题，见图8-58-5。图8-5这样一来，制定一个最优的设备更新方案问题就等价于寻求这样一来，制定一个最优的设备更新方案问题就等价于寻求从从v1到到v6的最短路的问题。的最短路的问题。按求解最短路的计算方法，按求解最短路的计算方法，v1，v3，v6及及v1，v4，v6均为最短路，即有两个最均为最短路，即有两个最优方案。优方案。一个方案是在第一个方案是在第1年、第年、第3年各购置一台新设备；年各购置一台新设备；另一个方案是在第另一个方案是在第1年、第年、第4年各购置一台新设备。年各购置一台新设备。五年总的支付费用均为五年总的支付费用均为53。城市出租车公司在纽约市为出租车司机曾经确定了10个搭乘车站。为了减少运转时间，提高效力质量以及最大化利用公司的车队，管理方希望出租车司机尽能够地选择最短道路。运用下面公路与街道的网络图，请阐明司机从车站1到车站10应选择什么样的道路。运转时间如下图。最优道路为：最优道路为：1 11010，最短间隔是，最短间隔是25 25 例：六个村庄每村上学人数见下表，村与村的间隔例：六个村庄每村上学人数见下表，村与村的间隔见以下图，现只能在某一个村建一所小学，问在哪见以下图，现只能在某一个村建一所小学，问在哪个村建校最为合理？个村建校最为合理？村庄村庄ABCDEF上学人数上学人数6040503070100ABCEFD633647281第四节第四节 网络最大流问题网络最大流问题p一、根本概念与根本定理一、根本概念与根本定理p二、寻求最大流的标号法二、寻求最大流的标号法容量网络、可行流容量网络、可行流24531142010519152730流流 量量容量 容量网络：标有弧容量的网络。156104610150可行流可行流 网络流的两个条件：每个弧的流量不能超越该弧的最大经过才干，即容量；中间支点的流量为零。可行流：中间点的流量为零。而发点和收点的流量必需相等。可行流与最大流可行流与最大流 在运输网络的实践问题中可以看出，对于流有两个明显的要求：在运输网络的实践问题中可以看出，对于流有两个明显的要求：1.是每个弧上的流量不能超越该弧的最大经过才干是每个弧上的流量不能超越该弧的最大经过才干(即弧的容即弧的容量量)；2.是中间点的流量为零。是中间点的流量为零。由于对于每个点，运出这点的产品总量与运进这点的产品总量由于对于每个点，运出这点的产品总量与运进这点的产品总量之差，是这点的净输出量，简称为是这一点的流量；由于中之差，是这点的净输出量，简称为是这一点的流量；由于中间点只起转运作用，所以中间点的流量必为零。间点只起转运作用，所以中间点的流量必为零。易见发点的净流出量和收点的净流入量必相等，也是这个方案易见发点的净流出量和收点的净流入量必相等，也是这个方案的总保送量。因此有：的总保送量。因此有：p定义：定义：满足下述条件的流满足下述条件的流 f 称为可行流：称为可行流：p (1)容量限制条件：对每一弧容量限制条件：对每一弧(vi，vj)Ap0fijcijp (2)平衡条件：平衡条件：p 对于中间点：流出量等于流入量，即对每个对于中间点：流出量等于流入量，即对每个i(is,t发点发点与收点与收点)有有p对于发点对于发点vs，记，记p对于收点对于收点vt，记，记p 式中式中v(f)称为这个可行流的流量，即发点的净输出量称为这个可行流的流量，即发点的净输出量(或或收点的净输入量收点的净输入量)。()A()A0ijjii jjiv,vv,vffssss()A()A()jjjjv,vv,vffvftttt()A()A()jjjjv,vv,vffv f p可行流总是存在的。比如令一切弧的流量可行流总是存在的。比如令一切弧的流量fij=0，就得到一，就得到一个可行流个可行流(称为零流称为零流)。其流量。其流量v(f)=0。p最大流问题就是求一个流最大流问题就是求一个流fij使其流量使其流量v(f)到达最大，并到达最大，并且满足：且满足：p0fijcij (vi，vj)A p p p最大流问题是一个特殊的线性规划问题。即求一组最大流问题是一个特殊的线性规划问题。即求一组fij，在满足条件和下使在满足条件和下使v(f)到达极大。将会看到利用图的特到达极大。将会看到利用图的特点，处理这个问题的方法较之线性规划的普通方法要方便、点，处理这个问题的方法较之线性规划的普通方法要方便、直观得多。直观得多。()()0()()()i jjiv fi=sffis,t-v fi=t增广链增广链13425201051419152730156104610150饱和弧非饱和弧零弧增广链增广链增广链增广链:设设f f是一个可行流，是一个可行流，C C 是从发点是从发点VsVs到收点到收点VtVt的一条链，假设的一条链，假设C C 满足以满足以 下条件，那么称下条件，那么称C C 为一条增广链：为一条增广链：(1)(1)在弧在弧 上，上，即，即C+(C+(弧的方向与链的方向一致弧的方向与链的方向一致 )中中每一条弧是非饱和弧每一条弧是非饱和弧(2)(2)在弧在弧 上，上，即，即C-(C-(弧的方向与链的方向相反弧的方向与链的方向相反 )中中每一条弧是非零流弧每一条弧是非零流弧Cvvji),(ijijcf 0ijijcf 0Cvvji),(C中每一条弧是非饱和弧中每一条弧是非饱和弧;C中每一条中每一条弧是非零流弧。弧是非零流弧。割集割集21st28811 任给一个包含收点但不包含发点的支点集V*，那么称i(弧起点)不属于V*，j(弧终点)属于V*的弧(i,j)的全体为割集。割集的容量是割集中一切弧的容量的总和。假设将割集从网络中移去，那么就不能够有从起点到终点的途径。一个网络能够有许多割集。任何从发点到收点的可行流小于等于任何割集的容量。直观上说，截集是从vs到vt的必经之道。V*割集割集任何割集的容量是从起点到终点的最大流的上界。假设能找到一个可行流和一个割集使得割集从起点到终点的容量等于可行流的流量，那么该可行流就是 一个最大流。最大流最大流-最小割集定理最小割集定理 V*=1,t割集是割集是(s,1)(s,1)，(2,t)(2,t)，容量，容量2+1=3 2+1=3 支点集支点集V V*=1,2,t,=1,2,t,割集？割集？(s,1)，(s,2),容量容量2+8=100jifjv)(,(jivlv 从一个可行流从一个可行流 出发，假设网络中没有给定出发，假设网络中没有给定f f，那么可以设，那么可以设f f是零流是零流需求经过标号过程与调整过程。需求经过标号过程与调整过程。1 1标号过程标号过程 在这个过程中，网络中的点或是标号点或是未标号点。每个标号点的标号包含在这个过程中，网络中的点或是标号点或是未标号点。每个标号点的标号包含两部分：第一标号表示它的标号是从哪一点得到的，以便找出增广链；第二两部分：第一标号表示它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量个标号是为确定增广链的调整量 用的。用的。标号过程开场时，总是先给发点标号过程开场时，总是先给发点 标上标上 。其他各点标号的规那么是：。其他各点标号的规那么是：设设 是已标号的点，检查与是已标号的点，检查与 点关联的另一顶点未标号的弧：点关联的另一顶点未标号的弧：1 1假设在弧假设在弧 上即前向弧，上即前向弧，那么给，那么给 标号标号 ，其中其中 。假设。假设 ，那么，那么 不标号。不标号。2 2假设在弧假设在弧 上即后向弧，上即后向弧，那么给，那么给 标号标号 ，其，其中中 ，负号阐明经后向弧到，负号阐明经后向弧到 。假设。假设 ，那么，那么 不标号。不标号。反复上述步骤，直到被反复上述步骤，直到被 标上号，阐明得到一条从标上号，阐明得到一条从 到到 的增广链的增广链C C，转，转入调整过程。入调整过程。ijijcfijff sv),0(iviv),(jivvijijcf)(,(jivlvjv),(min)(ijijijfcvlvljv),(ijvv),(min)(jiijfvlvliv0ijfjvtv)(,(jivlvsv求最大流的标号算法求最大流的标号算法tv0jif求最大流的标号算法求最大流的标号算法 2 2调整过程调整过程 由收点由收点 标号算出的标号算出的 作为调整量即作为调整量即 。对。对增广链各弧的调整如下：增广链各弧的调整如下：tv)(tvl)(tvlCvvfCvvffjiijjiijij),(),(增广链以外各弧流量不变。去掉一切标号，对新的可行流 ，重新进入标号过程。直到标号过程中断。当前流就是最大流。ijff标号算法标号算法vsv2v1v3vt32223(0,+)找到初始可行流。给网络中的各个点标号：总是先给发点vs标上(0,+)。其他各点标号的规那么是：设vi是已标号的点，检查与点vi关联的另一顶点未标号的弧：1假设在弧(vi,vj)上即前向弧，fij0，那么给vj标号(-vi,l(vj)，其中l(vj)=minl(vi),fji，负号阐明经后向弧到vi。假设fji=0，那么vj不标号。调整：按照第一标号找到增广链，按第二标号的最小值调整可行流，得到新的可行流。反复标号过程，直到没有增广链，即得到最大流。2112114(vs,2)(v3,1)(-v2,1)(v1,1)222022如以下图所示，弧上数字表示该弧的如以下图所示，弧上数字表示该弧的容量，求该网络的最大流。容量，求该网络的最大流。CvvfCvvffjiijjiijij),(),(增广链以外各弧流量不变增广链以外各弧流量不变 标号算法标号算法vsv2v1v3vt32223(0,+)反复标号过程。反复标号过程。给网络中的各个点标号：给网络中的各个点标号：先给发点先给发点vs标上标上(0,+)。检查检查vs给给v2标上标上(vs,1)，检查检查v2,在弧在弧(v2,vt)上上,f2t=C2t=2,不满足标号不满足标号条件，在弧条件，在弧(v1,v2)上，上，f12=0,也不满足标号条件，也不满足标号条件，标号无法继续。算法终了。标号无法继续。算法终了。4(vs,1)222022如以下图所示，弧上数字表示该弧的如以下图所示，弧上数字表示该弧的容量，求该网络的最大流。容量，求该网络的最大流。最大流量为从发点流出的量最大流量为从发点流出的量 422)(21ssfffv这时的可行流就是所求的最大流这时的可行流就是所求的最大流 练习：练习：用标号法求图用标号法求图8-7所示网络的最大流。所示网络的最大流。弧旁的数是弧旁的数是(cij，fij)。图8-7解：解：(1)标号过程标号过程 首先给首先给vs标上标上(0，+)检查检查vs，在弧，在弧(vs，v2)上，上，fs2=cs2=3，不满足标，不满足标号条件。弧号条件。弧(vs，v1)上，上，fs1=1，cs1=5，fs1cs1，那，那么么v1的标号为的标号为(vs，l(v1)，其中，其中l(v1)=minl(vs)，(cs1-fs1)=min+，5-1=4 检查检查v1，在弧，在弧(v1，v3)上，上，f13=2，c13=2，不满足标号条件。，不满足标号条件。在弧在弧(v2，v1)上，上，f21=10，那么给，那么给v2记下标号为记下标号为(-v1，l(v2)，这里这里l(v2)=minl(v1)，f21=min4，1=1 检查检查v2，在弧，在弧(v2，v4)上，上，f21=3，c24=4，f24c24，那么，那么给给v4标号标号(v2，l(v4)，这里，这里l(v4)=minl(v2)，(c24-f24)=min1，1=1在弧在弧(v3，v2)上，上，f32=10，给，给v3标号：标号：(-v2，l(v3)，这里，这里l(v3=minl(v2)，f32=min1，1=1 在在v3，v4中任选一个进展检查。例如中任选一个进展检查。例如在弧在弧(v3，vt)上，上，f3t=1，c3t=2，f3tc3t，给，给vt标号为标号为(v3，l(vt)，这里，这里l(vt)=minl(v3)，(c3t-f3t)=min1，1=1因因vt有了标号，故转入调整过程。有了标号，故转入调整过程。图8-8(2)调整过程按点的第一个标号找到一条增广链，如图调整过程按点的第一个标号找到一条增广链，如图8-8中双中双箭头线表示。箭头线表示。易见易见 +=(vs，v1)，(v3，vt)-=(v2，v1)，(v3，v2)按按=1在在上调整上调整f。+上：上：fs1+=1+1=2 f3t+=1+1=2 -上：上：f21=11=0 f32=11=0其他的其他的fij不变。不变。1V11(V,V)调整后得如以下图所示的可行流，对这个可行流进入标号过程，寻觅增广链。开场给vs标以(0，+)，于是检查vs，给v1标以(vs,3)，检查v1，弧(v1,v3)上，f13c13，弧(v2,v1)上，f21=0，均不符号条件，标号过程无法继续下去，算法终了。这时的可行流即为所求最大流。最大流量为v(f)=fs1+fs2=f4t+f3t=5与此同时可找到最小截集，其中V1为标号点集合，为未标号点集合。弧集合即为最小截集。11(V,V)从一个费用最小的可行流 出发这样的可行流一定存在，由于费用 ，所以 就是一个流量为0的最小费用流，找出这个可行流 的费用最小的一条增广链L，沿L调整 ，直到找不到费用最小的增广链，就得到了最小费用最大流。第五节第五节 最小费用流问题最小费用流问题 对于网络图G中的弧，除标明弧的容量 外，还要标明流过该弧单位流量的费用 ，G的一个可行流 ，使得流的总运输费用：到达最小。特别，假设可行流是最大流时，此问题就是最小费用最大流问题。ijcijbijff Ljiijijfbfb),()(ijff 0ijb0fff最小费用流问题最小费用流问题最小费用最大流的根本思绪最小费用最大流的根本思绪p例：以图例：以图8-6为例，求最小费用最大流。弧旁数字为为例，求最小费用最大流。弧旁数字为(bij,cij)。图8-6图5-3