数学建模最短路问题市公开课一等奖省赛课获奖课件

第11章最短路问题1.问题提出2.图论基本概念3.最短路问题求解算法4.建模实例第1页§1问题提出某学校行政部门u0经常有些人到7个部门办事，希望在现有道路网络中确定他们行走路线，使他们到各部门旅程最短。图中已经标明了部门到部门之间距离。第2页§2图论基本概念图论是离散数学主要分支，在物理学、化学、系统控制、电力通讯、编码理论、可靠性理论、科学管理、电子计算机等各个领域都含有极其广泛应用。图论历史能够追溯到1736年，这一年发表了图论第一篇论文，处理了著名哥尼斯堡（Königsberg）七桥问题。第3页Königsberg七桥问题哥尼斯堡城中有七座桥将普雷格尔(Pregel)河中两个岛与河岸联结起来，当初人们热衷于这么一个问题：一个人能否从四块陆地中任何一块出发走过七座桥，每座桥恰走一次，最终回到起点？(a)ABCDABCD(b)第4页图论基本概念1.图定义G=(V,E,ψ)顶点，边，e与v连接，v与e关联，相邻，环，重边，平面图，完全图（完备图），二部图（偶图），子图，生成图。与一个顶点vi关联边数目称为vi度（或次）。路、圈和连通有向图、赋权图第5页图论一个定理定理：∑d(v)=2|E|

v∈V证：因为每一条边提供给点度为2，所以图中全部点度数总和是边数2倍。推论：在任何图中，奇点个数为偶数。第6页2.图矩阵表示对于任意图G，定义一个n×m阶矩阵M=（mij）n×m(n为顶点数，m为边数)，其中mij是vi和ej相关联次数（0,1或2等），该矩阵称为G关联矩阵。图另一个表示形式是邻接矩阵A=（aij）n×n，其中aij是连接ai和aj边数目。第7页图矩阵表示关联矩阵邻接矩阵第8页§3最短路问题求解算法设G为赋权有向图或无向图，G边上权均非负。1.DijkstraAlgorithm:求G中从顶点u0到其余顶点最短路。定义：对每个顶点v，定义两个标号l(v),z(v),其中l(v)为从u0到v路长；z(v)为v父亲点（前一个点）。S：含有永久标号顶集。算法过程就是在每一步改进这两个标号，最终l(v)为u0到v最短路长。输入带权邻接矩阵（距离矩阵）w(u,v).第9页最短路问题求解算法DijkstraAlgorithmDijkstra算法所需时间与n2成正比。第10页用Dijkstra求解最短路问题例求从顶点u0到其余顶点最短路。解：先写出距离矩阵（实际应为对称矩阵）第11页Dijkstra算法迭代步骤以下迭代l(ui)次数u0u1u2u3u4u5u6u7

10∞∞∞∞∞∞∞221

8∞∞∞∞328∞∞10∞483∞10∞58610126710127912812最终标识：l(v)021736912z(v)u0u0u0u5u1u4u3u4

第12页最短路问题求解算法2.FloydAlgorithm(1962):求任意两点间最短路。D=（dij）n×n,dij是i到j最短路长，P=（pij）n×n,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).第13页FloydAlgorithm例已知距离矩阵为

求任意两点之间最短路。第14页FloydAlgorithm解：D(0)=W,P(0)=(0)n×n第15页建模案例分析B题钢管订购和运输第16页第17页B钢管运输分析求解步骤1.用Floyd算法求出铁道两点间最短路长，将路长转成费用。2.与公路运价组成矩阵D，再用Floyd求出S1,…,S7到A1,…,A15最短路，将购置单价计入运费之中。第18页第12章匹配与覆盖及其应用§1匹配与覆盖1.基本概念定义1设若M边互不相邻，则称M是G一个匹配。M边称为匹配边，E\M边称为自由边，若(u,v)∈M，则称u（或v）是v（或u）配偶。若顶点v与M一条边关联，则称v是M-饱和；不然称为M-非饱和。若M使G中每个顶点都是M-饱和，称M是G完美（理想）匹配。设M是G一个匹配，若不存在M'使|M'|>|M|，则称M为G最大匹配。第19页匹配与覆盖显然，完美匹配一定是最大匹配，反之不一定成立。(a)最大匹配(b)完美匹配第20页匹配与覆盖定义2设若G每条边都与K一个顶点关联，则称K是图G一个覆盖。设K是G一个覆盖，若不存在覆K'使|K'|<|K|，则称K是一个最小覆盖。第21页匹配与覆盖下列图为居民小区，安装消防设施，使每个相连街道都有消防设施可用。覆盖：(v1,v2,v3,v4,v5)，(v1,v2,v3,v4)，(v2,v3,v4)，(v1,v3,v5)，而(v2,v3,v4)，(v1,v3,v5)是最小覆盖。(c)居民小区v1v2v4v5v3第22页2.性质定义3设M是图G=(V,E)匹配，GM交织路是指边在E\M和M中交织出现路，M可扩路（增广路）是指其起点和终点都是M非饱和M交织路。定理1（Berge1957）设M是G一个匹配，则M是最大匹配充要条件是，G没有M-增广路。定理2设M是G匹配，K是覆盖，则(1)|M|≤|K|(2)若|M*|=|K~|，则M*是最大匹配，K~是最小覆盖。第23页3.二部图匹配定理3（König,1931）若M*和K~分别是二部图G最大匹配和最小覆盖，则|M*|=|K~|定理4(Hall,1935)对二部图G=(X,Y,E),G存在饱和X每个顶点匹配充要条件是：对任何SX,都有|N(S)|≥|S|，这里N(S)为与S顶点相邻全部顶点集合。假如G中全部顶点度数都为k，则称图G是k正则。推论若G是k正则二部图（k>0），则G有完美匹配。第24页二部图匹配例：假如一个乡村里每位姑娘恰好认识k位小伙子，而每个小伙子也恰好认识k位姑娘，则每位姑娘能够和她认识一个小伙子结婚，而且每个小伙子也能和他认识一位姑娘结婚。此即为“婚姻定理”。依据上面定理，Edmonds于1965年提出了以下匈牙利算法，处理了二部图基数匹配问题，步骤以下：第25页二部图匹配匈牙利算法：(1)设G=(X,Y,E)是二部图，M是一个匹配；(2)若M饱和X每个顶点，则算法终止，M为最大匹配；不然，取M-非饱和点u∈X，令S={u},T=Φ;(3)若N(S)=T,因为|T|=|S|-1，所以|N(S)|<|S|,算法终止，由定理4（Hall），不存在饱和X每个顶点匹配；不然取y∈N(S)\T;(4)若y是饱和，设yz∈M,用S∪{z}代替S，T∪{y}代替T，转(3)（此时|T|=|S|-1仍成立）；不然设P是M增广路P(u,y),并令M=MΔE(P)（对称差），转(2)第26页二部图基数匹配例x1x2x3x4x5y1y2y3y4y5第27页二部图基数匹配例x1x2x3x4x5y1y2y3y4y5第28页4.二部图赋权匹配G是完全二部图，有两个顶点集X={x1,x2,…,xn}，Y={y1,y2,…,yn}分别表示职员和工作，xi和yj之间用边相连，其权为wij表示职员xi做yj工作时效率，对每人分配一件工作，使总效率最大。能够用Kuhn-Munkres算法求赋权完全二部图最正确匹配。第29页二部图赋权匹配定义：在G顶点集V=X∪Y上定义一个实值函数L，使得任何x∈X,y∈Y都有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.第30页二部图赋权匹配可行顶点标号总是存在，如令第31页二部图赋权匹配定理：设L是G可行顶点标号，若GL包含完美（基数）匹配M*，则M*是G最正确（最大权）匹配。由上述定理知，欲求二部图最正确匹配，只需用匈牙利（Hungarian）算法求相等子图GL完美匹配。若GL不存在完美匹配，Kuhn和Munkres给出了一个修改顶点标号L算法，能够使新相等子图最大匹配扩大，这么，最终使相等子图含有完美匹配。第32页二部图赋权匹配Kuhn-Munkres算法：(1)设G=(X,Y,E)是二部图，从任一可行顶点标号L开始，确定GL，并在GL中选取一个匹配M。(2)若X是饱和，则M是GL完美匹配，是G最正确匹配，算法终止；不然，在GL中取一个M-非饱和点u∈X，令S={u}，T=Φ；第33页二部图赋权匹配(3)若NGL(S)=T,则GL没有完美匹配，计算给出可行顶点标号L'，以L'代替L，以GL'代替GL。不然转(4);(4)在NGL(S)\T中选择一个顶点y,若y是M饱和，而且yz∈M,则用S∪{z}代替S，T∪{y}代替T，转(3)；不然取GL中一条M增广路P(u,y),并令M=MΔE(P)（对称差），转(2)第34页赋权匹配例1五个人x1,x2,x3,x4,x5做五件工作y1,y2,y3,y4,y5，工作效率以以下矩阵所表示：

一个人只能做一件工作，问怎样安排工作使总工作效率最高？（结果为14）第35页二部图赋权匹配例1x1x2x3x4x5y1y2y3y4y5第36页赋权匹配例2五种原材料A、B、C、D、E都能够用来生产a、b、c、d、e五种产品，成本以以下矩阵所表示：

一个材料只能生产一个产品，问什么生产方案使成本最低（要求写出求解过程）？（结果为30）第37页§2建模案例锁具装箱问题(94B)

某厂生产一个弹子锁具，每个锁具钥匙有5个槽高度从{1,2,3,4,5,6}中任取一数。因为工艺原因，制造锁具对5个槽高度有两个限制：最少有3个不一样数；相邻两槽高度之差不能为5。满足以上条件制造出来全部互不相同锁具称为一批。若4个相同，另一槽高度差为1，则可能互开。其它情形不可能互开。在原来一批锁具中随机取60个装为一箱，成箱购置用户总埋怨购得锁含有互开现象。怎样装箱（60个为一箱），怎样给箱子以标志，出售时怎样利用这些标志，使团体用户降低埋怨。第38页第13章行遍历问题§1中国邮递员问题一、问题提出一位邮递员从邮局出发，带着所管辖地域信件、报纸支投递，投递结束后回到邮局，为了投递完全部邮件，当然他必须经过其所管辖每条街道最少一次，请为他设计一条路线，使行程尽可能短。

v2

2

6

7

v1

3

v5

6v3

1

1

v4第39页中国邮递员问题这就是中国邮递员问题原始模型，是我国管梅谷教授于1962年首先提出。用图论语言来叙述，中国邮递员问题就是在连通赋权图G上求一个回路（未必是简单），过每边最少一次，并使回路权最小。第40页二、欧拉图与Fleury算法定义设G=(V,E)是连通无向图(1)经过G每边最少一次闭通路称为（巡回）回路。(2)经过G每边恰好一次回路称为Euler回路。(3)存在Euler回路图称为Euler图。(4)过每边恰好一次（路）链称为Euler链。Euler回路、Euler链能够形象地描述为“一笔画问题”。定理1连通图G是Euler图，当且仅当G中无奇度顶点。第41页欧拉图与Fleury算法Fleury算法：(1)任取一个v0∈V，令W=v0.(2)设链W=v0e1v1e2…eivi已选定，则从E\{e1,e2,…,ei}中选取一条与ei相邻边ei+1，除非已无选择余地，不然不要选G\{e1,e2,…,ei}桥。(3)直到(2)不能进行为止，算法终止时得到是Euler回路。第42页三、奇偶点图上作业法与Edmonds算法假如G不是连通Euler图，则G中含有奇度顶点（但奇度顶点个数为偶数），此时图G一条邮递路线必定在一些街着上重复走了一次或屡次，它等价于在这些边上加一条或多条重复边，使新图G'不含奇度顶点，而且所加边总权为最小。设E1表示全部新增加边集合，它是图G边集一个子集。怎样求权最小新增边集E1呢？第43页奇偶点图上作业法定理2E1为权最小新增边集，当且仅当以下条件满足：(1)E1中没有重复出现边；(2)在G每个回路上，属于E1边权和不超出该回路边和二分之一。依据定理能够从某一可行新增边集开始，进行调整，最终得到最优解。这种方法称为“奇偶点图上作业法”。第44页奇偶点图上作业法“奇偶点图上作业法”对回路不太多图是可行。当回路很多时（如“田”字形图形就有13个回路），要检验全部回路是难以做到。Edmonds在1965年提出了一个有效方法，使中国邮递员问题得到了很好处理。第45页Edmonds算法(1)依据给定图G，结构一个新图G*，G*中顶点就是G中全部奇度顶点，并将G*中任意两顶点都相连，此时G*是一个完全图，G*中边权等于G中顶点与间最短距离。(2)在G*中找一个最小权完美匹配M（M是G*中含有以下性质一个边集：G*中每个点恰与M中一条边关联，且M权最小）。(3)在G中将相互匹配奇度顶点用最短路径相连，由此得到G最小新增边集。第46页Edmonds算法下面用Edmonds算法求解上图中国邮递员问题。依据图中奇度顶点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。

v2

2

4

5

v1

2v3

3

5

v5

v2

2

6

7

v1

3

v5

6v3

1

1

v4第47页§2推销员问题一、问题提出一旅行售货员需要到邻近50个村镇推销他商品，最终回到出发点。问怎样安排旅行路线使总行程最短？旅行售货员问题（TravelingSalesmanProblem）是NP-完备问题。第48页推销员问题二、Hamilton图定义1设G=(V,E)是连通无向图(1)经过G每个顶点恰好一次路径，称为G一条Hamilton路径，简称H路径。(2)经过G每个顶点恰好一次圈，称为GHamilton圈，简称H圈。(3)含Hamilton圈图称为Hamilton图，简称H图。第49页推销员问题上述旅行售货员问题中顶点表示城镇，边表示连接两城镇路，边上权表示距离（时间、费用），于是TSP就成为在赋权图中寻找一条经过每个顶点最少一次最短闭通路问题。定义2在赋权图G=(V,E)中(1)权最小Hamilton圈，称为最正确H圈。(2)经过每个顶点最少一次权最小闭通路称为最正确推销员回路。第50页推销员问题普通情况，最正确Hamilton圈不一定是最正确推销员回路，反之也不一定。（p213）但有以下定理。定理1设G=(V,E)是赋权图，若对任意x,y,z∈V,z≠x,z≠y,都有w(x,y)≤w(x,z)+w(z,y),则图G最正确H圈也是最正确推销员回路。第51页推销员问题能够用G中任意两点最短距离结构一个完全图G',则有定理2赋权图G最正确推销员回路权与G'最正确H圈权相同。故在赋权图中寻求最正确推销员回路问题就可转化为在一个完全赋权图G'中寻求最正确H圈问题。第52页推销员问题三、TSP近似算法二边逐次修正法，模拟退火法，弹性网法等第53页§3建模案例最正确灾情巡视路线（98B）下列图为某县乡（镇）、村公路网示意图，公路边数字为该路段公里数。

今年夏天该县遭受水灾。为考查灾情、组织自救，县领导决定，率领相关部门责任人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地路线。

若分三组（路）巡视，试设计总旅程最短且各组尽可能均衡巡视路线。

假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。要在24小时内完成巡视，最少应分几组；给出这种分组下你认为最正确巡视路线。

在上述关于T,t和v假定下，假如巡视人员足够多，完成巡视最短时间是多少；给出在这种最短时间完成巡视要求下，你认为最正确巡视路线。

若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和v改变对最正确巡视路线影响。

第54页第55页第14章网络流问题

1．

最大流问题E油田有

一个石油运输管网，Vs是石油产品产地，Vt是石油销地，边旁数子为单位时间允许最大输油量（单位：桶/分钟）。问题是决定从Vs到Vt单位时间最大输入油量。vsv1v2v3v4vt332224141第56页第14章网络流问题

概念发点（source），收点（sink），中间点，C为定义在aij上容量函数，其值cij为弧aij容量。vsv1v2v3v4vt332224141第57页最大流问题

网络N上流量指定义在弧集合A上一个函数f，记fij=f(aij)若流f还满足(1)

容量限制条件0≤fij≤cij(2)

流量守恒条件∑fij-∑fji=0i≠s,t则称f为可行流。第58页最大流问题一个网络可行流总是存在，如令全部弧流量fij=0，就得到一个流，其流量val(f)=0，并称该可行流为零流。确定E油田从Vs到Vt最大输油量，

也就是在全部可行流方案中确定一个使流量到达最大方案。第59页最大流问题最大流问题普通形式为第60页2.最大流基本定理定义：在网络Ｎ中，若点集Ｖ被剖分为两个非空集合，使得，则把弧集称为Ｎ中割。称为割容量。

第61页最大流基本定理轻易证实：任何一个可行流f流量都不会超出任一割容量，即尤其若有一可行流f和割，使上式等号成立，则f必为最大流，而必为最小割。第62页可增路设f是网络N一个可行流，对于N中每条路P，在其上定义一个非负函数：若δ(P)=0,则称路P是f饱和；δ(P)>0,则称路P是f非饱和，称P为可增路（增广路）

第63页最大流基本定理网络中f可增路P存在意味着f不是最大流。可沿着P增加一个值为δ(P)附加流量，得到由

所定义新可行流f’，val(f’)=val(f)+