运筹学-图论课件

图论第五章图与网络分析运筹学-图论主要内容：1图的基本概念与基本定理2树和最小支撑树3最短路问题4最大流问题5最小费用流问题运筹学-图论什么是图？图论中所谓的图是由一些点(vertices)，和一些连接兩点的边(edges)所形成的运筹学-图论5.1图的基本概念与基本定理

图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论、信息论、工程技术、交通运输、经济管理、电子计算机等各项领域。对于科学研究、市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如：各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决问题。运筹学-图论关于图的第一篇论文是瑞士数学家欧拉（E.Euler）在1736年发表的解决“哥尼斯堡”七桥难题的论文。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，当地的居民热衷于这样一个问题：一个散步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图所示图形的一笔画问题。运筹学-图论Königsberg(Koenigsberg)哥尼斯堡，原为东普鲁士(Prussia)首府，现属俄罗斯(飞地)，名为加里宁格勒(Kaliningrad)运筹学-图论运筹学-图论哥尼斯堡七桥问題:要如何走过每座桥恰一次，再返回出发点？普瑞格爾河运筹学-图论哥尼斯堡七桥问题ABCD运筹学-图论哥尼斯堡七桥问题可简化为以下图形其中的四个顶点都是奇顶点ABCD运筹学-图论CADB哥尼斯堡七橋問題可以看成是：对这样一个封闭的图形，是否可以一笔画完成它并且回到原点数学家欧拉(Euler,1707-1783)于1736年严格地证明了上述哥尼斯堡七桥问题无解，并且由此开创了图论的典型思维方式及论证方式运筹学-图论即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。

在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。运筹学-图论图论应用举例例如，在组织生产中，为完成某项任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。各种通信网络的合理架设交通网络的合理分布等运筹学-图论生活中的一些例子运筹学-图论台大网路架构图运筹学-图论例5.1

图5.2是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。石家庄太原北京天津塘沽济南青岛徐州连云港南京上海郑州武汉重庆图5.3运筹学-图论

例5.2

有六支球队进行足球比赛，我们分别用点v1，…，v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2

队，v2队战胜v3

队，v3队战胜v5队，如此等等。这个胜负情况，可以用图5.3所示的有向图反映出来v3v5v2v4v6v1运筹学-图论

从以上的几个例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。通常用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中对象的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图、工程图等本质上是不同的。运筹学-图论

图论中的图是由点、点与点之间的线所组成的。通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。如果一个图是由点和边所构成的，那么称为无向图，记作G=(V，E)，其中V表示图G

的点集合，E表示图G的边集合。连接点vi,vjV的边记作[vi,vj]，或者[vj,vi]。如果一个图是由点和弧所构成的，那么称为它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。

图的基本概念运筹学-图论

图5.4是一个无向图G=（V，E），其中V={v1,v2,v3,v4}E={[v1,v2],[v2,v1],[v2,v3],[v3,v4],[v1,v4],[v2,v4],[v3,v3]}v3v2v1v4图5.4运筹学-图论图5.5

是一个有向图D=（V，A）其中V={v1

,v2

,v3

,v4

,v5

,v6

,v7}A={(v1,v2),(v1,v3),(v3

,v2)(v3

,v4),(v2

,v4),(v4

,v5),(v4

,v6),(v5,v3),(v5

,v4),(v5

,v6),(v6

,v7)}图5.5v7v5v3v4v2v6v1运筹学-图论

图的基本概念一个图G或有向图D中的点数，记作P(G)或P(D)，简记作P；边数或者弧数，记作q(G)或者q(D)，简记作q。如果边[vi,vj]E，那么称vi,vj

是边的端点，或者vi,vj是相邻的。如果一个图G中，一条边的两个端点是相同的，那么称为这条边是环，如图5.4中的边[v3,v3]是环。运筹学-图论

图的基本概念如果两个端点之间有两条以上的边，那么称为它们为多重边，如图5.4中的边[v1

,v2],[v2

,v1]。v3v2v1v4运筹学-图论v1v5v4v3v2简单图（2）（4）（3）（3）（2）多重图v1v5v4v3v2（4）（6）（3）（3）（2）一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。运筹学-图论

以点v为端点的边的个数称为点v的度（次），记作d(v),如图5.4中d(v1)=3，d(v2

)=4，d(v3

)=4，d(v4)=3。度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。端点的度

d(v)：点v作为端点的边的个数奇点：d(v)=奇数；运筹学-图论偶点：d(v)

=偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边；孤立点：d(v)=0；空图：E=，无边图v1v2v3v4v5v6运筹学-图论v1v7v6v5v4v3v2V={v1,v2,v3,v4,v5,v6,v7}d(v1)=3;d(v2)=5;d(v3)=4;d(v4)=4;d(v5)=1;d(v6)=3;d(v7)=0其中v5

为悬挂点，v7为孤立点。图5.7运筹学-图论

定理5.1

所有顶点度数之和等于所有边数的2倍。

证明：因为在计算各个点的度时，每条边被它的两个端点个用了一次。运筹学-图论定理5.2

在任一图中，奇点的个数必为偶数。证明：设V1，V2

分别是图G中奇点和偶点的集合，由定理5.1，有因为是偶数，也是偶数，因此也必是偶数，从而V1

中的点数是偶数。运筹学-图论

图的连通性：链：由两两相邻的点及其相关联的边构成的点边序列。如:v0,e1

,v1

,e2

,v2，e3

,v3

,…,vn-1,en

，

vn;v0，vn分别为链的起点和终点

。记作（v0,v1

,v2，,v3

,…,vn-1,vn）简单链：链中所含的边均不相同；初等链：链中所含的点均不相同,也称通路；圈：若v0≠vn则称该链为开链，否则称为闭链或回路或圈；运筹学-图论简单圈：如果在一个圈中所含的边均不相同初等圈：除起点和终点外链中所含的点均不相同的圈；v1v2v4v3v5v6v7初等链:(v1,v2,v3,v6,v7,v5)初等圈：(v1,v2,v3,v5,v4,v1)简单链：(v1,v2,v3,v4,v5,v3)

简单圈：(v4,v1,v2,v3,v5,v7,v6,v3,v4)运筹学-图论以后除特别声明，均指初等链和初等圈。v1v2v3v4v5不连通图v1v5v4v3v2v6连通图：图中任意两点之间均至少有一条通路，否则称为不连通图。

连通图运筹学-图论有向图：关联边有方向弧：有向图的边a=(u,v),起点u,终点v；路：若有从u

到v

不考虑方向的链,且各方向一致,则称之为从u到v的路；初等路:

各顶点都不相同的路；初等回路:u=v

的初等路;连通图：

若不考虑方向是无向连通图;

强连通图：任两点有路;

运筹学-图论基本概念点边，弧无向图链端点关联边有向图圈始点，终点多重边简单图初等链/圈度（次）环多重图简单链/圈奇点，偶点连通图基础图悬挂点悬挂边不连通图路弧立点回路运筹学-图论

例一摆渡人欲将一只狼、一头羊、一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且狼与羊,羊与菜不能独处。给出渡河方法。

解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0)，共有24=16种状态，在河东岸的状态类似记作。

由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的，从而对应状态(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的。以可允许的10个状态向量作为顶点，将可能互相转移的状态用线段连接起来构成一个图。根据此图便可找到渡河方法。运筹学-图论(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河西=(人,狼,羊,菜)河东=(人,狼,羊,菜)

将10个顶点分别记为A1,A2,…,A10,则渡河问题化为在该图中求一条从A1到A10的路.

从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.运筹学-图论图的矩阵表示1.邻接矩阵Adjacencymatrix表示图中两点之间的相互关系两点之间有弧或边的，用1表示，否则用0表示，构成一个矩阵Av2v4v6v5v1v3v1v2v3v4v5v6v1011000v2101110v3110010v4010011v5011101v6000110运筹学-图论有向图v1v7v2v5v3v4v6v8v9v1v2v3v4v5v6v7v8v9v1011100000v2000010000v3010100000v4000001000v5000101110v6000010100v7000000010v8000000000v9000010010运筹学-图论矩阵A的元素全为0的行所对应的点称为汇点上图v8矩阵A的元素全为0的列所对应的点称为源点上图v1、v9运筹学-图论5.2树和最小支撑树一、树及其性质在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。

例5.3

已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。运筹学-图论如果用六个点v1…v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。表示任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图5.2.1是一个不含圈的连通图，代表了一个电话线网。运筹学-图论图5.2.1v6v3v4v2v5v1运筹学-图论树及其性质树：既简单又很有用树：一个无圈的连通图运筹学-图论组织结构图ManagerSubordSubord运筹学-图论荣国公贾代善贾赦贾政贾琏贾珠贾宝玉贾环贾兰运筹学-图论定理定理1：设G=(V,E)是一个树，p(G)>=2，则G中至少有两个悬挂点。定理2：图G=(V,E)是一个树的充要条件是G不含圈，且恰有p-1条边。定理3：图G=(V,E)是一个树的充要条件是G是连通图，且q(G)=p(G)-1。定理4：图G=(V,E)是一个树的充要条件是任意两个顶点之间恰有一条链。运筹学-图论推论从一个树中去掉任意一条边，则余下的图是不连通的。在树中不相邻的两个点间添上一条边，则恰好得到一个圈运筹学-图论运筹学-图论图的支撑树设图T=(V,E')是图G=(V,E)的一个支撑子图，如果T是一个树，则称T是G的一个支撑树定理5：图G有支撑树的充要条件是图G是连通的。破圈法：任取一个圈，从中去掉一条边，再对余下的图重复直到不再含图时为止。运筹学-图论破圈法运筹学-图论避圈法在图中任取一条边，找到一条与之不构成圈的边，再找一条前两边不构成圈的边重复直到不再能进行为止取出的边数为p-1条运筹学-图论避圈法运筹学-图论最小支撑树问题给定图G=(V,E)，对G中的每一条边[vi,vj]，相应地有一个数wij，则称这样的图为赋权图wij称为边[vi,vj]上的权权是与边有关的数量指标，可以是距离、时间、费用等。运筹学-图论赋权图不仅指出各个点之间的邻接关系，而且同时也表示出各点之间的数量关系广泛应用于解决工程技术及管理等领域的最优化问题最小支撑树问题就是赋权图上的最优化问题之一。运筹学-图论设有一个连通图G=(V,E)，每一边e=[vi,vj]有一个非负权w(e)=wij(wij>0)如果T=(V,E')，是G的一个支撑树，称E'中所有边的权之和为支撑树T

的权，记为w(T)运筹学-图论如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树（最小树），即式中对G的所有支撑树T取最小运筹学-图论最小支撑树问题就是要求G的最小支撑树。方法有二：避圈法Kruskal破圈法常见求赋权图的最小树。运筹学-图论

例5.4某厂内联结六个车间的道路网如下所示，已知每条路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。v1v2v4v6v3v5657152344运筹学-图论避圈法求最小支撑树v1v2v4v6v3v515234i=1,E0=Φ。从E中选最小权边。依次选最小权边，并使之不构成圈。共选5条边v1v2v4v6v5657152344最后，电话线总长1+2+3+4+5=15v3运筹学-图论破圈法求最小支撑树任取一个圈，从中去掉一条权最大的边。依次重复，直到不含圈为止。v1v2v4v6v5657152344最后，电话线总长1+2+3+4+5=15v3运筹学-图论矩阵计算方法T运筹学-图论TT运筹学-图论TTT运筹学-图论TTTT运筹学-图论TTTTT运筹学-图论TTTTTT运筹学-图论矩阵计算结果运筹学-图论一.引言最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。

5.3最短路问题运筹学-图论例5.6如图所示的单行线交通网，每弧旁的数字表示这条单行线的距离。现在某人要从v1出发，通过这个交通网到达v8

，求使总距离最短的旅行线路。v1v7v2v5616321v32v4v610310v8v9246234?运筹学-图论路很多v1v7v2v5616321v32v4v610310v8v92462341+10+2+4=176+1+6=133+2+1+3+4=133+2+10+10+6=31哪一条最短？运筹学-图论最短路算法如果P是D中从vs到vi的最短路，vi是P中的一个点，那么从vs沿P到vi的路是从vs到vi的最短路。1.图形的标号法2.所有wij≥0的情形—Dijkstra法1959运筹学-图论1.图形的标号法先标出离终点最近的一段，然后标号与该点距离最短的点，继续逆推至始点。C4AB1B2C1C2C3D1D2D3E1E2E3F1F2G5313668766688222255333333443510437597681310913121618从A到G的最短路为：A-B1-C2-D1-E2-F2-G运筹学-图论2.Dijkstra法基本思路：从vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为此点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)或者是从vs到该点的最短路的权的上界(称为T标号)方法的每一步是修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的点多一个，如此经过p-1步，就可以求出从vs到各点的最短路。运筹学-图论Dijkstra法具体步骤开始(i=0)，令S0={vs},P(vs)=0,λ(vs)=0,对每一个v≠

vs，令

T(v)=+∞,λ(v)=M,令k=s1.如果Si=V，算法终止，这时，对每个vSi，d(vs,v)=P(v)

；否则转入步骤22.考察每个使(vk,vj)A且vjSi的点vj。如果T(v)>P(vk)+wkj，则把T(vj)修改为P(vk)

+wkj

，把λ(vj)修改为k；否则转入步骤3运筹学-图论3.令T(vji)=min{T(vj)}如果T(vji)<∞则把vji的T标号变为P标号P(vji)=T(vji)，令Si+1=SiU{vji}，k=ji,把i换成i+1，转入步骤1；否则终止，这时对每一个，而对每一个vSi，d(vs,v)=T(v)运筹学-图论v1v2v3v4v5v6v7v80v2v3v4v5v6v7v8PTλ0∞0M∞M∞M∞M∞M∞M∞Mv1v7v2v5616321v32v4v610310v8v9246234若T(v)>P(vk)+wkj则T(v)=P(vk)+wkj

λ(vj)修改为k找到min{T(vj)}，将其TP标号P(vj)=T(vj)，S=

{v1，}6311111v4,v3,1143535v2,626v5,105951259v7,10v6,12v8v1到v8最短路V13258运筹学-图论求s到t的最短路。s3t267452418291415530204416116196运筹学-图论s3t267452418291415530204416116196

0S={}PQ={s,2,3,4,5,6,7,t}运筹学-图论s3t267452418291415530204416116196

0S={}PQ={s,2,3,4,5,6,7,t}运筹学-图论s3t267452418291415530204416116196

15

9

14

0S={s}PQ={2,3,4,5,6,7,t}

X

XX运筹学-图论s3t267452418291415530204416116196

15

9

14

0S={s}PQ={2,3,4,5,6,7,t}

X

XX运筹学-图论s3t267452418291415530204416116196

15

9

14

0S={s,2}PQ={3,4,5,6,7,t}

X

XX运筹学-图论s3t267452418291415530204416116196

15

9

14

0S={s,2}PQ={3,4,5,6,7,t}

X

XXX

33运筹学-图论s3t267452418291415530204416116196

15

9

14

0S={s,2}PQ={3,4,5,6,7,t}

X

XXX

33运筹学-图论s3t267452418291415530204416116196

15

9

14

0S={s,2,6}PQ={3,4,5,7,t}

X

XXX

33

44XX

32运筹学-图论s3t267452418291415530204416116196

15

9

14

0S={s,2,6}PQ={3,4,5,7,t}

X

XX

44X

X

33X

32运筹学-图论s3t2674518291415530204416116196

15

9

14

0S={s,2,6,7}PQ={3,4,5,t}

X

XX

44X

35X

59X24

X

33X

32运筹学-图论s3t267452418291415530204416116196

15

9

14

0S={s,2,6,7}PQ={3,4,5,t}

X

XX

44X

35X

59X

X

33X

32运筹学-图论s3t267452418291415530204416116196

15

9

14

0S={s,2,3,6,7}PQ={4,5,t}

X

XX

44X

35X

59XX

51X

34

X

33X

32运筹学-图论s3t2674518291415530204416116196

15

9

14

0S={s,2,3,6,7}PQ={4,5,t}

X

XX

44X

35X

59XX

51X

34

X

33X

3224运筹学-图论s3t2674518291415530204416116196

15

9

14

0S={s,2,3,5,6,7}PQ={4,t}

X

XX

44X

35X

59XX

51X

3424X

50X

45

X

33X

32运筹学-图论s3t2674518291415530204416116196

15

9

14

0S={s,2,3,5,6,7}PQ={4,t}

X

XX

44X

35X

59XX

51X

3424X

50X

45

X

33X

32运筹学-图论s3t2674518291415530204416116196

15

9

14

0S={s,2,3,4,5,6,7}PQ={t}

X

XX

44X

35X

59XX

51X

3424X

50X

45

X

33X

32运筹学-图论s3t2674518291415530204416116196

15

9

14

0S={s,2,3,4,5,6,7}PQ={t}

X

XX

44X

35X

59XX

51X

34X

50X

45

X

33X

3224运筹学-图论s3t267452418291415530204416116196

15

9

14

0S={s,2,3,4,5,6,7,t}PQ={}

X

XX

44X

35X

59XX

51X

34X

50X

45

X

33X

32运筹学-图论s3t267452418291415530204416116196

15

9

14

0S={s,2,3,4,5,6,7,t}PQ={}

X

XX

44X

35X

59XX

51X

34X

50X

45

X

33X

32运筹学-图论237184566134105275934682求从1到8的最短路径运筹学-图论237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0运筹学-图论237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2运筹学-图论237184566134105275934682X={1,2,4}min{c13,c23,c25,c47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3运筹学-图论237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3运筹学-图论237184566134105275934682X={1,2,4,6,7}min{c23,c25,c75,c78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6运筹学-图论237184566134105275934682X={1,2,4,6,7}min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8运筹学-图论237184566134105275934682X={1,2,3,4,6,7}min{c38,c58,c78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10运筹学-图论237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路径为{1，4，7，5，8}，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10运筹学-图论三、含有负权的最短路的求法83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v8例：求从v1

到v8

的最短路运筹学-图论83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-1-2383-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-71-15运筹学-图论83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56运筹学-图论83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56从v1

到v8

的最短路的长度为：6从v1

到v8

的最短路线为：v8v6v3v1运筹学-图论应用举例设备更新问题。某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧的，则需支付一定的维修费用。现在的问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少。运筹学-图论我们用一个五年之内要更新某种设备的计划为例，若已知该种设备在各年年初的价格如下表，还知使用不同时间的设备所需要的维修费用如下表。第1年第2年第3年第4年第5年价格1111121213使用年限0-11-22-33-44-5维修费用5681118运筹学-图论可供选择的设备更新方案显然是很多的。例如，每年都购置一台新设备，则其购置费用为11+11+12+12+13=59，而每年支付的维修费用为5，五年合计为25。于是5年的总费用为59+25=84再如，每1，3，5年各购进一台。此时设备购置费用为11+12+13=36，维修费用为5+6+5+6+5=27，5年总费用为36+27=63。如何制定总费用最省的设备更新计划呢？运筹学-图论转化为最短路问题。用点代表“第i年年初购进一台新设备”

这样上述设备更新问题就变为：在有向赋权图G=(V,E,F)(图解如下)中求v1到v6的最短路问题。运筹学-图论

由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5,v1到v6,v2到v6的连线；又设备使用一年后就更新则不划算,因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6五条连线后得到从上图中容易得到v1到v6只有两条路：v1v3v6和v1v4v6.

而这两条路都是v1到v6的最短路.五年的总费用为53。运筹学-图论例拣货路径问题Pickpath货架分布要拣货物运筹学-图论第1步

从第1通道到第2通道

每条路径代表图中的一条边运筹学-图论第2步

找出从第2通道到第3通道的每条路径运筹学-图论第3步

找出从第3通道到第4通道的每条路径运筹学-图论第4步

找出从第4通道到完成的每条路径运筹学-图论Findtheshortestpathoftheassociatedgraph运筹学-图论Theshortestpathontheassociatedgraphgivesanefficientpickpathinwarehouse对应图的最短路给出了仓库的有效拣选路径运筹学-图论运筹学-图论5.4网络的最大流5.4.1网络的最大流的概念网络流一般在有向图上讨论定义网络上支路的容量为其最大通过能力，记为cij，支路上的实际流量记为fij

图中规定一个发点s，一个收点t节点没有容量限制，流在节点不会存储容量限制条件：0fijcij平衡条件：viA(vi)B(vi)运筹学-图论5.4网络的最大流图中规定一个发点s，一个收点t－节点没有容量限制，流在节点不会存储－容量限制条件：0fijcij－平衡条件：

满足上述条件的网络流称为可行流，总存在最大可行流当支路上fij=cij，称为饱和弧；v(f)为可行流的流量最大流问题也是一个线性规划问题viA(vi)B(vi)运筹学-图论定义：设f是一个可行流，是vs从vt到的一条链，若

满足下列条件，则是可行流的一条增广链：(1)

弧(vi,vj)+上，即+

中每一条弧是非饱和弧；(2)弧(vi,vj)-上，即-

中每一条弧是非零流弧；运筹学-图论定义：把网络分割为两个成分的弧的最小集合，其中一个成分包含s

点，另一个包含t

点。一般包含s

点的成分中的节点集合用V表示，包含t

点的成分中的节点集合用V表示截量集容量是指截量集中前向弧的容量之和

福特-富克森定理：网络的最大流等于最小截量集容量运筹学-图论5.4.2确定网络最大流的标号法

从任一个初始可行流出发，如0流基本算法：找一条从s

到t

点的增广链。若在当前可行流下找不到增广链，则已得到最大流增广链中与s

到t方向一致的弧称为前向弧，反之后向弧

增广过程：前向弧fij=fij+,后向弧fij=fij

增广后仍是可行流运筹学-图论

最大流最小截量的标号法步骤第一步：标号过程，找一条增广链1、给源点s

标号[s+,q(s)=]，表示从s点有无限流出潜力2、找出与已标号节点i

相邻的所有未标号节点j，若(1)(i,j)是前向弧且饱和，则节点j

不标号；(2)(i,j)是前向弧且未饱和，则节点j

标号为[i+,q(j)]，表示从节点i

正向流出，可增广q(j)=min[q(i),cijfij]；(3)(j,i)是后向弧，若fji=0，则节点j

不标号；(4)(j,i)是后向弧，若fji>0，则节点j

标号为[i,q(j)]，表示从节点j

流向i，可增广q(j)=min[q(i),fji]；运筹学-图论

最大流最小截量的标号法步骤3、重复步骤2，可能出现两种情况：(1)节点t

尚未标号，但无法继续标记，说明网络中已不存在增广链，当前流v(f)就是最大流；所有获标号的节点在V

中，未获标号节点在V

中，V与V

间的弧即为最小截量集；算法结束(2)节点t

获得标号，找到一条增广链，由节点t

标号回溯可找出该增广链；到第二步运筹学-图论

最大流最小截量的标号法步骤第二步：增广过程1、对增广链中的前向弧，令f=f+q(t)，q(t)为节点t

的标记值2、对增广链中的后向弧，令f=fq(t)3、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步一次只找一条增广链，增广一次换一张图最后一次用广探法，以便找出最小截量集运筹学-图论最大流最小截量集的标号法举例(s+,)(s+,6)(2,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5,2)(4+,2)运筹学-图论(s+,)(s+,3)(2,3)最小截量集运筹学-图论§5.5最小费用最大流问题

在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。运筹学-图论

我们首先考察，在一个网络D中，当沿可行流f的一条增广链μ，以调整量θ=1改进f，得到的新可行流f'的流量，有v(f

)=v(f)+1，而此时总费用b(f

)比b(f)增加了

设一个网络D=（V，A，C），对于每一个弧(vi,vj)∈A,给定一个单位流量的费用bij0，网络系统的最小费用最大流问题，是指要寻求一个最大流f，并且流的总费用达到最小。运筹学-图论结论：如果可行流f

在流量为v(f)的所有可行流中的费用最小，并且是关于f的所有增广链中的费用最小的增广链，那么沿增广链μ调整可行流f，得到的我们将叫做这条增广链的费用。运筹学-图论新可行流f

，也是流量为v(f

)的所有可行流中的最小费用流。依次类推，当f是最大流时，就是所要求的最小费用最大流。

显然，零流f={0}是流量为0的最小费用流。寻求最小费用流，总可以从零流f={0}开始。下面的问题是：如果已知f是流量为v(f)的最小费用流，那么就要去寻找关于f的最小费用增广链。运筹学-图论

对此，重新构造一个赋权有向图M(f)，其顶点是原网络D的顶点，而将D中的每一条弧(vi,vj)变成两个相反方向的弧（vi,vj）和(vj,vi)，并且定义M(f)中弧的权wij为：并且将权为+∞的弧从M(f)

中略去。运筹学-图论

这样，在网络D中寻找关于f的最小费用增广链就等于价于在M(f)中寻求从vs到vt

的最短路。

算法开始，取零流f(0)

={0}.一般地，如果在第K-1步得到最小费用流f

(K-1),则构造图M(f(k-1))。在图M(f(k-1))中，寻求从vs到vt的最短路。如果存在最短路，则f(k-1)就是最小费用最大流。如果存在最短路，则在原网络D中得到相对应（一一对应）的增广链μ0

运筹学-图论在增广链μ上对f(k–1)进行调整，取调整量令：得到一个新的可行流f(k)，在对f(k)重复以上的步骤，直到D中找不到相对应的增广链时为止。运筹学-图论

例求图5.5.1所示网络中的最小费用最大流，弧旁的权是（bij,cij）.(bij,cij)(1,8)(3,10)(2,4)(6,2)(1,7)(4,10)(2,5)v1v2vsv3vt图5.5.1运筹学-图论

解：（1）取初始可行流为零流f(0)={0},构造赋权有向图M(f(0)),求出从vs到vt的最短路(vs,v2,v1,vt),如图5.5.1

a

中双箭头所示。(1)(3)(2)(6)(1)(4)(2)M(f(0))v1vsv2v3vt图5.5.1a运筹学-图论

（2）在原网络D中，与这条最短路相对应的增广链为μ=（vs

,v2

,v1

,vt）。（3）在μ上对f(0)={0}进行调整，取θ=5，得到新可行流f(1)，如图5.5.1b所示。按照以上的算法，依次类推，可以得到f(1)，f(2)，f(3)，f(4)，流量分别为5，7，10，11，并且分别构造相对应的赋权有向图M(f(1)),M(f(2)),M(f(3)),M(f(4))。由于在M(f(4))中已经不存在从vs到vt的最短路，因此，可行流f(4)，v(f(1))=11是最小费用最大流。运筹学-图论(8,5)(10,0)(4,0)(2,0)(7,5)(10,0)(5,5)图5.5.1bf(1),v(f(1))=5v1vsv2v2vt运筹学-图论M(f(1))图5.5.1cv1(2)(-1)v3(1)(3)(6)(1)(4)(-2)(-1)vsv2vt运筹学-图论(2,0)(5,5)(8,5)(4,0)(7,7)(10,2)(10,0)图5.5.1df(2),v(f(2))=7v1vsv2v3vt运筹学-图论M(f(2)

)图5.5.1e(1)(3)(2)(6)(-1)(4)(-2)(-1)(-4)v1vsv3vtv2运筹学-图论(8,8)(10,3)(4,3)(2,0)(7,7)(10,2)(5,5)图5.5.1ff(3),v(f(3))=10v1vsv2v3vt运筹学-图论(-1)(3)(2)(6)(-1)(4)(-2)(-4)M(f(3))图5.5.1g(-2)(-3)v1vsv2v3vt运筹学-图论(8,8)(10,4)(4,4)(2,0)(7,7)(10,3)(5,4)图5.5.1hf(4),v(f(4))=11v1vsv2v3vt运筹学-图论(-1)(3)(-2)(6)(-1)(4)(2)(-4)M(f(4)

)图5.5.1i(-2)(-3)v1vsv2v3vt运筹学-图论ApplicationsofNetworkOptimization网络最优化模型的应用网络在交通、电子和通讯网络遍及我们日常生活的各个方面，网络规划也广泛用于解决不同领域中的各种问题，如生产、分配、项目计划、厂址选择、资源管理和财务策划等等。网络规划为描述系统各组成部分之间的关系提供了非常有效直观和概念上的帮助，广泛应用于科学、社会和经济活动的每个领域中。运筹学-图论Networkrepresentation网络表述这种描述还有其他应用吗？想想看！运筹学-图论TypesofNetworkOptimizationProblem网络最优化问题类型MinimumCostNetworkFlowModel

最小费用流问题

MaximumFlowProblems

最大流问题

ShortestPathProblem

最短路问题

MinimumSpanningTreeProblem

最小支撑树问题

运筹学-图论MinimumCostNetworkFlowModel最小费用流问题最小费用流问题的构成：节点(nodes)（供应点、需求点、转运点）弧（arcs）

目标:通过网络满足需求提供供应， 最小化流的总成本运筹学-图论Assumptions