运筹学图与网络模型

关于运筹学图与网络模型图论

GraphTheory哥尼斯堡七桥问题(KönigsbergBridgeProblem)LeonhardEuler(1707-1783)在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联BACD第2页,共56页，星期六，2024年，5月§1

图与网络的基本概念

1.1图与网络节点(Vertex)物理实体、事物、概念一般用vi

表示边(Edge)节点间的连线，表示有关系一般用eij

表示图(Graph)节点和边的集合，一般用G(V,E)表示点集V={v1,v2,…,vn}边集E={eij}网络(Network)边上具有表示连接强度的权值，如wij又称加权图(Weightedgraph)第3页,共56页，星期六，2024年，5月1.2无向图与有向图边都没有方向的图称为无向图，如图1在无向图中eij=eji，或(vi,vj)=(vj,vi)当边都有方向时，称为有向图，用G(V,A)表示在有向图中，有向边又称为弧，用aij表示，i,j的顺序是不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图第4页,共56页，星期六，2024年，5月

1.3端点，关联边，相邻，次图中可以只有点，而没有边；而有边必有点若节点vi,vj

之间有一条边eij，则称vi,vj

是eij的端点(endvertex)，而eij

是节点vi,vj的关联边(incid%ntedge)同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行边(paralleledges)既没有自环也没有平行边的图称为简单图(simplegraph)在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为d

；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(evengraph)第5页,共56页，星期六，2024年，5月

1.3端点，关联边，相邻，次有向图中，由节点指向外的弧的数目称为正次数，记为d+，指向该节点的弧的数目称为负次数，记为d–次数为0的点称为孤立点(isolatedvertex)

，次数为1的点称为悬挂点(pendantvertex)定理1：图中奇点的个数总是偶数个

1.4链，圈，路径，回路，欧拉回路相邻节点的序列

{v1

,v2

,…,vn

}构成一条链(link)，又称为行走(walk)；首尾相连的链称为圈(loop)，或闭行走在无向图中，节点不重复出现的链称为路径(path)；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径(directedpath)首尾相连的路径称为回路(circuit)；第6页,共56页，星期六，2024年，5月

1.4链，圈，路径，回路，连通图走过图中所有边且每条边仅走一次的闭行走称为欧拉回路定理2：偶图一定存在欧拉回路(一笔画定理)1.4连通图，子图，成分设有两个图G1(V1,E1),G2(V2,E2),若V2

V1,E2

E1，则G2是G1的子图无向图中，若任意两点间至少存在一条路径，则称为连通图(connectedgraph)，否则为非连通图(discon-nectedgraph)；非连通图中的每个连通子图称为成分

(component)链，圈，路径(简称路)，回路都是原图的子图平面图(planargraph)，若在平面上可以画出该图而没有任何边相交第7页,共56页，星期六，2024年，5月§2树图与最小生成树一般研究无向图树图：倒置的树，根(root)在上，树叶(leaf)在下多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图第8页,共56页，星期六，2024年，5月

2.1树的定义及其性质任两点之间有且只有一条路径的图称为树(tree)，记为T

树的性质：最少边的连通子图，树中必不存在回路任何树必存在次数为1的点具有n

个节点的树T的边恰好为

n

1条，反之，任何有n

个节点，n

1条边的连通图必是一棵树

2.2图的生成树树T是连通图G的生成树(spanningtree)，若T是G的子图且包含图G的所有的节点；包含图G中部分指定节点的树称为steinertree第9页,共56页，星期六，2024年，5月

2.3

最小生成树有n个乡村，各村间道路的长度是已知的，如何铺设光缆线路使n个乡村连通且总长度最短显然，这要求在已知边长度的网路图中找最小生成树

第10页,共56页，星期六，2024年，5月2.4求解最小生成树的破圈算法所谓的最小生成树问题就是在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。算法的具体步骤如下：在给定的赋权的连通图上任找一个圈；在所找的圈中去掉一条权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条。如果所余下的图中已不含圈，则计算结束，所余下的图即为最小生成数，否则返回第1步。第11页,共56页，星期六，2024年，5月应用举例：某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能连通的路径如图G所示，图中v1,…,v7表示7个学院办公室，图中的边为可能联网的路径，边上所赋的权数为这条路线的长度，单位为百米。请设计一个网络能连通7个学院办公室，并使总的线路长度最短。v1v2v3v4v6v5v7103343278541G第12页,共56页，星期六，2024年，5月v1v2v3v4v6v5v7103343278541G1

1.

在G中找到一个圈（v1,v7,v6,v1），并知在此圈上边[v1,v6]的权数10为最大，在G中去掉边[v1,v6]得图G1。第13页,共56页，星期六，2024年，5月v1v2v3v4v6v5v7334327541G2

2.

在G1中找到一个圈（v3,v4,v5,v7,v3），并知在此圈上边[v4,v5]的权数8为最大，在G1中去掉边[v4,v5]得图G2。8第14页,共56页，星期六，2024年，5月v1v2v3v4v6v5v733432741G33.

在G2中找到一个圈（v2,v3,v5,v7,v2），并知在此圈上边[v5,v7]的权数5为最大，在G2中去掉边[v5,v7]得图G3。5第15页,共56页，星期六，2024年，5月v1v2v3v4v6v5v733432741G44.

在G3中找到一个圈（v3,v5,v6,v7,v3），并知在此圈上边[v5,v6]和[v3,v7]的权数4为最大，在G3中去掉边[v5,v6]得图G4。第16页,共56页，星期六，2024年，5月v1v2v3v4v6v5v73343271G55.

在G4中找到一个圈（v2,v3,v7,v2），并知在此圈上边[v3,v7]的权数5为最大，在G2中去掉边[v5,v7]得图G3。第17页,共56页，星期六，2024年，5月v1v2v3v4v6v5v7333271G56.在G5中已找不到任何一个圈了，可知G5即为图G的最小生成树。这个最小生成树的所有边的总权数为3+3+3+1+2+7=19。第18页,共56页，星期六，2024年，5月§3最短路问题最短路问题是对一个赋权的有向图G（权数可能是路程的长度、花费的成本等等）中的指定的两个点Vs和Vt找到一条从Vs到Vt的路，使得这条路上所有弧的权数的总和最小，这条路被称为从Vs到Vt的最短路，这条路上所有弧的权数的总和被称之为从Vs到Vt的距离。第19页,共56页，星期六，2024年，5月3.1求解最短路的Dijkstra算法（Dijkstraalgorithm,1959）

Dijkstra算法也称为双标号算法。所谓双标号，也就是对图中的点vj赋予两个标号(lj,kj)，第一个标号lj表示从起点vs到vj的最短路的长度，第二个标号kj表示在vs到vj的最短路上vj前面一个邻点的下标。给起点v1以标号(0,s)表示从v1到v1的距离为0，v1为起点。找出已标号的点的集合I，没标号的点的集合J以及弧的集合{(vi,vj)|vi∈I,vj∈J}，这里这个弧的集合是指所有从已标号的点到未标号的点的弧的集合。如果上述弧的集合是空集，则计算结束。如果vt已标号(lt,kt)，则vs到vt的距离即为lt，而从vs到vt的最短路径，则可以从kt反向追踪到起点vs而得到。如果vt未标号，则可以断言不存在从vs到vt的有向路。否则转下一步。对上述弧的集合中的每一条弧，计算sij=li+cij在所有的sij中，找到其值为最小的弧，不妨设此弧为(vc,vd)，则给此弧的终点以双标号(scd,c),返回第2步。第20页,共56页，星期六，2024年，5月例1.求下图中v1到v6的最短路。v1v4v3v2v5v62531255173第21页,共56页，星期六，2024年，5月给起始点v1标以(0,s)，表示从v1到v1的距离为0。已标号点集I={v1}，未标号点集J={v2,v3,v4,v5,v6}，弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v2),(v1,v3),(v1,v4)}，并有s12=l1+c12=0+3=3,s13=l1+c13=0+2=2,s14=l1+c14=0+5,min(s12,s13,s14)=s13=2.我们给弧(v1,v3)的终点v3标以(2,1).I={v1,v3},J={v2,v4,v5,v6},弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v2),(v1,v4),(v3,v4)}且s34=l3+c34=2+1=3,min(s12,s14,s34)=s12=s34=3.给弧(v1,v2)的终点标以(3,1),弧(v3,v4)的终点标以(3,3).I={v1,v2,v3,v4},J={v5,v6},弧集{(vi,vj)|vi∈I,vj∈J}={(v2,v6),(v4,v6)},并有s26=l2+c26=3+7=10,s46=l4+c46=3+5=8,min(s26,s46)=s46=8.I={v1,v2,v3,v4,v6},J={v5},弧集为∅，计算结束。v5没有标号表明从v1到v5没有有向路。最短路径为v1￫v3￫v4￫v6.第22页,共56页，星期六，2024年，5月例1的各点的标号如下(v1到v5没有有向路）v1v4v3v2v5v62531255173(0,s)(3,3)(8,4)(3,1)(2,1)第23页,共56页，星期六，2024年，5月3.2最短路问题的应用例2.电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给了甲、乙两地间的交通图，图中的点v1,v2,...,v7表示7个地点，其中v1表示甲地，v7表示乙地，点之间的联线（边）表示两地之间的公路，边所赋的权数表示两地间的公路长度。v1甲地v7乙地v3v4v6v2v51510173465642第24页,共56页，星期六，2024年，5月起始点v1标号为(0,s).I={v1},J={v2,v3,v4,v5,v6,v7},边集{[vi,vj]|vi,vj中一个∈I,另一个∈J}={[v1,v2],[v1,v3]}，且s12=l1+c12=0+15=15，s13=l1+c13=0+10=10，min(s12,s13)=s13=10，边[v1,v3]中未标号点v3标以(10,1).I={v1,v3},J={v2,v4,v5,v6,v7},边集{[vi,vj]}={[v1,v2],[v3,v2],[v3,v5]},且s32=l3+c32=10+3=13，s35=l3+c35=10+4=14，min(s12,s32,s35)=s32=13.边[v3,v2]中未标号的点v2标以(13,3).I={v1,v3,v2},J={v4,v5,v6,v7},边集{[vi,vj]}={[v3,v5],[v2,v4],[v2,v7]},且s24=l2+c24=13+6=19,s27=l2+c27=13+17=30,min(s35,s24,s27)=s35=14.边[v3,v5]中未标号的点v5标以(14,3).I={v1,v2,v3,v5},J={v4,v6,v7},边集{[vi,vj]}={[v2,v4],[v5,v4],[v2,v7],[v5,v6]},并有s54=l5+c54=14+4=18,s56=l5+c56=14+2=16,min(s24,s54,s27,s56)=s56=16.边[v5,v6]中未标号的点v6标以(16,5).第25页,共56页，星期六，2024年，5月I={v1,v2,v3,v5,v6},J={v4,v7}.边集{[vi,vj]}={[v2,v4],[v2,v7],[v5,v4],[v6,v7]},且s67=l6+c67=16+6=22,min(s24,s27,s54,s67)=s54=18.边[v5,v4]中未标号的点v4标以(18,5).I={v1,v2,v3,v4,v5,v6},J={v7}.边集{[vi,vj]}={[v2,v7],[v4,v7],[v6,v7]},且s47=l4+c47=18+8=23,min(s27,s47,s67)=s67=22.边[v6,v7]中未标号的点v7标以(22,6).此时I={v1,v2,v3,v4,v5,v6,v7},J=∅.边集合{[vi,vj]}为空集，计算结束。从v1到v7的最短距离为22,其最短路径为v1￫v3￫v5￫v6￫v7.第26页,共56页，星期六，2024年，5月例2的各点标号如下：v1甲地v7乙地v3v4v6v2v51510173465642(0,s)(18,5)(10,1)(16,5)(14,3)(13,3)(22,6)第27页,共56页，星期六，2024年，5月例3.设备更新问题。某公司试用一台设备，在每年年初，公司就要决定是购买新设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。现在需要我们制定一个五年之内的更新设备计划，使得五年内购置费和维修总的支付费用最小。这种设备每年年初的价格以及使用不同时间的设备所需要的维修费如下表所示。年份12345年初价格1111121213使用年数0-11-22-33-44-5每年维修费用5681118第28页,共56页，星期六，2024年，5月将该问题转化成求最短路问题，vi表示“第i年年初购进一台新设备”，对于弧(vi,vj)，它的权数定义为从第i年年初购进设备使用到第j-1年年底所花费的购置费及维修费的总和，计算结果如下：ji1234561—16223041592——162230413———1723314————17235—————186——————第29页,共56页，星期六，2024年，5月v1v2v3v4v5v6161817171623312322304159413022第30页,共56页，星期六，2024年，5月起始点v1标以(0,s).I={v1},J={v2,v3,v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v2),(v1,v3),(v1,v4),(v1,v5),(v1,v6)}并有s12=l1+c12=0+16=16,s13=l1+c13=0+22=22,s14=l1+c14=0+30=30,s15=l1+c15=0+41=41,s16=l1+c16=0+59=59,min(s12,s13,s14,s15,s16)=s12=16.给弧(v1,v2)的终点v2标以(16,1).I={v1,v2},J={v3,v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v3),(v1,v4),(v1,v5),(v1,v6),(v2,v3),(v2,v4),(v2,v5),(v2,v6)}并有s23=l2+c23=16+16=32,s24=l2+c24=16+22=38,s25=l2+c25=16+30=46,s26=l2+c26=16+41=57,min(s13,s14,s15,s16,s23,s24,s25,s26)=s13=22.给弧(v1,v3)的终点v3标以(22,1).第31页,共56页，星期六，2024年，5月I={v1,v2,v3},J={v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v4),(v1,v5),(v1,v6),(v2,v4),(v2,v5),(v2,v6),(v3,v4),(v3,v5),(v3,v6)}并有s34=l3+c34=22+17=39,s35=l3+c35=22+23=45,s36=l3+c36=22+31=53,min(s14,s15,s16,s24,s25,s26,s34,s35,s36)=s14=30.给弧(v1,v4)的终点v4标以(30,1).I={v1,v2,v3,v4},J={v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v5),(v1,v6),(v2,v5),(v2,v6),(v3,v5),(v3,v6),(v4,v5),(v4,v6)}并有s45=l4+c45=30+17=47,s46=l4+c46=30+23=53,min(s15,s16,s25,s26,s35,s36,s45,s46)=s15=41.给弧(v1,v5)的终点v5标以(41,1).I={v1,v2,v3,v4,v5},J={v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v6),(v2,v6),(v3,v6),(v4,v6),(v5,v6)}并有s56=l5+c56=41+18=59,min(s16,s26,s36,s46,s56)=s36=s46=53.给弧(v3,v6)和(v4,v6)的终点v6标以(53,3)和(53,4).第32页,共56页，星期六，2024年，5月v1v2v3v4v5v6161817171623312322304159413022(0,s)(16,1)(30,1)(41,1)(53,4)(53,3)(22,1)第33页,共56页，星期六，2024年，5月§4最大流问题最大流问题：给了一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。第34页,共56页，星期六，2024年，5月4.1最大流的数学模型例：某石油公司拥有一个管道网络，使用这个网络可以把石油从开采地运送到一些销售点。由于管道的直径的变化，他的各段管道(vi,vj)的流量cij也不一样，如下图所示。cij的单位为万加仑/小时。如果使用这个网络系统从开采地v1向销地v7运送石油，问每小时能运送多少加仑石油？v1v6v3v4v5v2v761223236542第35页,共56页，星期六，2024年，5月设弧(vi,vj)上的流量为fij，网络上的总的流量为F，则上述问题的线性规划模型为：目标函数：maxF=f12+f14约束条件：f12=f23+f25f14=f43+f46+f47f23+f43=f35+f36f25+f35=f57f36+f46=f67f57+f67+f47=f12+f14fijcij,(i=1,2,...,6;j=2,...,7)fij0,(i=1,2,...,6;j=2,...,7)第36页,共56页，星期六，2024年，5月4.2最大流问题网络图论的解法对一条弧(vi,vj)的容量用一对数(cij,0)标在弧(vi,vj)上，cij表示从vi到vj容许通过的容量，0表示从vj到vi容许通过的容量。vivjvivjvivjcijvivj0cjicijcijcjicij第37页,共56页，星期六，2024年，5月求最大流的基本算法找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于0。如果不存在这样的路，则已求得最大流。找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的逆流容量pf，返回步骤①。注意：在步骤①中尽量选择包含弧数最少的路。第38页,共56页，星期六，2024年，5月引例的Ford-Fulkerson标号算法：(贝尔曼-福特算法)第一次迭代：选择路为：v1v4v7.弧(v4,v7)的顺流容量为2，决定了pf=2，改进的网络流量如图所示：v1v6v3v4v5v7612232365422000000000042020v2第39页,共56页，星期六，2024年，5月第二次迭代：选择路为：v1v2v5v7.弧(v2,v5)的顺流容量为c25=3，决定了pf=3，改进的网络流量如图所示：v1v6v3v4v5v7612323542200000000420233230350v2第40页,共56页，星期六，2024年，5月第三次迭代：选择路为：v1v4v6v7.弧(v4,v6)的顺流容量为c46=1，决定了pf=1，改进的网络流量如图所示：v1v6v3v4v5v7122342500000420233230363301310v2第41页,共56页，星期六，2024年，5月第四次迭代：选择路为：v1v4v3v6v7.弧(v3,v6)的顺流容量为c36=2，决定了pf=2，改进的网络流量如图所示：v1v6v3v4v5v702234261000033023323038151321020v2第42页,共56页，星期六，2024年，5月第五次迭代：选择路为：v1v2v3v5v7.弧(v2,v3)的顺流容量为c23=2，决定了pf=2，改进的网络流量如图所示：v1v6v3v4v5v7022110812032150233230310105022005v2第43页,共56页，星期六，2024年，5月最大流如图所示：v1v6v3v4v5v72101223252355v2第44页,共56页，星期六，2024年，5月§5最小费用最大流问题最小费用最大流问题：给了一个带收发点的网络，对每一条弧(vi,vj),除了给出了容量cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流F,并使总运送费用最小。第45页,共56页，星期六，2024年，5月5.1最小费用最大流的数学模型例：在上例中，假设不同的单位流量的费用为bij，对每段管道(vi,vj)用(cij,bij)表示流量和费用，如图所示。如果使用这个网络系统从开采地v1向销地v7运送石油，怎样运送才能运送最多的石油并使得总的运送费用最少？求出每小时的最大流量及相应的最小费用。v1v6v3v4v5v2v7(6,6)(6,3)(3,4)(2,3)(2,4)(1,3)(3,2)(2,8)(2,5)(4,4)(5,7)第46页,共56页，星期六，2024年，5月设弧(vi,vj)上的流量为fij，网络上的总的流量为F，则上述问题的线性规划模型为：目标函数：minz=fij

bij=6f12+3f14+4f25+5f23+2f43+4f35+7f57+3f36+3f46+8f47+4f67约束条件：f12+f14=F=10f12=f23+f25f14=f43+f46+f47f23+f43=f35+f36f25+f35=f57f36+f46=f67f57+f67+f47=f12+f14fijcij,(i=1,2,...,6;j=2,...,7)fij0,(i=1,2,...,6;j=2,...,7)第47页,共56页，星期六，2024年，5月5.2最小费用最大流问题网络图论的解法对一条弧(vi,vj)的容量用一对数(cij,0)标在弧(vi,vj)上，cij表示从vi到vj容许通过的容量，0表示从vj到vi容许通过的容量。vivjvivjvivj(cij,bij)(cij,bij)(0,-bij)(0,-bji)(0,-bij)(cji,bji)(cij,bij)vjvi(cji,bji)(cij,bij)第48页,共56页，星期六，2024年，5月求最小费用最大流的基本算法找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于0。如果不存在这样的路，则已求得最大流。找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的逆流容量pf，返回步骤①。注意：在步骤①中选择一条从发点到收点的费用的最短路。第49页,共56页，星期六，2024年，5月第一次迭代：选择最短路为：v1v4v6v7，此路的总单位费用为3+3+4=10，弧(v4,v6)的顺流容量为1，决定了pf=1，改进的网络流量如图所示：v1v6v3v4v5v2v7(6,6)(5,3)(3,4)(2,3)(2,4)(0,3)(3,2)(2,8)(2,5)(3,4)(5,7)第一次迭代后总流量为1，总的费用为10×1=10.(0,-3)(0,-4)(0,-5)(0,-2)(1,-3)(1,-3)(1,-4)(0,-7)(0,-4)(0,-6)(0,-8)1第50页,共56页，星期六，2024年，5月第二次迭代：选择最短路为：v1v4v7，此路的总单位费用为3+8=11，弧(v4,v7)的顺流容量为2，决定了pf=2，改进的网络流量如图所