[小学教育]第7讲图与网络模型ppt课件

1、1 第七讲第七讲 图与网络模型图与网络模型1 1 图与网络的根本概念图与网络的根本概念2 2 最短路问题最短路问题3 3 最小生成树问题最小生成树问题4 4 最大流问题最大流问题21 1 图与网络的根本概念图与网络的根本概念 图论中图是由点和边构成，可以反映一些对象之间的关系。图论中图是由点和边构成，可以反映一些对象之间的关系。 例如：在一个人群中，对互相认识这个关系我们可以用图例如：在一个人群中，对互相认识这个关系我们可以用图来表示，图来表示，图11-111-1就是一个表示这种关系的图。就是一个表示这种关系的图。(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)

2、陈陈e2e1e3e4e5图图11-13 1 1 图与网络的根本概念图与网络的根本概念 当然图论不仅仅是要描绘对象之间关系，还要研究特定关当然图论不仅仅是要描绘对象之间关系，还要研究特定关系之间的内在规律，一般情况以下图中点的相对位置如何、点系之间的内在规律，一般情况以下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的互相认识关系我们也可以用图要的，如对赵等七人的互相认识关系我们也可以用图11-211-2来表来表示，可见图论中的图与几何图、工程图是不一样的。示，可见图论中的图与几何图、工程图是

3、不一样的。(v1)赵赵(v2)钱钱孙孙(v3) 李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5图图11-241 1 图与网络的根本概念图与网络的根本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈图图11-3 假如我们把上面例子中的假如我们把上面例子中的“互相认识关系改为互相认识关系改为“认识认识 的关系，那么只用两点之间的联线就很难刻画他们之间的的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图关系了，这是我们引

4、入一个带箭头的联线，称为弧。图11-3就是一个反映这七人就是一个反映这七人“认识关系的图。互相认识用两条反认识关系的图。互相认识用两条反向的弧表示。向的弧表示。5 1 1 图与网络的根本概念图与网络的根本概念 无向图：无向图： 由点和边构成的图，记作由点和边构成的图，记作G=V，E。有向图：有向图： 由点和弧构成的图，记作由点和弧构成的图，记作D=V，A。连通图连通图： 对无向图对无向图G，假设任何两个不同的点之间，至少存在一条链，假设任何两个不同的点之间，至少存在一条链，那么那么G为连通图。为连通图。回路：回路： 假设路的第一个点和最后一个点一样，那么该路为回路。假设路的第一个点和最后一个点

5、一样，那么该路为回路。赋权图：赋权图： 对一个无向图对一个无向图G的每一条边的每一条边vi,vj，相应地有一个数，相应地有一个数wij，那么称图那么称图G为赋权图，为赋权图，wij称为边称为边vi,vj上的权。上的权。网络：网络： 在赋权的有向图在赋权的有向图D中指定一点，称为发点，指定另一点称为中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，中的每一条弧的赋权数称为弧的容量，D就称为网络。就称为网络。62 2 最短路问题最短路问题( ,)|,ijijv vvI vJ最短路问题：对一个赋权的有向图最短路问题：对一个

6、赋权的有向图D中的指定的两个点中的指定的两个点Vs和和Vt找到一条找到一条从从 Vs 到到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从之为从Vs到到Vt的最短路。这条路上所有弧的权数的总和被称为从的最短路。这条路上所有弧的权数的总和被称为从Vs到到Vt的间隔的间隔 。一、求解最短路的一、求解最短路的Dijkstra算法算法双标号法双标号法步骤：步骤：1.给出点给出点V1以标号以标号0,s2.找出已标号的点的集合找出已标号的点的集合I，没标号的点的集合，没标号的点的集合J以及弧的集合以及弧的集合3. 假如上述弧的集合是空集

7、，那么计算完毕。假如假如上述弧的集合是空集，那么计算完毕。假如vt已标号已标号lt,kt，那么，那么 vs到到vt的间隔的间隔 为为lt，而从，而从 vs到到vt的最短途径，那么可以从的最短途径，那么可以从kt 反向追踪到起反向追踪到起点点vs 而得到。假如而得到。假如vt 未标号，那么可以断言不存在从未标号，那么可以断言不存在从 vs到到vt的有向路。的有向路。假如上述的弧的集合不是空集，那么转下一步。假如上述的弧的集合不是空集，那么转下一步。4. 对上述弧的集合中的每一条弧，计算对上述弧的集合中的每一条弧，计算 sij=li+cij 。在所有的。在所有的 sij中，找到其中，找到其值为最小

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

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

10、的点到未标号的点的弧的集合改成已标号解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。的点到未标号的点的边的集合即可。 V1 （甲地）（甲地）151762444 31065v2V7 （乙地）（乙地）v3v4v5v692 2 最短路问题最短路问题例例2最终解得：最终解得：最短途径最短途径v1 v3 v5 v6 v7，每点的标号见以下图，每点的标号见以下图0,s V1 甲地甲地151762443106513,3 v2 22,6V7 乙地乙地V514,3V616,5 V310,1 V418,5102 2 最短路问题最短路问题 例例3 设备更新问题。某公司使

11、用一台设备，在每年年初，公司就设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购置新的设备还是继续使用旧设备。假如购置新设备，就要要决定是购置新的设备还是继续使用旧设备。假如购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。假如继续使用旧设支付一定的购置费，当然新设备的维修费用就低。假如继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的方案，使得五年内购置费用和维修费用总的支付费用最小。新设备的方案，使得五年内购置费用和维修费用总的支付费用最小。 ：设备每年年初的价格表：设备每年年初

12、的价格表 设备维修费如下表设备维修费如下表年份年份12345年初价格年初价格1111121213使用年数使用年数0-11-22-33-44-5每年维修每年维修费用费用5681118112 2 最短路问题最短路问题例例3的解：的解： 将问题转化为最短路问题，如以下图：将问题转化为最短路问题，如以下图： 用用vi表示表示“第第i年年初购进一台新设备年年初购进一台新设备,弧弧vi,vj表示第表示第i年年初购年年初购进的进的设备一直使用到第设备一直使用到第j年年初。年年初。把所有弧的权数计算如下表：把所有弧的权数计算如下表：v1v2v3v4v5v6123456116223041592162230413

13、172331417235186122 2 最短路问题最短路问题 继上页继上页 把权数赋到图中，再用把权数赋到图中，再用Dijkstra算法求最短路。算法求最短路。 最终得到以下图，可知，最终得到以下图，可知，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)133 3 最小生成树问题最小

14、生成树问题 树是图论中的重要概念，所谓树就是一个无圈的连通图。树是图论中的重要概念，所谓树就是一个无圈的连通图。 图图11-11中，中，a就是一个树，而就是一个树，而b因为图中有圈所因为图中有圈所以就不是树，以就不是树， c因为不连通所以也不是树。因为不连通所以也不是树。图图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)143 3 最小生成树问题最小生成树问题 给了一个无向图给了一个无向图G=G=V,EV,E，我们保存，我们保存G G的所有点，而删掉部分的所有点，而删掉部分G G的边的边或者说保存一部分或者说

15、保存一部分G G的边，所获得的图的边，所获得的图G G，称之为，称之为G G的生成子图。在图的生成子图。在图11-1211-12中，中，b b和和c c都是都是a a的生成子图。的生成子图。 假如图假如图G G的一个生成子图还是一个树，那么称这个生成子图为生成树，的一个生成子图还是一个树，那么称这个生成子图为生成树，在图在图11-1211-12中，中，c c就是就是a a的生成树。的生成树。 最小生成树问题就是指在一个赋权的连通的无向图最小生成树问题就是指在一个赋权的连通的无向图G G中找出一个生成中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。树，并使得这个生成树的所有边的权数之

16、和为最小。图图11-12abc153 3 最小生成树问题最小生成树问题一、求解最小生成树的破圈算法一、求解最小生成树的破圈算法算法的步骤：算法的步骤：1、在给定的赋权的连通图上任找一个圈。、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边假如有两条或两、在所找的圈中去掉一个权数最大的边假如有两条或两条以上的边都是权数最大的边，那么任意去掉其中一条。条以上的边都是权数最大的边，那么任意去掉其中一条。3、假如所余下的图已不包含圈，那么计算完毕，所余下的、假如所余下的图已不包含圈，那么计算完毕，所余下的图即为最小生成树，否那么返回第图即为最小生成树，否那么返回第1步。步。163

17、 3 最小生成树问题最小生成树问题例例4 用破圈算法求图用破圈算法求图a中的一个最小生成树中的一个最小生成树v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)图图11-13173 3 最小生成树问题最小生成树问题 例例5、某大学准备对其所属的、某大学准备对其所属的7个学院办公室计算机联网，这个网络的个学院办公室计算机联网，这个网络的可能联通

18、的途径如以下图，图中可能联通的途径如以下图，图中v1,v7 表示表示7个学院办公室，请设计个学院办公室，请设计一个网络能联通一个网络能联通7个学院办公室，并使总的线路长度为最短。个学院办公室，并使总的线路长度为最短。 解：此问题实际上是求图解：此问题实际上是求图11-1411-14的最小生成树，这在例的最小生成树，这在例4 4中已经求得，中已经求得，也即按照图也即按照图11-1311-13的的f f设计，可使此网络的总的线路长度为最短，为设计，可使此网络的总的线路长度为最短，为1919百米。百米。 “ “管理运筹学软件有专门的子程序可以解决最小生成树问题。管理运筹学软件有专门的子程序可以解决最

19、小生成树问题。v1331728541034v7v6v5v4v2v3图图11-14184 4 最大流问题最大流问题最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。一、最大流的数学模型一、最大流的数学模型 例例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如以下图所示。由于管道的地运送到一些销售点，这个网络的一部

20、分如以下图所示。由于管道的直径的变化，它的各段管道直径的变化，它的各段管道vi,vj的流量的流量cij容量也是不一样的。容量也是不一样的。cij的单位为万加仑的单位为万加仑/小时。假如使用这个网络系统从采地小时。假如使用这个网络系统从采地 v1向销地向销地 v7运运送石油，问每小时能运送多少加仑石油？送石油，问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6图图11-26194 4 最大流问题最大流问题1412232514434647234335362535573646675767471214,1,2,6;1,2,70,1,2,6;1,2,712ijijijmaxF

21、 = fffffffffffffffffffffffffcijfij目标函数：约束条件： 我们可以为此例题建立线性规划数学模型：我们可以为此例题建立线性规划数学模型： 设弧设弧vi,vj上流量为上流量为fij，网络上的总的流量为，网络上的总的流量为F，那么有：，那么有：204 4 最大流问题最大流问题 在这个线性规划模型中，其约束条件中的前在这个线性规划模型中，其约束条件中的前6 6个方程表示个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必收点的总流入量；其余的点称之为中间点，

22、它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧须等于总流出量。其后面几个约束条件表示对每一条弧v vi i,v,vj j的流量的流量fij要满足流量的可行条件，应小于等于弧要满足流量的可行条件，应小于等于弧v vi i,v,vj j的容量的容量c cijij，并大于等于零，即，并大于等于零，即0 0ffijij c cijij。我们把。我们把满足守恒条件及流量可行条件的一组网络流满足守恒条件及流量可行条件的一组网络流 ffijij 称之为可行称之为可行流，即线性规划的可行解，可行流中一组流量最大也流，即线性规划的可行解，可行流中一组流量最大也即发出点总流出量最大的称之为最大流即

23、线性规划的最即发出点总流出量最大的称之为最大流即线性规划的最优解。优解。 我们把例我们把例6 6的数据代入以上线性规划模型，用的数据代入以上线性规划模型，用“管理运筹管理运筹学软件，马上得到以下的结果：学软件，马上得到以下的结果：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。21 4 4 最大流问题最大流问题二、最大流问题网络图论的解法

24、二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如以下图对网络上弧的容量的表示作改进。为省去弧的方向，如以下图: a和和b、c和和d的意义一样。的意义一样。 用以上方法对例用以上方法对例6的图的容量标号作改进，得以下图的图的容量标号作改进，得以下图vivjvivjcij0ab cijcijvivjcjicvivj cij cjid63522241263v1v2v5v7v4v3v60000000000022 4 4 最大流问题最大流问题 求最大流的根本算法求最大流的根本算法1找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容找出一条从发点到收点的路，在这条路上

25、的每一条弧顺流方向的容量都大于零。假如不存在这样的路，那么已经求得最大流。量都大于零。假如不存在这样的路，那么已经求得最大流。2找出这条路上各条弧的最小的顺流的容量找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络，通过这条路增加网络的流量的流量pf。3在这条路上，减少每一条弧的顺流容量在这条路上，减少每一条弧的顺流容量pf ，同时增加这些弧的逆流，同时增加这些弧的逆流容量容量pf，返回步骤，返回步骤1。 用此方法对例用此方法对例6求解：求解： 第一次迭代：选择路为第一次迭代：选择路为v1 v4 v7 。弧。弧 v4 , v7 的顺流容量为的顺流容量为2，决定了决定了pf=2，改进的

26、网络流量图如以下图：，改进的网络流量图如以下图：63522241263v1v2v5v7v4v3v6000000000004202234 4 最大流问题最大流问题 第二次迭代：选择路为第二次迭代：选择路为v1 v2 v5 v7 。弧。弧 v2 , v5 的顺流容量为的顺流容量为3，决定了，决定了pf=3，改进的网络流量图如以下图：，改进的网络流量图如以下图： 第三次迭代：选择路为第三次迭代：选择路为v1 v4 v6 v7 。弧。弧 v4 , v6 的顺流容量为的顺流容量为1，决定了，决定了pf=1，改进的网络流量图如以下图：，改进的网络流量图如以下图：635222413v1v2v5v7v4v3v

27、60000000042022033303222413v1v2v5v7v4v3v600000042022033333013244 4 最大流问题最大流问题 第四次迭代：选择路为第四次迭代：选择路为v1 v4 v3 v6 v7 。弧。弧 v3 , v6 的顺流容的顺流容量为量为2，决定了，决定了pf=2，改进的网络流量图如以下图：，改进的网络流量图如以下图： 第五次迭代：选择路为第五次迭代：选择路为v1 v2 v3 v5 v7 。弧。弧 v2 , v3 的顺流的顺流容容量为量为2，决定了，决定了pf=2，改进的网络流量图如以下图：，改进的网络流量图如以下图：22243v1v2v5v7v4v3v61

28、00001203203335031200231322v1v2v5v7v4v3v61012020333501202313150020205254 4 最大流问题最大流问题 经过第五次迭代后在图中已经找不到从发点到收点的一条路，路经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停顿。得到最大流量为上的每一条弧顺流容量都大于零，运算停顿。得到最大流量为10。 最大流量图如以下图：最大流量图如以下图：22v1v2v5v7v4v3v6123522355 “管理运筹学软件中还有专门的子程序用于解决最大流问题。管理运筹学软件中还有专门的子程序用于解决最大流问题。26

29、5 5 最小费用最大流问题最小费用最大流问题 最小费用最大流问题：给了一个带收发点的网络，对每一条弧最小费用最大流问题：给了一个带收发点的网络，对每一条弧vi,vj，除了给出容量，除了给出容量cij外，还给出了这条弧的单位流量的费用外，还给出了这条弧的单位流量的费用bij，要，要求一个最大流求一个最大流F，并使得总运送费用最小。，并使得总运送费用最小。一、最小费用最大流的数学模型一、最小费用最大流的数学模型 例例7 由于输油管道的长短不一，所以在例由于输油管道的长短不一，所以在例6中每段管道中每段管道 vi,vj 除除了有不同的流量限制了有不同的流量限制cij外，还有不同的单位流量的费用外，还

30、有不同的单位流量的费用bij ，cij的单位为的单位为万万加仑加仑/小时，小时， bij的单位为百元的单位为百元/万加仑。如图。从采地万加仑。如图。从采地 v1向销地向销地 v7运送运送石石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流流量和最小费用。量和最小费用。6,63,45,72,52,42,34,41,32,83,2v1v2v5v7v4v3v66,3275 5 最小费用最大流问题最小费用最大流问题(,)ijijijv vAfb 这个最小费用最大流问题也是一个线性规划的问题。这个最小费用最大流问题也是一个线性

31、规划的问题。 解：我们用线性规划来求解此题，可以分两步走。解：我们用线性规划来求解此题，可以分两步走。 第一步，先求出此网络图中的最大流量第一步，先求出此网络图中的最大流量F，这已在例，这已在例6中建中建立了线性规划的模型，通过管理运筹学软件已经获得结果。立了线性规划的模型，通过管理运筹学软件已经获得结果。 第二步，在最大流量第二步，在最大流量F的所有解中，找出一个最小费用的的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下：解，我们来建立第二步中的线性规划模型如下： 仍然设弧仍然设弧vi,vj上的流量为上的流量为fij，这时网络中最大流量为，这时网络中最大流量为F，只要在

32、例只要在例6的约束条件上，再加上总流量必须等于的约束条件上，再加上总流量必须等于F的约束条件：的约束条件：f12=f14=F,即得此线性规划的约束条件，此线性规划的目的函数即得此线性规划的约束条件，此线性规划的目的函数显然是求其流量的最小费用显然是求其流量的最小费用 。 由此得到线性规划模型如下：由此得到线性规划模型如下：285 5 最小费用最大流问题最小费用最大流问题1214252343(,)355736464767121412232514434647234335362535573646675767471214min63452473384. .10,(1,2,6;ijijijv vAijij

33、fbfffffffffffstffFfffffffffffffffffffffffcij2,3,7),0,(1,2,6;2,3,7),ijfij 295 5 最小费用最大流问题最小费用最大流问题 用管理运筹学软件，可求得如下结果：用管理运筹学软件，可求得如下结果：f f1212=4,f=4,f1414=6,=6,f f2525=3,f=3,f2323=1,f=1,f4343=3,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。对照前面例。对照前

34、面例6 6的结果，可对最小费用的结果，可对最小费用最大流的概念有一个深化的理解。最大流的概念有一个深化的理解。 假如我们把例假如我们把例7 7的问题改为：每小时运送的问题改为：每小时运送6 6万加仑的石油万加仑的石油从采地从采地v v1 1到销地到销地v v7 7最小费用是多少？应怎样运送？这就变成了最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，所谓最小费用流的问题一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧就是：在给定了收点和发点并对每条弧v vi i,v,vj j赋权以容量赋权以容量c cijij及单位费用及单位费用b bi

35、jij的网络中，求一个给定值的网络中，求一个给定值f f的流量的最小费用，的流量的最小费用，这个给定值这个给定值f f的流量应小于等于最大流量的流量应小于等于最大流量F F，否那么无解。求，否那么无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量模型中的约束条件中的发点流量F F改为改为f f即可。在例即可。在例6 6中只要把中只要把f f1212+f+f1414=F=F改为改为f f1212+f+f1414=f=6=f=6得到了最小费用流的线性规划的模型得到了最小费用流的线性规划的模型了。了。305 5

36、 最小费用最大流问题最小费用最大流问题二、最小费用最大流的网络图论解法二、最小费用最大流的网络图论解法对网络上弧对网络上弧vi,vj的的cij,bij的表示作如下改动，用的表示作如下改动，用b来表示来表示a。用上述方法对例用上述方法对例7中的图形进展改进，得图如下页：中的图形进展改进，得图如下页：vivjvivjcij,bij 0,-bij abcij,bij cij,bij vivjcji,bji cij,bij vivjcji,bji 0,-bji0,-bjicd315 5 最小费用最大流问题最小费用最大流问题 求最小费用最大流的根本算法求最小费用最大流的根本算法 在对弧的标号作了改进的网

37、络图上求最小费用最大流的根本算在对弧的标号作了改进的网络图上求最小费用最大流的根本算法与求法与求最大流的根本算法完全一样，不同的只是在步骤最大流的根本算法完全一样，不同的只是在步骤1中要选择一条总的中要选择一条总的单位费用最小的路，而不是包含边数最小的路。单位费用最小的路，而不是包含边数最小的路。(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,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）图图11-2811-28325

38、5 最小费用最大流问题最小费用最大流问题用上述方法对例用上述方法对例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-29335 5 最小费用最大流问题最小费用最大流问题第二次迭代：找到最短路第二次迭代：找到最短

39、路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-30345 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,-4)(0,-5)（2,4）(0,-7)(3,-4)（2,-3）图图11-3111-31355 5 最小费用最大流问题最小费用最大流问题第四次迭代：找到最短路第四次迭代：找到最短路v1 v4 v3 v5