《第11章图与网络模型精选PPT.ppt》由会员分享，可在线阅读，更多相关《第11章图与网络模型精选PPT.ppt（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第11章图与网络模型第1页，此课件共41页哦11图与网络的基本概念图与网络的基本概念2 图论中图是由点和边构成，可以反映一些对象之间的关系。图论中图是由点和边构成，可以反映一些对象之间的关系。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图11-111-1就是一个表示这种关系的图。就是一个表示这种关系的图。(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5图图11-1第2页，此课件共41页哦 1 1图与网络的基本概念图与网络的基本概念 3 当然图论不仅仅是要描述对象之间
2、关系，还要研究特定关系之当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图七人的相互认识关系我们也可以用图11-211-2来表示，可见图论中的图与来表示，可见图论中的图与几何图、工程图是不一样的。几何图、工程图是不一样的。(v1)赵赵(v2)钱钱孙孙(v3)李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5图图1
3、1-2第3页，此课件共41页哦11图与网络的基本概念图与网络的基本概念4a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈图图11-3 如果我们把上面例子中的如果我们把上面例子中的“相互认识相互认识”关系改为关系改为“认识认识”的关系，的关系，那么只用两点之间的连线就很难刻画他们之间的关系了，这是我们引那么只用两点之间的连线就很难刻画他们之间的关系了，这是我们引入一个带箭头的连线，称为弧。图入一个带箭头的连线，称为弧。图11-3就是一个反映这七人就是一个反映这七人“认识认识”关关系的图。相
4、互认识用两条反向的弧表示。系的图。相互认识用两条反向的弧表示。第4页，此课件共41页哦 1 1图与网络的基本概念图与网络的基本概念无向图：无向图：由点和边构成的图，记作由点和边构成的图，记作G=G=（V V，E E）。）。有向图：有向图：由点和弧构成的图，记作由点和弧构成的图，记作D=D=（V V，A A）。）。连通图连通图：对无向图对无向图G G，若任何两个不同的点之间，至少存在一条链，则，若任何两个不同的点之间，至少存在一条链，则G G为连通图。为连通图。回路：回路：若路的第一个点和最后一个点相同，则该路为回路。若路的第一个点和最后一个点相同，则该路为回路。赋权图：赋权图：对一个无向图对一
5、个无向图G G的每一条边的每一条边(v(vi i,v,vj j)，相应地有一个数，相应地有一个数w wij ij，则称图，则称图G G为赋权图，为赋权图，w wij ij称为边称为边(v(vi i,v,vj j)上的权。上的权。网络：网络：在赋权的有向图在赋权的有向图D D中指定一点，称为发点中指定一点，称为发点(记为记为v vs s)，指定另一点称为收点，指定另一点称为收点(记为记为v vt t)，其它点称为中间点，并把，其它点称为中间点，并把D D中的每一条弧的赋权数中的每一条弧的赋权数c cij ij称为弧称为弧(v(vi i,v,vj j)的容量，的容量，这样的赋权有向图这样的赋权有向
6、图D D就称为网络。就称为网络。5第5页，此课件共41页哦22最短路问题最短路问题最短路问题：对一个赋权的有向图最短路问题：对一个赋权的有向图D D中的指定的两个点中的指定的两个点V Vs s和和V Vt t找到一条从找到一条从 V Vs s 到到 V Vt t 的的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从路，使得这条路上所有弧的权数的总和最小，这条路被称之为从V Vs s到到V Vt t的最短路。这的最短路。这条路上所有弧的权数的总和被称为从条路上所有弧的权数的总和被称为从V Vs s到到V Vt t的距离。的距离。一、求解最短路的一、求解最短路的DijkstraDijkst
7、ra算法算法(双标号法）双标号法）步骤：步骤：1.1.给出点给出点V V1 1以标号以标号(0,s)(0,s)2.2.找出已标号的点的集合找出已标号的点的集合I I，没标号的点的集合，没标号的点的集合J J以及弧的集合以及弧的集合3.3.如果上述弧的集合是空集，则计算结束。如果如果上述弧的集合是空集，则计算结束。如果v vt t已标号（已标号（l lt t,k,kt t），则），则 v vs s到到v vt t的距的距离为离为l lt t，而从，而从 v vs s到到v vt t的最短路径，则可以从的最短路径，则可以从v vt t 反向追踪到起点反向追踪到起点v vs s 而得到。如果而得到。
8、如果v vt t 未未标号，则可以断言不存在从标号，则可以断言不存在从 v vs s到到v vt t的有向路。如果上述的弧的集合不是空集，则的有向路。如果上述的弧的集合不是空集，则转下一步。转下一步。4.4.对上述弧的集合中的每一条弧，计算对上述弧的集合中的每一条弧，计算 s sij ij=l=li i+c+cij ij 。在所有的。在所有的 s sij ij中，找到其值为最小中，找到其值为最小的弧。不妨设此弧为（的弧。不妨设此弧为（V Vc c,V,Vd d），则给此弧的终点以双标号（），则给此弧的终点以双标号（s scdcd,c,c）,返回步骤返回步骤2 2。6第6页，此课件共41页哦22
9、最短路问题最短路问题 例例1 1 求下图中求下图中v v1 1到到v v6 6的最短路的最短路解：采用解：采用DijkstraDijkstra算法，可解得最短路径为算法，可解得最短路径为v v1 1 v v3 3 v v4 4 v v6 6 各点的标号图如下：各点的标号图如下：7v23527531512v1v6v5v3v4(3,1)v23527531512 V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4第7页，此课件共41页哦22最短路问题最短路问题 例例2 2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆
10、线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。路的长度（单位：公里）。解：这是一个求无向图的最短路的问题。可以把无向图的每一边（解：这是一个求无向图的最短路的问题。可以把无向图的每一边（v vi i,v,vj j）都用方）都用方向相反的两条弧（向相反的两条弧（v vi i,v,vj j）和（）和（v vj j,v,vi i）代替，就化为有向图，即可用）代替，就化为有向图，即可用DijkstraDijkstra算法来求算法来求解。也可直接在无向图中用解。也可直接在无向图中用DijkstraDijkst
11、ra算法来求解。只要在算法中把从已标号的算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。可。8 V1（甲地）（甲地）1517624431065v2V7（乙地）（乙地）v3v4v5v6第8页，此课件共41页哦22最短路问题最短路问题例例2 2最终解得：最终解得：最短路径最短路径v v1 1 v v3 3 v v5 5 v v6 6 v v7 7，每点的标号见下图，每点的标号见下图9（0,s）V1（甲地）（甲地）1517624431065(13,3)v2 (22,6)V7（乙地）（乙
12、地）V5(14,3)V6(16,5)V3(10,1)V4(18,5)第9页，此课件共41页哦22最短路问题最短路问题 例例3 3 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维
13、修费就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。用总的支付费用最小。已知：设备每年年初的价格表已知：设备每年年初的价格表 设备维修费如下表设备维修费如下表10年份年份12345年初价格年初价格1111121213使用年数使用年数0-11-22-33-44-5每年维修每年维修费用费用5681118第10页，此课件共41页哦22最短路问题最短路问题例例3 3的解：的解：将问题转化为最短路问题，如下图：将问题转化为最短路问题，如下图：用用v vi i表示表示“第第i i年年初购进一台新设备年年初购进一台新设备”,弧（弧（v vi i,v,vj j）表示第
14、）表示第i i年年初购进的年年初购进的设备一直使用到第设备一直使用到第j j年年初。年年初。把所有弧的权数计算如下表：把所有弧的权数计算如下表：11v1v2v3v4v5v6123456116223041592162230413172331417235186第11页，此课件共41页哦22最短路问题最短路问题(继上页继上页)把权数赋到图中，再用把权数赋到图中，再用DijkstraDijkstra算法求最短路。算法求最短路。最终得到下图，可知，最终得到下图，可知，v v1 1到到v v6 6的距离是的距离是5353，最短路径有两条：，最短路径有两条：v v1 1 v v3 3 v v6 6和和 v
15、v1 1 v v4 4 v v6 612v1v2v3v4v5v6162230415916223041312317181723 V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)第12页，此课件共41页哦33最小生成树问题最小生成树问题树是图论中的重要概念，所谓树就是一个无圈的连通图。树是图论中的重要概念，所谓树就是一个无圈的连通图。13 图图11-11中，中，(a)就是一个树，而就是一个树，而(b)因为图中有圈所以就不是树，因为图中有圈所以就不是树，(c)因为不连通所以也不是树。因
16、为不连通所以也不是树。图图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)第13页，此课件共41页哦33最小生成树问题最小生成树问题 14 给了一个无向图给了一个无向图G=(V,E)G=(V,E)，我们保留，我们保留G G的所有点，而删掉部分的所有点，而删掉部分G G的边或者说保留一的边或者说保留一部分部分G G的边，所获得的图的边，所获得的图G G，称之为，称之为G G的生成子图。在图的生成子图。在图11-1211-12中，中，(b)(b)和和(c)(c)都是都是(a)(a)的生的生成子图。成子图。如果图如果
17、图G G的一个生成子图还是一个树，则称这个生成子图为生成树，在图的一个生成子图还是一个树，则称这个生成子图为生成树，在图11-11-1212中，中，(c)(c)就是就是(a)(a)的生成树。的生成树。最小生成树问题就是指在一个赋权的连通的无向图最小生成树问题就是指在一个赋权的连通的无向图G G中找出一个生成树，并使中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。得这个生成树的所有边的权数之和为最小。图图11-12(a)(b)(c)第14页，此课件共41页哦33最小生成树问题最小生成树问题一、求解最小生成树的破圈算法一、求解最小生成树的破圈算法算法的步骤：算法的步骤：1 1、在给定的
18、赋权的连通图上任找一个圈。、在给定的赋权的连通图上任找一个圈。2 2、在所找的圈中去掉一个权数最大的边（如果有两条或两条、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。以上的边都是权数最大的边，则任意去掉其中一条）。3 3、如果所余下的图已不包含圈，则计算结束，所余下的图即、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第为最小生成树，否则返回第1 1步。步。15第15页，此课件共41页哦33最小生成树问题最小生成树问题例例4 4 用破圈算法求图（用破圈算法求图（a a）中的一个最小生成树）中的一个最小生成树16v1
19、331728541034v7v6v5v4v2v13317285434v7v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)图图11-13第16页，此课件共41页哦33最小生成树问题最小生成树问题 例例5 5、某大学准备对其所属的、某大学准备对其所属的7 7个学院办公室计算机联网，这个网络的可能联通个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中的途径如下图，图中v v1 1,v,v7 7 表示表示7 7
20、个学院办公室，请设计一个网络能联通个学院办公室，请设计一个网络能联通7 7个学院办公室，并使总的线路长度为最短。个学院办公室，并使总的线路长度为最短。17 解：此问题实际上是求图解：此问题实际上是求图11-1411-14的最小生成树，这在例的最小生成树，这在例4 4中已经求得，也即按中已经求得，也即按照图照图11-1311-13的的(f)(f)设计，可使此网络的总的线路长度为最短，为设计，可使此网络的总的线路长度为最短，为1919百米。百米。“管理运筹学管理运筹学”软件有专门的子程序可以解决最小生成树问题。软件有专门的子程序可以解决最小生成树问题。v1331728541034v7v6v5v4v
21、2v3图图11-14第17页，此课件共41页哦44最大流问题最大流问题最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。的容量的前提下，求出从发点到收点的最大流量。一、最大流的数学模型一、最大流的数学模型 例例6 6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，到一些销售点，这个网络的一部分如下图所示。由于管道的直径
22、的变化，它的各段管道（它的各段管道（v vi i,v,vj j）的流量）的流量c cij ij（容量）也是不一样的。（容量）也是不一样的。c cij ij的单位为万加仑的单位为万加仑/小时。小时。如果使用这个网络系统从采地如果使用这个网络系统从采地 v v1 1向销地向销地 v v7 7运送石油，问每小时能运送多少加仑运送石油，问每小时能运送多少加仑石油？石油？18v563522241263v1v2v7v4v3v6图图11-26第18页，此课件共41页哦44最大流问题最大流问题 19 我们可以为此例题建立线性规划数学模型：我们可以为此例题建立线性规划数学模型：设弧设弧(vi,vj)上流量为上流
23、量为fij，网络上的总的流量为，网络上的总的流量为F，则有：，则有：第19页，此课件共41页哦44最大流问题最大流问题 20 在这个线性规划模型中，其约束条件中的前在这个线性规划模型中，其约束条件中的前6 6个方程表示了网络个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧出量。其后面几个约束条件表示对每一条弧(v(vi i,v,vj j)的流量的流量fij要满要满足流量的可行
24、条件，应小于等于弧足流量的可行条件，应小于等于弧(v(vi i,v,vj j)的容量的容量c cijij，并大于等于零，并大于等于零，即即0f0fijij c cijij。我们把满足守恒条件及流量可行条件的一组网络。我们把满足守恒条件及流量可行条件的一组网络流流 ffijij 称之为可行流，（即线性规划的可行解），可行流中一组流量称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。解）。我们把例我们把例6 6的数据代入以上线性规划模型，用的数据代入以上线性规划模型
25、，用“管理运筹学软件管理运筹学软件”，马上得到以下的结果：，马上得到以下的结果：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。第20页，此课件共41页哦 44最大流问题最大流问题二、最大流问题网络图论的解法二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图对网络上弧的容量的表示作改进。为省去弧的方
26、向，如下图:(a):(a)和和(b)(b)、(c)(c)和和(d)(d)的意义相同。的意义相同。用以上方法对例用以上方法对例6 6的图的容量标号作改进，得下图的图的容量标号作改进，得下图21vivjvivjcij0（a）（b）cijcijvivj（cji）（c）vivj cij cji（d）63522241263v1v2v5v7v4v3v600000000000第21页，此课件共41页哦 44最大流问题最大流问题 求最大流的基本算法求最大流的基本算法（1 1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都
27、大于零。如果不存在这样的路，则已经求得最大流。果不存在这样的路，则已经求得最大流。（2 2）找出这条路上各条弧的最小的顺流的容量）找出这条路上各条弧的最小的顺流的容量p pf f，通过这条路增加网络的流量，通过这条路增加网络的流量p pf f。（3 3）在这条路上，减少每一条弧的顺流容量）在这条路上，减少每一条弧的顺流容量p pf f ，同时增加这些弧的逆流容量，同时增加这些弧的逆流容量p pf f，返回步骤（返回步骤（1 1）。）。用此方法对例用此方法对例6 6求解：求解：第一次迭代：选择路为第一次迭代：选择路为v v1 1 v v4 4 v v7 7 。弧（。弧（v v4 4,v v7 7
28、 ）的顺流容量为）的顺流容量为2 2，决定了决定了p pf f=2=2，改进的网络流量图如下图：，改进的网络流量图如下图：2263522241263v1v2v5v7v4v3v6000000000004202第22页，此课件共41页哦44最大流问题最大流问题 第二次迭代：选择路为第二次迭代：选择路为v v1 1 v v2 2 v v5 5 v v7 7 。弧。弧（v v2 2,v v5 5 ）的顺流容量为）的顺流容量为3 3，决定了，决定了p pf f=3=3，改进的网，改进的网络流量图如下图：络流量图如下图：23635222413v1v2v5v7v4v3v6000000004202203330
29、3第23页，此课件共41页哦 第三次迭代：选择路为第三次迭代：选择路为v v1 1 v v4 4 v v6 6 v v7 7 。弧。弧（v v4 4,v v6 6 ）的顺流容量为）的顺流容量为1 1，决定了，决定了p pf f=1=1，改进的网，改进的网络流量图如下图：络流量图如下图：24222313v1v2v5v7v4v3v60000004202203333301第24页，此课件共41页哦44最大流问题最大流问题 第四次迭代：选择路为第四次迭代：选择路为v v1 1 v v4 4 v v3 3 v v6 6 v v7 7 。弧。弧（v v3 3,v v6 6 ）的顺流容量为）的顺流容量为2
30、2，决定了，决定了p pf f=2=2，改进的网，改进的网络流量图如下图：络流量图如下图：2522233v1v2v5v7v4v3v6110002032033350312002133第25页，此课件共41页哦 第五次迭代：选择路为第五次迭代：选择路为v v1 1 v v2 2 v v3 3 v v5 5 v v7 7 。弧。弧（v v2 2,v v3 3 ）的顺流容量为）的顺流容量为2 2，决定了，决定了p pf f=2=2，改进的网，改进的网络流量图如下图：络流量图如下图：2622v1v2v5v7v4v3v61012020333501202133150020205第26页，此课件共41页哦44
31、最大流问题最大流问题 经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为每一条弧顺流容量都大于零，运算停止。得到最大流量为1010。最大流量图如下图：最大流量图如下图：2722v1v2v5v7v4v3v6123522355 “管理运筹学软件管理运筹学软件”中还有专门的子程序用于解决最大流问题。中还有专门的子程序用于解决最大流问题。第27页，此课件共41页哦55最小费用最大流问题最小费用最大流问题 最小费用最大流问题：给了一个带收发点的网络，对每一条弧最小费用最大流问题：给了一
32、个带收发点的网络，对每一条弧（v vi i,v,vj j），除了给出容量），除了给出容量c cij ij外，还给出了这条弧的单位流量的费用外，还给出了这条弧的单位流量的费用b bij ij，要，要求一个最大流求一个最大流F F，并使得总运送费用最小。，并使得总运送费用最小。一、最小费用最大流的数学模型一、最小费用最大流的数学模型 例例7 7 由于输油管道的长短不一，所以在例由于输油管道的长短不一，所以在例6 6中每段管道（中每段管道（v vi i,v,vj j ）除）除了有不同的流量限制了有不同的流量限制c cij ij外，还有不同的单位流量的费用外，还有不同的单位流量的费用b bij ij
33、，c cij ij的单位为万的单位为万加仑加仑/小时，小时，b bij ij的单位为百元的单位为百元/万加仑。如下图所示。从采地万加仑。如下图所示。从采地 v v1 1向销地向销地 v v7 7运运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。大流量和最小费用。28(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)第28页，此课件共41页哦55最小费用最大流问题最小费用最大流问题 29 这个最小费用最大流问题
34、也是一个线性规划的问题。这个最小费用最大流问题也是一个线性规划的问题。解：我们用线性规划来求解此题，可以分两步走。解：我们用线性规划来求解此题，可以分两步走。第一步，先求出此网络图中的最大流量第一步，先求出此网络图中的最大流量F，这已在例，这已在例6中建立了线性中建立了线性规划的模型，通过规划的模型，通过“管理运筹学管理运筹学”软件已经获得结果。软件已经获得结果。第二步，在最大流量第二步，在最大流量F的所有解中，找出一个最小费用的解，我们的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下：来建立第二步中的线性规划模型如下：仍然设弧（仍然设弧（vi,vj）上的流量为）上的流量
35、为fij，这时已知网络中最大流量为，这时已知网络中最大流量为F，只，只要在例要在例6的约束条件上，再加上总流量必须等于的约束条件上，再加上总流量必须等于F的约束条件：的约束条件：f12+f14=F,即得此线性规划的约束条件，此线性规划的目标函数显然是求其流即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用量的最小费用 。由此得到线性规划模型如下：由此得到线性规划模型如下：第29页，此课件共41页哦55最小费用最大流问题最小费用最大流问题 30第30页，此课件共41页哦55最小费用最大流问题最小费用最大流问题 31 用管理运筹学软件，可求得如下结果：用管理运筹学软件，可求得如
36、下结果：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。其最优值。其最优值(最最小费用小费用)为为145145。对照前面例。对照前面例6 6的结果，可对最小费用最大流的概念有的结果，可对最小费用最大流的概念有一个深刻的理解。一个深刻的理解。如果我们把例如果我们把例7 7的问题改为：每小时运送的问题改为：每小时运送6 6万加仑的石油从采地万加仑的石油从采地v v1 1到销地到销地v
37、 v7 7最小费用是多少？应怎样运送？这就变成了一个最小费用流最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧对每条弧(v(vi i,v,vj j)赋权以容量赋权以容量c cijij及单位费用及单位费用b bijij的网络中，求一个给定的网络中，求一个给定值值f f的流量的最小费用，这个给定值的流量的最小费用，这个给定值f f的流量应小于等于最大流量的流量应小于等于最大流量F F，否则无解。求最小费用流的问题的线性规划的模型只要把最小费用最否则无解。求最小
38、费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量大流模型中的约束条件中的发点流量F F改为改为f f即可。在例即可。在例6 6中只要把中只要把f f1212+f+f1414=F=F改为改为f f1212+f+f1414=f=6=f=6得到了最小费用流的线性规划的模型了。得到了最小费用流的线性规划的模型了。第31页，此课件共41页哦55最小费用最大流问题最小费用最大流问题二、最小费用最大流的网络图论解法二、最小费用最大流的网络图论解法对网络上弧（对网络上弧（v vi i,v,vj j）的（）的（c cij ij,b,bij ij）的表示作如下改动，用）的表示作如下改动
39、，用(b)(b)来表示来表示(a)(a)。用上述方法对例用上述方法对例7 7中的图形进行改进，得图如下页：中的图形进行改进，得图如下页：32vivjvivj（cij,bij）（0,-bij）（a）（b）（cij,bij）（cij,bij）vivj（cji,bji）（cij,bij）vivj（cji,bji）（0,-bji)（0,-bji)（c）（d）第32页，此课件共41页哦55最小费用最大流问题最小费用最大流问题 求最小费用最大流的基本算法求最小费用最大流的基本算法 在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求最大流
40、的基本算法完全一样，不同的只是在步骤（最大流的基本算法完全一样，不同的只是在步骤（1 1）中要选择一条总的）中要选择一条总的单位费用最小的路，而不是包含边数最小的路。单位费用最小的路，而不是包含边数最小的路。33(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-28第33页，此课件共41页哦55最小费用最大流问题最小费用最大流问题用上述方法对例用上述方法对例
41、7 7求解：求解：第一次迭代：找到最短路第一次迭代：找到最短路v v1 1 v v4 4 v v6 6 v v7 7。第一次迭代后总流量为第一次迭代后总流量为1 1，总，总费用费用1010。34v5(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第34页，此课件共41页哦55最小费用最大流问题最小费用最大流问题第二次迭代：找到最短路第二次迭代：找到最短路v
42、 v1 1 v v4 4 v v7 7。第二次迭代后总流量为第二次迭代后总流量为3 3，总费用，总费用3232。35(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-30第35页，此课件共41页哦55最小费用最大流问题最小费用最大流问题第三次迭代：找到最短路第三次迭代：找到最短路v v1 1 v v4 4 v v3 3 v v6 6 v v7 7。第三次迭代
43、后总流量为第三次迭代后总流量为5 5，总费用，总费用5656。36(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-31第36页，此课件共41页哦55最小费用最大流问题最小费用最大流问题第四次迭代：找到最短路第四次迭代：找到最短路v v1 1 v v4 4 v v3 3 v v5 5 v v7 7。第四次迭代后总流量为第四次迭代后总流量为6 6，总费用，总费
44、用7272。37(6,6)(3,4)(4,7)(2,5)(1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(0,3)(6,-3)(2,-8)(1,-3)（3,-2）(0,-6)(0,-4)(0,-5)（1,4）(1,-7)(3,-4)（2,-3）图图11-3211-32第37页，此课件共41页哦55最小费用最大流问题最小费用最大流问题 第五次迭代：找到最短路第五次迭代：找到最短路v v1 1 v v2 2 v v5 5 v v7 7。第五次迭代后总流量为第五次迭代后总流量为9 9，总，总费用费用123123。38(3,6)(0,4)(1,7)(2,5)(
45、1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(0,3)(6,-3)(2,-8)(1,-3)（3,-2）(3,-6)(3,-4)(0,-5)（1,4）(4,-7)(3,-4)（2,-3）图图11-3311-33第38页，此课件共41页哦55最小费用最大流问题最小费用最大流问题 第六次迭代：找到最短路第六次迭代：找到最短路v v1 1 v v2 2 v v3 3 v v5 5 v v7 7。第六次迭代后总流量为第六次迭代后总流量为1010，总费用，总费用145145。已经找不到从。已经找不到从v v1 1到到v v7 7的每条弧容量都大于零的路了，故的每
46、条弧容量都大于零的路了，故已求得最小费用最大流了。已求得最小费用最大流了。39(2,6)(0,4)(0,7)(1,5)(2,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(0,3)(6,-3)(2,-8)(1,-3)（3,-2）(4,-6)(3,-4)(1,-5)（0,4）(5,-7)(3,-4)（2,-3）图图11-3411-34第39页，此课件共41页哦55最小费用最大流问题最小费用最大流问题 40 如果对例如果对例7求一个最小费用流的问题：每小时运送求一个最小费用流的问题：每小时运送6万加仑石油从万加仑石油从v1到到v7的最小的最小费用是多少，或者每
47、小时运送费用是多少，或者每小时运送7万加仑呢？我们可以从第四次迭代及图万加仑呢？我们可以从第四次迭代及图11-32即可得到运即可得到运送送6万加仑最小费用万加仑最小费用72百元，其运送方式通过比较图百元，其运送方式通过比较图11-28及图及图11-32即得图即得图11-36所示。所示。至于每小时运送至于每小时运送7万加仑，我们可以在图万加仑，我们可以在图11-36的基础上，再按第五次迭代所选的的基础上，再按第五次迭代所选的最短路运送最短路运送1万加仑即得最小费用：万加仑即得最小费用：72+1*17=89百元，其运送方式如图百元，其运送方式如图11-35所示。所示。35123126v1v2v5v4v3v610342v710第六次迭代第六次迭代后总流量后总流量图图11-35第40页，此课件共41页哦55最小费用最大流问题最小费用最大流问题 41123126v1v2v5v4v3v6631v7图图11-361223126v1v2v5v4v3v6311v7图图11-37注：注：“管理运筹学管理运筹学”软件有专门的子软件有专门的子程序用于解决这类问题。程序用于解决这类问题。1第41页，此课件共41页哦