[互联网]12997171025437500011-图与网络

1、chapter 11：图与网络模型图与网络模型l11.1 图与网络的基本概念图与网络的基本概念l11.2最短路问题最短路问题l11.3 最小生成树问题最小生成树问题l11.4 最大流问题最大流问题l11.5 最小费用最大流问题最小费用最大流问题page 3图论：图是由点和边构成，可以反映一些对象之间的关系 图g区别于几何学中的图。这里只关心图中有多少个点、以及哪些点之间有连线。例如：在一个人群中，对相互认识这个关系我们可以用图来表示例如：在一个人群中，对相互认识这个关系我们可以用图来表示一般情况下，图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。(v1)赵赵

2、(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5(v1)赵赵(v2)钱钱孙孙(v3) 李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5page 4图论：图是由点和边构成，可以反映一些对象之间的关系。图论：图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。对于反映对象之间的关系并不是重要的。图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，若用点表示研究的对象，用边表示这些对象

3、之间的联系，则图则图g可以定义为可以定义为 “点点” 和和 “边边” 的集合，记作：的集合，记作：,evg 其中其中: v点集点集 e边集边集 图图g区别于几何学中的图。这里只关心图中有多少个点以区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。及哪些点之间有连线。无向图page 5定义定义: 图中的点用图中的点用v表示，边用表示，边用e表示。表示。对每条边可用它所连接的点表示，记作：，记作：e1=v1,v1; e2=v1,v2; v3e7e4e8e5e6e1e2e3v1v2v4v5l 端点，关联边，相邻若有边若有边e可表示为可表示为 e=vi,vj，称，称vi和和vj是是 边

4、边 e 的的端点端点，反之称，反之称 边边e 为为 点点vi或或vj的的关联边关联边。若若 点点vi、vj 与同一条边关联，称与同一条边关联，称 点点vi和和vj 相邻相邻；若；若 边边ei和和ej 具有公共的端具有公共的端点，称点，称 边边ei和和ej 相邻相邻。page 6如果如果 边边e 的两个端点相重，称该边的两个端点相重，称该边为为 环环如右图中边如右图中边e1为环为环如果两个点之间多于一条边，称为如果两个点之间多于一条边，称为多重边多重边，如右图中的，如右图中的e4和和e5对无环、无多重边的图称作对无环、无多重边的图称作简单图简单图v3e7e4e8e5e6e1e2e3v1v2v4v

5、5l 环，多重边，简单图page 7与某一个与某一个 点点vi 相关联的相关联的 边的数目边的数目 称为称为 点点vi的的次次（也叫做度），记作（也叫做度），记作d(vi)右图中右图中d(v1)4，d(v3)=5，d(v5)=1次为奇数的点称作次为奇数的点称作奇点奇点，次为偶数的，次为偶数的点称作点称作偶点偶点，次为，次为1的点称为的点称为悬挂点悬挂点，次为次为0的点称作的点称作孤立点孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次图的次: 一个图的次等于各点的次之和。一个图的次等于各点的次之和。l 次，奇点，偶点，孤立点page 8图中某些点和边的交替序列，若其图中某些点和

6、边的交替序列，若其中各边互不相同，且对任意中各边互不相同，且对任意vt-1和和vt均相邻，称为均相邻，称为链链。用。用 表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5,110kkvevev 起点与终点重合的链称作起点与终点重合的链称作圈（回路）圈（回路）如果任意两个顶点之间至少存在一条如果任意两个顶点之间至少存在一条链，称这样的图为链，称这样的图为连通图连通图l 链，圈（回路），连通图 如果我们把上面例子中的如果我们把上面例子中的“相互认识相互认识”关系改为关系改为“认识认识” ” 的关系，那么只的关系，那么只用两点之间的连线就很难用两点之间的连线就很难刻画他们之间的关系了，

7、刻画他们之间的关系了，这时我们引入一个这时我们引入一个带箭头带箭头的连线的连线，称为，称为弧弧。相互认。相互认识用两条反向的弧表示。识用两条反向的弧表示。11.1 图与网络的基本概念有向图的定义：图图d被定义为被定义为 “点点” 和和 “弧弧” 的集合，记作：的集合，记作：其中其中: v点集；点集； a弧集弧集a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈,avd page 10无向图无向图 g(v, e)，对，对g的每一条的每一条 边边(vi , vj) 相应赋予数量指标相应赋予数量

8、指标wij，称称wij为边为边(vi , vj)上的上的权权，称图，称图g为为赋权图赋权图赋权的有向图赋权的有向图 d = (v, a)，指定一点为，指定一点为 发点发点（vs），指定另一点为），指定另一点为 收点收点（vt），称其它点为），称其它点为中间点中间点，并把，并把 d 中每一条弧的中每一条弧的 赋权数赋权数 cij 称为弧称为弧(vi,vj)的的容量容量，这样的赋权有向图，这样的赋权有向图d就称为就称为网络网络910201571419256l 赋权图，网络权可以代表距离、费用、通过能力(容量) 等等page 11有些问题，如选址、管道铺设时的选线、设备更新、投有些问题，如选址、管道

9、铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。路的问题。因此这类问题在生产实际中得到广泛应用。最短路问题对一个赋权的图（对一个赋权的图（g或或d）中的指定的两个点）中的指定的两个点 vs 和和 vt 找到一条从找到一条从 vs 到到 vt 的路，使得这条路上所有的路，使得这条路上所有 弧（边）的权数的总和最小，弧（边）的权数的总和最小，这条路被称之为从这条路被称之为从vs到到vt的最短路。的最短路。这条路上所有弧的权数的总和被称为从这条路上所有弧的权数的总和被称为

10、从vs到到vt的距离。的距离。从给定的网络图中找出一点到各点 或任意两点之间距离最短的一条路 dijkstra 算法 (双标号法）(3,1)v23527531512 v1（0,s)v5(8,4)v6(2,1)v3(3,3)v41. 给出给出 点点vs 以标号以标号 ( 0, s )2. 找出已标号的点的集合找出已标号的点的集合 i，没标号的点的集合，没标号的点的集合 j，以及，以及弧的集合弧的集合 3. 如果如果 b是空集，则计算结束。是空集，则计算结束。 如果如果vt已标号已标号 ( lt, kt )，则，则 vs到到vt的距离为的距离为lt，而，而从从 vs到到vt的最短路径，则可以从的最

11、短路径，则可以从vt 反向追踪到起点反向追踪到起点vs （根据（根据 kt 的记录）而得到。的记录）而得到。 如果如果vt 未标号，则可以断言不存在从未标号，则可以断言不存在从 vs到到vt的路。的路。11.2 最短路问题dijkstra 双标号法 的步骤：jvivvvbjiji,),(如果上述的弧如果上述的弧(b)的集合不是空集，则转下一步。的集合不是空集，则转下一步。4. 对对b中的每一条弧，计算中的每一条弧，计算 sij = li + cij 。在所有的。在所有的 sij中，中，找到其值为最小的弧。不妨设此弧为（找到其值为最小的弧。不妨设此弧为（vc,vd），则给），则给此弧的终点以双标

12、号（此弧的终点以双标号（scd , c），返回步骤），返回步骤2。11.2 最短路问题dijkstra 双标号法 的步骤：例例1. 求下图中求下图中v1到到v6的最短路的最短路11.2 最短路问题dijkstra 双标号法 ：v23527531512v1v6v5v3v4v23527531512v1v6v5v3v4（0，s）0+30+20+5（2，1）2+1（3，1）(3,3)3+73+5(8,4) v1 v1到到v6v6的最短距离的最短距离为为8 8；最短路为：最短路为：v1 v3 v1 v3 v4 v4 v6v6page 15从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，

13、说明已找到起点vs到到该点的最短路线及最短距离，因此可以将每个点标该点的最短路线及最短距离，因此可以将每个点标号，求出号，求出vs到任意点的最短路线，如果某个点到任意点的最短路线，如果某个点vj不能不能标号，说明标号，说明vs不可达不可达vj 。注：无向图最短路的求法只将上述步骤中的弧改成边即可。注：无向图最短路的求法只将上述步骤中的弧改成边即可。page 16例例3. 求下图求下图v1到各点的最短距离及最短路线。到各点的最短距离及最短路线。4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是 v1 到该点的最短距离，

14、最短路线就是红色的链。page 17课堂练习：课堂练习：1. 用用dijkstra算法求下图从算法求下图从v1到到v6的最短距离及路线。的最短距离及路线。v3v54v1v2v4v635222421v1到到v6的最短路为：的最短路为：6521vvvvpage 182. 求从求从v1到到v8的最短路径的最短路径237184566134105275934682page 19237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路径为的最短路径为v1v4v7v5v8，最短距离为，最短距离为10page 203. 求下图中求下

15、图中v1点到另外任意一点的最短路径点到另外任意一点的最短路径v1v2v3v4v6v5322762133page 21v1v2v3v4 v6v5322762133024714page 22v1v2v3v4 v6v5322762133024714page 23例例4. 电信公司准备在甲、乙两地沿路架设一条光缆线，问电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。通图。权数表示两地间公路的长度（单位：公里）。 v1 （甲地）（甲地）1517624431065

16、v2v7 (乙地乙地)v3v4v5v6page 24解：这是一个求无向图的最短路的问题。解：这是一个求无向图的最短路的问题。 v1 （甲地）（甲地）1517624431065v2v7 (乙地乙地)v3v4v5v6(0,s)(10,1)(13,3)(14,3)(16,5)(18,5)(22,6)甲地到乙地的最短路为：甲地到乙地的最短路为：76531vvvvvpage 25例例5. 设备更新问题。某公司使用一台设备，在每年年初，设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定

17、的购置费，当然新设备的维修费用置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表设备每年年初的价格表年份年份12345年初价格年初价格1111121213page 26设备维修费如下表设备维修费如下表使用年数使用年数0-11-22-33-44-5每年维修费用每年维修费用568111

18、8解：解：将问题转化为最短路问题，如下图：用将问题转化为最短路问题，如下图：用vi表示表示“第第i年年年年初购进一台新设备初购进一台新设备”,弧（弧（vi,vj）表示第）表示第i年年初购进的设备一年年初购进的设备一直使用到第直使用到第j年年初。年年初。v1v2v3v4v5v6page 27把所有弧的权数计算如下表，把权数赋到图中，再用把所有弧的权数计算如下表，把权数赋到图中，再用dijkstra算法求最短路。算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723pag

19、e 28 最终得到下图，可知，最终得到下图，可知，v1到到v6的距离是的距离是53，最短路径有两条：，最短路径有两条： v1v3v6和和 v1v4v6 v1（0,s）v3v4(41,1) v5v62230415916(22,1)3041312317181723 v2（16,1）16(30,1)(53,3)(53,4)page 29性质性质1：任何树中必存在次为：任何树中必存在次为1的点。的点。性质性质2：n 个顶点的树必有个顶点的树必有n-1 条边。条边。性质性质3：树中任意两个顶点之间，恰有且仅有一条链。：树中任意两个顶点之间，恰有且仅有一条链。性质性质4：树连通，但去掉任一条边，必变为不连

20、通。：树连通，但去掉任一条边，必变为不连通。性质性质5：树无回圈，但不相邻的两个点之间加一条边，恰：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。得到一个圈。v1v2v3v4v5v6l 树：无圈的连通图即为树11.3 最小生成树问题图图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)下列图中，哪些是树？下列图中，哪些是树？page 31图图g1=v1、e1和图和图g2=v2，e2，如果有如果有 ，称，称g1是是g2的一个的一个子图子图若有若有 ，则称，则称g1是是g2的一个的一个支撑子图支撑子图2121

21、eevv 和和2121eevv ，v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5(a)v3e7e4e8e6e2e3v1v2v4v5(b)（g图）图）l 子图，支撑子图page 32如果如果g2是是g1的支撑图（生成图），又是树图，则称的支撑图（生成图），又是树图，则称g2是是g1的的生成树（或支撑树）。生成树（或支撑树）。v1v2v3v4v5v1v2v3v4v5g1g2l 图的生成树（支撑树）page 33破圈法l 求支撑树的方法：破圈法 和 避圈法page 34生成树（支撑树）生成树（支撑树）l 求支撑树的方法：破圈法 和 避圈法page 35v1v2v

22、3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5l 求支撑树的方法：破圈法 和 避圈法避圈法page 36最小生成树问题：在一个赋权的、连通的、无向图 g 中找出一个生成树，并使得这个生成树的所有边的权数之和为最小l 图的最小生成树（支撑树）1. 在给定的赋权的连通图上任找一个圈在给定的赋权的连通图上任找一个圈2. 在所找的圈中去掉一个权数最大的边（如果有两条或两在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束

23、，所余下的、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第图即为最小生成树，否则返回第1步。步。求解最小生成树的破圈算法page 37v1v2v4v5v6435215878破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v3边数边数n-1=5l 图的最小生成树（支撑树）6page 38v1v2v3v4v5v643521min c(t)=15l 图的最小生成树（支撑树）page 39page 40page 413749346321min c(t)=12min c(t)=15254173

24、314475答案：答案：page 4234122323242min c(t)=12213638534567454321min c(t)=18例例6. 用破圈算法求图（用破圈算法求图（a）中的一个最小生成树）中的一个最小生成树11.3 最小生成树问题v1331728541034v7v6v5v4v2v3(a)7v6v5v4v2v3(b)v133725434v7v6v5v4v2v31(c)v13372434v7v6v5v4v2v31(d)v4v1337234v7v6v5v2v31(e)v133723v7v6v5v4v2v31(f)例例7. 某大学准备对其所属的某大学准备对其

25、所属的7个学院办公室计算机联网，个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中这个网络的可能联通的途径如下图，图中v1,v7 表表示示7个学院办公室，请设计一个网络能联通个学院办公室，请设计一个网络能联通7个学院办个学院办公室，并使总的线路长度为最短。公室，并使总的线路长度为最短。11.3 最小生成树问题v1331728541034v7v6v5v4v2v3图图11-14 此问题实际上是求图此问题实际上是求图11-1411-14的最小生成树，的最小生成树，这在例这在例6 6中已经求得，中已经求得，即按照图即按照图 (f) (f) 的设计，的设计，可使此网络的总的线可使此网络的总的线

26、路长度为最短，为路长度为最短，为1919百米。百米。v563522241263v1v2v7v4v3v6图图11-2611.4 最大流问题最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。一、最大流的数学模型 例例8. 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（的变化，它的各段管道（vi,vj）的流量）的流量cij（容量

27、）是不一样的。（容量）是不一样的。cij的单的单位为万加仑位为万加仑/小时。如果使用这个网络系统从采地小时。如果使用这个网络系统从采地 v1向销地向销地 v7运送石油，运送石油，问每小时能运送多少加仑石油？问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6图图11-2611.4 最大流问题 我们可以为此例题建立线性规划数学模型：我们可以为此例题建立线性规划数学模型： 设弧设弧(vi,vj)上流量为上流量为fij，网络上的总的流量为，网络上的总的流量为f，则有：，则有：1 41 22 32 51 44 34 64 72 34 33 53 62 53 55 73 64

28、66 75 76 74 71 21 4,1, 2, 6;1, 2,70,1, 2, 6;1, 2,71 2ijijijm a xf =fffffffffffffffffffffffffcijfij目 标 函 数 ：约 束 条 件 ：一、最大流的数学模型11.4 最大流问题 1、在这个线性规划模型中，其约束条件中的前、在这个线性规划模型中，其约束条件中的前6个方程表示个方程表示了网络中的流量必须满足守恒条件：了网络中的流量必须满足守恒条件：发点的流出量必须等于收点的总流入量；发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其余的点称之为中间点，它的总流入量

29、必须等于总流出量。2、对每一条弧、对每一条弧(vi,vj)的流量的流量fij要满足流量的可行条件，应小要满足流量的可行条件，应小于等于弧于等于弧(vi,vj)的容量的容量cij，并大于等于零，即，并大于等于零，即0fij cij。我们把满足守恒条件及流量可行条件的一组网络流 fij 称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。11.4 最大流问题一、最大流的数学模型二、最大流问题的网络图论解法 对网络上弧的容量的表示作改进。对一条弧（对网络上弧的容量的表示作改进。对一条弧（vi,vj)的的容量我们用一对数容量我们用一

30、对数cij,0标在弧（标在弧（vi,vj) 上，上，cij靠近靠近vi点点，0靠靠近近vj点，表示从点，表示从vi到到vj容许通过的容量为容许通过的容量为cij，而从，而从vj到到vi 容容许通过的容量为许通过的容量为0，这样我们可以省去弧的方向了。如下图，这样我们可以省去弧的方向了。如下图: (a)和和 (b)、(c)和和(d)的意义相同。的意义相同。vivjcij0（b）vivj（a） cijcijvivj（cji）（c）vivj cij cji（d）11.4 最大流问题63522241263v1v2v5v7v4v3v60000000000011.4 最大流问题二、最大流问题的网络图论解法

31、用以上方法对例用以上方法对例8的图的容量标号作改进，得下图：的图的容量标号作改进，得下图：（1）找出一条从发点到收点的路，在这条路上的每一条弧）找出一条从发点到收点的路，在这条路上的每一条弧 顺流方向顺流方向的容量都大于零的容量都大于零。如果不存在这样的路，则已经求得最大流。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的）找出这条路上各条弧的 最小的顺流的容量最小的顺流的容量pf，从而通过这条路，从而通过这条路增加网络的流量增加网络的流量pf。（3）在这条路上，减少每一条弧的顺流容量）在这条路上，减少每一条弧的顺流容量pf ，同时增加这些弧的，同时增加这些弧的逆流容量逆流容量

32、pf，返回步骤（，返回步骤（1）。）。 * * * * * 为了使算法更快捷有效，我们一般在步骤（为了使算法更快捷有效，我们一般在步骤（1 1）中尽量选择包）中尽量选择包含弧数最少的路。含弧数最少的路。11.4 最大流问题二、最大流问题的网络图论解法基本算法步骤：基本算法步骤： 第一次迭代：选择路为第一次迭代：选择路为 v1 v4 v7 。弧（。弧（ v4 , v7 ）的）的顺流容量为顺流容量为2，决定了，决定了pf=2，改进的网络流量图如下图：，改进的网络流量图如下图：63522241263v1v2v5v7v4v3v60000000000042022第一次迭代第一次迭代后的总流量后的总流量2

33、11.4 最大流问题二、最大流问题的网络图论解法用此方法对例用此方法对例8求解：求解： 第二次迭代：选择路为第二次迭代：选择路为v1 v2 v5 v7 。弧。弧（ v2 , v5 ）的顺流容量为）的顺流容量为3，决定了，决定了pf=3，改进的网，改进的网络流量图如下图：络流量图如下图：635222413v1v2v5v7v4v3v6000000004202203330355第二次迭代第二次迭代后的总流量后的总流量11.4 最大流问题二、最大流问题的网络图论解法 第三次迭代：选择路为第三次迭代：选择路为v1 v4 v6 v7 。弧。弧（ v4 , v6 ）的顺流容量为）的顺流容量为1，决定了，决定

34、了pf=1，改进的网，改进的网络流量图如下图：络流量图如下图：222413v1v2v5v7v4v3v600000042022033333013166第三次迭代第三次迭代后的总流量后的总流量11.4 最大流问题二、最大流问题的网络图论解法 第四次迭代：选择路为第四次迭代：选择路为v1 v4 v3 v6 v7 。弧。弧（ v3 , v6 ）的顺流容量为）的顺流容量为2，决定了，决定了pf=2，改进的网络流量，改进的网络流量图如下图：图如下图： 22233v1v2v5v7v4v3v611000203203335031200213388第四次迭代第四次迭代后的总流量后的总流量111.4 最大流问题二、

35、最大流问题的网络图论解法 第五次迭代：选择路为第五次迭代：选择路为v1 v2 v3 v5 v7 。弧。弧（ v2 , v3 ）的顺流容量为）的顺流容量为2，决定了，决定了pf=2，改进的网络流量，改进的网络流量图如下图：图如下图：22v1v2v5v7v4v3v6101202033350120213315002020510第五次迭代第五次迭代后的总流量后的总流量1011.4 最大流问题二、最大流问题的网络图论解法经过第五次迭代后在图中已经找不到从发点到收点的一经过第五次迭代后在图中已经找不到从发点到收点的一条路条路路上的每一条弧顺流容量都大于零，运算停止。路上的每一条弧顺流容量都大于零，运算停止

36、。得到最大流量为得到最大流量为10。 最大流量图如下图：最大流量图如下图：22v1v2v5v7v4v3v612352235511.4 最大流问题二、最大流问题的网络图论解法11.5 最小费用最大流问题一个带收发点的网络，对每一条弧（vi,vj），除了给出容量cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流 f，并使得总运送费用最小(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)一、最小费用最大流的数学模型 例例9. 由于输油管道的长短不一，所以在例由于输油管道的长短不一，所以在例6中每段管道

37、（中每段管道（ vi,vj ）除了）除了有不同的流量限制有不同的流量限制cij外，还有不同的单位流量的费用外，还有不同的单位流量的费用bij ，cij的单位为的单位为万加仑万加仑/小时，小时， bij的单位为百元的单位为百元/万加仑。如下图所示。从采地万加仑。如下图所示。从采地 v1 向销向销地地 v7 运送石油，怎样运送才能运送最多的石油并使得总的运送费用最运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量的最小费用。小？求出最大流量的最小费用。11.5 最小费用最大流问题(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2

38、）v1v2v5v7v4v3v6(6,3) 1214252343(,)355736464767121412232514434647234335362535573646675767471214min63452473384. .10,(1, 2,6;ijijijvvaijijfbfffffffffffs tffffffffffffffffffffffffffcij2,3,7),0,(1, 2,6;2,3,7),ijfij一、最小费用最大流的数学模型11.5 最小费用最大流问题一、最小费用最大流的数学模型 一般来说，所谓最小费用流的问题就是：在给定了收点和一般来说，所谓最小费用流的问题就是：在给定了收

39、点和发点并对每条弧发点并对每条弧(vi,vj)赋权以容量赋权以容量cij及单位费用及单位费用bij的网络的网络中，中，求一个给定流量 f 的最小费用，这个给定流量，这个给定流量 f 应小应小于等于最大流量于等于最大流量f，否则无解。，否则无解。 求最小费用流的问题的线性规划的模型只要把最小费用最求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量大流模型中的约束条件中的发点流量f改为改为f即可。即可。11.5 最小费用最大流问题二、最小费用最大流问题的网络图论解法 对网络上弧（对网络上弧（vi,vj）的（）的（cij,bij）的表示作如下改动）的表示作如下改动11

40、.5 最小费用最大流问题vivj（cij,bij ）（0,-bij ）（b）vivj（a）（cij,bij ）（cij,bij ）vivj（cji,bji ）（c）（cij,bij ）vivj（cji,bji ）（0,-bij)（0,-bji)（d）11.5 最小费用最大流问题二、最小费用最大流问题的网络图论解法用以上方法对例用以上方法对例9的图形进行改进，得下图：的图形进行改进，得下图：(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-

41、4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）图图11-2811-2811.5 最小费用最大流问题二、最小费用最大流问题的网络图论解法最小费用最大流的基本算法：最小费用最大流的基本算法： 在对弧的标号作了改进的网络图上求最小费用最大流的基在对弧的标号作了改进的网络图上求最小费用最大流的基本算法，与求最大流的基本算法完全一样，不同的只是：本算法，与求最大流的基本算法完全一样，不同的只是： * 在步骤（在步骤（1）中要选择一条总的单位费用最小的路，而）中要选择一条总的单位费用最小的路，而不是包含边数最小的路。不是包含边数最小的路。用上述方法对例用上述方法对例9求解：求解： 第一次迭

42、代：找到最短路第一次迭代：找到最短路v1 v4 v6 v7。第一次迭。第一次迭代后总流量为代后总流量为1，决定了，决定了pf=1,总费用为总费用为10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）图图11-2911-2911第一次迭代第一次迭代后的总流量后的总流量11.5 最小费用最大流问题二、最小费用最大流问题的网络图论解法 第二次迭代：找到最短路第二次迭代：找到最短路

43、v1 v4 v7。第二次迭代。第二次迭代后总流量为后总流量为3，总费用，总费用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）图图11-3011-3033第二次迭代第二次迭代后的总流量后的总流量11.5 最小费用最大流问题二、最小费用最大流问题的网络图论解法 第三次迭代：找到最短路第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后总流量为第三次迭代后总流量为5，总费用，总费用56。(6,6)(3,4)(5,7)(2,5)(0,-4)（0,3）(1,4)(0,3)(0,8)（1,2）v1v2v5v7v4v3v6(1,3)(5,-3)(2,-8)(1,-3)（2,-2）(0,-6)(0,-