《数学建模最短路问题.ppt》由会员分享，可在线阅读，更多相关《数学建模最短路问题.ppt（71页珍藏版）》请在三一办公上搜索。
1、第11章 最短路问题,1.问题的提出2.图论的基本概念3.最短路问题求解算法4.建模实例,1 问题的提出,某学校行政部门u0经常有人到7个部门办事，希望在现有的道路网络中确定他们行走的路线，使他们到各部门的路程最短。图中已经标明了部门到部门之间的距离。,2 图论的基本概念,图论是离散数学的重要分支，在物理学、化学、系统控制、电力通讯、编码理论、可靠性理论、科学管理、电子计算机等各个领域都具有极其广泛的应用。图论的历史可以追溯到1736年，这一年发表了图论的第一篇论文，解决了著名的哥尼斯堡（Knigsberg）七桥问题。,Knigsberg七桥问题,哥尼斯堡城中有七座桥将普雷格尔(Pregel)
2、河中的两个岛与河岸联结起来，当时人们热衷于这样一个问题：一个人能否从四块陆地中的任何一块出发走过七座桥，每座桥恰走一次，最后回到起点？,(a),图论的基本概念,1.图的定义G=(V,E,)顶点，边，e与v连接，v与e关联，相邻，环，重边，平面图，完全图（完备图），二部图（偶图），子图，生成图。与一个顶点vi关联的边的数目称为vi的度（或次）。路、圈和连通有向图、赋权图,图论的一个定理,定理：d(v)=2|E|vV,证：因为每一条边提供给点的度为2，所以图中所有点的度数总和是边数的2倍。推论：在任何图中，奇点个数为偶数。,2.图的矩阵表示,对于任意图G，定义一个nm阶矩阵M=（mij）nm(n为
3、顶点数，m为边数)，其中mij是vi和ej相关联的次数（0,1或2等），该矩阵称为G的关联矩阵。图的另一种表示形式是邻接矩阵A=（aij）nn，其中aij是连接ai和aj的边的数目。,图的矩阵表示,关联矩阵 邻接矩阵,3最短路问题求解算法,设G为赋权有向图或无向图，G边上的权均非负。1.Dijkstra Algorithm:求G中从顶点u0到其余顶点的最短路。定义：对每个顶点v，定义两个标号l(v),z(v),其中l(v)为从u0到v的路长；z(v)为v的父亲点（前一个点）。S：具有永久标号的顶集。算法的过程就是在每一步改进这两个标号，最终l(v)为u0到v的最短路长。输入带权邻接矩阵（距离矩
4、阵）w(u,v).,最短路问题求解算法,Dijkstra Algorithm,Dijkstra算法所需时间与n2成正比。,用Dijkstra求解最短路问题,例 求从顶点u0到其余顶点的最短路。,解：先写出距离矩阵（实际应为对称矩阵）,Dijkstra算法的迭代步骤如下,迭代 l(ui)次数 u0 u1 u2 u3 u4 u5 u6 u7,1 0 2 2 1 8 3 2 8 10 4 8 3 10 5 8 6 10 126 7 10 127 9 12 8 12,最后标记：l(v)0 2 1 7 3 6 9 12z(v)u0 u0 u0 u5 u1 u4 u3 u4,最短路问题求解算法,2.Flo
5、yd Algorithm(1962):求任意两点间的最短路。D=（dij）nn,dij是i到j的最短路长，P=（pij）nn,pij是i到j的最短路上中间节点的最大号码，pij=0，表示无中间节点，,(1)赋初值：dij=wij,pij=0,k=1(2)更新dij,pij：对所有i,j，若dik+dkj dij，则 dij=dik+dkj,pij=k(3)若k=n，停止；否则k=k+1,转(2).,Floyd Algorithm,例 已知距离矩阵为 求任意两点之间的最短路。,Floyd Algorithm,解：D(0)=W,P(0)=(0)nn,建模案例分析,2000B题 钢管订购和运输,20
6、00B钢管运输分析求解步骤,1.用Floyd算法求出铁道两点间的最短路长，将路长转成费用。2.与公路运价组成的矩阵D，再用Floyd求出S1,S7到A1,A15的最短路，将购买单价计入运费之中。,第12章 匹配与覆盖及其应用,1 匹配与覆盖1.基本概念定义1设若M的边互不相邻，则称M是G的一个匹配。M的边称为匹配边，EM的边称为自由边，若(u,v)M，则称u（或v）是v（或u）的配偶。若顶点v与M的一条边关联，则称v是M-饱和的；否则称为M-非饱和的。若M使G中每个顶点都是M-饱和的，称M是G的完美（理想）匹配。设M是G的一个匹配，若不存在M 使|M|M|，则称M为G的最大匹配。,匹配与覆盖,
7、显然，完美匹配一定是最大匹配，反之不一定成立。(a)最大匹配(b)完美匹配,匹配与覆盖,定义2 设若G的每条边都与K的一个顶点关联，则称K是图G的一个覆盖。设K是G的一个覆盖，若不存在覆K使|K|K|，则称K是一个最小覆盖。,匹配与覆盖,下图为居民小区，安装消防设施，使每个相连的街道都有消防设施可用。覆盖：(v1,v2,v3,v4,v5)，(v1,v2,v3,v4)，(v2,v3,v4)，(v1,v3,v5)，而(v2,v3,v4)，(v1,v3,v5)是最小覆盖。(c)居民小区,2.性质,定义3 设M是图G=(V,E)的匹配，G的M交错路是指边在EM和M中交错出现的路，M可扩路（增广路）是指
8、其起点和终点都是M非饱和的M交错路。定理1（Berge1957）设M是G的一个匹配，则M是最大匹配的充要条件是，G没有M-增广路。定理2 设M是G的匹配，K是覆盖，则(1)|M|K|(2)若|M*|=|K|，则M*是最大匹配，K是最小覆盖。,3.二部图的匹配,定理3（Knig,1931）若M*和K分别是二部图G的最大匹配和最小覆盖，则|M*|=|K|定理4(Hall,1935)对二部图G=(X,Y,E),G存在饱和X的每个顶点的匹配的充要条件是：对任何S X,均有|N(S)|S|，这里N(S)为与S的顶点相邻的所有顶点的集合。如果G中所有顶点的度数都为k，则称图G是k正则的。推论 若G是k正则
9、二部图（k0），则G有完美匹配。,二部图的匹配,例：如果一个乡村里每位姑娘恰好认识k位小伙子，而每个小伙子也恰好认识k位姑娘，则每位姑娘能够和她认识的一个小伙子结婚，并且每个小伙子也能和他认识的一位姑娘结婚。此即为“婚姻定理”。根据上面的定理，Edmonds于1965年提出了如下的匈牙利算法，解决了二部图的基数匹配问题，步骤如下：,二部图的匹配,匈牙利算法：(1)设G=(X,Y,E)是二部图，M是一个匹配；(2)若M饱和X的每个顶点，则算法终止，M为最大匹配；否则，取M-非饱和点uX，令S=u,T=;(3)若N(S)=T,由于|T|=|S|-1，所以|N(S)|S|,算法终止，由定理4（Hal
10、l），不存在饱和X每个顶点的匹配；否则取yN(S)T;(4)若y是饱和的，设yzM,用Sz代替S，Ty代替T，转(3)（此时|T|=|S|-1仍成立）；否则设P是M增广路P(u,y),并令M=ME(P)（对称差），转(2),二部图的基数匹配例,x1 x2 x3 x4 x5 y1 y2 y3 y4 y5,二部图的基数匹配例,x1 x2 x3 x4 x5 y1 y2 y3 y4 y5,4.二部图的赋权匹配,G是完全二部图，有两个顶点集X=x1,x2,xn，Y=y1,y2,yn分别表示职员和工作，xi和yj之间用边相连，其权为wij表示职员xi做yj工作时的效率，对每人分配一件工作，使总效率最大。可
11、以用Kuhn-Munkres算法求赋权完全二部图的最佳匹配。,二部图的赋权匹配,定义：在G的顶点集V=XY上定义一个实值函数L，使得任何xX,yY均有L(x)+L(y)w(x,y)其中w(x,y)是边(x,y)上的权,称函数L(v)为该二部图的一个可行顶点标号。若用EL表示使上式等号成立的那些边的集合，即EL=(x,y)|(x,y)E,L(x)+L(y)=w(x,y)则称以EL为边集的G的生成子图为G对应于可行顶点标号L的相等子图，记为GL.,二部图的赋权匹配,可行顶点标号总是存在的，如令,二部图的赋权匹配,定理：设L是G的可行顶点标号，若GL包含完美（基数）匹配M*，则M*是G的最佳（最大权
12、）匹配。由上述定理知，欲求二部图的最佳匹配，只需用匈牙利（Hungarian）算法求相等子图GL的完美匹配。若GL不存在完美匹配，Kuhn和Munkres给出了一个修改顶点标号L的算法，可以使新相等子图的最大匹配扩大，这样，最终使相等子图具有完美匹配。,二部图的赋权匹配,Kuhn-Munkres算法：(1)设G=(X,Y,E)是二部图，从任一可行顶点标号L开始，确定GL，并在GL中选取一个匹配M。(2)若X是饱和的，则M是GL的完美匹配，是G的最佳匹配，算法终止；否则，在GL中取一个M-非饱和点uX，令S=u，T=；,二部图的赋权匹配,(3)若NGL(S)=T,则GL没有完美匹配，计算 给出可
13、行顶点标号L，以L代替L，以GL代替GL。否则转(4);(4)在NGL(S)T中选择一个顶点y,若y是M饱和的，并且yzM,则用Sz代替S，Ty代替T，转(3)；否则取GL中一条M增广路P(u,y),并令M=ME(P)（对称差），转(2),赋权匹配例1,五个人x1,x2,x3,x4,x5做五件工作y1,y2,y3,y4,y5，工作 效率如下列矩阵所示：一个人只能做一件工作，问如何安排工作使总的工作效率最高？（结果为14）,二部图的赋权匹配例1,x1 x2 x3 x4 x5 y1 y2 y3 y4 y5,赋权匹配例2,五种原材料A、B、C、D、E都可以用来生产a、b、c、d、e五种产品，成本如下
14、列矩阵所示：一种材料只能生产一种产品，问什么生产方案使成本最低（要求写出求解过程）？（结果为30）,2建模案例,锁具装箱问题(94 B)某厂生产一种弹子锁具，每个锁具的钥匙有5个槽的高度从1,2,3,4,5,6中任取一数。由于工艺原因，制造锁具对5个槽的高度有两个限制：至少有3个不同的数；相邻两槽的高度之差不能为5。满足以上条件制造出来的所有互不相同的锁具称为一批。若4个相同，另一槽的高度差为1，则可能互开。其它情形不可能互开。在原来一批锁具中随机取60个装为一箱，成箱购买的顾客总抱怨购得的锁具有互开现象。如何装箱（60个为一箱），如何给箱子以标志，出售时如何利用这些标志，使团体顾客减少抱怨。
15、,第13章 行遍历问题,1中国邮递员问题一、问题的提出一位邮递员从邮局出发，带着所管辖地区的信件、报纸支投递，投递结束后回到邮局，为了投递完所有邮件，当然他必须经过其所管辖的每条街道至少一次，请为他设计一条路线，使行程尽可能短。,中国邮递员问题,这就是中国邮递员问题的原始模型，是我国管梅谷教授于1962年首先提出的。用图论的语言来叙述，中国邮递员问题就是在连通赋权图G上求一个回路（未必是简单的），过每边至少一次，并使回路的权最小。,二、欧拉图与Fleury算法,定义 设G=(V,E)是连通无向图(1)经过G的每边至少一次的闭通路称为（巡回）回路。(2)经过G的每边恰好一次的回路称为Euler回
16、路。(3)存在Euler回路的图称为Euler图。(4)过每边恰好一次的（路）链称为Euler链。Euler回路、Euler链可以形象地描述为“一笔画问题”。定理1 连通图G是Euler图，当且仅当G中无奇度顶点。,欧拉图与Fleury算法,Fleury算法：(1)任取一个v0V，令W=v0.(2)设链W=v0e1v1e2eivi已选定，则从Ee1,e2,ei中选取一条与ei相邻的边ei+1，除非已无选择余地，否则不要选Ge1,e2,ei的桥。(3)直到(2)不能进行为止，算法终止时得到的是Euler回路。,三、奇偶点图上作业法与Edmonds算法,如果G不是连通的Euler图，则G中含有奇度
17、顶点（但奇度顶点的个数为偶数），此时图G的一条邮递路线必定在某些街着上重复走了一次或多次，它等价于在这些边上加一条或多条重复边，使新图G 不含奇度顶点，并且所加边的总权为最小。设E1表示所有新增加边的集合，它是图G边集的一个子集。如何求权最小的新增边集E1呢？,奇偶点图上作业法,定理2 E1为权最小的新增边集，当且仅当下列条件满足：(1)E1中没有重复出现的边；(2)在G的每个回路上，属于E1的边权和不超过该回路边和的一半。根据定理可以从某一可行新增边集开始，进行调整，最终得到最优解。这种方法称为“奇偶点图上作业法”。,奇偶点图上作业法,“奇偶点图上作业法”对回路不太多的图是可行的。当回路很多
18、时（如“田”字形的图形就有13个回路），要检查所有的回路是难以做到的。Edmonds在1965年提出了一种有效的方法，使中国邮递员问题得到了较好的解决。,Edmonds算法,(1)根据给定的图G，构造一个新图G*，G*中的顶点就是G中的所有奇度顶点，并将G*中任意两顶点都相连，此时G*是一个完全图，G*中边的权等于G中顶点与间的最短距离。(2)在G*中找一个最小权完美匹配M（M是G*中具有如下性质的一个边集：G*中每个点恰与M中一条边关联，且M的权最小）。(3)在G中将互相匹配的奇度顶点用最短路径相连，由此得到G的最小新增边集。,Edmonds算法,下面用Edmonds算法求解上图的中国邮递员
19、问题。根据图中奇度顶点v1,v2,v3,v5构造一个完全图G*，如下图。求G*的最小权完美匹配M，得M=（v1,v2）,（v3,v5），其权为2+5=7，在G中加入（v1,v2）和（v3,v4,v1,v5）两条最短路，使G变为Euler图，其权值为26+7=33。,2推销员问题,一、问题的提出一旅行售货员需要到邻近的50个村镇推销他的商品，最后回到出发点。问如何安排旅行路线使总行程最短？旅行售货员问题（Traveling Salesman Problem）是NP-完备问题。,推销员问题,二、Hamilton图定义1 设G=(V,E)是连通无向图(1)经过G的每个顶点正好一次的路径，称为G的一条
20、Hamilton路径，简称H路径。(2)经过G的每个顶点正好一次的圈，称为G的Hamilton圈，简称H圈。(3)含Hamilton圈的图称为Hamilton图，简称H图。,推销员问题,上述旅行售货员问题中顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（时间、费用），于是TSP就成为在赋权图中寻找一条经过每个顶点至少一次的最短闭通路问题。定义2 在赋权图G=(V,E)中(1)权最小的Hamilton圈，称为最佳H圈。(2)经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路。,推销员问题,一般情况，最佳Hamilton圈不一定是最佳推销员回路，反之也不一定。（p213）但有下列定理。定
21、理1 设G=(V,E)是赋权图，若对任意x,y,zV,zx,zy,都有w(x,y)w(x,z)+w(z,y),则图G的最佳H圈也是最佳推销员回路。,推销员问题,可以用G中任意两点的最短距离构造一个完全图G,则有定理2 赋权图G的最佳推销员回路的权与G 的最佳H圈的权相同。故在赋权图中寻求最佳推销员回路的问题就可转化为在一个完全赋权图G 中寻求最佳H圈的问题。,推销员问题,三、TSP近似算法二边逐次修正法，模拟退火法，弹性网法等,3建模案例,最佳灾情巡视路线（98B）下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有
22、关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。在上述关于T,t和v的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和v改变对最佳巡视路线的影响。,第14章网络流问题,1 最
23、大流问题E油田有 一个石油运输管网，Vs是石油产品产地，Vt是石油销地，边旁数子为单位时间容许的最大输油量（单位：桶/分钟）。问题是决定从Vs到Vt单位时间的最大输入油量。,第14章网络流问题,概念发点（source），收点（sink），中间点，C为定义在aij上的容量函数，其值cij为弧aij的容量。,最大流问题,网络N上的流量指定义在弧集合A上的一个函数f，记fij=f(aij)若流f还满足(1)容量限制条件 0fijcij(2)流量守恒条件 fij-fji=0 is,t则称f为可行流。,最大流问题,一个网络的可行流总是存在的，如令所有弧的流量fij=0，就得到一个流，其流量val(f)=
24、0，并称该可行流为零流。确定E油田从Vs到Vt的最大输油量，也就是在所有可行流方案中确定一个使流量达到最大的方案。,最大流问题,最大流问题的一般形式为,2.最大流基本定理,定义：在网络中，若点集被剖分为两个非空集合，使得，则把弧集 称为中的割。称为割的容量。,最大流基本定理,容易证明：任何一个可行流f的流量都不会超过任一割的容量，即特别若有一可行流f和割，使上式等号成立，则f必为最大流，而 必为最小割。,可增路,设f是网络N的一个可行流，对于N中的每条路P，在其上定义一个非负函数：若(P)=0,则称路P是f饱和的；(P)0,则称路P是f非饱和的，称P为可增路（增广路）,最大流基本定理,网络中f
25、可增路P的存在意味着f不是最大流。可沿着P增加一个值为(P)的附加流量，得到由所定义的新可行流f，val(f)=val(f)+(P),称为基于P的调整流。,最大流基本定理,定理1 N中的可行流f是最大流当且仅当N不包含f可增路。定理2 在任何网络中，最大流的流量等于最小割的容量。,3Ford和Fulkerson标号算法,(1)置每个fij等于一个可行流f的对应值。若网络中没有给定f，则设f是零流。(2)给发点vs标上(0，+)，vs成为已标号而未检查的点，其它点为未标号点。(3)如果不存在已标号而未检查的点，算法终止，现行流即为最大流；否则按标号的先后次序取一个已标号而未检查的点vi，对一切未
26、标号点vj，若弧(vi,vj)为非饱和弧，即fij0，则给vj以标号(vi，j)，其中j=mini,fji 这时成为已标号而未检查的点。考虑完一切未标号点vj后，vi便成为已标号并检查过后点。,Ford和Fulkerson标号算法,(4)如果收点vt未标号，转(3)；否则转(5)。(5)从开始vt，通过第一标号，逆向找出可增路P，并令 去掉所的点的标号，转(2)。,4最小费用最大流,上节我们已经求得石油运输管网的最大输油量为5桶/分钟。假设运输管网上各管道aij输送石油的单位流量的运费如下图所示，要确定这样一个方案，使输油量最大，同时使总的运输费用最小。,cij,bij,调整网络,对网络N的可
27、行流定义调整容量的流网络N(f)如下：N与N有相同的顶点集合；对N的弧(vi,vj)，其上的流为fij，容量为cij，费用为bij，N中有两条弧(vi,vj)和(vj,vi)与之对应，弧(vi,vj)的容量为cij-fij，费用为bij；弧(vj,vi)的容量为fij，费用为-bij，再去掉所有容量为0的弧。由这个定义可知，N(f)中自vs到vt的一条有向路P(N)确定了中一条vs到vt的可增路。,5迭加算法,定理2 设f1是N中流量为F的最小费用流，f2是N(f1)中沿最小费用的有向路P的单位流，则f1+f2是N中流量为F+1的最小费用流。,Ford和Fulkerson迭加算法,(1)给定目标流量F（或），从给定的最小费用流f开始，若未给，令f为零流。(2)若val(f)=F，停止，f为最小费用流；否则转(3)。(3)在N(f)中寻找从vs到vt的最小费用有向路P，沿P增加流f的流量直到F，转(2)；若不存在从vs到vt的最小费用的有向路P，停止，f就是最小费用最大流。,
