天津大学管理运筹学课件第二章图论

第二章图论与网络分析图的基本概念网络分析最小支撑树问题最短路径问题网络最大流问题网络计划问题12/1/2022管理运筹学第二章图论与网络分析图的基本概念网络分析最小支撑1ABCDACBD图论起源——哥尼斯堡七桥问题结论：每个结点关联的边数均为偶数。问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？12/1/2022管理运筹学ABCDACBD图论起源——哥尼斯堡七桥问题结论：每个结点关2§1图的基本概念由点和边组成，记作G=(V，E)，其中V={v1，v2，……，vn}为结点的集合，E={e1，e2，……，em}为边的集合。点表示研究对象边表示表示研究对象之间的特定关系1.图12/1/2022管理运筹学§1图的基本概念由点和边组成，记作G=(V，E)，其中3图无向图，记作G=(V，E)有向图，记作D=(V，A)例1：哥尼斯堡桥问题的图为一个无向图。有向图的边称为弧。例2：五个球队的比赛情况，v1v2表示v1胜v2。v1v2v3v4v52、图的分类12/1/2022管理运筹学图无向图，记作G=(V，E)有向图，记作D=(V，A)例1：4v1v2v3v4v53、链与路、圈与回路链点边交错的序列圈起点=终点的链路点弧交错的序列回路起点=终点的路v1v2v3v4v5无向图：有向图：12/1/2022管理运筹学v1v2v3v4v53、链与路、圈与回路链点边交错的序列圈起54、连通图任何两点之间至少存在一条链的图称为连通图，否则称为不连通图。G1G2G1为不连通图，G2为连通图例：12/1/2022管理运筹学4、连通图任何两点之间至少存在一条链的图称为连通图，否则称为65、支撑子图图G=(V，E)和G'=(V'，E')，若V=V'且E'E，则称G'为G的支撑子图。G2为G1的支撑子图v1v2v3v4v5G1v1v2v3v4v5G2例：12/1/2022管理运筹学5、支撑子图图G=(V，E)和G'=(V'，E')，若76、赋权图（网络）图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作D=(V，A，C)。55.5v1v2v3v4v53.57.5423例：12/1/2022管理运筹学6、赋权图（网络）图的每条边都有一个表示一定实际含义的权数，8§2最小支撑树问题本节主要内容：树支撑树最小支撑树

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

图的支撑树的应用举例v1v2v3v4v555.57.53.542312/1/2022管理运筹学[例]某地新建5处居民点，拟修道路连接5处，经勘测其道路12问题：求网络的支撑树，使其权和最小。三、最小支撑树问题55.5v1v2v3v4v57.53.5423算法1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数）。[例]求上例中的最小支撑树解：3v12v4v545v23.5v312/1/2022管理运筹学问题：求网络的支撑树，使其权和最小。三、最小支撑树问题55.13算法2（破圈法）：

在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。55.5v1v2v3v4v57.53.542312/1/2022管理运筹学算法2（破圈法）：55.5v1v2v3v4v57.53.5414算法2（破圈法）：

在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。55.5v1v2v3v4v53.542312/1/2022管理运筹学算法2（破圈法）：55.5v1v2v3v4v53.5423115算法2（破圈法）：

在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。5v1v2v3v4v53.542312/1/2022管理运筹学算法2（破圈法）：5v1v2v3v4v53.542311/316算法2（破圈法）：

在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。5v1v2v3v4v53.52312/1/2022管理运筹学算法2（破圈法）：5v1v2v3v4v53.52311/3017

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

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

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

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

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

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

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。IJABCDEFGHKS22222223431此即为最经济的煤气管道路线，所需的总费用为25万元12/1/2022管理运筹学[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在24案例分析：默登公司的联网问题默登（Modern）公司的管理层决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信。图1中的节点显示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。每条虚线旁边的数字表示成本（单位：百万美元）。问：需要铺设哪些光缆使得总成本最低？ABCEGFD252745713144图1光缆铺设费用图12/1/2022管理运筹学案例分析：默登公司的联网问题默登（Modern）25案例分析：默登公司的联网问题ABCEGFD225131图1光缆铺设最小费用图12/1/2022管理运筹学案例分析：默登公司的联网问题ABCEGFD225131图126§3最短路问题问题：求网络中起点到其它点之间的一条最短路线。v2v1v3v4v5v6v7v8v9163222266133101044[例]求网络中v1到v9的最短路12/1/2022管理运筹学§3最短路问题问题：求网络中起点到其它点之间的一条最短27算法：Dijkstra（狄克斯拉）标号法基本思想：从起点vs开始，逐步给每个结点vj标号[dj，vi]，其中dj为起点vs到vj的最短距离，vi为该最短路线上的前一节点。12/1/2022管理运筹学算法：Dijkstra（狄克斯拉）标号法基本思想：从起点vs2810v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1](1)给起点v1标号[0,v1](3)考虑所有这样的边[vi,vj]，其中vi∈VA，vj∈VB，挑选其中与起点v1距离最短（min{di+cij}）的vj，对vj进行标号(4)重复(2)、(3)，直至终点vn标上号[dn,vi]，则dn即为v1→vn的最短距离，反向追踪可求出最短路。步骤：(2)把顶点集V分成VA：已标号点集VB：未标号点集12/1/2022管理运筹学10v2v1v3v4v5v6v7v8v9163222266129[0,v1][1,v1][3,v1](1)给起点v1标号[0,v1](3)考虑所有这样的边[vi,vj]，其中vi∈VA，vj∈VB，挑选其中与起点v1距离最短（min{di+cij}）的vj，对vj进行标号(4)重复(2)、(3)，直至终点vn标上号[dn,vi]，则dn即为v1→vn的最短距离，反向追踪可求出最短路。步骤：(2)把顶点集V分成VA：已标号点集VB：未标号点集10v2v1v3v4v5v6v7v8v9163222266133104412/1/2022管理运筹学[0,v1][1,v1][3,v1](1)给起点v130[0,v1][1,v1][3,v1][5,v3]10v2v1v3v4v5v6v7v8v9163222266133104412/1/2022管理运筹学[0,v1][1,v1][3,v1][5,v3]1031[0,v1][1,v1][3,v1][5,v3][6,v2]10v2v1v3v4v5v6v7v8v9163222266133104412/1/2022管理运筹学[0,v1][1,v1][3,v1][5,v3][632[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5]10v2v1v3v4v5v6v7v8v9163222266133104412/1/2022管理运筹学[0,v1][1,v1][3,v1][5,v3][633[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5]10v2v1v3v4v5v6v7v8v9163222266133104412/1/2022管理运筹学[0,v1][1,v1][3,v1][5,v3][634[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5][12,v5]此时终点v9已标号[12,v5]，则12即为v1→vn的最短距离，反向追踪可求出最短路10v2v1v3v4v5v6v7v8v9163222266133104412/1/2022管理运筹学[0,v1][1,v1][3,v1][5,v3][635[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5][12,v5]v1到v9的最短路为：v1→v3→v2→v5→v9，最短距离为1210v2v1v3v4v5v6v7v8v9163222266133104412/1/2022管理运筹学[0,v1][1,v1][3,v1][5,v3][636[课堂练习]P129习题5.3[0,v1][4,v1][3,v1][5,v2][6,v2][9,v7][7,v4/v6][8.5,v6][6,v2]v2v1v5v4v3v6v8v7v943232.53352342112/1/2022管理运筹学[课堂练习]P129习题5.3[0,v1][437[课堂练习]无向图情形求网络中v1至v7的最短路。v1v2v3v4v5v6v722535571571312/1/2022管理运筹学[课堂练习]无向图情形求网络中v1至v7的最短路。v1v238[课堂练习]无向图情形答案（1）：v1v2v3v4v5v6v7225355715713[0,v1][2,v1][3,v1][4,v2/v4][7,v3][8,v5][13,v6]12/1/2022管理运筹学[课堂练习]无向图情形答案（1）：v1v2v3v4v5v639[课堂练习]无向图情形答案（2）：v1v2v3v4v5v6v7225355715713[0,v1][2,v1][3,v1][4,v2/v4][7,v3][8,v5][13,v6]12/1/2022管理运筹学[课堂练习]无向图情形答案（2）：v1v2v3v4v5v640最短路模型的应用——设备更新问题（P119例5.3）v2v1v3v4v5v6第i年12345价格ai1111121213使用寿命0~11~22~33~44~5费用bj5681118[0,v1][16,v1][22,v1][30,v1][41,v1][53,v3/v4]16分析：结点：V={v1，…，v6}，vi表示第i年初；边：E={(vi，vj)}表示第i年初购买，用至第j年初；i=1,…,5;j=2,…,6权cij：i年初~j年初的费用，即cij=i年初购买费+（j-i）年里的维修费302241591622304117233117231812/1/2022管理运筹学最短路模型的应用——设备更新问题（P119例5.3）v241§4网络最大流问题引例：下图为V1到V6的一交通网，权表示相应运输线的最大通过能力，制定一方案，使从V1到V6的产品数量最多。v2v1v3v4v5v68104175531163531221336212/1/2022管理运筹学§4网络最大流问题引例：下图为V1到V6的一交通网，权42设有网络D=(V,A,C)，其中C={cij}，cij为弧(vi,vj)上的容量，现在D上要通过一个流f={fij}，fij为弧(vi,vj)上的流量。

问题：如何安排fij，可使网络D上的总流量V最大？v2v1v3v4v5v681041755311635312213362一、一般提法：12/1/2022管理运筹学设有网络D=(V,A,C)，其中C={cij}，cij43二、最大流问题的模型maxv=v（f）容量约束平衡约束s.t.v2Vsv3v4v5Vt81041755311635312213362注：满足约束条件的流f称为可行流12/1/2022管理运筹学二、最大流问题的模型maxv=v（f）44三、基本概念与定理1.弧按流量分为饱和弧fij=cij非饱和弧fij<cij零流弧fij=0非零流弧fij≠0v2v1v3v4v5v68104175531163531221336212/1/2022管理运筹学三、基本概念与定理1.弧按流量分为饱和弧fij=c452.增广链f为一可行流，u为vs至vt的链，令u+={正向弧}，u-={反向弧}。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。v2v1v3v4v5v68104175531163531221336212/1/2022管理运筹学2.增广链f为一可行流，u为vs至462.增广链f为一可行流，u为vs至vt的链，令u+={正向弧}，u-={反向弧}。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。v2v1v3v4v5v68104175531163531221336212/1/2022管理运筹学2.增广链f为一可行流，u为vs至472.增广链f为一可行流，u为vs至vt的链，令u+={正向弧}，u-={反向弧}。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。v2v1v3v4v5v68104175531163531221336212/1/2022管理运筹学2.增广链f为一可行流，u为vs至482.增广链f为一可行流，u为vs至vt的链，令u+={正向弧}，u-={反向弧}。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。v2v1v3v4v5v68104175531163531221336212/1/2022管理运筹学2.增广链f为一可行流，u为vs至493.截集与截量把V分成两部分：V1和V2(V1∩V2=φ,V1∪V2=V)且vs∈V1、vt∈V2，则弧集(V1,V2)称为D的截集。截集上的容量和称为截量，记为C(V1,V2)。{(vs,v2),(v1,vt)}；截量为：C(V1,V2)=4+3=7截集为：例若V1={vs,v1}，则v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）12/1/2022管理运筹学3.截集与截量把V分成两部分：V1和V2(V1504.流量与截量的关系任一可行流的流量都不会超过任一截集的截量（∵v(f)=f(V1,V2)-f(V2,V1)≤f(V1,V2)≤C(V1,V2)）最大流最小截定理：网络的最大流量等于最小截量。v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）12/1/2022管理运筹学4.流量与截量的关系任一可行流的流量都不会超过任一截集的51例.如图所示的网络中，弧旁数字为(cij,fij)v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）确定所有的截集；（2）求最小截集的容量；（3）证明图中的流为最大流；12/1/2022管理运筹学例.如图所示的网络中，弧旁数字为(cij,fij)v152v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有的截集：①V1={vs}，截集为{(vs,v1),(vs,v2)}，截量为：612/1/2022管理运筹学v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）53v1vsv2v3vt（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)}，截量为：712/1/2022管理运筹学v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）54v1vsv2v3vt（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}，截集为{……}，截量为：712/1/2022管理运筹学v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）55v1vsv2v3vt（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}，截集为{……}，截量为：1212/1/2022管理运筹学v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）56v1vsv2v3vt（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}，截集为{……}，截量为：512/1/2022管理运筹学v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）57v1vsv2v3vt（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……12/1/2022管理运筹学v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）58v1vsv2v3vt（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*是最大流。12/1/2022管理运筹学v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）59四、求最大流方法——标号法理论依据：不存在关于f的增广链可行流f是最大流思路：从始点开始标号，寻找是否存在增广链。给vj标号为[θj,vi]，其中θj为调整量，vi为前一节点。12/1/2022管理运筹学四、求最大流方法——标号法理论依据：不存在关于f的增广链可行60步骤：(1)给vs标号为[∞,vs]，流出未饱和弧(vs,vj),给vj标号[θj,vs],其中θj=csj-fsj例.图中网络弧旁数字为(cij,fij)，用标号法求最大流。[∞,vs][4,vs]选与vs关联的v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）（3,0）12/1/2022管理运筹学步骤：(1)给vs标号为[∞,vs]，流出未饱和弧(vs61(2)把节点集V分为VA：已标号点集VB：未标号点集v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）[∞,vs][4,vs]（3,0）12/1/2022管理运筹学(2)把节点集V分为VA：已标号点集VB：未标号点集v2Vs62考虑所有VA→VB的弧，若该弧为流出未饱弧,则给vj标号[θj,vi],其中θj=cij-fij流入非零弧,则给vj标号[θj,-vi],其中θj=fij(3)[1,-v1]v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）[∞,vs][4,vs]（3,0）12/1/2022管理运筹学考虑所有VA→VB的弧，若该弧为流出未饱弧,则给vj标号[63(4)v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）[∞,vs][4,vs][1,-v1]重复（2）,（3），依次进行的结局可能为vt已标号，得到一条增广链u(反向追踪)，转（5）；vt未标号，且无法再标号,此时的流为最大流,此时的截集为最小截。（3,0）12/1/2022管理运筹学(4)v2Vsv1v4v3Vt（3,3）（5,1）（1,1）64v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）[∞,vs][4,vs][1,-v1](4)重复（2）,（3），依次进行的结局可能为vt已标号，得到一条增广链u(反向追踪)，转（5）；vt未标号，且无法再标号,此时的流为最大流,此时的截集为最小截。[1,v2]（3,0）12/1/2022管理运筹学v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,65(4)重复（2）,（3），依次进行的结局可能为vt已标号，得到一条增广链u(反向追踪)，转（5）；vt未标号，且无法再标号,此时的流为最大流,此时的截集为最小截。v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）[∞,vs][4,vs][1,-v1][1,v2]（3,0）[2,v4]12/1/2022管理运筹学(4)重复（2）,（3），依次进行的结局可能为vt已标号，得66(4)重复（2）,（3），依次进行的结局可能为vt已标号，得到一条增广链u(反向追踪)，转（5）；vt未标号，且无法再标号,此时的流为最大流,此时的截集为最小截。v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）[∞,vs][4,vs][1,-v1][1,v2]（3,0）[2,v4]12/1/2022管理运筹学(4)重复（2）,（3），依次进行的结局可能为vt已标号，得67v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）[∞,vs][4,vs][1,-v1][1,v2]（3,0）[1,-v2][2,v4](5)调整。取，令，得新流,转(1)。12/1/2022管理运筹学v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,68v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）[∞,vs][4,vs][1,-v1][1,-v2]（3,0）[1,-v2][2,v4]v2Vsv1v4v3Vt（3,3）（5,2）（1,0）（2,2）（1,1）（5,4）（2,1）（4,4）（3,0）调整12/1/2022管理运筹学v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,69v2Vsv1v4v3Vt（3,3）（5,2）（1,0）（2,2）（1,1）（5,4）（2,1）（4,4）（3,0）[∞,vs][3,vs]12/1/2022管理运筹学v2Vsv1v4v3Vt（3,3）（5,2）（1,0）（2,70v2Vsv1v4v3Vt（3,3）（5,2）（1,0）（2,2）（1,1）（5,4）（2,1）（4,4）（3,0）[∞,vs][3,vs]此时标号无法进行，当前流为最大流，最大流量为5；最小截为{(vs,v2),(v1,v3)}，截量为：512/1/2022管理运筹学v2Vsv1v4v3Vt（3,3）（5,2）（1,0）（2,71例有三个发电站v1,v2,v3，发电能力分别为15、10和40兆瓦，经输电网可把电力送到8号地区，电网能力如图所示。求三个发电站输到该地区的最大电力。v2v1v3v4v5v6v7v8401530154510151020v010154010201515151020102020153512/1/2022管理运筹学例有三个发电站v1,v2,v3，发电能力分别为15、1072例、图中A、B、C、D、E、F分别表示陆地和岛屿，①②……⒁表示桥梁及其编号。河两岸分别互为敌对的双方部队占领，问至少应切断几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的。试用图论方法进行分析。ABDEFC①②③④⑤⑥⑦⑧⑨⑩⑾⑿⒀⒁12/1/2022管理运筹学例、图中A、B、C、D、E、F分别表示陆地和岛屿，①②……⒁73分析：转化为一个网络图，弧的容量为两点间的桥梁数。则问题为求最小截。ABDEFC①②③④⑤⑥⑦⑧⑨⑩⑾⑿⒀⒁ABCDEF21111122222212/1/2022管理运筹学分析：转化为一个网络图，弧的容量为两点间的桥梁数。则问题为求74分析：转化为一个网络图，弧的容量为两点间的桥梁数。则问题为求最小截。答案：最小截为{AE、CD、CF}ABDEFC①②③④⑤⑥⑦⑧⑨⑩⑾⑿⒀⒁ABCDEF21111122222212/1/2022管理运筹学分析：转化为一个网络图，弧的容量为两点间的桥梁数。则问题为求75例、有一批人从我国A城赴俄罗斯B城，可能的旅行路线如图：边防队拟建立足够数量检查站以便使每辆汽车至少必经过一个检查站，建立检查站的费用根据各路段条件有所不同（如图数字所示），求最小费用解。aBAbcdefg468232573843764（分析：最小截问题）12/1/2022管理运筹学例、有一批人从我国A城赴俄罗斯B城，可能的旅行路线如图：76例、过纽约ALBANY的北-南高速公路，路况通过能力如下图所示，图中弧上数字单位：千辆/小时。求（1）该路网能承受的北-南向最大流量；（2）若要扩充通过能力，应在那一组路段上扩充，说明原因。2143562366241331进入Albany（北）离开Albany（南）12/1/2022管理运筹学例、过纽约ALBANY的北-南高速公路，路况通过能力如下图所77案例：垃圾处理问题某地区有3个城镇，各城镇每天产生的垃圾要运往该地区的4个垃圾处理场处理，现考虑各城镇到各处理场的道路对各城镇垃圾外运的影响。假设各城镇每日产生的垃圾量、各处理场的日处理能力及各条道路（可供运垃圾部分）的容量（其中容量为0表示无此直接道路）如右表所示，试用网络流方法分析目前的道路状况能否使所有垃圾都运到处理场得到处理，如果不能，应首先拓宽哪条道路。处理场城镇1234垃圾量130201005020020407035040205080处理量6040903012/1/2022管理运筹学案例：垃圾处理问题处理场1234垃圾量1302010050278§5工程网络计划引例：沏茶1324烧水（10）备茶（3）沏茶（2）洗碗（2）12/1/2022管理运筹学§5工程网络计划引例：沏茶1324烧水（10）备茶（379一、问题描述一项工程，已知各工序完成时间t及其先后关系求：工程完工期及关键工序关键工序：主矛盾工序，不能延期完工路线：从始点到终点的一条路关键路线：由关键工序组成的路线，是所有路线中时间最长的路线。相关概念：1324烧水（10）备茶（3）沏茶（2）洗碗（2）12/1/2022管理运筹学一、问题描述一项工程，已知各工序完成时间t及其先后关系关键80二、求解方法——关键路径法（CPM）分为三步：绘制工程网络图标号法求工期T标号法求关键路线12/1/2022管理运筹学二、求解方法——关键路径法（CPM）分为三步：11/30/81将整个工程分解为若干工序确定各工序的前后顺序（紧前、紧后）确定工序完成时间三点估计法：最乐观时间a、最可能时间m、最悲观时间btij=6a+4m+b一点估计法准备工作12/1/2022管理运筹学将整个工程分解为若干工序三点估计法：最乐观时间a、最可能821、绘制工程网络图（1）顺序：按工序的先后从左至右（2）图的结构弧：表示工序，、为工序的起点、终点结点：相邻工序的时间分界点，称为事项权：工序的完成时间相邻弧：工序的前后衔接关系，称为紧前或紧后工序（3）绘图要求图中不能出现缺口、回路和多重边多重边的处理：12ab12a3bb'虚工序1324烧水（10）备茶（3）沏茶（2）洗碗（2）12/1/2022管理运筹学1、绘制工程网络图（1）顺序：按工序的先后从左至右（2）图的83例某工厂进行技术改造，需要拆掉旧厂房、建造新厂房和安排设备。这项改建工程可以分解为7道工序，其相关资料如下表：工序代号工序名称紧前工序工序时间（周）A拆迁/2B工程设计/3C土建工程设计B2.5D采购设备B6E厂房土建C、A20F设备安装D、E4G设备调试F212/1/2022管理运筹学例某工厂进行技术改造，需要拆掉旧厂房、建造新厂房和安排8412345A（2）B(3)C(2.5)D(6)E(20)F(4)6G(2)工序代号工序名称紧前工序工序时间（周）A拆迁/2B工程设计/3C土建工程设计B2.5D采购设备B6E厂房土建C、A20F设备安装D、E4G设备调试F2解：12/1/2022管理运筹学12345A（2）B(3)C(2.5)D(6)E(285工序代号紧前工序工序时间（周）A/2B/3C/2DA3EA4工序代号紧前工序工序时间（周）FB7GB6HD、E4IB、C10JG、I3例：绘制工程网络图续左表解：1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)12/1/2022管理运筹学工序代号紧前工序工序时间（周）A/2B/3C/2DA3EA486②四个工序A、B、X、Y有如下关系：A是X的紧前工序，A和B同时又是Y的紧前工序123456ABXYA'虚工序两种情况需要引入虚工序：12AB12A3B虚工序①两个工序A、B有相同的始点和终点B'12/1/2022管理运筹学123456ABXYA'虚工序两种情况需要引入虚工序：187[课堂练习]P150习题6.1160234756891011121314abcdefghijklmnopq142030211071225510601015257f'b'12/1/2022管理运筹学[课堂练习]P150习题6.11602347568910882、用标号法求工期T步骤：（1）标出各事项的最早时间（2）终点即为工期的标号T1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)0233tE(j)Ⅱ、给任意事项标，tE(j)=max{以”}为箭头的各箭之“箭尾+箭长t

(i,j)661316Ⅰ、给始点①标012/1/2022管理运筹学2、用标号法求工期T步骤：（1）标出各事项的最早时间（2）893、用标号法求关键路线步骤：1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)0233661316（1）标出各事项的最晚时间TⅠ、给终点标1612813330tL(i)

=min{以”}为箭尾的各箭之“箭头－箭长Ⅱ、给任意事项标，

12tL(i)t

(i,j)12/1/2022管理运筹学3、用标号法求关键路线步骤：1A(2)D(3)C(2)901A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)0233661316T161212813330注：关键工序头尾皆有=（反之未必成立）R

(i,j)

=的－的－（2）计算各工序的时差R

(i,j)

：则关键工序为R

(i,j)=0的工序。t

(i,j)12/1/2022管理运筹学1A(2)D(3)C(2)2E(4)3F(7)B'91其他时间参数：（1）工序(i,j)最早开始时间1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)02336613161612813330（2）工序(i,j)最晚开始时间12/1/2022管理运筹学其他时间参数：（1）工序(i,j)最早开始时间1A92其他时间参数：（3）工序(i,j)最早结束时间1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)02336613161612813330（4）工序(i,j)最晚结束时间12/1/2022管理运筹学其他时间参数：（3）工序(i,j)最早结束时间1A93其他时间参数：（5）工序(i,j)的自由时差1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)0233661316161281333012/1/2022管理运筹学其他时间参数：（5）工序(i,j)的自由时差1A(94[课堂练习]P150习题6.1160234756891011121314abcdefghijklmnopq142030211071225510601015257b'f'15212/1/2022管理运筹学[课堂练习]P150习题6.11602347568910195三、工程工期的概率分析——计划评审技术（PERT）

PERT与CPM的主要区别：

CPM工序时间是确定的；PERT工序时间tij是随机变量，而完工期T也是随机的，由概率知识：T服从正态分布TTE12/1/2022管理运筹学三、工程工期的概率分析——计划评审技术（PERT）PER96确定平均工序时间的三点估计法：总工期其中：（I为关键路线）TTE标准化12/1/2022管理运筹学确定平均工序时间的三点估计法：总工期其中：（I为关键路971.给定时间T*，求工期T≤T*内完工的概率PERT的内容方法：首先计算，然后查表求。12/1/2022管理运筹学1.给定时间T*，求工期T≤T*内完工的概率PERT的98912.837.838.17410.3312.1711ABCDEFGH2135764例、已知某工程网络图，以及各工序的时间参数。工序ambA101315B5810C7810D7911E246F81014G101215H91113TE=42.330.44/1.00//0.25/0.691112.1710.33498.177.8312.83tij求工程在40天内完工的概率。关键路线I为:A→C→F→H；解：12/1/2022管理运筹学912.837.838.17410.3312.1711ABC992.给定概率p，求完工可能性为p的工期方法：首先查表求，使；再由解出例、上例中，求完工可能性达95%的工期。解：由，查表再由解出12/1/2022管理运筹学2.给定概率p，求完工可能性为p的工期方法：首先查表求，使100四、网络图的调整与优化1.缩短工程工期问题压缩关键工序在非关键工序上挖掘潜力尽量采用平行工序和交叉工序注意关键路线的变化12/1/2022管理运筹学四、网络图的调整与优化1.缩短工程工期问题压缩关键工1012.工程的时间费用分析（1）费用构成：直接费用：原材料、工时费等间接费用：管理费、办公费AB完工时间间接费用间接费用率一般固定，与工序无关。ABCD完工时间直接费用T*:最低成本工期总费用间接费用直接费用12/1/2022管理运筹学2.工程的时间费用分析（1）费用构成：直接费用：原材料、工102工程的时间费用分析求最低成本工期T*求规定工期下的最小成本方案12/1/2022管理运筹学工程的时间费用分析求最低成本工期T*求规定工期下的最小成本方103T*:最低成本工期总费用间接费用直接费用（2）求最低成本工期T*方法：求出正常工期和关键工序（用CPM方法）比较直接费用率（q）、间接费用率（p）：（注:当有多条关键路线时，应以各路线上最小的q之和与p比较。）若关键路线上最小的q>p，则正常工期即为T*；否则，在关键工序上压缩。先压缩q最小的，直至不能再压为止，再压次小的，以此类推。直至q>p为止。（注：当压缩引起出现新的关键路线时，若压要同时压。）压缩时间t的确定：若t取值β，则产生了新的关键路线12/1/2022管理运筹学T*:最低成本工期总费用间接费用直接费用（2）求最低成本工期104例：设某工程有关资料如表，间接费用率p=5；求最低费用工期。工序紧前工序工序时间直接费用率可压天数A/3//BA731CA443DC562解：画出网络图，T=12，关键路线：A-C-D。1234A(3)B(7)C(4)D(5)先压C，在C上可压缩可节省费用：2天，（5-4)×2=2此时出现两条关键路线，∴T*=101234A(3)B(7)C(2)D(5)直接费用之和3+4>5，故不能再压。此时需B、C同时压，但其12/1/2022管理运筹学例：设某工程有关资料如表，间接费用率p=5；求最低费用工期105（3）求规定工期下的最小成本方案方法：求出正常工期和关键工序在关键工序上压，先压缩其中直接费用率最低的，当出现多于一条的关键路线时要同时压，直至满足规定为止。（间接费用率是确定的，与工序无关，只需考虑直接费用）12/1/2022管理运筹学（3）求规定工期下的最小成本方案方法：求出正常工期和关键工106例、某建筑公司安装水管的工程有关资料：工作紧前工作正常情况应急情况时间（天）费用（元）时间（天）费用（元）a/11.7240//ba3.2752110ca25.24500157200da18.048017600ed9.05408710fb,c7.7168051800ge,f16.84000145700hg7.2160051775ie,f12.85009129812/1/2022管理运筹学例、某建筑公司安装水管的工程有关资料：工作紧前工作正常情况应107按正常情况画出施工网络图，求完工期并找出关键工序。现提出这项工程要60天完成，求使总应急费用最小的方案。14276835a(11.7)b(3.2)c

(25.2)d(18.0)e(9.0)f(7.7)g(16.8)h(7.2)i(12.8)b'(0)解：（1）网络图如下：标号法求得：正常工期T=68.6天，关键工序：a---c---f---g---h12/1/2022管理运筹学按正常情况画出施工网络图，求完工期并找出关键工序。14276108（2）计算各工序的直接费用率：工序abcdefghi可压时间/1.210.2112.72.82.23.8直接费用率/29.17264.7112017044.4607.1479.55367.8914276835a(11.7)b(3.2)c

(25.2)d(18.0)e(9.0)f(7.7)g(16.8)h(7.2)i(12.8)b'(0)需压缩8.6天：f压缩2.7天（不会出现新关键路线）h压缩2.2天（不会出现新关键路线）还需压缩3.7天C先压缩3.2天，出现新的关键路线。c、d同时压缩0.5天。（∵c、d总费用率384.71<g的费用率607.14。）还需压缩0.5天12/1/2022管理运筹学（2）计算各工序的直接费用率：工序abcdefghi可压时间10912/1/2022管理运筹学11/30/2022管理运筹学110第二章图论与网络分析图的基本概念网络分析最小支撑树问题最短路径问题网络最大流问题网络计划问题12/1/2022管理运筹学第二章图论与网络分析图的基本概念网络分析最小支撑111ABCDACBD图论起源——哥尼斯堡七桥问题结论：每个结点关联的边数均为偶数。问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？12/1/2022管理运筹学ABCDACBD图论起源——哥尼斯堡七桥问题结论：每个结点关112§1图的基本概念由点和边组成，记作G=(V，E)，其中V={v1，v2，……，vn}为结点的集合，E={e1，e2，……，em}为边的集合。点表示研究对象边表示表示研究对象之间的特定关系1.图12/1/2022管理运筹学§1图的基本概念由点和边组成，记作G=(V，E)，其中113图无向图，记作G=(V，E)有向图，记作D=(V，A)例1：哥尼斯堡桥问题的图为一个无向图。有向图的边称为弧。例2：五个球队的比赛情况，v1v2表示v1胜v2。v1v2v3v4v52、图的分类12/1/2022管理运筹学图无向图，记作G=(V，E)有向图，记作D=(V，A)例1：114v1v2v3v4v53、链与路、圈与回路链点边交错的序列圈起点=终点的链路点弧交错的序列回路起点=终点的路v1v2v3v4v5无向图：有向图：12/1/2022管理运筹学v1v2v3v4v53、链与路、圈与回路链点边交错的序列圈起1154、连通图任何两点之间至少存在一条链的图称为连通图，否则称为不连通图。G1G2G1为不连通图，G2为连通图例：12/1/2022管理运筹学4、连通图任何两点之间至少存在一条链的图称为连通图，否则称为1165、支撑子图图G=(V，E)和G'=(V'，E')，若V=V'且E'E，则称G'为G的支撑子图。G2为G1的支撑子图v1v2v3v4v5G1v1v2v3v4v5G2例：12/1/2022管理运筹学5、支撑子图图G=(V，E)和G'=(V'，E')，若1176、赋权图（网络）图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作D=(V，A，C)。55.5v1v2v3v4v53.57.5423例：12/1/2022管理运筹学6、赋权图（网络）图的每条边都有一个表示一定实际含义的权数，118§2最小支撑树问题本节主要内容：树支撑树最小支撑树

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

图的支撑树的应用举例v1v2v3v4v555.57.53.542312/1/2022管理运筹学[例]某地新建5处居民点，拟修道路连接5处，经勘测其道路122问题：求网络的支撑树，使其权和最小。三、最小支撑树问题55.5v1v2v3v4v57.53.5423算法1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数）。[例]求上例中的最小支撑树解：3v12v4v545v23.5v312/1/2022管理运筹学问题：求网络的支撑树，使其权和最小。三、最小支撑树问题55.123算法2（破圈法）：

在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。55.5v1v2v3v4v57.53.542312/1/2022管理运筹学算法2（破圈法）：55.5v1v2v3v4v57.53.54124算法2（破圈法）：

在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。55.5v1v2v3v4v53.542312/1/2022管理运筹学算法2（破圈法）：55.5v1v2v3v4v53.54231125算法2（破圈法）：

在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。5v1v2v3v4v53.542312/1/2022管理运筹学算法2（破圈法）：5v1v2v3v4v53.542311/3126算法2（破圈法）：

在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。5v1v2v3v4v53.52312/1/2022管理运筹学算法2（破圈法）：5v1v2v3v4v53.52311/30127

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

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