韩伯棠管理运筹学(第三版)-第十一章-图与网络模型

第十一章

图与网络模型运筹学1第八章图与网络模型图与网最短路问络的根本概念最小生成树问题最大流问题最小费用流问题2哥尼斯堡七桥问题哥尼斯堡〔现名加里宁格勒〕是欧洲一个城市，Pregei河把该城分成两局部，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有方法从某处〔如A〕出发，经过各桥一次且仅一次最后回到原地呢？§1图与网络的根本概念3ABCD?只经过各桥一次最后能回到原地吗？4ABCD?只经过各桥一次最后能回到原地吗？5最后，数学家Euler〔欧拉〕在1736年巧妙地给出了这个问题的答案，并因此奠定了图论的根底，Euler把A、B、C、D四块陆地分别收缩成四个顶点，把桥表示成连接对应顶点之间的边，问题转化为从任意一点出发，能不能经过各边一次且仅一次，最后返回该点。这就是著名的Euler问题。§1图与网络的根本概念6ACBD一笔画问题Euler问题7图：由假设干点以及点间联线构成〔P229，230〕点：表示某一具体事物。点间联线：表示事物之间某种特殊的关系。边：不带箭头的点间联线。弧(有向边)：带箭头的点间联线。无向图——由点，边构成〔P229〕有向图——由点，弧构成。〔P230〕网络〔赋权图〕——图中每一条边〔弧〕[vi,vj],有一常数wij与之对应,。wij称为边[vi,vj]上的权.〔常表示距离，费用，时间，容量等〕〔P231〕§1图与网络的根本概念8图G〔V，E〕：V是顶点集合,V={vi|i=1,…,n}，E是边的集合,E={ej|j=1,…,m}对于边e3=[v1,v4]，v1,v4是e3的端点，e3是v1,v4的关联边。e1e2e31214106104131112396581052v5v7v8v1v2v4v3v9v10v6e1e2e31214106104131112396581052v5v7v8v1v2v4v3v9v10v6§1图与网络的根本概念9设G1=[V1,E1],G2=[V2,E2]子图：如果V2V1,E2E1称G2是G1的子图；真子图：如果V2V1,E2E1称G2是G1的真子图;生成图：如果V2=V1,E2E1称G2是G1的生成图〔局部图〕。§1图与网络的根本概念10链：由两两相邻的点及其相关联的边构成的点边序列；如：

v1,e1,v2,e4,v5,e7,v3,e9,v7,e18,v9；

v1,v9分别为链的起点和终点.§1图与网络的根本概念e3v5v7v8v1v2v4v3v9v10v6e1e2e4e5e6e7e8e9e10e11e12e13e14e15e16e17e18e19e2011有向图：关联边有方向的图。弧：有向图的边a=(u,v)，起点u，终点v；路：假设有从u到w的链，且各方向一致，那么称之为从u到w的路；

回路：起点与终点相同的路.uvwxy§1图与网络的根本概念12§2最短路问题〔P207〕最短路问题：寻找网络中从点v1到点vn的路L，使该路上所有弧〔或边〕的权之和最小。要求〔1〕最短距离〔2〕最短路线13求最短路的狄克斯拉算法和福特算法：1、狄克斯拉〔Dijkstra〕算法：适用于解决所有权数大于等于0的最短路问题，能求出起点v1到所有其它点vj的最短距离。2、福特〔Ford〕算法：适用于有负权系数的最短路问题，能求出起点v1到所有其它点vj的最短距离。〔略〕§2最短路问题14

Dijkstra算法求解的过程实际上是一种给点标号的过程。标号〔数，是给点记的一个数〕临时标号〔T标号〕——从发点到本节点的最短距离的上界；固定标号〔P标号〕——从发点到本节点的最短距离。发点P标号，其余点T标号

某点T标号改为P标号

终点为P标号

§2最短路问题15

例1：如图是一个单向道路系统。大批物资集中在出发地S，要求用车尽快运输到目的地T。A,B,C,D,E是中间站。图中数字为相邻两站间的路程。SABCDET252741434571§2最短路问题16SABCDET252741434571v5v2v3v4v1v6v70∞∞∞∞∞∞Step1：令始点P(v1)=0,其它点T(vj)=∞Step2:计算：T(vj)=min{T(vj),P(vi)+wij}§2最短路问题17SABCDET252741434571v5v2v3v4v1v6v70∞∞∞∞∞∞Step1：令始点P(v1)=0,其它点T(vj)=∞Step2:计算：T(vj)=min{T(vj),P(vi)+wij}Step3:令：P(vj)=min{T(vj)}，返回Step2§2最短路问题25418SABCDET252741434571v5v2v3v4v1v6v702∞∞∞∞Step1：令始点P(v1)=0,其它点T(vj)=∞Step2:计算：T(vj)=min{T(vj),P(vi)+wij}Step3:令：P(vj)=min{T(vj)}，返回Step2§2最短路问题5419SABCDET252741434571v5v2v3v4v1v6v702∞∞∞∞Step1：令始点P(v1)=0,其它点T(vj)=∞Step2:计算：T(vj)=min{T(vj),P(vi)+wij}Step3:令：P(vj)=min{T(vj)}，返回Step2§2最短路问题44920SABCDET252741434571v5v2v3v4v1v6v702∞9∞∞Step1：令始点P(v1)=0,其它点T(vj)=∞Step2:计算：T(vj)=min{T(vj),P(vi)+wij}Step3:令：P(vj)=min{T(vj)}，返回Step2§2最短路问题447821SABCDET252741434571v5v2v3v4v1v6v702∞9∞∞Step1：令始点P(v1)=0,其它点T(vj)=∞Step2:计算：T(vj)=min{T(vj),P(vi)+wij}Step3:令：P(vj)=min{T(vj)}，返回Step2§2最短路问题447822SABCDET252741434571v5v2v3v4v1v6v702∞9∞∞Step1：令始点P(v1)=0,其它点T(vj)=∞Step2:计算：T(vj)=min{T(vj),P(vi)+wij}Step3:令：P(vj)=min{T(vj)}，返回Step2§2最短路问题44781423SABCDET252741434571v5v2v3v4v1v6v702∞9∞14Step1：令始点P(v1)=0,其它点T(vj)=∞Step2:计算：T(vj)=min{T(vj),P(vi)+wij}Step3:令：P(vj)=min{T(vj)}，返回Step2§2最短路问题44781324SABCDET252741434571v5v2v3v4v1v6v702∞9∞14Step1：令始点P(v1)=0,其它点T(vj)=∞Step2:计算：T(vj)=min{T(vj),P(vi)+wij}Step3:令：P(vj)=min{T(vj)}，返回Step2§2最短路问题44781325SABCDET252741434571v5v2v3v4v1v6v702∞9∞14§2最短路问题447813由此而得两条从v1到v7的最短路R7*:{v1,v2,v3,v6,v7}与{v1,v2,v3,v5,v6,v7}26用Dijkstra算法不仅能求出从发点到终点的最短距离，而且可求出从发点到网络中任一点的最短距离。

管理运筹学软件能解决最短路问题

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

V1（甲地）15176244431065v2V7（乙地）v3v4v5v6§2最短路问题28解：这是一个求无向图的最短路的问题。可以把无向图的每一边〔vi,vj〕都用方向相反的两条弧〔vi,vj〕和〔vj,vi〕代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。

V1（甲地）15176244431065v2V7（乙地）v3v4v5v6§2最短路问题291517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕T=∞T=∞T=∞T=∞T=∞T=∞§2最短路问题301517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕T=10T=∞T=∞T=∞T=∞T=∞§2最短路问题311517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕T=10T=15T=∞T=∞T=∞T=∞§2最短路问题321517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10T=15T=∞T=∞T=∞T=∞§2最短路问题331517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10T=13T=∞T=∞T=∞T=∞§2最短路问题341517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10T=13T=∞T=14T=∞T=∞§2最短路问题351517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10P=13T=∞T=14T=∞T=∞§2最短路问题361517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10P=13T=19T=14T=∞T=∞§2最短路问题371517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10P=13T=19T=14T=∞T=30§2最短路问题381517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10P=13T=19P=14T=∞T=30§2最短路问题391517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10P=13T=18P=14T=∞T=30§2最短路问题401517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10P=13T=18P=14T=16T=30§2最短路问题411517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10P=13T=18P=14P=16T=30§2最短路问题421517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10P=13T=18P=14P=16T=22§2最短路问题431517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10P=13T=18P=14P=16T=22§2最短路问题441517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10P=13P=18P=14P=16T=22§2最短路问题451517624431065v2V7〔乙地〕V5V6

V3

V4P=0V1〔甲地〕P=10P=13P=18P=14P=16P=22例2最终解得：最短路径v1v3v5v6v7，每点的标号见图.§2最短路问题46练习：求如下图之G的从v1到v8的最短路R8*及路长L8*.

v1

v2

v3

v4

v5

v6

v7

v8

4281

6

7122934962§2最短路问题47得一条最短路R8*：{v1,v3,v5,v2,v6,v8}路长为L8*=11v1

v2

v3

v4

v5

v6

v7

v8

428167122934962§2最短路问题48最短路问题的应用例3设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购置新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的方案，使得五年内购置费用和维修费用总的支付费用最小。：设备每年年初的价格表设备维修费如下表年份12345年初价格1111121213使用年数0-11-22-33-44-5每年维修费用5681118§2最短路问题49解：要用最短路问题求解，得先针对条件作出相应的网络：点、弧、权。如以下图：用vi表示“第i年年初购进一台新设备〞,弧〔vi,vj〕表示第i年年初购进的设备一直使用到第j年年初。v1v2v3v4v5v6§2最短路问题50把所有弧的权数计算如右表：把权数赋到图中，再用Dijkstra算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723§2最短路问题51最终得到以下图，可知，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)§2最短路问题52树：无圈连通图。记为T＝T〔V，E〕.生成树：假设一个图G的生成图T是树，那么称T为生成树.§3最小生成树问题53树的性质243512435124351如果树的顶点个数为m，那么边的个数为m-1。树中任意两个顶点之间只有唯一的一条链。在树的任意两个不相邻的顶点之间增加一条边，那么形成唯一的圈。图中任意两个顶点之间有且仅有一条链，那么该图是一棵树。任何一个顶点个数为m，边数为m-1的连通图是一棵树。§3最小生成树问题54依据树的特点〔即无圈和连通〕，构造生成树的方法〔破圈法〕。1、破圈法①在图中寻找一个圈。假设不存在圈，那么已经得到生成树或该图不存在生成树；②去掉该圈中一边；反复重复①②两步，直到求出生成树。构成生成树方法§3最小生成树问题55依据树的特点〔即无圈和连通〕，构造生成树的方法〔破圈法〕。1、破圈法①在图中寻找一个圈。假设不存在圈，那么已经得到生成树或该图不存在生成树；②去掉该圈中一边；反复重复①②两步，直到求出生成树。构成生成树方法§3最小生成树问题56依据树的特点〔即无圈和连通〕，构造生成树的方法〔破圈法〕。1、破圈法①在图中寻找一个圈。假设不存在圈，那么已经得到生成树或该图不存在生成树；②去掉该圈中一边；反复重复①②两步，直到求出生成树。构成生成树方法§3最小生成树问题57依据树的特点〔即无圈和连通〕，构造生成树的方法〔破圈法〕。1、破圈法①在图中寻找一个圈。假设不存在圈，那么已经得到生成树或该图不存在生成树；②去掉该圈中一边；反复重复①②两步，直到求出生成树。构成生成树方法§3最小生成树问题58构成生成树方法依据树的特点〔即无圈和连通〕，构造生成树的方法〔破圈法〕。1、破圈法①在图中寻找一个圈。假设不存在圈，那么已经得到生成树或该图不存在生成树；②去掉该圈中一边；反复重复①②两步，直到求出生成树。§3最小生成树问题59依据树的特点〔即无圈和连通〕，构造生成树的方法〔破圈法〕。1、破圈法①在图中寻找一个圈。假设不存在圈，那么已经得到生成树或该图不存在生成树；②去掉该圈中一边；反复重复①②两步，直到求出生成树。构成生成树方法§3最小生成树问题60依据树的特点〔即无圈和连通〕，构造生成树的方法〔破圈法〕。1、破圈法①在图中寻找一个圈。假设不存在圈，那么已经得到生成树或该图不存在生成树；②去掉该圈中一边；反复重复①②两步，直到求出生成树。构成生成树方法§3最小生成树问题61构成生成树方法依据树的特点〔即无圈和连通〕，构造生成树的方法〔破圈法〕。1、破圈法①在图中寻找一个圈。假设不存在圈，那么已经得到生成树或该图不存在生成树；②去掉该圈中一边；反复重复①②两步，直到求出生成树。§3最小生成树问题62最小生成树：网络中边的权之和最小的生成树。求最小生成树的破圈法破圈法计算步骤：①在网络图中寻找一个圈。假设不存在圈，那么已经得到最小生成树，或网络中不存在生成树；②去掉该圈中权数最大的边；反复重复①②两步，直到求出最小生成树。SABCDET252741434571§3最小生成树问题63最小生成树：网络中边的权之和最小的生成树。求最小生成树的破圈法破圈法计算步骤：①在网络图中寻找一个圈。假设不存在圈，那么已经得到最小生成树，或网络中不存在生成树；②去掉该圈中权数最大的边；反复重复①②两步，直到求出最小生成树。SABCDET252741434571§3最小生成树问题64最小生成树：网络中边的权之和最小的生成树。求最小生成树的破圈法破圈法计算步骤：①在网络图中寻找一个圈。假设不存在圈，那么已经得到最小生成树，或网络中不存在生成树；②去掉该圈中权数最大的边；反复重复①②两步，直到求出最小生成树。SABCDET252741434571§3最小生成树问题65最小生成树：网络中边的权之和最小的生成树。求最小生成树的破圈法破圈法计算步骤：①在网络图中寻找一个圈。假设不存在圈，那么已经得到最小生成树，或网络中不存在生成树；②去掉该圈中权数最大的边；反复重复①②两步，直到求出最小生成树。SABCDET252741434571§3最小生成树问题66最小生成树：网络中边的权之和最小的生成树。求最小生成树的破圈法破圈法计算步骤：①在网络图中寻找一个圈。假设不存在圈，那么已经得到最小生成树，或网络中不存在生成树；②去掉该圈中权数最大的边；反复重复①②两步，直到求出最小生成树。SABCDET252741434571§3最小生成树问题67最小生成树：网络中边的权之和最小的生成树。求最小生成树的破圈法破圈法计算步骤：①在网络图中寻找一个圈。假设不存在圈，那么已经得到最小生成树，或网络中不存在生成树；②去掉该圈中权数最大的边；反复重复①②两步，直到求出最小生成树。SABCDET252741434571§3最小生成树问题68最小生成树：网络中边的权之和最小的生成树。求最小生成树的破圈法破圈法计算步骤：①在网络图中寻找一个圈。假设不存在圈，那么已经得到最小生成树，或网络中不存在生成树；②去掉该圈中权数最大的边；反复重复①②两步，直到求出最小生成树。SABCDET252741434571最小生成树=14§3最小生成树问题69例5、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如以下图，图中v1,…,v7表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。解：此问题实际上是求上图中的最小生成树，可求得此网络的总的线路长度为最短，为19百米。“管理运筹学软件〞有专门的子程序可以解决最小生成树问题。v1331728541034v7v6v5v4v2v370用破圈算法求前图中最小生成树的计算步骤：v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)71作业：用破圈法求以下网络中的最小生成树。

v1

v2

v3

v4

v5

v6

v7

v8

4281

6

7122934962§3最小生成树问题72§4最大流问题最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。例6某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一局部如以下图所示。由于管道的直径的变化，它的各段管道〔vi,vj〕的流量cij〔容量〕也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运送多少加仑石油？73v563522241263v1v2v7v4v3v6§4最大流问题74

我们可以为此例题建立线性规划数学模型：设弧(vi,vj)上流量为fij，网络上的总的流量为F，那么有：§4最大流问题75§4最大流问题一、网络流的根本概念弧的容量

cij：即弧的权可行流满足以下条件的流称为可行流：1、容量限制0≤fij≤cij2、每一个节点流量平衡。流与网络流量：将一定的物资数量从发点经网络中的弧送至收点就形成一个流f;输送的物资数量称为网络流量记作v(f)。

弧的流量

fij：通过弧输送的物资数量76每一个节点流量平衡是指：中间点流出量=流入量,即流出量-流入量=0发点

流出量-流入量=v(f)

收点

流出量-流入量=-v(f)