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

《运筹学chap6网络优化模型课件》由会员分享，可在线阅读，更多相关《运筹学chap6网络优化模型课件（52页珍藏版）》请在金锄头文库上搜索。

1、本章主要讨论图论基本概念、理论和方法以及最短路问题、最本章主要讨论图论基本概念、理论和方法以及最短路问题、最大流问题和最小费用流问题等网络优化模型及其基本算法。大流问题和最小费用流问题等网络优化模型及其基本算法。 第六章第六章 图与网络优化模型图与网络优化模型 运筹学chap6网络优化模型第一节第一节 图与网络图与网络p运筹学的重要分支运筹学的重要分支n主要应用领域：物理学、化学、控制论、信息论、主要应用领域：物理学、化学、控制论、信息论、科学管理、电子计算机等科学管理、电子计算机等n图论理论和方法应用实例：图论理论和方法应用实例：p在组织生产中，为完成某项生产任务，各工序之在组织生产中，为完

2、成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。间怎样衔接，才能使生产任务完成得既快又好。p一个邮递员送信，要走完他负责投递的全部街道，一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。所走的路程最短。p各种通信网络的合理架设，交通网络的合理分布各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。等问题，应用图论的方法求解都很简便。运筹学chap6网络优化模型p图论的起源与发展图论的起源与发展n七桥问题：七桥问题：哥尼斯堡城中有一条河叫普雷格尔河，该河中有两

3、个岛，哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥。当时那里的居民热衷于这样的问题：一个散步者能否河上有七座桥。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。图走过七座桥，且每座桥只走过一次，最后回到出发点。图8-1(a)图6-1n欧拉在欧拉在1736年发表了图论方面的第一篇论文，解决了著名的哥尼斯年发表了图论方面的第一篇论文，解决了著名的哥尼斯堡堡七桥问题七桥问题。n欧拉将此问题归结为如图欧拉将此问题归结为如图6-1(b)所示图形的一笔画问题。即能否从所示图形的一笔画问题。即能否从某一点开始，不重复地一笔画出这个图形，最后回到

4、出发点。欧拉证某一点开始，不重复地一笔画出这个图形，最后回到出发点。欧拉证明了这是不可能的，因为图明了这是不可能的，因为图6-1(b)中的每个点都只与奇数条线相关中的每个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成。联，不可能将这个图不重复地一笔画成。运筹学chap6网络优化模型一、一、 图的基本概念图的基本概念p人们为反映一些对象之间关系时，常会用示意图。n例1 右图是我国北京、上海等十个城市间的铁路交通图，反映了这十个城市间的铁路分布情况。这里用点代表城市，用点和点之间的连线代表这两个城市之间的铁路线。n其他示意图的例子p电话线分布图、煤气管道图、航空线图等。铁路交通示意图铁路交

5、通示意图图6-2图是由点和边构成，可以反映一些图是由点和边构成，可以反映一些对象之间的关系。对象之间的关系。运筹学chap6网络优化模型p例例2 有甲、乙、丙、丁、戊五个球队，它们之间比赛的情有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况用图表示出来。况用图表示出来。n已知甲队和其他各队都比赛过一次，乙队和甲、丙队比已知甲队和其他各队都比赛过一次，乙队和甲、丙队比赛过，丙队和甲、乙、丁队比赛过，丁队和甲、丙、戊赛过，丙队和甲、乙、丁队比赛过，丁队和甲、丙、戊队比赛过，戊队和甲、丁队比赛过。为了反映这个情况，队比赛过，戊队和甲、丁队比赛过。为了反映这个情况，可以用点分别代表这五个队，某两个队之

6、间比赛过，就可以用点分别代表这五个队，某两个队之间比赛过，就在这两个队所相应的点之间联一条线，这条线不过其他在这两个队所相应的点之间联一条线，这条线不过其他的点，如图的点，如图6-3所示。所示。比赛情况图比赛情况图图6-3运筹学chap6网络优化模型p关系的关系的对称性和非称性和非对称性：称性：n几个例子中涉及到的几个例子中涉及到的对象之象之间的的“关系关系”具有具有“对称性称性”，就是，就是说，如果甲，如果甲与乙有与乙有这种关系，那么同种关系，那么同时乙与甲也有乙与甲也有这种关系。种关系。n实际生活中，有生活中，有许多关系不具有多关系不具有这种种对称性。称性。 p如例如例2，如果人，如果人们

7、关心的是五个球关心的是五个球队比比赛的的胜负情况，那么从情况，那么从图5-3中中就看不出来了。就看不出来了。为了反映了反映这一一类关系，可以用一条关系，可以用一条带箭箭头的的连线表示。表示。p例如，如果球例如，如果球队v1胜了球了球队v2，可以从，可以从v1引一条引一条带箭箭头的的连线到到v2p类似似胜负这种非种非对称性的关系，在生称性的关系，在生产和生活中是常和生活中是常见的，如交通运的，如交通运输中的中的“单行行线”，部，部门之之间的的领导与被与被领导的关系，一的关系，一项工程中各工工程中各工序之序之间的先后关系等。的先后关系等。比赛胜负图比赛胜负图6-4运筹学chap6网络优化模型术语术

8、语顶点（结点）、弧、边（取消弧的方向）、有向图、无向图、链、道路、顶点（结点）、弧、边（取消弧的方向）、有向图、无向图、链、道路、环、连通图、连通子图、次环、连通图、连通子图、次1234123412345213次道路顶点无向图链有向图弧环连通图 弧是由一对有序的顶点组成，表示了两个顶点之间可能运动的方向 连通子图 由顶点集和弧 组成的图称为有向图有向图 由顶点集和边组成的图称为无向图无向图 链有一序列弧，如果每一个弧与前一个弧恰有一个公共顶点，则称这一序列弧为一个链。 道路 如果链中每一个弧的终点是下面一个弧的起点，则这个链称为一个道路。 环环 连接连接a a点与点与b b点的一条链，如点的一

9、条链，如果果a a与与b b是同一个是同一个点时，称此链为点时，称此链为环。环。 连通图连通图 一个图一个图中任意两点间至中任意两点间至少有一个链相连，少有一个链相连，则称此图为连通则称此图为连通图。图。 任何一个不连通图任何一个不连通图都可以分为若干个都可以分为若干个连通子图，每一个连通子图，每一个子图称为原图的一子图称为原图的一个分图。个分图。 次次: 以以a点为点为顶点的边的条顶点的边的条数称为顶点的数称为顶点的次次 图6-5运筹学chap6网络优化模型例：例： 设设V = v1 , v2 , v3 , v4, E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 ,

10、 v3v4, 画出画出G = (V, E ) 的图的图。或或运筹学chap6网络优化模型二、网络二、网络l 点或边带有某种数量指标的图叫网络网络图图，简称网络网络。l 与点或边有关的某些数量指标，我们经常称之为权权，权可以代表如距离、费用、容量等。 左图可以看作：左图可以看作： 从发电厂（节点1）向某城市（节点6）输送电力，必须通过中转站（节点2，3，4，5）转送，边上数字代表两节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。 一个输油管道网。节点1表示管道的起点，节点6表示管道的终点，节点2到5表示中转站，旁边的数字表示该段管道能通过的最大输送量。应怎样安排输油线路

11、，使从节点1到节点6的总输送量最大？ 一张城市分布图。现在要在各城市之间架设电话线，应如何架设，使各城市之间既能通话，又使总的架设路线最短？ 运筹学chap6网络优化模型第二节第二节 树树p定义定义1（树的定义）（树的定义）n连通且不含环的无向图称为树。p例例1 某工厂的组织机构如下所示工厂组织机构图工厂组织机构图运筹学chap6网络优化模型 树的性质树的性质： 任意两顶点之间必有一条且仅有一条链。 去掉任一条边，则树成为不连通图。 不相邻的两个顶点间添上一条边，恰好得到一个环。运筹学chap6网络优化模型部分图、生成子图、部分树部分图、生成子图、部分树 部分图部分图如果如果如果如果VV1 1

12、 V V， E E1 1 E E则称则称则称则称GG1 1为为为为( (全部顶点和部分边全部顶点和部分边全部顶点和部分边全部顶点和部分边)G)G的部分图；的部分图；的部分图；的部分图；设设设设G=(VG=(V，E E) )和和和和GG1 1=(V=(V1 1，E E1 1) )运筹学chap6网络优化模型部分图、生成子图、部分树部分图、生成子图、部分树 部分图部分图生成子图生成子图设设设设G=(VG=(V，E E) )和和和和GG1 1=(V=(V1 1，E E1 1) ) 如果如果如果如果GG1 1=(V=(V1 1，E E1 1) )，G=(VG=(V，E E) )，并且，并且，并且，并且

13、VV1 1 V V ， , ,则称则称则称则称GG1 1为为为为GG的生成子图；的生成子图；的生成子图；的生成子图；运筹学chap6网络优化模型部分图、生成子图、部分树部分图、生成子图、部分树 部分图部分图生成子图生成子图部分树部分树如果如果如果如果VV1 1 V V， E E1 1 E E则称则称则称则称GG1 1为为为为GG的部分图；的部分图；的部分图；的部分图；设设设设G=(VG=(V，E E) )和和和和GG1 1=(V=(V1 1，E E1 1) ) 如果如果如果如果GG1 1=(V=(V1 1，E E1 1) )，G=(VG=(V，E E) )，并且，并且，并且，并且VV1 1 V

14、 V ， , ,则称则称则称则称GG1 1为为为为GG的生成子图；的生成子图；的生成子图；的生成子图； 如果如果如果如果G=(VG=(V，E E) )的部分的部分的部分的部分图图图图GG1 1=(V=(V，E E1 1) )是树是树是树是树，则称则称则称则称GG1 1为为为为GG的一个部分树。的一个部分树。的一个部分树。的一个部分树。 运筹学chap6网络优化模型1325464332322最小生成树不一定唯一最小生成树不一定唯一最小生成树：最小生成树：设有一连通图设有一连通图G=(V,L),对于每一边对于每一边e=(vi,vj)，有一个权，有一个权wij0。一棵生成树所有树枝上权的总和，称为这

15、个生成树的权。具有一棵生成树所有树枝上权的总和，称为这个生成树的权。具有最小权的生成树称为最小生成树（最小树）。最小权的生成树称为最小生成树（最小树）。 运筹学chap6网络优化模型 例：某大学准备对其所属的例：某大学准备对其所属的7个学院办公室计算机联网，这个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中个网络的可能联通的途径如下图，图中v1,v7 表示表示7个学个学院办公室，请设计一个网络能联通院办公室，请设计一个网络能联通7个学院办公室，并使总个学院办公室，并使总的线路长度为最短。的线路长度为最短。v1331728541034v7v6v5v4v2v3图图6-11运筹学chap

16、6网络优化模型方法一：破圈法方法一：破圈法步骤：步骤：1、在给定的赋权的连通图上任找一个圈。、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边（如、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第所余下的图即为最小生成树，否则返回第1步。步。运筹学chap6网络优化模型v1331728541034v7v6v5v4v2v13317285434v7v

17、6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)解：按照图解：按照图16-1116-11的的(f)(f)设计，可使此网络的总的线路长度为最短，为设计，可使此网络的总的线路长度为最短，为19001900米。米。运筹学chap6网络优化模型方法二：方法二：(加边加边)避圈法（避圈法（Kruskal）p开始选一条最小权的边，以后每一步中，开始选一条最小权的边，以后每一步中，总从未被选中的边中选一条最小权的边，总从未被选中

18、的边中选一条最小权的边，使之与已选的边不构成圈，直到所有的使之与已选的边不构成圈，直到所有的边都检验完，即可得最小树。（每步中，边都检验完，即可得最小树。（每步中，若有两条或两条以上的边都是权最小的若有两条或两条以上的边都是权最小的边，则从中任选一条）。边，则从中任选一条）。 运筹学chap6网络优化模型例：右图例：右图, ,用避圈用避圈法求其最小生成法求其最小生成树。树。 类似地类似地, ,可定义连通可定义连通图图G 的最大生成树的最大生成树. .运筹学chap6网络优化模型练习：房屋开发商正规划设计某居住新区的下水管练习：房屋开发商正规划设计某居住新区的下水管道，图中各数字表示各栋楼房之间

19、铺设管道的工程道，图中各数字表示各栋楼房之间铺设管道的工程费用。房屋开发商应怎样设计最佳的管道铺设方案，费用。房屋开发商应怎样设计最佳的管道铺设方案，使总工程费用最少。使总工程费用最少。 2873965657单位：十万元6V1V2V3V5V4V6运筹学chap6网络优化模型从一特殊的节点出发，找出从该节点到网络中任何其它节点的最短路径问题从一特殊的节点出发，找出从该节点到网络中任何其它节点的最短路径问题某人买了一辆价值12000美元的新车，一辆车每年的维护费用依赖于年初时的车龄，具体费用见下表。为了避免旧车的高维护费用，他决定卖掉旧车买新车。旧车的价格依赖于交易时的车龄，见右表。为计算简单起见

20、，假设任何时间新车的价格不变均为12000美元。他希望在今后5年内的净费用最小（ 即 ： 净 费 用=购 买 价+维 护 价-售 出 价 ） 。 车龄每年的每年的维护费用用售出价格售出价格123456200040005000900012000700060002000100001234562177777121212213131441221第三节第三节 最短路问题最短路问题 节点i表示第i年年初，当ij时，弧（i,j）表示第i年年初买一辆新车并一直用到第j年年初。弧（i,j）的长度为cij，cij表示如果第i年年初买车并在第j年年初卖掉更换新车，从第i年年初到第j年年初期间总费用。Cij=(i,i

21、+1,j-1年的维护费)+第i年年初买新车的费用-第j年年初该车的售出价格C12=2+12-7=7C13+c35+c56是1到6的最小费用，第3年年初与第五年初交易，今后5年的净费用最小。运筹学chap6网络优化模型算法算法（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标

22、号；在所有剩下的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)=0运筹学chap6

23、网络优化模型pDijkstra方法方法的基本思想：的基本思想：n从从vs出出发，逐步向外探，逐步向外探寻最短路。最短路。执行行过程中，程中，与每个点与每个点对应，记录下一个数下一个数(称称为这个点的个点的标号号)，它或者表示从，它或者表示从vs到到该点的最短路的点的最短路的权(称称为P标号号)，或者是从，或者是从vs到到该点的最短路的点的最短路的权的上界的上界(称称为T标号号)，方法的每一步是去修改，方法的每一步是去修改T标号，并号，并且把某一个具且把某一个具T标号的点改号的点改变为具具P标号的点，从号的点，从而使而使D中具中具P标号的号的顶点数多一个，点数多一个，这样，至多，至多经过p1步，

24、就可以求出从步，就可以求出从vs到各点的最短路。到各点的最短路。运筹学chap6网络优化模型p例：用例：用Dijkstra方法求方法求图8-4所示的所示的赋权图中，从中，从v1到所有点的最短路。到所有点的最短路。图8-4运筹学chap6网络优化模型p解：解： 计算的最后算的最后结果果为nP(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。n这样从从v1到到v8的最短的最短链为(v1，v3，v2，v5，v9，v8)，总权为11。运筹学chap6网络优化模型p练习：练习： 设备更新问题设备更新问题。某企

25、业使用一台设备，在每年年初，。某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备，购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。现在的问题是如何制定一个几年则需支付一定的维修费用。现在的问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少。我们用一个之内的设备更新计划，使得总的支付费用最少。我们用一个五年之内要更新某种设备的计划为例，若已知该种设备在各五年之内要更新某种设备的计划为例，若已知该种设备在各年年初的价格为

26、：年年初的价格为：第第1年年第第2年年第第3年年第第4年年第第5年年1111121213v还已知使用不同时间还已知使用不同时间(年年)的设备所需要的维修费用为：的设备所需要的维修费用为：使用年数使用年数0112233445维维修修费费用用5681118运筹学chap6网络优化模型v可供选择的设备更新方案显然是很多的。可供选择的设备更新方案显然是很多的。v例如，每年都购置一台新设备，则其购置费用例如，每年都购置一台新设备，则其购置费用为为11+11+12+12+13=59，而每年支付的维修费用，而每年支付的维修费用为为5，五年合计为，五年合计为25。于是五年总的支付费用为。于是五年总的支付费用为

27、59+25=84。v又如决定在第一、三、五年各购进一台，这个又如决定在第一、三、五年各购进一台，这个方案的设备购置费为方案的设备购置费为11+12+13=36，维修费为，维修费为5+6+5+6+5=27。五年总的支付费用为。五年总的支付费用为63。运筹学chap6网络优化模型p解：如何制定使得总的支付费用最少的设备更新计划解：如何制定使得总的支付费用最少的设备更新计划呢呢? ?可以把这个问题化为最短路问题，见图可以把这个问题化为最短路问题，见图8-58-5。图8-5运筹学chap6网络优化模型这样这样一来，制定一个最一来，制定一个最优优的的设备设备更新更新计计划划问题问题就等价于就等价于寻寻求

28、求从从v1到到v6的最短路的的最短路的问题问题。n按求解最短路的按求解最短路的计算方法，算方法，nv1，v3，v6及及v1，v4，v6均均为最短路，即有两个最最短路，即有两个最优方案。方案。n一个方案是在第一个方案是在第1年、第年、第3年各年各购置一台新置一台新设备；n另一个方案是在第另一个方案是在第1年、第年、第4年各年各购置一台新置一台新设备。n五年五年总的支付的支付费用均用均为53。 运筹学chap6网络优化模型 城市出租车公司在纽约市为出租车司机已经确定了城市出租车公司在纽约市为出租车司机已经确定了10个搭乘车站。个搭乘车站。为了减少运行时间，提高服务质量以及最大化利用公司的车队，为了

29、减少运行时间，提高服务质量以及最大化利用公司的车队，管理方希望出租车司机尽可能地选择最短路线。使用下面公路与管理方希望出租车司机尽可能地选择最短路线。使用下面公路与街道的网络图，请说明司机从车站街道的网络图，请说明司机从车站1到车站到车站10应选择什么样的路应选择什么样的路线。运行时间如图所示。线。运行时间如图所示。最优路线为：最优路线为：1 11010，最短距离是，最短距离是25 25 运筹学chap6网络优化模型例：六个村庄每村上学人数见下表，村与村的距离例：六个村庄每村上学人数见下表，村与村的距离见下图，现只能在某一个村建一所小学，问在哪个见下图，现只能在某一个村建一所小学，问在哪个村建

30、校最为合理？村建校最为合理？村庄村庄ABCDEF上学人数上学人数6040503070100ABCEFD633647281运筹学chap6网络优化模型第四节第四节 网络最大流问题网络最大流问题p一、基本概念与基本定理一、基本概念与基本定理p二、寻求最大流的标号法二、寻求最大流的标号法运筹学chap6网络优化模型容量网络、可行流容量网络、可行流24531142010519152730流流 量量容量 容量网络：容量网络：标有弧容量的网络。156104610150可行流可行流 网络流的两个条件：网络流的两个条件：每个弧的流量不能超过该弧的最大通过能力，即容容量；量；中间支点的流量为零。可行流：可行流：

31、中间点的流量为零。而发点和收点的流量必须相等。运筹学chap6网络优化模型可行流与最大流可行流与最大流 在运输网络的实际问题中可以看出，对于流有两个明显的要求：在运输网络的实际问题中可以看出，对于流有两个明显的要求：1.是每个弧上的流量不能超过该弧的最大通过能力是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量即弧的容量)；2.是中间点的流量为零。是中间点的流量为零。 因为对于每个点，运出这点的产品总量与运进这点的产品总量因为对于每个点，运出这点的产品总量与运进这点的产品总量之差，是这点的净输出量，简称为是这一点的流量；之差，是这点的净输出量，简称为是这一点的流量；由于中间由于中间点只起转

32、运作用，所以中间点的流量必为零。点只起转运作用，所以中间点的流量必为零。 易见发点的净流出量和收点的净流入量必相等，也是这个方案易见发点的净流出量和收点的净流入量必相等，也是这个方案的总输送量。因此有：的总输送量。因此有：运筹学chap6网络优化模型p定定义： 满足下述条件的流足下述条件的流 f 称称为可行流可行流： (1) 容量限制条件：容量限制条件：对每一弧每一弧(vi，vj)A0fijcij (2) 平衡条件：平衡条件： 对于中于中间点：流出量等于流入量，即点：流出量等于流入量，即对每个每个i(is,t发点与点与收点收点)有有p对于于发点点vs，记p对于收点于收点vt，记 式中式中v(f

33、 )称称为这个可行流的流量，即个可行流的流量，即发点的点的净输出量出量(或收或收点的点的净输入量入量)。运筹学chap6网络优化模型p可行流可行流总是存在的。比如令所有弧的流量是存在的。比如令所有弧的流量fij=0，就得到一，就得到一个可行流个可行流(称称为零流零流)。其流量。其流量v(f)=0。p最大流最大流问题就是求一个流就是求一个流fij使其流量使其流量v(f)达到最大，并达到最大，并且且满足：足：0fijcij (vi，vj)A p最大流最大流问题是一个特殊的是一个特殊的线性性规划划问题。即求一。即求一组fij，在在满足条件足条件和和下使下使v(f)达到极大。将会看到利用达到极大。将会

34、看到利用图的特的特点，解决点，解决这个个问题的方法的方法较之之线性性规划的一般方法要方便、划的一般方法要方便、直直观得多。得多。 运筹学chap6网络优化模型增广链增广链13425201051419152730156104610150饱和弧非饱和弧零弧增广链增广链增广链增广链: : 设设f f是一个可行流，是一个可行流，C C 是从发点是从发点VsVs到收点到收点V Vt t的一条链，若的一条链，若C C 满足以满足以 下条件，则称下条件，则称C C 为一条增广链：为一条增广链：(1) (1) 在弧在弧 上，上， ，即，即C C+ +( (弧的方向与链的方向一致弧的方向与链的方向一致 ) )中

35、每一中每一条弧是非饱和弧条弧是非饱和弧(2) (2) 在弧在弧 上，上， ，即，即C C- -( (弧的方向与链的方向相反弧的方向与链的方向相反 ) )中每一中每一条弧是非零流弧条弧是非零流弧 C中每一条弧是非饱和弧中每一条弧是非饱和弧; C中每一条弧是非零流弧。中每一条弧是非零流弧。 运筹学chap6网络优化模型割集割集21st28811 任给一个包含收点但不包含发点的支点集任给一个包含收点但不包含发点的支点集V*，则称，则称i(弧起点弧起点)不属于不属于V*，j(弧终点弧终点)属于属于V*的弧的弧(i,j)的全体为割集。的全体为割集。 割集的容量是割集中所有弧的容量的总和。割集的容量是割集

36、中所有弧的容量的总和。 如果将割集从网络中移去，则就不可能有从起点到终点的路径。如果将割集从网络中移去，则就不可能有从起点到终点的路径。 一个网络可能有许多割集。一个网络可能有许多割集。 任何从发点到收点的可行流小于等于任何割集的容量。直观上说，截集是从任何从发点到收点的可行流小于等于任何割集的容量。直观上说，截集是从vs到到vt的必经之道。的必经之道。V*割集割集任何割集的容量是从起点到终点的最大流的上界。如果能找到一个可行流和一个割集使得割集从起点到终点的容量等于可行流的流量，则该可行流就是 一个最大流。 最大流最大流-最小割集定理最小割集定理 V*=1,t割集是割集是(s s,1),1)

37、，(2,(2,t t)，容量，容量2+1=32+1=3 支点集支点集V V*=1,2,*=1,2,t t , ,割集？割集？(s,1)，(s,2),容量容量2+8=10运筹学chap6网络优化模型 从一个可行流从一个可行流 出发，（若网络中没有给定出发，（若网络中没有给定f f，则可以设，则可以设f f是零流）需是零流）需要经过标号过程与调整过程。要经过标号过程与调整过程。1 1标号过程标号过程 在这个过程中，网络中的点或是标号点或是未标号点。每个标号点的标号包含在这个过程中，网络中的点或是标号点或是未标号点。每个标号点的标号包含两部分：第一标号表示它的标号是从哪一点得到的，以便找出增广链；第

38、二两部分：第一标号表示它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量个标号是为确定增广链的调整量 用的。用的。 标号过程开始时，总是先给发点标号过程开始时，总是先给发点 标上标上 。其余各点标号的规则是：。其余各点标号的规则是： 设设 是已标号的点，检查与是已标号的点，检查与 点关联的另一顶点未标号的弧：点关联的另一顶点未标号的弧：（1 1）如果在弧）如果在弧 上（即前向弧），上（即前向弧）， ，则给，则给 标号标号 ，其中其中 。如果。如果 ，则，则 不标号。不标号。（2 2）如果在弧）如果在弧 上（即后向弧），上（即后向弧）， ，则给，则给 标号标号 ，其中，其

39、中 ，负号说明经后向弧到，负号说明经后向弧到 。如果。如果 ，则，则 不标号。不标号。 重复上述步骤，直到被重复上述步骤，直到被 标上号，表明得到一条从标上号，表明得到一条从 到到 的增广链的增广链C C，转，转入调整过程。入调整过程。求最大流的标号算法求最大流的标号算法运筹学chap6网络优化模型求最大流的标号算法求最大流的标号算法 2 2调整过程调整过程 由收点由收点 标号算出的标号算出的 作为调整量（即作为调整量（即 ）。对）。对增广链各弧的调整如下：增广链各弧的调整如下： 增广链以外各弧流量不变。去掉所有标号，对新的可行流增广链以外各弧流量不变。去掉所有标号，对新的可行流 ，重新进入标

40、号过程。直到标号过程中断。当前流就是最，重新进入标号过程。直到标号过程中断。当前流就是最大流。大流。运筹学chap6网络优化模型标号算法标号算法vsv2v1v3vt32223(0,+) 找到初始可行流。找到初始可行流。 给网络中的各个点标号：给网络中的各个点标号： 总是先给发点总是先给发点v vs s标上标上(0,+)(0,+)。 其余各点标号的规则是：设其余各点标号的规则是：设v vi i是已标是已标号的点，检查与点号的点，检查与点v vi i关联的另一顶点未关联的另一顶点未标号的弧：标号的弧：（1 1）如果在弧）如果在弧( (v vi i,v,vj j) )上（即前向弧），上（即前向弧），

41、f fijij 00，则给，则给v vj j标号标号(-(-v vi i,l(v,l(vj j)，其中，其中l l(v(vj j)=)=minl(vminl(vi i),f),fjiji ，负号说明经后向，负号说明经后向弧到弧到v vi i。如果。如果f fjiji=0=0，则，则v vj j不标号。不标号。 调整：调整： 按照第一标号找到增广链，按照第一标号找到增广链， 按第二标号的最小值调整可行流，得按第二标号的最小值调整可行流，得到新的可行流。到新的可行流。 重复标号过程，直到没有增广链，即重复标号过程，直到没有增广链，即得到最大流。得到最大流。 2112114(vs,2)(v3,1)(

42、-v2,1)(v1,1)222022如下图所示，弧上数字表示该弧的容如下图所示，弧上数字表示该弧的容量，求该网络的最大流。量，求该网络的最大流。增广链以外各弧流量不变增广链以外各弧流量不变 运筹学chap6网络优化模型标号算法标号算法vsv2v1v3vt32223(0,+)重复标号过程重复标号过程。 给网络中的各个点标号：给网络中的各个点标号： 先给发点先给发点v vs s标上标上(0,+)(0,+)。 检查检查vsvs给给v v2 2标上标上(v(vs s,1),1)，检，检查查v v2 2, ,在弧在弧(v(v2 2,v,vt t) )上上,f,f2t2t=C=C2t2t=2,=2,不满足

43、标号条件，在弧不满足标号条件，在弧(v(v1,1,v v2 2) )上，上，f f1212=0,=0,也不满足标也不满足标号条件，标号无法继续。算号条件，标号无法继续。算法结束。法结束。4(vs,1)222022如下图所示，弧上数字表示该弧的容如下图所示，弧上数字表示该弧的容量，求该网络的最大流。量，求该网络的最大流。最大流量为从发点流出的量最大流量为从发点流出的量 这时的可行流就是所求的最大流这时的可行流就是所求的最大流 运筹学chap6网络优化模型练习： 用用标号法求号法求图8-7所示网所示网络的最大流。的最大流。弧旁的数是弧旁的数是(cij，fij)。图8-7运筹学chap6网络优化模型

44、解：解： (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运筹学chap6网络优化模型 检查v1，在弧，在弧(v1，v3)上，上，f13=2，c13=2，不，不满足足标号条件。号条件。在弧在弧(v2，v1)上，上，f21=10，则给v2记下下标号号为(-v1，l (v2)，这里里l (v2)=minl (v1)，

45、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=

46、1因因vt有了有了标号，故号，故转入入调整整过程。程。 运筹学chap6网络优化模型图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不不变。运筹学chap6网络优化模型 调调整后得如下整后得如下图图所示的可行流，所示的可行流，对这对这个可行流个可行流进进入入标标号号过过程，程，寻寻找

47、增广找增广链链。开始给vs标以(0，+)，于是检查vs，给v1标以(vs,3)，检查v1，弧(v1,v3)上，f13c13，弧(v2,v1)上，f21=0，均不符号条件，标号过程无法继续下去，算法结束。这时的可行流即为所求最大流。最大流量为v(f)=fs1+fs2=f4t+f3t=5与此同时可找到最小截集 ， 其中V1为标号点集合，为未标号点集合。弧集合即为最小截集。 运筹学chap6网络优化模型从一个费用最小的可行流 出发（这样的可行流一定存在，因为费用 ，所以 就是一个流量为0的最小费用流），找出这个可行流 的费用最小的一条增广链L，沿L调整 ，直到找不到费用最小的增广链，就得到了最小费用最大流。第五节第五节 最小费用流问题最小费用流问题 对于网络图G中的弧，除标明弧的容量 外，还要标明流过该弧单位流量的费用 ，G的一个可行流 ，使得流的总运输费用：达到最小。特别，如果可行流是最大流时，此问题就是最小费用最大流问题。 最小费用流问题最小费用流问题最小费用最大流的基本思路最小费用最大流的基本思路运筹学chap6网络优化模型p例：以例：以图8-6为例，求最小例，求最小费用最大流。弧旁数字用最大流。弧旁数字为(bij,cij)。图8-6运筹学chap6网络优化模型运筹学chap6网络优化模型图5-3运筹学chap6网络优化模型