运筹学-图与网络模型以及最小费用最大流分解讲课教案

1、福建师范大学经济学院管管 理理 运运 筹筹 学学运筹学-图与网络模型以及最小费用最大流分解近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名这就是著名的的“哥尼斯堡哥尼斯堡 7 桥桥”难题。难题。Euler1736年证明了不可能存在这样年证明了不可能存在这样的路线。的路线。 图论中图是由点和边构成，可以反映一些对象之间的关系。图论中图是由点和边构成，可以反映一些对象之间的关系。 一般情况下图中点的相对位置如何、点与点之间联线的长短曲一般情况下图

2、中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。直，对于反映对象之间的关系并不是重要的。若用点表示研究的对象，用边表示这些对象之间的联系，则图若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作：可以定义为点和边的集合，记作：,EVG 其中其中: : V点集点集 E边集边集 图图G区别于几何学中的图。这里只关心图中有多少个点以及哪区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。些点之间有连线。(v1)赵(v2)钱孙(v3) 李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)

3、孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来例如：在一个人群中，对相互认识这个关系我们可以用图来表示。表示。a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈图图11-3 如果我们把上面例子中的如果我们把上面例子中的“相互认识相互认识”关系改为关系改为“认识认识” ” 的关系，那么只用两点之间的联线就很难刻画他们之间的关的关系，那么只用两

4、点之间的联线就很难刻画他们之间的关系了，这是我们引入系了，这是我们引入一个带箭头的联线，称为弧一个带箭头的联线，称为弧。图。图11-311-3就就是一个反映这七人是一个反映这七人“认识认识”关系的图。相互认识用两条反向关系的图。相互认识用两条反向的弧表示。的弧表示。 定义定义: : 图中的点用图中的点用v v表示，边用表示，边用e e表示。对每条边可用它所表示。对每条边可用它所连接的点表示，记作：连接的点表示，记作：e e1 1=v=v1 1,v,v1 1; e; e2 2=v=v1 1,v,v2 2; ; v3e7e4e8e5e6e1e2e3v1v2v4v5若有边若有边e可表示为可表示为e=

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

6、v4v5 图中某些点和边的交替序列，若其图中某些点和边的交替序列，若其中各边互不相同，且对任意中各边互不相同，且对任意Vi-1,Vi 和和vi+1均相邻称为均相邻称为链链。用。用表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5,110kkvevev 起点与终点重合的链称作起点与终点重合的链称作圈圈。如。如果每一对顶点之间至少存在一条果每一对顶点之间至少存在一条链，称这样的图为链，称这样的图为连通图连通图，否则，否则称称图不连通图不连通。 ）(P232)(P232)设图设图G（V，E），对），对G的每一条边的每一条边(vi,vj)相应赋予数量指标相应赋予数量指标wij，wij称为

7、边称为边(vi,vj)的权的权,赋予权的图赋予权的图G称为称为网络网络(或赋权图）。或赋权图）。权权可以代表距离、费用、通过能力可以代表距离、费用、通过能力(容量容量)等等。等等。端点无序的赋权图称为端点无序的赋权图称为无向网络无向网络，端点有序的赋权图称为，端点有序的赋权图称为有有向网络。向网络。910201571419256无向图无向图：由点和边构成的图，记作：由点和边构成的图，记作G=（V，E）。）。有向图有向图：由点和弧构成的图，记作：由点和弧构成的图，记作D=（V，A）。）。连通图连通图：对无向图：对无向图G，若，若两个不同的点之间，至少存在一条链，则两个不同的点之间，至少存在一条链

8、，则G为连通图。为连通图。回路回路：若路的第一个点和最后一个点相同，则该路为回路。：若路的第一个点和最后一个点相同，则该路为回路。赋权图赋权图：对一个无向图：对一个无向图G的每一条边的每一条边(vi,vj)，相应地有一个数，相应地有一个数wij，则称，则称图图G为赋权图，为赋权图，wij称为边称为边(vi,vj)上的权。上的权。网络网络：在：在中指定一点，称为发点，指定另一点称为收点，中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，中的每一条弧的赋权数称为弧的容量，D就就称为网络。称为网络。 如何用最短的线路将三部电话连

9、起来？如何用最短的线路将三部电话连起来？ 此问题可抽象为设此问题可抽象为设ABC为等边三角形，连接三顶点为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如线者显然是二边之和（如ABAC）。）。ABCABCP 但若增加一个周转站（新点但若增加一个周转站（新点P），连接），连接4点的新网络的最短点的新网络的最短路线为路线为PAPBPC。最短新路径之长。最短新路径之长N比原来只连三点比原来只连三点的最短路径的最短路径O要短。这样得到的网络不仅比原来节省材料，要短。这样得到的网络不仅比原来节省材料，而且稳定性也

10、更好。而且稳定性也更好。 要求：要求：就是从给定的网络图中找出一点到各点或任意两就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路点之间距离最短的一条路 .有些问题，如选址、管道铺设时的选线、设备更新、投有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应最短路的问题。因此这类问题在生产实际中得到广泛应用。用。一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人

11、以外，只能到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。以用求最短路方法解决。 1）人）人M（Man），狼），狼W（Wolf），）， 羊羊G（Goat），）， 草草H（Hay） 2） 点点 Vi 表示河岸的状态表示河岸的状态 3） 边边 ek 表示由状态表示由状态 vi 经一次渡河到状态

12、经一次渡河到状态 vj 4） 权权边边 ek 上的权定为上的权定为 1我们可以得到下面的加权有向图我们可以得到下面的加权有向图： 状态说明：状态说明： v1,u1 =( M,W,G,H ); v2,u2 =(M,W,G); v3,u3 =(M,W,H); v4,u4=(M,G,H); v5,u5 =(M,G)此游戏转化为在下面的二部图中求从此游戏转化为在下面的二部图中求从 v v1 1 到到 u u1 1 的最短路问题。的最短路问题。v1v2v3v4v5u5u4u3u2u1 求最短路有两种算法求最短路有两种算法: : 狄克斯屈拉狄克斯屈拉(Dijkstra)（双标号）算法（双标号）算法 逐次逼

13、近算法逐次逼近算法最短路问题：最短路问题：对一个赋权的有向图对一个赋权的有向图D中的指定的两个点中的指定的两个点Vs和和Vt找找到一条从到一条从 Vs 到到 Vt 的路，使得这条路上所有弧的权数的总和最小，的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从这条路被称之为从Vs到到Vt的最短路。这条路上所有弧的权数的总的最短路。这条路上所有弧的权数的总和被称为从和被称为从Vs到到Vt的距离。的距离。若序列若序列 vs,v1.vn-1,vn 是从是从vs到到vt间的最短路，则序列间的最短路，则序列 vs,v1.vn-1 必为从必为从vs 到到vn-1的最短路。的最短路。假定假定v1v2 v

14、3 v4是是v1 v4的最短路，则的最短路，则v1 v2 v3一定是一定是v1 v3的最短路，的最短路，v2 v3 v4也一定是也一定是v2 v4的的最短路。最短路。v1v2v3v4v51.给出点V1以标号(0,s)2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合3. 如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则 vs到vt的距离为lt，而从 vs到vt的最短路径，则可以从kt 反向追踪到起点vs 而得到。如果vt 未标号，则可以断言不存在从 vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步。4. 对上述弧的集合中的每一条弧，计算 sij=li+ci

15、j 。在所有的 sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。( ,)|,ijijv vvI vJ(P233)例例1 求下图中求下图中v1到到v6的最短路的最短路解：采用解：采用Dijkstra算法，可解得最短路径为算法，可解得最短路径为v1 v3 v4 v6 各点的标号图如下：各点的标号图如下：v23527531512v1v6v5v3v4(3,1)v23527531512 V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4( P234) 例例2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使电信公司准备在甲、乙

16、两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。的长度（单位：公里）。 解：这是一个求无向图的最短路的问题。可以把无向图的每一边解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（）都用方向相反的两条弧（vi,vj）和（）和（vj,vi）代替，就化为有向图，）代替，就化为有向图，即可用即可用Dijkstra算法来求解。也可直接在无向图中用算法来求解。也可直接在无向图中用Dijkstra算法来求解。算法来求解。只要在算法

17、中把从已标号的点到未标号的点的弧的集合改成已标号的点到只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。未标号的点的边的集合即可。 V1 （甲地）（甲地）151762444 31065v2V7 （乙地）（乙地）v3v4v5v6（0,s） V1 （甲地）（甲地）1517624431065(13,3) v2 (22,6)V7 （乙地）（乙地）V5(14,3)V6(16,5) V3(10,1) V4(18,5) 例例3 3 设备更新问题。某公司使用一台设备，在每年年初，公司就要设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用

18、旧设备。如果购置新设备，就要支付一决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。使得五年内购置费用和维修费用总的支付费用最小。 已知：设备每年年初的价格表已知：设备每年年初的价格表 设备维修费如下表设备维修费如下表年份年份12345年初价格年初价格1111121213使用年数使用

19、年数0-11-22-33-44-5每年维修每年维修费用费用5681118例例3的解：的解： 将问题转化为最短路问题，如下图：将问题转化为最短路问题，如下图： 用用vi表示表示“第第i年年初购进一台新设备年年初购进一台新设备”,弧（弧（vi,vj）表示第）表示第i年年初购进年年初购进的的设备一直使用到第设备一直使用到第j年年初。年年初。把所有弧的权数计算如下表：把所有弧的权数计算如下表：v1v2v3v4v5v6123456116223041592162230413172331417235186 (继上页继上页) 把权数赋到图中，再用把权数赋到图中，再用Dijkstra算法求最短路。算法求最短路。

20、 最终得到下图，可知，最终得到下图，可知，v1到到v6的距离是的距离是53，最短路径有两条：，最短路径有两条： v1 v3 v6和和 v1 v4 v6v1v2v3v4v5v6162230415916223041312317181723 V1（0,s）v3v4(41,1) v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4) 课堂练习：课堂练习：1. 用用Dijkstra算法求下图从算法求下图从v1到到v6的最短距离及路线。的最短距离及路线。v3v54v1v2v4v635222421v1到到v6的最短路为：的最短路为：

21、6521vvvv 2. 求从求从v1到到v8的最短路径的最短路径237184566134105275934682237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10 v1到到v8的最短路径为的最短路径为v1v4v7v5v8，最短距离为，最短距离为10 3. 求下图中求下图中v1点到另外任意一点的最短路径点到另外任意一点的最短路径v1v2v3v4v6v5322762133v1V2V3V4 V6V5322762133024714v1V2V3V4 V6V5322762133024714 Dijkstra算法只适用于全部权为非负情况，如果算

22、法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次某边上权为负的，算法失效。此时可采用逐次逼近算法。逼近算法。 例例6.7 如右图所示中按如右图所示中按dijkstra算法可得算法可得P(v1)=5为从为从vsv1的的最短路长显然是错误的，从最短路长显然是错误的，从vsv2v1路长只有路长只有3。v2vsv15-58 树是图论中结构最简单但又十分重要的图。在自然和社会树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。领域应用极为广泛。 例例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。如下图所

23、示。AB CDEF GH运动员运动员 例例 某企业的组织机构图也可用树图表示。某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科任何树中必存在次为任何树中必存在次为1的点。的点。(一个点一个点Vi的相关联边的数目称为点的相关联边的数目称为点Vi的次的次)n 个顶点的树必有个顶点的树必有n-1 条边。条边。树中任意两个顶点之间，恰有且仅有一条链。树中任意两个顶点之间，恰有且仅有一条链。树连通，但去掉任一条边，必变为不连通。树连通，

24、但去掉任一条边，必变为不连通。树无回圈，但不相邻的两个点之间加一条边，恰树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。得到一个圈。v1v2v3v4v5v6 树是图论中的重要概念，所谓树就是一个无圈的连通图。树是图论中的重要概念，所谓树就是一个无圈的连通图。 图图11-11中，中，(a)就是一个树，而就是一个树，而(b)因为图中有圈所以就不因为图中有圈所以就不是树，是树， (c)因为不连通所以也不是树。因为不连通所以也不是树。图图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c) 如果如果G2是是G1的部分

25、图，又是树图，则称的部分图，又是树图，则称G2是是G1的部分树的部分树（或支撑树）。树图的各条边称为树枝，一般图（或支撑树）。树图的各条边称为树枝，一般图G1含有多含有多个部分树，其中树枝总长最小的部分树，称为该图的最小个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2 给了一个无向图给了一个无向图G=(V,E)，我们保留，我们保留G的所有点，而删掉部分的所有点，而删掉部分G的边或者的边或者说保留一部分说保留一部分G的边，所获得的图的边，所获得的图G，称之为，称之为G的生成子图。在图的生成子图。在图

26、11-12中，中，(b)和和(c)都是都是(a)的生成子图。的生成子图。 如果图如果图G的一个生成子图还是一个树，则称这个生成子图为生成树，在的一个生成子图还是一个树，则称这个生成子图为生成树，在图图11-12中，中，(c)就是就是(a)的生成树。的生成树。 最小生成树问题就是指在一个赋权的连通的无向图最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。并使得这个生成树的所有边的权数之和为最小。图图11-12(a)(b)(c)部分树v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1

27、v3v2v5：任取一圈，去掉圈中最长边，直到无圈。任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数边数n-1=5v1v2v3v4v5v643521得到最小树得到最小树：Min C(T)=15去掉去掉G中所有边，得到中所有边，得到n个孤立点；然后加边。个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通形成圈，直到点点连通(即即:n-1条边条边)。5v1v2v3v4v5v6843752618v1v2v3v4v5v6435215v1v2v3v4v

28、5v6843752618Min C(T)=153749346321Min C(T)=12Min C(T)=15254173314475答案：34122323242Min C(T)=12213638534567454321Min C(T)=18 例例5、某大学准备对其所属的、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中能联通的途径如下图，图中v1,v7 表示表示7个学院办公室，请设计一个网个学院办公室，请设计一个网络能联通络能联通7个学院办公室，并使总的线路长度为最短。个学院办公室，并使总的线路长度为最短。 解：此问题实际

29、上是求图解：此问题实际上是求图11-1411-14的最小生成树，这在例的最小生成树，这在例4 4中已经求得，中已经求得，也即按照图也即按照图11-1311-13的的(f)(f)设计，可使此网络的总的线路长度为最短，为设计，可使此网络的总的线路长度为最短，为1919百米。百米。 “ “管理运筹学软件管理运筹学软件”有专门的子程序可以解决最小生成树问题。有专门的子程序可以解决最小生成树问题。v1331728541034v7v6v5v4v2v3图图11-14 如何制定一个运输计划使生产地到销售地的产品输送量最大。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。这就是一

30、个网络最大流问题。 基本概念：基本概念：队网络上的每条弧队网络上的每条弧(v(vii,v,vj j) )都给出一个最大的都给出一个最大的通过能力，称为该弧的通过能力，称为该弧的，简记为，简记为c cij ij。容量网络中通常。容量网络中通常规定一个规定一个( (也称源点，记为也称源点，记为s) s)和一个和一个( (也称汇点，也称汇点，记为记为t) t)，网络中其他点称为，网络中其他点称为。st48441226792. 2. 网络的最大流网络的最大流是指网络中从发点到收点之间允许通过的最大流量。是指网络中从发点到收点之间允许通过的最大流量。3. 3. 流与可行流流与可行流 流流是指加在网络各条

31、弧上的实际流量，对加在弧是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上上的负载量记为的负载量记为fij。若。若fij=0，称为零流。，称为零流。满足以下条件的一组流称为满足以下条件的一组流称为可行流可行流。 容量限制条件。容量网络上所有的弧满足：容量限制条件。容量网络上所有的弧满足：0fijcij 中间点平衡条件。中间点平衡条件。),(0),(),(tsivvfvvfijji 若以若以v(f)表示网络中从表示网络中从st的流量，则有：的流量，则有： 0),(),()(tjjsvvfvvffv结论结论：任何网络上一定存在可行流。（零流即是：任何网络上一定存在可行流。（零流即是可行流）可

32、行流）网络最大流问题：网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使指满足容量限制条件和中间点平衡的条件下，使v(f)v(f)值达到最大。值达到最大。一、最大流的数学模型一、最大流的数学模型 例例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（的变化，它的各段管道（vi,vj）的流量）的流量cij（容量）也是不一样的。（容量）也是不一样的。cij的的单位为万加仑单位为万加仑/

33、小时。如果使用这个网络系统从采地小时。如果使用这个网络系统从采地 v1向销地向销地 v7运送石运送石油，问每小时能运送多少加仑石油？油，问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6图图11-26 1412232514434647234335362535573646675767471214,1,2,6;1,2,70,1,2,6;1,2,712ijijijmaxF = fffffffffffffffffffffffffcijfij目标函数：约束条件： 我们可以为此例题建立线性规划数学模型：我们可以为此例题建立线性规划数学模型： 设弧设弧(vi,vj)上流量为上流量

34、为fij，网络上的总的流量为，网络上的总的流量为F，则有：，则有： 在这个线性规划模型中，其约束条件中的前在这个线性规划模型中，其约束条件中的前6 6个方程表示个方程表示了网络中的流量必须满足守恒条件，了网络中的流量必须满足守恒条件，发点的流出量必须等于发点的流出量必须等于收点的总流入量收点的总流入量；其余的点称之为；其余的点称之为中间点中间点，它的总流入量必，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧须等于总流出量。其后面几个约束条件表示对每一条弧(v(vi i,v,vj j) )的流量的流量fij要满足流量的可行条件，应小于等于弧要满足流量的可行条件，应小于等于弧(v(

35、vi i,v,vj j) )的容的容量量c cijij，并大于等于零，即，并大于等于零，即0 0f fijij c cijij。我们把满足守恒条件。我们把满足守恒条件及流量可行条件的一组网络流及流量可行条件的一组网络流 ffijij 称之为称之为可行流可行流，（即线性，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为出量最大）的称之为最大流最大流（即线性规划的最优解）。（即线性规划的最优解）。 我们把例我们把例6 6的数据代入以上线性规划模型，用的数据代入以上线性规划模型，用“管理运筹管理运筹学软件学软件”，马上

36、得到以下的结果：，马上得到以下的结果：f f1212=5=5，f f1414=5=5，f f2323=2=2，f f2525=3=3，f f4343=2=2，f f4646=1=1，f f4747=2=2，f f3535=2=2，f f3636=2=2，f f5757=5=5，f f6767=3=3。最优值。最优值（最大流量）（最大流量）=10=10。二、最大流问题网络图论的解法二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图对网络上弧的容量的表示作改进。为省去弧的方向，如下图: (a)和和(b)、(c)和和(d)的意义相同。的意义相同。 用以上方法对例用以上

37、方法对例6的图的容量标号作改进，得下图的图的容量标号作改进，得下图vivjvivjcij0（a）（b） cijcijvivj（cji）（c）vivj cij cji（d）63522241263v1v2v5v7v4v3v600000000000 求最大流的基本算法求最大流的基本算法（1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。都大于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的最小的顺流的容量）找出这条路上各条弧的最小的顺流的容量pf，通过这条路

38、增加网络的流，通过这条路增加网络的流量量pf。（3）在这条路上，减少每一条弧的顺流容量）在这条路上，减少每一条弧的顺流容量pf ，同时增加这些弧的逆流容，同时增加这些弧的逆流容量量pf，返回步骤（，返回步骤（1）。）。 用此方法对例用此方法对例6求解：求解： 第一次迭代：选择路为第一次迭代：选择路为v1 v4 v7 。弧（。弧（ v4 , v7 ）的顺流容量为）的顺流容量为2，决定了决定了pf=2，改进的网络流量图如下图：，改进的网络流量图如下图：63522241263v1v2v5v7v4v3v6000000000004202 第二次迭代：选择路为第二次迭代：选择路为v1 v2 v5 v7 。

39、弧（。弧（ v2 , v5 ）的顺流容量为）的顺流容量为3，决定了，决定了pf=3，改进的网络流量图如下图：，改进的网络流量图如下图： 第三次迭代：选择路为第三次迭代：选择路为v1 v4 v6 v7 。弧（。弧（ v4 , v6 ）的顺流容量为）的顺流容量为1，决定了，决定了pf=1，改进的网络流量图如下图：，改进的网络流量图如下图：635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v600000042022033333013 第四次迭代：选择路为第四次迭代：选择路为v1 v4 v3 v6 v7 。弧（。弧（ v3 , v6

40、 ）的顺流容）的顺流容量为量为2，决定了，决定了pf=2，改进的网络流量图如下图：，改进的网络流量图如下图： 第五次迭代：选择路为第五次迭代：选择路为v1 v2 v3 v5 v7 。弧（。弧（ v2 , v3 ）的顺流容）的顺流容量为量为2，决定了，决定了pf=2，改进的网络流量图如下图：，改进的网络流量图如下图：22243v1v2v5v7v4v3v6100001203203335031200231322v1v2v5v7v4v3v61012020333501202313150020205 经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的经过第五次迭代后在图中已经找不到从发点到收点的

41、一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为每一条弧顺流容量都大于零，运算停止。得到最大流量为10。 最大流量图如下图：最大流量图如下图：22v1v2v5v7v4v3v6123522355 “管理运筹学软件管理运筹学软件”中还有专门的子程序用于解决最大流问题。中还有专门的子程序用于解决最大流问题。 最小费用最大流问题：给了一个带收发点的网络，对每一条弧最小费用最大流问题：给了一个带收发点的网络，对每一条弧（vi,vj），除了给出容量），除了给出容量cij外，外，还给出了这条弧的单位流量的费用还给出了这条弧的单位流量的费用bij，要，要求一个最大流求一个最大流F，并使得总运送

42、费用最小。，并使得总运送费用最小。一、最小费用最大流的数学模型一、最小费用最大流的数学模型 例例7 由于输油管道的长短不一，所以在例由于输油管道的长短不一，所以在例6中每段管道（中每段管道（ vi,vj ）除）除了有不同的流量限制了有不同的流量限制cij外，还有不同的单位流量的费用外，还有不同的单位流量的费用bij ，cij的单位为万的单位为万加仑加仑/小时，小时， bij的单位为百元的单位为百元/万加仑。如图。从采地万加仑。如图。从采地 v1向销地向销地 v7运送石运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出

43、最大流量和最小费用。量和最小费用。(6,6)(3,4)(5,7)v1v2v5v7(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v4v3v6(6,3) (,)ijijijv vAfb 这个最小费用最大流问题也是一个线性规划的问题。这个最小费用最大流问题也是一个线性规划的问题。 解：我们用线性规划来求解此题，可以分两步走。解：我们用线性规划来求解此题，可以分两步走。 第一步，先求出此网络图中的最大流量第一步，先求出此网络图中的最大流量F，这已在例，这已在例6中建中建立了线性规划的模型，通过管理运筹学软件已经获得结果。立了线性规划的模型，通过管理运筹学软件已经获得结果。 第二

44、步，在最大流量第二步，在最大流量F的所有解中，找出一个最小费用的的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下：解，我们来建立第二步中的线性规划模型如下： 仍然设弧（仍然设弧（vi,vj）上的流量为）上的流量为fij，这时已知中最大流量为，这时已知中最大流量为F，只要在例只要在例6的约束条件上，再加上总流量必须等于的约束条件上，再加上总流量必须等于F的约束条件：的约束条件：f12=f14=F,即得此线性规划的约束条件，此线性规划的目标函数即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用显然是求其流量的最小费用 fij . bij 。 由此得到线性规

45、划模型如下：由此得到线性规划模型如下： 1214252343(,)355736464767121412232514434647234335362535573646675767471214min63452473384. .10,(1,2,6;ijijijv vAijijfbfffffffffffstffFfffffffffffffffffffffffcij2,3,7),0,(1,2,6;2,3,7),ijfij 用管理运筹学软件，可求得如下结果：用管理运筹学软件，可求得如下结果：f f1212=4,f=4,f1414=6,=6,f f2525=3,f=3,f2323=1,f=1,f4343=3,

46、F=3,F5757=5,f=5,f3636=2,f=2,f4646=1,f=1,f4747=2,f=2,f6767=3,f=3,f3535=2=2。其最。其最优值优值( (最小费用最小费用)=145)=145。对照前面例。对照前面例6 6的结果，可对最小费用最的结果，可对最小费用最大流的概念有一个深刻的理解。大流的概念有一个深刻的理解。 如果我们把例如果我们把例7 7的问题改为：每小时运送的问题改为：每小时运送6 6万加仑的石油万加仑的石油从采地从采地v v1 1到销地到销地v v7 7最小费用是多少？应怎样运送？这就变成了最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，

47、所谓最小费用流的问题一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：就是：在给定了收点和发点并对每条弧在给定了收点和发点并对每条弧(v(vi i,v,vj j) )赋权以容量赋权以容量c cijij及单位费用及单位费用b bijij的网络中，求一个给定值的网络中，求一个给定值f f的流量的最小费用，的流量的最小费用，这个给定值这个给定值f f的流量应的流量应小于等于最大流量小于等于最大流量F F，否则无解。，否则无解。求最求最小费用流的问题的线性规划的模型只要把最小费用最大流模小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量型中的约束条件中的发点流量F

48、F改为改为f f即可。在例即可。在例6 6中只要把中只要把f f1212+f+f1414=F=F改为改为f f1212+f+f1414=f=6=f=6得到了最小费用流的线性规划的模型得到了最小费用流的线性规划的模型了。了。二、最小费用最大流的网络图论解法二、最小费用最大流的网络图论解法对网络上弧（对网络上弧（vi,vj）的（）的（cij,bij）的表示作如下改动，用）的表示作如下改动，用(b)来表示来表示(a)。用上述方法对例用上述方法对例7中的图形进行改进，得图如下页：中的图形进行改进，得图如下页：vivjvivj（cij,bij ）（0,-bij ）（a）（b）（cij,bij ）（cij

49、,bij ）vivj（cji,bji ）（cij,bij ）vivj（cji,bji ）（0,-bji)（0,-bji)（c）（d） 求最小费用最大流的基本算法求最小费用最大流的基本算法 在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求最大流的基本算法完全一样，不同的只是在步骤（最大流的基本算法完全一样，不同的只是在步骤（1）中要选择一条总的）中要选择一条总的单位费用最小的路，而不是包含边数最小的路。单位费用最小的路，而不是包含边数最小的路。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)

50、(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）图图11-2811-28用上述方法对例用上述方法对例7求解：求解： 第一次迭代：找到最短路第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后总流量为第一次迭代后总流量为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-29第二次迭代：找到最短路第二次迭代：找到最短路v1 v4 v7。第二次迭代后总流量为第二次迭代后总流量为3，总费，总费用用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(