图与网络模型

图与网络模型第1页，课件共110页，创作于2023年2月1引言

图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。第2页，课件共110页，创作于2023年2月2

随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。第3页，课件共110页，创作于2023年2月3

1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图1a所示。第4页，课件共110页，创作于2023年2月4AB图1aCD第5页，课件共110页，创作于2023年2月5

当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图1b所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。第6页，课件共110页，创作于2023年2月6图1bACDB第7页，课件共110页，创作于2023年2月7§1图与网络的基本概念

在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例1:图8-1是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。第8页，课件共110页，创作于2023年2月8太原重庆武汉南京徐州连云港上海郑州石家庄塘沽青岛济南天津北京图11-1第9页，课件共110页，创作于2023年2月9

例2:有六支球队进行足球比赛，我们分别用点v1…v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图8-2所示的有向图反映出来。第10页，课件共110页，创作于2023年2月10v3v1v2v4v6v5图8-2第11页，课件共110页，创作于2023年2月11例3：在一个人群中，对相互认识这个关系我们可以用图来表示，图11-3就是一个表示这种关系的图。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5图8-3第12页，课件共110页，创作于2023年2月12

当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图8-4来表示。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5图8-4第13页，课件共110页，创作于2023年2月13

从以上的几个例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。第14页，课件共110页，创作于2023年2月14a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图11-5如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图11-5就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。第15页，课件共110页，创作于2023年2月15

§1图与网络的基本概念无向图：由点和边构成的图，记作G=（V，E）。有向图：由点和弧构成的图，记作D=（V，A）。第16页，课件共110页，创作于2023年2月16次（度）：与顶点关联的边数。简单图：没有环和重边的图。悬挂点：次为1的点。悬挂边：次为1的边。孤立点：次为0的点。(e8)=(v4，v4),称为自回路(环)；v6是孤立点，v5为悬挂点，e7为悬挂边，顶点v3的次为4，顶点v2的次为3。第17页，课件共110页，创作于2023年2月17定理1：在一个图中，所有顶点次的和等于边的两倍。定理2：在任意一个图中，奇顶点的个数必为偶数。第18页，课件共110页，创作于2023年2月18圈（Circuit）封闭的链称为圈如：μ={(1,2),(2,4),(4,3),(3,1}

链:由图G中的某些点与边相间构成的序列{V1,e1,V2,e2,……,Vk,ek},若满足ei=[Vi,Vi],则称此点边序列为G中的一条链。如：μ={(1,2),(3,2),(3,4)}4231第19页，课件共110页，创作于2023年2月19回路：若路的第一个点和最后一个点相同，则该路为回路。赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：

在赋权的图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。第20页，课件共110页，创作于2023年2月20连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。第21页，课件共110页，创作于2023年2月21二、图的矩阵表示

图非常直观，但是不容易计算，特别不容易在计算机上进行计算，一个有效的解决办法是将图表示成矩阵形式，通常采用的矩阵是邻接矩阵、边长邻接矩阵、弧长矩阵和关联矩阵。第22页，课件共110页，创作于2023年2月221邻接矩阵

邻接矩阵A表示图G的顶点之间的邻接关系，它是一个n×n的矩阵，如果两个顶点之间有边相联时，记为1，否则为0。第23页，课件共110页，创作于2023年2月23v1v2v3v4第24页，课件共110页，创作于2023年2月24

v1v2v3v4v10111v21110v31101v41010无向图的邻接矩阵是对称矩阵。v1v2v3v4第25页，课件共110页，创作于2023年2月25v1v5v4v3v2也可以对有向图第26页，课件共110页，创作于2023年2月26

v1v2v3v4v5v100011v210010v301100v401101v510010第27页，课件共110页，创作于2023年2月27二、边长矩阵

在图的各边上一个数量指标，具体表示这条边的权（距离，单价，通过能力等）——赋权图或网络。以边长代替邻接矩阵中的元素得到边长矩阵。第28页，课件共110页，创作于2023年2月28v1v2v3v4256434第29页，课件共110页，创作于2023年2月29

v1v2v3v4v10256v22430v35304v46040第30页，课件共110页，创作于2023年2月303弧长矩阵对有向图的弧可以用弧长矩阵来表示。其中0表示两点之间没有弧连接。第31页，课件共110页，创作于2023年2月31v1v5v4v3v2142322612第32页，课件共110页，创作于2023年2月32

v1v2v3v4v5v1010

02v200204v302010

v403206v50

0

0

00第33页，课件共110页，创作于2023年2月33§2最短路问题最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从Vs

到Vt

的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。第34页，课件共110页，创作于2023年2月34最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。第35页，课件共110页，创作于2023年2月35一、求解最短路的Dijkstra算法(双标号法）步骤：1.给出点V1以标号(0,s)2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合3.如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则vs到vt的距离为lt，而从vs到vt的最短路径，则可以从kt

反向追踪到起点vs

而得到。如果vt

未标号，则可以断言不存在从vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步。4.对上述弧的集合中的每一条弧，计算sij=li+cij

。在所有的sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,Vc）,返回步骤2。第36页，课件共110页，创作于2023年2月36例：求v1至v8的最短路。v2v3v7v1v8v4v5v66134105275934682第37页，课件共110页，创作于2023年2月37(1)v1:[0,v1]计算min{0+2,0+1,0+3}=min{2,1,3}=1v4:[1.v1]v2v3v7v1v8v4v5v66134105275934682[1,v1][0,v1](2)I={v1}检查弧（v1,v2),(v1,v4),(v1,v6)第38页，课件共110页，创作于2023年2月38v2v3v7v1v8v4v5v66134105275934682(3)I={v1,v4}计算min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2v2:[2,v1][0,v1][1,v1][2,v1]考虑弧（v1,v2),(v1,v6),(v4,v2),(v4,v7)第39页，课件共110页，创作于2023年2月39v2v3v7v1v8v4v5v66134105275934682（4）I={v1,v2,v4}

计算min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3v6:[3,v1][2,v1][1,v1][0,v1][3,v1]考虑弧（v1,v6),(v2,v3),(v2,v5),(v4,v7)第40页，课件共110页，创作于2023年2月40v2v3v7v1v8v4v5v66134105275934682(5)I={V1,V2,V4,V6}计算min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3v7:[3,v4][2，V1][1，V1][0，V1][3，V1][3,v4]考虑弧(v2,v3),(v2,v5),(v4,v7),(v6,v7)第41页，课件共110页，创作于2023年2月41V2V3V7V1V8V4V5V66134105275934682(6)I={V1,V2,V4,V6,V7}计算min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6v5:[6,v7][2,v1][1,v1][0,v1][3,v1][3,v4][6,v7]考虑弧(v2,v3),(v2,v5),(v7,v5),(v7,v8)第42页，课件共110页，创作于2023年2月42v2v3v7v1v8v4v5v66134105275934682(7)I={V1,V2,V4,V6,V7}计算min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8v3:[8,v2][2,V1][1,V1][0,V1][3,V1][3,V4][6,V7][8,v2]考虑弧(v2,v3),(v5,v3),(v5,v8),(v7,v8)第43页，课件共110页，创作于2023年2月43v2v3v7v1v8v4v5v66134105275934682(8)I={v1,v2,v3,v4,v6,v7}

计算min{8+6,6+4,3+7}=min{14,10,11}=10v8:[10,v5][2,v1][1,v1][0,v1][3,v1][3,v4][6,v7][8,v2][10,v5]考虑弧（v3,v8),(v5,v8),(v7,v8)第44页，课件共110页，创作于2023年2月44v2v3v7v1v8v4v5v66134105275934682(9)I={v1,v2,v3,v4,v6,v7,v8}v1到v8的最短路径为v1—v4—v7—v5—v8，最短路长度为10。[2,v1][1,v1][0,v1][3,v1][3,v4][6,v7][8,v2][10,v5]反向追踪：v8-v5-v7-v4-v1第45页，课件共110页，创作于2023年2月45

例2求下图中v1到v6的最短路v23527531512v1v6v5v3v4第46页，课件共110页，创作于2023年2月46解：采用Dijkstra算法，可解得最短路径为v1v3v4v6

各点的标号图如下：(3,1)v23527531512

V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4第47页，课件共110页，创作于2023年2月47

例3电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。

V1（甲地）15176244431065v2V7（乙地）v3v4v5v6第48页，课件共110页，创作于2023年2月48解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。第49页，课件共110页，创作于2023年2月49最终解得：最短路径v1v3v5v6v7，每点的标号见下图（0,s）

V1（甲地）1517624431065(13,3)v2

(22,6)V7（乙地）V5(14,3)V6(16,5)

V3(10,1)

V4(18,5)第50页，课件共110页，创作于2023年2月50

例4:设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。第51页，课件共110页，创作于2023年2月51年份12345年初价格1111121213使用年数0-11-22-33-44-5每年维修费用5681118已知：设备每年年初的价格表维修价格表：第52页，课件共110页，创作于2023年2月52例4的解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。v1v2v3v4v5v6第53页，课件共110页，创作于2023年2月53123456116223041592162230413172331417235186所有弧的权数计算如下表：第54页，课件共110页，创作于2023年2月54

(继上页)把权数赋到图中，再用Dijkstra算法求最短路。

v1v2v3v4v5v6162230415916223041312317181723第55页，课件共110页，创作于2023年2月55最终得到下图，可知，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)第56页，课件共110页，创作于2023年2月56例：某交通网络如下图，求v1到v8的最短路线v1v2v4v5v6v7v86312216104310446练习：求最短路第57页，课件共110页，创作于2023年2月57树是图论中的重要概念，所谓树就是一个无圈的连通图。

图8-11中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。图8-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)8.3最小生成树问题第58页，课件共110页，创作于2023年2月58

给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子图。在图8-12中，(b)和(c)都是(a)的生成子图。如果图G的一个生成子图还是一个树，则称这个生成子图为生成树，在图8-12中，(c)就是(a)的生成树。最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。图8-12(a)(b)(c)第59页，课件共110页，创作于2023年2月59树的性质243512435124351如果树T有m个结点，则边的个数为m-1。

树中任意两个节点间有且只有一条链。

在树中任意去掉一条边，则不连通。第60页，课件共110页，创作于2023年2月60定理图G有生成树的充分必要条件为图是连通图。定义（最优树）在赋权图G中，一棵生成树所有树枝上权的和，称为生成树的权。具有最小权的生成树，称为最优树（或最小树）。求最小树的方法有破圈法和避圈法。第61页，课件共110页，创作于2023年2月61一求解最小支撑树问题的破圈法方法：去边破圈的过程。步骤：1）在给定的赋权的连通图上任找一个圈。

2）在所找的圈中去掉一条权数最大的边。

3）若所余下的图已不含圈，则计算结束，余下的图即为最小支撑树，否则返回1）。第62页，课件共110页，创作于2023年2月62423142314231生成树2生成树3生成树1////例：用破圈法求右图的最小支撑树。4231

74581总权数=3+4+1=8第63页，课件共110页，创作于2023年2月63二求解最小支撑树的避圈法方法：选边的过程。步骤：1）从网络中任意选一点vi，找出与vi相关联的权最小的边[vi,vj]，得第二个顶点vj。

2）把顶点集V分为互补得两部分A,Ā，其中：

A：与已选边相关联得点集

Ā

：不与已选边相关联得点集第64页，课件共110页，创作于2023年2月64

3)考虑所有这样的边[vi,vj]，其中vi∈A,vj∈Ā,挑选其中权最小的。

4）重复3），直至全部顶点均属于A即可。V4V2V3V1

74581例：用避圈法求由图的最小支撑树。第65页，课件共110页，创作于2023年2月65①任选点v1，挑与之相关联的权最小的边（v1,v4）.②A={v1,v4},Ā={v3,v2}

从边（v1,v3）,（v1,v2）,（v2,v4）,（v4,v3）中选权最小的边（v1,v2）。V4V2V3V1

74581③A={v1,v2,v4},Ā={v3}

从边（v1,v3）,（v2,v3）,（v3,v8）中选权最小的边（v2,v3）。④A={v1,v2,v3，

v4}第66页，课件共110页，创作于2023年2月66

例5、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,…,v7

表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。

v1331728541034v7v6v5v4v2v3图8-14第67页，课件共110页，创作于2023年2月67解：此问题实际上是求图8-14的最小生成树，这在例4中已经求得，也即按照图8-13的(f)设计，可使此网络的总的线路长度为最短，为19百米。“管理运筹学软件”有专门的子程序可以解决最小生成树问题。第68页，课件共110页，创作于2023年2月68v1v7v4v3v2v5v620159162532817412336练习用破圈法或者避圈法求最小生成树

第69页，课件共110页，创作于2023年2月69v1v7v4v3v2v5v693174123总造价=1+4+9+3+17+23=57第70页，课件共110页，创作于2023年2月70§4最大流问题最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。第71页，课件共110页，创作于2023年2月71一、最大流的数学模型例6某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运送多少加仑石油？63522241263v1v2v7v4v3v6图8-26v5第72页，课件共110页，创作于2023年2月72

我们可以为此例题建立线性规划数学模型：设弧(vi,vj)上流量为fij，网络上的总的流量为F，则有：第73页，课件共110页，创作于2023年2月73

在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等于弧(vi,vj)的容量cij，并大于等于零，即0≤fij≤cij。我们把满足守恒条件及流量可行条件的一组网络流{fij}称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。

第74页，课件共110页，创作于2023年2月74二、最大流问题网络图论的解法

对网络上弧的容量的表示作改进。为省去弧的方向，如下图:(a)和(b)、(c)和(d)的意义相同。

vivjvivjcij0（a）（b）

cijcijvivj（cji）（c）vivj

cij

cji（d）第75页，课件共110页，创作于2023年2月75用以上方法对例6的图的容量标号作改进，得下图63522241263v1v2v5v7v4v3v600000000000第76页，课件共110页，创作于2023年2月76

求最大流的基本算法（1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。（3）在这条路上，减少每一条弧的顺流容量pf

，同时增加这些弧的逆流容量pf，返回步骤（1）。

第77页，课件共110页，创作于2023年2月77用此方法对例6求解：第一次迭代：选择路为v1v4v7

。弧（v4,

v7

）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：第78页，课件共110页，创作于2023年2月7863522241263v1v2v5v7v4v3v6000000000004202第79页，课件共110页，创作于2023年2月79

第二次迭代：选择路为v1v2v5v7

。弧（v2,

v5

）的顺流容量为3，决定了pf=3，改进的网络流量图如下图：

635222413v1v2v5v7v4v3v60000000042022033303第80页，课件共110页，创作于2023年2月80第三次迭代：选择路为v1v4v6v7

。弧（v4,

v6

）的顺流容量为1，决定了pf=1，改进的网络流量图如下图：222413v1v2v5v7v4v3v600100042022033333013第81页，课件共110页，创作于2023年2月81

第四次迭代：选择路为v1v4v3v6v7

。弧（v3,

v6

）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：

22243v1v2v5v7v4v3v61100012032033350312002333第82页，课件共110页，创作于2023年2月82第五次迭代：选择路为v1v2v3v5v7

。弧（v2,

v3

）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：22v1v2v5v7v4v3v61012020333501202333150020205第83页，课件共110页，创作于2023年2月83

经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为10。最大流量图如下图：22v1v2v5v7v4v3v6123522355第84页，课件共110页，创作于2023年2月84练习：求从发点V1到收点V7的最大流。弧的流量放在括号内。如图.V=20v1v2v34v5v6v786314383410764第85页，课件共110页，创作于2023年2月85§5最小费用最大流问题最小费用最大流问题：给了一个带收发点的网络，对每一条弧（vi,vj），除了给出容量cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流F，并使得总运送费用最小。第86页，课件共110页，创作于2023年2月86一、最小费用最大流的数学模型例7由于输油管道的长短不一，所以在例6中每段管道（vi,vj

）除了有不同的流量限制cij外，还有不同的单位流量的费用bij

，cij的单位为万加仑/小时，bij的单位为百元/万加仑。如图。从采地v1向销地v7运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。第87页，课件共110页，创作于2023年2月87v7(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v4v3v6(6,3)v5（Cij，Bij）第88页，课件共110页，创作于2023年2月88

这个最小费用最大流问题也是一个线性规划的问题。解：我们用线性规划来求解此题，可以分两步走。第一步，先求出此网络图中的最大流量F，这已在例6中建立了线性规划的模型，通过管理运筹学软件已经获得结果。

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

由此得到线性规划模型如下：第90页，课件共110页，创作于2023年2月90

第91页，课件共110页，创作于2023年2月91

用管理运筹学软件，可求得如下结果：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最优值(最小费用)=145。第92页，课件共110页，创作于2023年2月92如果我们把例7的问题改为：每小时运送6万加仑的石油从采地v1到销地v7最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。

第93页，课件共110页，创作于2023年2月93一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧(vi,vj)赋权以容量cij及单位费用bij的网络中，求一个给定值f的流量的最小费用，这个给定值f的流量应小于等于最大流量F，否则无解。第94页，课件共110页，创作于2023年2月94求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量F改为f即可。在例6中只要把f12+f14=F改为f12+f14=f=6得到了最小费用流的线性规划的模型了。第95页，课件共110页，创作于2023年2月95二、最小费用最大流的网络图论解法对网络上弧（vi,vj）的（cij,bij）的表示作如下改动，用(b)来表示(a)。vivj（cij,bij）（0,-bji

）（b）（a）vivj（cij,bij）（cij,bij）vivj（cji,bji）（cij,bij）vivj（cji,bji）（0,-bji)（0,-bji)（c）（d）第96页，课件共110页，创作于2023年2月96用上述方法对例7中的图形进行改进，得图如下(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）图8-28第97页，课件共110页，创作于2023年2月97

求最小费用最大流的基本算法在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求最大流的基本算法完全一样，不同的只是在步骤（1）中要选择一条总的单位费用最小的路，而不是包含边数最小的路。第98页，课件共110页，创作于2023年2月98用上述方法对例7求解：第一次迭代：找到最短路v1v4v6v7。第一次迭代后总流量为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）图8-29第99页，课件共110页，创作于2023年2月99第二次迭代：找到最短路v1v4v7。第二次迭代后总流量为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