第5章 图论与网络规划模型ppt课件.ppt

第5章 图论与网络规划模型,图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中许多方面都能提供有力的数学模型来解决实际问题。,比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。,第5章 图论与网络规划模型,5.1 图的基本概念,5.2 最短路问题与最大流问题,5.3 最优连线问题与旅行商问题,5.1.1 图的定义,5.1 图的基本概念,图G是一个偶对（V,E），其中V(G)=v1,v2, ,vn为图的 顶点集（vertex set），E(G)=e1,e2,en 为图的边集（edge set）或弧集（常用A表示）, 记ek=(vi,vj)(k=1,2 , ,m)。 若ek是无序对，则称G为无向图（undirected graph）；若ek=(vi,vj)是有序对，则称G为有向图（directed graph），vi为的起点，vj为的终点，称去掉有向图的方向得到的图为基础图（underlying graph）。,5.1.1 图的定义,一个图称为有限图，如果它的顶点集和边集都有限。图G的顶点数用符号|V|表示，边数用|E|表示。 端点重合为一点的边称为环(loop)。连接两个相同顶点的边的条数称为边的重数，重数大于1的边称为重边(multi-edges)。在有向图中，两个顶点相同但方向相反的边称为对称边(symmetric edge)。一个图称为简单图(simple graph)，如果它既没有环也没有重边。,5.1.2 完全图、二分图、子图,每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n个顶点的完全图记为Kn；完全图的定向图称为竞赛图。,若V(G)=XY，XY=空集，|X|Y|0,X中无相邻顶点对，Y中亦然，则称G为二分图(bipartite graph)；特别地，若对任意的xX, yY ，都有xy E(G)，则称G为完全二分图，记成K|X|,|Y|。,G的支撑子图是指满足V(H)=V(G)的子图。,若H是G的子图，则G称为H的母图。,5.1.3 顶点的度,设vV(G)，G中与v关联的边数（每个环算作两条边）称为v的度(degree)，记作d(v)。若d(v)是奇数，称v是奇度顶点(odd point)；若d(v)是偶数，称v是偶度顶点(even point)。,对有向图，以v为起点的有向边数称为v的出度(out-degree)，记作d+ (v)；以为终点的有向边数称为的入度(in-degree)，记作d(v)；顶点的度d(v)= d+ (v)+d(v) 。,5.1.4 迹、路、圈与连通,无向图G的一条途径(walk)是指一个有限的非空序列W=v0e1v1e2e kvk ，其中eiE(G)，1ik，v j V(G)，0 j k，e i 与v i-1 v i 关联，称k为W的长(length)。若途经的边互不相同，则称W为迹(trail)；若途径的顶点互不相同，则称W为路(path)；如果v0=v k ，并且没有其他相同的 顶点，则称W为圈(cycle)。,若图G的两个顶点u,v间存在道路，则称u和v连通(connected)。u,v间的最短轨的长叫做u,v间的距离。记作d(u,v)。若图G的任二顶点均连通，则称G是连通图。,5.1.5 图与网络的数据结构,为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的5种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。,首先假设G=(V,A)是一个简单有向图，|V|=n,|A|=m，并假设V中的顶点用自然数1,2,n表示或编号，A中的弧用自然数1,2,m表示或编号。,5.1.5 图与网络的数据结构-邻接矩阵表示法,邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。图G=(V,A)的邻接矩阵是如下定义的：C是一个nn的矩阵，即,5.1.5 图与网络的数据结构-邻接矩阵表示法,对于下图所示的有向图，可以用邻接矩阵表示为,对于网络中的权，也可以用类似邻接矩阵的矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。无向图的邻接矩阵为对称阵。,邻接矩阵举例,n支球队循环赛，每场比赛 只计胜负，没有平局.,根据比赛结果排出各队名次.,方法1. 寻找按箭头方向通过全部顶点的路径.,312456,146325,方法2. 计算得分：,2, 3队 , 4, 5队无法排名!,6支球队比赛结果,32，4 5,1队胜4场，,2, 3队各胜3场，,4, 5队各胜2场，,6队胜1场.,循环比赛的结果竞赛图,3个顶点的竞赛图,名次,1，2，3,(1,2,3)并列,1, 2, 3, 4,2,(1,3,4),(1,3,4), 2,4个顶点的竞赛图,名次,(1,2),(3,4),1, 2, 3, 4?,竞赛图每对顶点间都有边相连的有向图,竞赛图的3种形式,具有唯一的完全路径，如(1)；,双向连通图任一对顶点存在两条 有向路径相互连通，如(4)；,其他，如(2)， (3) .,竞赛图的性质,必存在完全路径；,若存在唯一的完全路径，则由它确定的顶 点顺序与按得分排列的顺序一致，如(1) .,4个顶点的竞赛图,双向连通竞赛图G=(V,E)的名次排序,邻接矩阵,得分向量,双向连通竞赛图的名次排序,对于n(3)个顶点的双向连通竞赛图，存在 正整数r，使邻接矩阵A 满足Ar 0，A称素阵.,排名为1，2，4，3,1, 2, 3, 4?,6支球队比赛结果,排名次序为1，3， 2，5，4，6,32, 4 5,排名 132456?,1:4分; 2,3:3分; 4,5:2分; 6:1分.,5.2.1 最短路问题,5.2 最短路问题与最大流问题,背景：给定连接若干城市的铁路网，寻求从指定城市到各城去的最短道路。,数学模型：图为一赋权图，对任给的，寻求路，使得,其中是路上各边权之和。这一问题可用Dijkstra算法解决 。,例1 在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一个城市的最短路。下图表示的是公路网, 节点表示货车可以停靠的城市，弧上的权表示两个城市之间的距离(百公里)。那么,货车从城市S出发到达城市T，如何选择行驶路线，使所经过的路程最短?,分析,假设从S到T的最优行驶路线 P 经过城市C1, 则P中从S到C1的子路也一定是从S到C1的最优行驶路线; 假设 P 经过城市C2, 则P中从S到C2的子路也一定是从S到C2的最优行驶路线. 因此, 为得到从S到T的最优行驶路线, 只需先求出从S到 Ck (k=1,2)的最优行驶路线, 就可方便地得到从S到T的最优行驶路线。 同样,为了求出从S到Ck(k=1,2)的最优行驶路线, 只需要先求出从S到Bj(j=1,2)的最优行驶路线; 为了求出从S到Bj(j=1,2)的最优行驶路线, 只需要先求出从S到Ai (i=1,2,3)的最优行驶路线. 而S到Ai(i=1,2,3)的最优行驶路线是很容易得到的(实际上, 此例中S到Ai(i=1,2,3)只有唯一的道路) 。,分析,此例中可把从S到T的行驶过程分成4个阶段,即 SAi (i=1,2或3), Ai Bj(j=1或2), Bj Ck(k=1或2), Ck T. 记d(Y,X)为城市Y与城市X之间的直接距离(若这两个城市之间没有道路直接相连，则可以认为直接距离为)，用L(X)表示城市S到城市X的最优行驶路线的路长:,本例的计算,所以, 从S到T的最优行驶路线的路长为20. 进一步分析以上求解过程, 可以得到从S到T的最优行驶路线为S A3 B2 C1 T.,这种计算方法在数学上称为动态规划(Dynamic Programming),本例的LINGO求解,“CITIES”(城市):一个基本集合(元素通过枚举给出),L:CITIES对应的属性变量(我们要求的最短路长),“ROADS”(道路):由CITIES导出的一个派生集合(请特别注意其用法),由于只有一部分城市之间有道路相连，所以不应该把它定义成稠密集合，将其元素通过枚举给出，这就是一个稀疏集合。,D:稀疏集合ROADS对应的属性变量(给定的距离),本例的LINGO求解,从模型中还可以看出：这个LINGO程序可以没有目标函数，这在LINGO中，可以用来找可行解(解方程组和不等式组)。,在数据段对L进行赋值，只有L(S)=0已知，后面的值为空(但位置必须留出来，即逗号“，”一个也不能少，否则会出错)。如果这个语句直接写成“L=0；”，语法上看也是对的，但其含义是L所有元素的取值全部为0，所以也会与题意不符。,本例的LINGO求解,虽然集合CITIES中的元素不是数字，但当它以CITIES(I)的形式出现在循环中时，引用下标I却实际上仍是正整数，也就是说I指的正是元素在集合中的位置(顺序)，一般称为元素的索引(INDEX)。,在for循环中的过滤条件里用了一个函数“index”, 其作用是返回一个元素在集合中的索引值，这里index(S)=1(即元素S在集合中的索引值为1)，所以逻辑关系式“I#GT#index(S)”可以可以直接等价地写成“I#GT#1” 。这里index(S)实际上还是index(CITIES,S)的简写，即返回S在集合CITIES中的索引值。,本例的LINGO求解结果,从S到T的最优行驶路线的路长为20(进一步分析，可以得到最优行驶路线为S A3 B2 C1 T)。,本例中定义稀疏集合ROADS的方法是将其元素通过枚举给出，有时如果元素比较多，用起来不方便。另一种定义稀疏集合的方法是“元素过滤”法，能够从笛卡儿积中系统地过滤下来一些真正的元素。,个顶点的赋权图的赋权矩阵是一个阶 矩阵,其分量为,最短路问题的直接解法,假设图有n个顶点，现需要求从顶点1到顶点 的最短路.设决策变量为 , 当 , 说明弧 位于顶点1至顶点 的路上；否则不在. 其数学规划表达式为,最短路问题的直接解法,之前我们接触到了最短路问题的求解，当时的求解方法是按照Dijkstra算法设计的，下面介绍的方法是按照规划问题(3)-(5)设计的.,求例1中，从城市S到城市T的最短路.,解：写出相应的LINGO程序,MODEL: 1! We have a network of 9 cities. We want to find 2 the length of the shortest route from city 1 to city 9; 3,最短路问题的直接解法,4sets: 5 ! Here is our primitive set of nine cities; 6 cities/S, A1,A2,A3,B1, B2, C1, C2, T/; 7 8 ! The Derived set roads lists the roads that 9 exist between the cities; 10 roads(cities, cities)/ 11 S,A1 S,A2 S,A3 A1,B1 A1,B2 A2,B1 A2,B2 A3,B1 12 A3,B2 B1,C1 B1,C2 B2,C1 B2,C2 C1,T C2,T/: w, x; 13endsets 14 15data: 16 ! Here are the distances that correspond,17 to above links; 18 w = 6 3 3 6 5 8 6 7 4 6 7 8 9 5 6; 19enddata 20 21n=size(cities); ! The number of cities; 22min=sum(roads: w*x); 23for(cities(i) | i #ne# 1 #and# i #ne# n: 24 sum(roads(i,j): x(i,j) = sum(roads(j,i): x(j,i); 25sum(roads(i,j)|i #eq# 1 : x(i,j)=1; END,在上述程序中， 21句中的n=size(cities)是计算集cities的个数，这里的计算结果是n=9, 这样编写方法目的在于提高程序的通用性. 22句表示目标函数(3), 即求道路的最小权值. 23, 24句表示约束(4) 中 的情况，即最短路中中间点的约束条件. 25句表示约束中 的情况，即最短路中起点的约束.,约束(4)中 的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前个方程相关.当然，如果你将此方程列入到LINGO程序中，计算时也不会出现任何问题，因为LINGO,软件可以自动删除描述线性规划可行解中的多余方程.,LINGO软件计算结果（仅保留非零变量）如下,Global optimal solution found. Objective value: 20.00000 Variable Value Reduced Cost X( S, A3) 1.000000 0.000000 X( A3, B2) 1.000000 0.000000 X( B2, C1) 1.000000 0.000000 X( C1, T) 1.000000 0.000000,即最短路是 , 最短路长为20个单位.,例2 现需要将城市s的石油通过管道运送到城市t，中间有4个中转站 和 , 城市与中转站的连接以及管道的容量如图所示，求从城市s到城市t的最大流.,5.2.2 最大流问题,图中给出的有一个源和一个汇的网络. 网络 中每一条边 有一个容量 , 除此之外,每 对边 还有一个通过边的流(Flow), 记为 . 显然, 边 上的流量 不会超过该边上的容量 , 即,称满足不等式（6）的网络 是相容的. 对于所有中间顶点, 流入的总量应等于流出的总量 , 即:,一个网络 的流量(Value of flow)值定义为从源 流出的总流量, 即,由式(18)和(19)式可以看出, 的流量值也为流入汇 的总流量,即:,称满足式(10)的网络 为守恒的.,定义 如果流 满足不等式(6)和式 (10), 则称流 是可行的. 如果存在可行流 , 使得对所有的可行流 均有,则称 为最大流(Maximum Flow).,通过上述推导得到最大流的数学规划表达式,MODEL: 1sets: 2 nodes/s,1,2,3,4,t/; 3 arcs(nodes, nodes)/ 4 s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, f; 5endsets 6data: 7 c = 8 7 5 9 9 2 5 6 10; 8enddata 9max = flow; 10for(nodes(i) | i #ne# 1 #and# i #ne# size(nodes): 11sum(arcs(i,j):f(i,j) - sum(arcs(j,i):f(j,i)=0); 12sum(arcs(i,j)|i #eq# 1 : f(i,j) = flow; 13for(arcs: bnd(0, f, c);,程序的第10到 12行表示约束(12), 第13行表示有界约束(13).,相应的LINGO程序,LINGO软件的计算结果（只保留流值 ）如下:,Global optimal solution found at iteration: 6 Objective value: 14.00000 Variable Value Reduced Cost FLOW 14.00000 0.000000 F( S, 1) 7.000000 0.000000 F( S, 2) 7.000000 0.000000 F( 1, 2) 2.000000 0.000000 F( 1, 3) 5.000000 0.000000 F( 2, 4) 9.000000 -1.000000 F( 3, 2) 0.000000 0.000000 F( 3, T) 5.000000 -1.000000 F( 4, 3) 0.000000 1.000000 F( 4, T) 9.000000 0.000000,因此，该网络的最大流为14，F的值对应弧上的流，如图所示, 其中网络中的第一个数为容量，第二个数为流量.,在上面的程序中，采用稀疏集的编写方法，下面介绍的程序编写方法是利用邻接矩阵，这样可以不使用稀疏集的编写方法，更便于推广到复杂网络.,MODEL: 1sets: 2 nodes/s,1,2,3,4,t/; 3 arcs(nodes, nodes): p, c, f; 4endsets 5data: 6 p = 0 1 1 0 0 0 7 0 0 1 1 0 0 8 0 0 0 0 1 0 9 0 0 1 0 0 1 10 0 0 0 1 0 1 11 0 0 0 0 0 0;,12 c = 0 8 7 0 0 0 13 0 0 5 9 0 0 14 0 0 0 0 9 0 15 0 0 2 0 0 5 16 0 0 0 6 0 10 17 0 0 0 0 0 0; 18enddata 19max = flow; 20for(nodes(i) | i #ne# 1 #and# i #ne# size(nodes): 21 sum(nodes(j): p(i,j)*f(i,j) 22 = sum(nodes(j): p(j,i)*f(j,i); 23sum(nodes(i):p(1,i)*f(1,i) = flow; 24for(arcs:bnd(0, f, c); END,在上述程序中，由于使用了邻接矩阵，当两点之间无弧时，定义弧容量为零.计算结果与前面程序的结果完全相同，这里就不再列出了.,（续例2）由于输油管道的长短不一，或地质等原因，使每条管道上运输费用也不相同，因此，除考虑输油管道的最大流外，还需要考虑输油管道输送最大流的最小费用，图中所示是带有运费的网络，其中第1个数字是网络的容量，第2个数字是网络的单位运费.,5.2.3 最小费用最大流问题,本例所提出的问题就是最小费用最大流问题(Minimum-cost maximum flow)，即考虑网络在最大流情况下的最小费用.例2虽然给出了最大流一组方案，但它是不是关于费用的最优方案呢？这还需要进一步讨论.,1. 最小费用流的数学表达式,min,s.t.,其中,当 为网络的最大流进，数学规划 表示的就是最小费用最大流问题.,MODEL: 1sets: 2 nodes/s,1,2,3,4,t/:d; 3 arcs(nodes, nodes)/ 4 s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, u, f; 5endsets 6data: 7 d = 14 0 0 0 0 -14; 8 c = 2 8 5 2 3 1 6 4 7; 9 u = 8 7 5 9 9 2 5 6 10; 10enddata 11min=sum(arcs:c*f); 12for(nodes(i) | i #ne# 1 #and# i #ne# size(nodes): 13 sum(arcs(i,j):f(i,j) - sum(arcs(j,i):f(j,i)=d(i); 14sum(arcs(i,j)|i #eq# 1 : f(i,j)=d(1); 15for(arcs:bnd(0,f,u); END,LINGO软件的计算结果(仅保留流值 )如下:,Global optimal solution found at iteration: 3 Objective value: 205.0000 Variable Value Reduced Cost F( S, 1) 8.000000 -1.000000 F( S, 2) 6.000000 0.000000 F( 1, 2) 1.000000 0.000000 F( 1, 3) 7.000000 0.000000 F( 2, 4) 9.000000 0.000000 F( 3, 2) 2.000000 -2.000000 F( 3, T) 5.000000 -7.000000 F( 4, T) 9.000000 0.000000,因此，最大流的最小费用是205单位.而原最大流费用为210单位，原方案并不是最优的.,下课！,