运筹学图与网络分析课件

第5章图论与网络分析

图的基本概念网络分析最小支撑树问题

最短路径问题网络最大流问题运筹学图与网络分析ABCDACBD图论起源：哥尼斯堡七桥问题问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？结论：每个结点关联的边数均为偶数运筹学图与网络分析§1图的基本概念由点和边组成，记作G=(V，E)，其中V=(v1，v2，……，vn)为结点的集合，E=(e1，e2，……，em)为边的集合。点表示研究对象边表示研究对象之间的特定关系1.图p114运筹学图与网络分析图无向图，记作G=(V，E)有向图，记作D=(V，A)例1：哥尼斯堡桥问题的图为一个无向图。有向图的边称为弧。例2：五个球队的比赛情况，v1v2表示v1胜v2。v1v2v3v4v52、图的分类运筹学图与网络分析v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例图1运筹学图与网络分析v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}图2运筹学图与网络分析v1v2v3v4v53、链与路、圈与回路链点边交错的序列圈起点=终点的链路点弧交错的序列回路起点=终点的路v1v2v3v4v5无向图：有向图：链与路中的点均不相同，则称为初等链

(路)类似可定义初等圈（回路）运筹学图与网络分析4、连通图任何两点之间至少存在一条链的图称为连通图，否则称为不连通图。G1G2G1为不连通图，G2为连通图例：运筹学图与网络分析5、支撑子图图G=(V，E)和G'=(V'，E')，若V=V'且E'E，则称G'为G的支撑子图。G2为G1的支撑子图v1v2v3v4v5G1v1v2v3v4v5G2例：运筹学图与网络分析G2是G1的子图；v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)v1v2v3v4v5v6v7e1e6e7e9e10e11(c)例：运筹学图与网络分析6、赋权图（网络）图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作D=(V，A，C)。55.5v1v2v3v4v53.57.5423例：运筹学图与网络分析§2最小支撑树问题本节主要内容：树支撑树最小支撑树

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531运筹学图与网络分析树：无圈的连通图，记为T。一、树的概念与性质树的性质：（1）树的任2点间有且仅有1链；（2）在树中任去掉1边，则不连通；故树是使图保持连通且具有最少边数的一种图形（3）在树中不相邻2点间添1边，恰成1圈；（4）若树T有m个顶点，则T有m-1条边。(A)(B)(C)运筹学图与网络分析若一个图G=（V,E）的支撑子图T=（V,E´）构成树，则称T为G的支撑树，又称生成树。二、图的支撑树(G)(G1)(G2)(G3)(G4)例运筹学图与网络分析[例]某地新建5处居民点，拟修道路连接5处，经勘测其道路可铺成如图所示。为使5处居民点都有道路相连，问至少要铺几条路？解：该问题实为求图的支撑树问题，共需铺4条路。v1v2v3v4v5

图的支撑树的应用举例v1v2v3v4v555.53.57.5423运筹学图与网络分析用破圈法求出下图的一个生成树。

v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8运筹学图与网络分析最小支撑树：求网络的支撑树，使其权和最小。三、最小支撑树问题算法1（破圈法）：①在给定的赋权的连通图上找一个圈；②在所找的圈中去掉一条权数最大的边(若有两条或两条以上的边都是权数最大的边，则任意去掉其中一条)：③若所余下的图已不含圈，则计算结束，所余下的图即为最小支撑树，否则，返问①。运筹学图与网络分析55.5v1v2v3v4v53.57.5423[例]求上例中的最小支撑树解：55.5v1v2v3v4v53.57.5423运筹学图与网络分析55.5v1v2v3v4v53.57.54233v12v4v545v23.5v3算法2（避圈法）：从某一点开始，把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数）。运筹学图与网络分析最小生成树举例：某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。

v1v2v3v4v5v66515723445v1v4v5v6v2v31234运筹学图与网络分析v1v2v3v4v514231352运筹学图与网络分析

[联系]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531运筹学图与网络分析

[练习]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS222222452634531运筹学图与网络分析

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS22222252634531运筹学图与网络分析

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222222634531运筹学图与网络分析

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。ABCDEFGHIJKS2222222634531运筹学图与网络分析

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。IABCDEFGHJKS222222234531运筹学图与网络分析

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。IJABCDEFGHKS22222223431此即为最经济的煤气管道路线，所需的总费用为25万元运筹学图与网络分析§3最短路径问题最短路问题是在一个网络（赋权有向图）中寻找从起点到某个节点之间一条最短的路线。现欲求出υ1至υ6距离最短的路径。运筹学图与网络分析基本思想：从起点vs开始，逐步给每个结点vj标号[dj,vi]，其中dj为起点vs到vj的最短距离，vi为该最短路线上的前一节点.

若给终点vt标上号[dt,vi],表示已求出v1至vt的最短路其最短路长为dt，最短路径可根据标号vi反向追踪而得最短路问题的Dijstra解法（狄克拉斯）运筹学图与网络分析v2v1v3v4v5v6v7v8v9163222266133101044例题：求网络中v1到v9的最短路运筹学图与网络分析10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1](3)考虑所有这样的边[vi,vj]，其中vi∈VA，vj∈VB，挑选其中与起点v1距离最短（min{di+cij}）的vj，对vj进行标号(4)重复(2)、(3)，直至终点vn标上号[dn,vi]，则dn即为v1→vn的最短距离，反向追踪可求出最短路。(1)给起点v1标号[0,v1](2)把顶点集V分成VA:已标号点集VB：未标号点集运筹学图与网络分析10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1](3)考虑所有这样的边[vi,vj]，其中vi∈VA，vj∈VB，挑选其中与起点v1距离最短（min{di+cij}）的vj，对vj进行标号(4)重复(2)、(3)，直至终点vn标上号[dn,vi]，则dn即为v1→vn的最短距离，反向追踪可求出最短路。(1)给起点v1标号[0,v1](2)把顶点集V分成VA:已标号点集VB：未标号点集[3,v1]运筹学图与网络分析[0,v1][1,v1][3,v1][5,v3]10v2v1v3v4v5v6v7v8v91632222661331044运筹学图与网络分析[0,v1][1,v1][3,v1][5,v3][6,v2]10v2v1v3v4v5v6v7v8v91632222661331044运筹学图与网络分析[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5]10v2v1v3v4v5v6v7v8v91632222661331044运筹学图与网络分析[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5]10v2v1v3v4v5v6v7v8v91632222661331044运筹学图与网络分析[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5][12,v5]此时终点v9已标号[12,v5]，则12即为v1→vn的最短距离，反向追踪可求出最短路10v2v1v3v4v5v6v7v8v91632222661331044运筹学图与网络分析[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5][12,v5]v1到v9的最短路为：v1→v3→v2→v5→v9，最短距离为1210v2v1v3v4v5v6v7v8v91632222661331044p119运筹学图与网络分析

5V5V24541V612455V4V1V8238V7V37练习：用Dijkstra算法求下图中V1至V8的最短路及最短路长。运筹学图与网络分析关键线路：1.V1--V2--V4--V6--V82.V1--V2--V4—V7--V8最短路长：12V3

5V5V24541V612455V4V1V8238V77(0,V1)(1,V1)(2,V1)(6,V2)(5,V2)(9,V4)(7,V4)(12,V6/V7)运筹学图与网络分析[课堂练习]无向图情形求网络中v1至v7的最短路。v1v2v3v4v5v6v7225355715713运筹学图与网络分析[课堂练习]无向图情形v1v2v3v4v5v6v7225355715713[0,v1][2,v1][3,v1][4,v2/v4][7,v3][8,v5][13,v6]运筹学图与网络分析[课堂练习]无向图情形答案（2）：v1v2v3v4v5v6v7225355715713[0,v1][2,v1][3,v1][4,v2/v4][7,v3][8,v5][13,v6]运筹学图与网络分析最短路模型的应用——设备更新问题第i年12345价格ai1111121213使用寿命0~11~22~33~44~5费用bj5681118例某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。

运筹学图与网络分析最短路模型的应用——设备更新问题分析：结点：V={v1，…，v6}，vi表示第i年初；弧：A={(vi，vj)}表示第i年初购买，用至第j年初；i=1,…,5;j=2,…,6权cij：i年初~j年初的费用，即cij=i年初购买费+（j-i）年里的维修费通路：表示一个更新策略。例如v1-v2-v6表示第一年购买用到第二年更新，继续用至第五年末的一个更新策略运筹学图与网络分析最短路模型的应用——设备更新问题v2v1v3v4v5v6第i年12345价格ai1111121213使用寿命0~11~22~33~44~5费用bj5681118[0,v1][16,v1][22,v1][30,v1][41,v1][53,v3/v4]163022415916223041172331172318建模：求解：运筹学图与网络分析v2v1v3v4v5v6[0,v1][16,v1][22,v1][30,v1][41,v1][53,v3/v4]163022415916223041172331172318求得两个最优更新策略：v1-v4-v6，即第一年购买设备，用到第四年更新，再用至第五年年末V1-v3-v6，即第一年购买设备，用到第三年更新，再用至第五年年末最优费用为53运筹学图与网络分析计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。

年份12345购置费1820212324使用年数0~11~22~33~44~5维修费57121825练习：设备更新问题运筹学图与网络分析年份12345购置费1820212324使用年数0~11~22~33~44~5维修费5712182528v1v2v3v4v5v62325262930426085324462334530运筹学图与网络分析算法的基本思路与步骤：首先设任一点vi到任一点vj都有一条弧。无弧相连的点之间假设存在权为+∞的弧相连。从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：

(二)Ford法(逐次逼近法)

（权有负数）运筹学图与网络分析开始时，令即用v1到vj的直接距离做初始解。从第二步起，使用递推公式：求，当进行到第t步，若出现即为v1到各点的最短路长。则停止计算，运筹学图与网络分析例:

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837运筹学图与网络分析从第二步起，使用递推公式

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837运筹学图与网络分析从第二步起，使用递推公式

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837运筹学图与网络分析

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-23

0000v260

2

-1-5-5-5v3

-30-5

1

-2-2-2-2v48

0

2

3-7-7-7v5

-1

0

1-3-3v6

1017

-1-1-1v7

-1

0

5-5-5v8

-3

-50

66运筹学图与网络分析

为了求出从v1到各个点的最短路，一般采用反向追踪的方法：如果已知d(vs,vj),那么寻求一个点vk,使得d(vs,vk)+wkj=d(vs,vj),然后记录下(vk,vj)；在看d(vs,vk),寻求一个点vi,使得d(vs,vi)+wik=d(vs,vk)…依次类推，一直到达为止。这样，从vs到vj的最短路是（vs,…vi,vk,vj）v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-23

0000v260

2

-1-5-5-5v3

-30-5

1

-2-2-2-2v48

0

2

3-7-7-7v5

-1

0

1-3-3v6

1017

-1-1-1v7

-1

0

5-5-5v8

-3

-50

66运筹学图与网络分析v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-23

0000v260

2

-1-5-5-5v3

-30-5

1

-2-2-2-2v48

0

2

3-7-7-7v5

-1

0

1-3-3v6

1017

-1-1-1v7

-1

0

5-5-5v8

-3

-50

66d(v1,v8)=6,由于d(v1,v6)+w68=(-1)+7记录下v6由于d(v1,v3)+w36=d(v1,v6),

记录下v3由于d(v1,v1)+w13=d(v1,v3),于是，从v1到v8的最短路是(v1,v3,v6,v8)。运筹学图与网络分析§4网络最大流问题引例：下图为V1到V6的一交通网，权表示相应运输线的最大通过能力，制定一方案，使从V1到V6的运输产品数量最多。v2v1v3v4v5v681041755311635312213362运筹学图与网络分析已知网络D=（V，A，C），其中V为顶点集，A为弧集，C={cij}为容量集，cij为弧（vi，vj）上的容量。现D上要通过一个流f={fij}，其中fij为弧（vi，vj）上的流量。问题：应如何安排流量fij可使D上通过的总流量v最大？v2v1v3v4v5v681041755311635312213362一、一般提法运筹学图与网络分析二、最大流问题的数学模型maxv=v（f）容量约束平衡约束s.t.v2Vsv3v4v5Vt81041755311635312213362P125满足上述所有约束条件的流成为可行流。运筹学图与网络分析

（1）容量条件：对于每一个弧（vi,vj）∈A，有0≤

fij

≤

cij

。（2）平衡条件：对于发点vs，有对于收点vt

，有对于中间点，有为可行流f的流量(发点的净输出量或收点的净输入量)1、称满足下列条件的流f为可行流：三、基本概念和定理运筹学图与网络分析

可行流特征：（1）容量条件：每一个弧上的流量不能超过该弧的容量。（2）每一个中间点的流入量与流出量的代数和为零。（转运的作用）（3）出发点的总流出量与收点的总流入量必相等。任意一个网络上的可行流总是存在的。例如零流v(f)=0,就是满足以上条件的可行流。

网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量v(f)达到最大值。运筹学图与网络分析可行流中fij＝cij

的弧叫做饱和弧；

fij＜cij的弧叫做非饱和弧；

fij＞0的弧叫做非零流弧；

fij＝0的弧叫做零流弧。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2、饱和弧与零流弧运筹学图与网络分析f为一可行流，u为vs至vt的链，令u+={正向弧}，u-={反向弧}。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。v2v1v3v4v5v6810417553116353122133623、增广链运筹学图与网络分析增广链v2v1v3v4v5v681041755311635312213362显然图中增广链不止一条运筹学图与网络分析增广链v2v1v3v4v5v681041755311635312213362运筹学图与网络分析

容量网络D=（V，A，C），vs为始点，vt为终点。如果把V分成两个非空集合使则所有始点属于V1，而终点属于的弧的集合，称为分离vs和vt的截集。4、截集和截集的截量截集是连接起点和终点的必经之路。

截集中所有弧的容量之和，称为这个截集的截量，记为运筹学图与网络分析vsv1v2v4v3vt374556378V运筹学图与网络分析13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)则截集为设容量为24运筹学图与网络分析13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)设则截集为容量为20运筹学图与网络分析流量与截量的关系：任一可行流的流量都不会超过任一截集的截量v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）最大流最小截定理：任一网络D中，从vs至vt的最大流的流量等于分离vs、vt的最小截集的容量。运筹学图与网络分析例.如图所示的网络中，弧旁数字为(cij,fij)v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）确定所有的截集；（2）求最小截集的容量；（3）证明图中的流为最大流；运筹学图与网络分析v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有的截集：①V1={vs}，截集为{(vs,v1),(vs,v2)}，截量为：6运筹学图与网络分析v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有的截集：①V1={vs}，截集为{(vs,v1),(vs,v2)}，截量为：6②V1={vs,v1}，截集为{(vs,v2),(v1,vt)}，截量为：7运筹学图与网络分析v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有的截集：①V1={vs}，截集为{(vs,v1),(vs,v2)}，截量为：6②V1={vs,v1}，截集为{(vs,v2),(v1,vt)}，截量为：7③V1={vs,v2}，截集为{……}，截量为：7运筹学图与网络分析①V1={vs}，截集为{(vs,v1),(vs,v2)}，截量为：6②V1={vs,v1}，截集为{(vs,v2),(v1,vt)}，截量为：7③V1={vs,v2}，截集为{……}，截量为：7④V1={vs,v3}，截集为{……}，截量为：12v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有的截集：运筹学图与网络分析v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有的截集：①V1={vs}，截集为{(vs,v1),(vs,v2)}，截量为：6②V1={vs,v1}，截集为{(vs,v2),(v1,vt)}，截量为：7③V1={vs,v2}，截集为{……}，截量为：7④V1={vs,v3}，截集为{……}，截量为：12⑤V1={vs,v1,v2}，截集为{……}，截量为：5……运筹学图与网络分析v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（2）最小截量minC(V1,V2)=5；（3）∵v(f*)=5=minC(V1,V2)∴f*是最大流。运筹学图与网络分析最大流判定定理：

可行流f*是最大流的充分必要条件是当且仅当不存在从vs到vt

的关于f*的增广链。

p124运筹学图与网络分析寻求网络最大流问题的主要步骤：

（1）确定初始可行流（观察法和零流法）

（2）检验当前可行流是否是网络中的最大流(对已知可行流用标号法寻找可扩充链，若存在，则当前可行流不是最大流，转(3)；若不存在，则是最大流）

（3）将当前的可行流调整成一个流量更大的新可行流．再由(2)检验四、求最大流方法——标号法思路：从始点开始标号，寻找是否存在增广链。给vj标号为[θj,vi]，其中θj为调整量，vi为前一节点。运筹学图与网络分析标号具体步骤：检查所有已标号点与没标号点的关联弧流出弧和流入弧运筹学图与网络分析（b）标号终止，说明不存在可扩充链，当前即为流为最大流，并得最小截集（a）说明存在可扩充链,反向追踪找出,转(4)运筹学图与网络分析例5用标号法求下面网络的最大流。（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6步骤：(1)给vs标号为[∞,vs]，选与vs关联的流出未饱和弧(vs,vj),给vj标号[θj,vs],其中θj=csj-fsj运筹学图与网络分析例5用标号法求下面网络的最大流。（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6(2)把节点集V分为VA：已标号点集VB：未标号点集运筹学图与网络分析例5用标号法求下面网络的最大流。（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6（3）考虑所有弧(vi,vj)或(vj,

vi),其中vi∈VA,vj∈VB，若该弧为流出未饱弧,则给vj标号[θj,vi],其中θj=min(cij-fij，θi）流入非零弧,则给vj标号[θj,-vi],其中θj=min(fij，θi）运筹学图与网络分析（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6例5用标号法求下面网络的最大流。vt已标号，得到一条增广链u(反向追踪)，转（5）；vt未标号，且无法再标号,此时的流为最大流,此时的截集为最小截。（4）重复（2）,（3），依次进行的结局可能为：运筹学图与网络分析（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6例5用标号法求下面网络的最大流。vt已标号，得到一条增广链u(反向追踪)，转（5）；vt未标号，且无法再标号,此时的流为最大流,此时的截集为最小截。（4）重复（2）,（3），依次进行的结局可能为：运筹学图与网络分析（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6例5用标号法求下面网络的最大流。vt已标号，得到一条增广链u(反向追踪)，转（5）；vt未标号，且无法再标号,此时的流为最大流,此时的截集为最小截。（4）重复（2）,（3），依次进行的结局可能为：运筹学图与网络分析（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6例5用标号法求下面网络的最大流。(5)调整。取=θt，令，得新流{fij'}转(1)。运筹学图与网络分析（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6（2,2）（1,0）（3,3）（1,1）（4,4）（5,2）（3,0）（2,1）（5,4）vsv2v1v3v4v6运筹学图与网络分析（2,2）（1,0）（3,3）（1,1）（4,4）（5,2）（3,0）（2,1）（5,4）vsv2v1v3v4v6此时标号无法进行，当前流为最大流，最大流量为5；最小截为{(vs,v2),(v1,v3)}，截量为：5运筹学图与网络分析练习：有三个发电站v1,v2,v3，发电能力分别为15、10和40兆瓦，经输电网可把电力送到8号地区，电网能力如图所示。求三个发电站输到该地区的最大电力。v2v1v3v4v5v6v7v8401530154510151020运筹学图与网络分析v0101540v2v1v3v4v5v6v7v8401530154510151020（1）由于网络图中只有一个发点和一个收点，所以有必要添加一个虚设的起点和弧弧上各容量为，分别为三点的发电能力，如图所示：运筹学图与网络分析v2v1v3v4v5v6v7v8401530154510151020v010154010101515150101010101525(2)由观察法得一初始可行流即图上所标。

为弧上容量，为弧上流量。运筹学图与网络分析(2)由观察法得一初始可行流即图上所标。

为弧上容量，为弧上流量。v3(40,10)(15,15)(30,10)(15,15)(45,25)(10,10)(15,15)(10,0)(20,10)v0(10,10)(15,15)(40,10)(3)用标号法寻找可扩充链v0||||v6||v5v4||v2v1v7v8反向追踪，得一v0-v8的可扩充链:v0-v3-v6-v5-v2-v7-v8运筹学图与网络分析v3(40,10)(15,15)(30,10)(15,15)(45,25)(10,10)(15,15)(10,0)(20,10)v0(10,10)(15,15)(40,10)v0||||v6||v5v4||v2v1v7v8(4)调整流量。由可扩充链确定一新可行流，可扩充链上前向弧上流量均增加(45,35)(40,20)(10,10)(20,20)(30,20)(40,20)运筹学图与网络分析(5)继续用标号法检验当前可行流是否为最大流v3(40,20)(15,15)(30,20)(15,15)(45,35)(10,10)(15,15)(10,10)(20,20)v0(10,10)(15,15)(40,20)v0||||v6||v5v4v2v1v7v8||标号完毕，且终点未标号。这说明网络中已找不到可扩充链，当前即为最大流，最大流流量为：20+15+10＝45即三个发电站输送到8号地区的最大电力为45兆瓦。运筹学图与网络分析练习：图中A、B、C、D、E、F分别表示陆地和岛屿，①②……⒁表示桥梁及其编号。河两岸分别互为敌对的双方部队占领，问至少应切断几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的。试用图论方法进行分析。ABDEFC①②③④⑤⑥⑦⑧⑨⑩⑾⑿⒀⒁运筹学图与网络分析分析：转化为一个网络图，弧的容量为两点间的桥梁数。则问题为求最小截。ABDEFC①②③④⑤⑥⑦⑧⑨⑩⑾⑿⒀⒁步骤（1）确定初始可行流2112ABCDEF21112122221122运筹学图与网络分析1(1)1(0)分析：转化为一个网络图，弧的容量为两点间的桥梁数。则问题为求最小截。答案：最小截为{AE、CD、CF}ABCDEF2(1)1(1)1(1)1(1)1(0)2(2)2(1)2(1)2(1)2(2)2(2)步骤（1）确定初始可行流（2）标号法求最大流得最小截1(0)1(0)2(0)2(0)2(0)ABDEFC①②③④⑤⑥⑦⑧⑨⑩⑾⑿⒀⒁运筹学图与网络分析ABDEFC①②③④⑤⑥⑦⑧⑨⑩⑾⑿⒀⒁F2ABCDE21111122222211221答案：至少应当切掉3座桥，分别是AE：（12）号桥，CD：(7)号桥，CF：(6)号桥运筹学图与网络分析案例：有一批人从我国A城赴俄罗斯B城，可能的旅行路线如图：边防队拟建立足够数量检查站以便使每辆汽车至少必经过一个检查站，建立检查站的费用根据各路段条件有所不同（如图数字所示），求最小费用解。aBAbcdefg468232573843764（分析：最小截问题）运筹学图与网络分析分析：转化为一个网络图，弧的容量为各路段得费用。则问题为求最小截。步骤aBAbcdefg4682325738437644(4)6(6)8(3)2(2)3(3)2(2)5(5)7(6)3(0)8(4)4(3)3(3)7(3)6(6)4(4)（1）确定初始可行流（2）标号法求最大流得最小截答案：最小截为{Aa、Ab、cb}，即在这三个路段修建检查站，最小费用为13运筹学图与网络分析案例：垃圾处理问题某地区有3个城镇，各城镇每天产生的垃圾要运往该地区的4个垃圾处理场处理，现考虑各城镇到各处理场的道路对各城镇垃圾外运的影响。假设各城镇每日产生的垃圾量、各处理场的日处理能力及各条道路（可供运垃圾部分）的容量（其中容量为0表示无此直接道路）如右表所示，试用网络流方法分析目前的道路状况能否使所有垃圾都运到处理场得到处理，如果不能，应首先拓宽哪条道路。处理场城镇1234垃圾量a302010050b00204070c5040205080处理量60409030运筹学图与网络分析分析：转化为一个网络图，弧的容量为各路段能处理垃圾的数量。abc1234st80504020506040903020703050102040则问题为求最小截。运筹学图与网络分析b80(80)50(30)40(20)20(0)50(30)60(60)40(40)90(20)30(30)20(20)70(20)30(30)50(50)10(0)20(20)40(0)805040205060409020703050102040s（1）确定初始可行流30（2）标号法求最大流得最小截4c321at运筹学图与网络分析b80(80)50(30)40(20)20(0)50(30)60(60)40(40)90(20)30(30)20(20)70(20)30(30)50(50)10(0)20(20)40(0)s（3）反向追踪，找可扩充链4c321at90(40)20(20)50(10)40(20)70(40),得一s-t的可扩充链:s-b-4-c-3-t，调整量运筹学图与网络分析b90(40)50(10)40(20)70(40)80(80)50(30)40(20)20(20)60(60)40(40)30(30)20(20)30(30)50(50)10(0)20(20)（4）重复标号321ats4ca21a3（5）反向追踪，找可扩充链（6）找到可扩充流S-b-4-c-3-t,调整量为10运筹学图与网络分析b80(80)50(40)40(20)20(20)60(60)40(40)30(30)20(20)30(20)50(50)10(10)20(20)321ats4ca21a3（6）找到可扩充流S-b-4-c-3-t,调整量为1090(50)50(0)40(30)70(50)运筹学图与网络分析90(50)20(20)50(0)40(30)70(50)80(80)50(40)40(20)60(60)40(40)30(30)20(20)30(20)50(50)10(10)20(20)（4）重复标号，直至终止321atc321atsb4答案：最小截为{sa、sc、b3、4t},垃圾最大处理量为180<50+70+80运筹学图与网络分析答案综上，目前的道路状况不能使所有垃圾都运到处理场得到处理。从图上不难发现，理论上应当拓宽割集所在的道路。但由于sa,sc和4t都是添加的虚拟道路，所以只有拓宽割集中的b3道路的路宽，或者增大4号处理场处理垃圾的能力，才能解决问题。

运筹学图与网络分析练习：过纽约ALBANY的北-南高速公路，路况通过能力如下图所示，图中弧上数字单位：千辆/小时。求（1）该路网能承受的北-南向最大流量；（2）若要扩充通过能力，应在那一组路段上扩充，说明原因。2143562366241331进入Albany（北）离开Albany（南）运筹学图与网络分析(1)选取一个可行流123546（进入Albany(北)离开Albany(南)2(2)4(1)3(0)1(1)6(5)3(3)2(2)3(3)6(2)1(1)V1—V4—V2—V5—V6，可扩充量为1，调整成新流，继续标号,用标号法得可扩充链运筹学图与网络分析123546（进入Albany(北)离开Albany(南)2(2)4(2)3(1)1(1)6(5)3(3)2(2)3(3)6(3)1(0)标号终止，当前流为最大流，最大流量为8割集为：12,45，46，36应该在割集弧上扩大流量运筹学图与网络分析[练习1][0,v1][4,v1][3,v1][5,v2][6,v2][9,v7][7,v4/v6][8.5,v6][6,v2]v2v1v5v4v3v6v8v7v943232.533523421有9个城市v1、v2、…v9，其公路网如图所示。弧旁数字是该段公路的长度，有一批物资要从v1运到v9，问走哪条路最近？运筹学图与网络分析习题课练习（最小支撑树）已知有A、B、C、D、E、F六个城镇间的道路网络如图，现要在六个城镇间架设通讯网络（均沿道路架设），每段道路上的架设费用如图。求能保证各城镇均能通话且总架设费用最少的架设方案。EACBFD51069353978284[练习2]运筹学图与网络分析第四节最小费用最大流问题

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

设一个网络D=（V，A，C），对于每一个弧(vi,vj)∈A,给定一个单位流量的费用bij

0，网络系统的最小费用最大流问题，是指要寻求一个最大流f，并且流的总费用达到最小。运筹学图与网络分析而此时总费用b(f'

)比b(f)增加了我们将叫做这条增广链的费用。我们首先考察，在一个网络D中，当沿可行流f的一条增广链μ，以调整量θ=1改进f，得到的新可行流f'的流量，有v(f'

)=v(f)+1运筹学图与网络分析显然，零流f={0}是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f={0}开始。问题是：如果已知f是流量为v(f)的最小费用流，如何寻找关于f的最小费用增广链？结论：若f是流量为v(f)的所有可行流中的费用最小，而是关于f的所有增广链中的费用最小的增广链，则f沿增广链μ调整量为1得到的新可行流f'

，一定是流量为v(f'

)+1的所有可行流中的最小费用流。依次类推，当f'是最大流时，就是所要求的最小费用最大流。运筹学图与网络分析若u是从vs到vt关于f的增广链，它的费用若果把u-中的边(vi

,vj)反向，并且令它的权是-bij，而u+中的方向不变，并且的它的权是bij，这样就把求从vs到vt关于f的最小费用增广链就转换成寻求从vs

到vt

的最短路。构造一个赋权有向图M(f)，其顶点是原网络D的顶点，他的边根据f的情况确定：若原图中（vi，vj