数学建模提高班第六讲-网络优化模型及案例分析市公开课获奖课件省名师优质课赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,网络优化模型及案例分析,赵承业 /4/2,4,1/94,本专题学习目,掌握把实际问题转化为图或网络问题方法,了解图基本概念和矩阵表示方法,掌握最短路问题、最小生成树问题算法,了解旅行商问题,2/94,一个表示工具,图,最小生成树,主要内容,一个时间安排问题,图论起源,人、狼、羊、菜渡河问题,最短路问题,图矩阵表示方法,3/94,练习题,主要内容,旅行商问题,4/94,图论起源七桥问题,5/94,c,a,b,d,c,a,b,d,图论起源：七桥问题,图1,图2,6/94,欧拉,图论之父,定理1：一个图存在经过每边恰好一次回到出发点路线充要条件是：,1,）图要是,连通,2,）与图中每一顶点相连边必须是,偶数,条。,于是得出结论：七桥问题无解。,图论起源：七桥问题,返 回,7/94,无向图，普通用大写字母,G,H,表示。,一个表示工具,图,顶点,边,d,c,a,b,图3,8/94,无向图：,G=(V,E),，,顶点集：,V,；边集：,E,。,e,与,顶点,u,v,相关联。,u,与,v,相邻。,两边相邻。,重边,c,a,b,d,一个表示工具,图,图4,9/94,两种特殊图简单图,完全图，记为,K,n,b,d,c,a,b,d,c,a,一个表示工具,图,图6,图5,10/94,有向图：,V,1,V,2,V,3,V,5,V,4,想,你能给出一个可用有向图描述实际例子吗？,一个表示工具,图,图7,11/94,网络,这些数字能够代表,距离,，,费用,，,可靠性,或其它相关参数。,1,2,3,4,5,8,6,9,1,5,7,10,3,一个表示工具,图,图8,12/94,(G),和,(G),分别表示图,G,顶点数和边数,在无向图中，,v,度数,，记为,d(v),；,在有向图中，,v,出度,，记为,d,+,(v);v,入度,，记为,d,-,(v),。,一个表示工具,图,返 回,13/94,一个时间安排问题,学校要为一年级硕士开设六门基础数学课：统计,(S),，数值分析,(N),，图论,(G),，矩阵论,(M),，随机过程,(R),和数理方程,(P),。按培养计划，注册学生必须选修其中一门以上，你作为教务管理人员，要设法安排一个课表，使每个学生所选课程，在时间上不会发生冲突。,14/94,一个时间安排问题,表1,15/94,S,N,G,R,P,M,完成上述表示课程冲突关系图,直观、清楚地表示已知信息方式,一个时间安排问题,返 回,图9,16/94,人狼羊菜渡河问题,摆渡人,F,狼,W,羊,G,菜,C,图10,17/94,南岸状态：,16,种，其中,WG,GC,WGC,，从而,FC,FW,F,为不允许状态，,FWGC,FWG,FWC,FGC,FG,O,C,G,W,WC,10,个允许状态：,人狼羊菜渡河问题,18/94,FWGC,FWG,FWC,FGC,FG,O,C,G,W,WC,寻求图中从顶点“,FWGC”,到顶点“,O”,最短路径，这么路径有几条？求出最优渡河方案。,想,语言描述时未显示关系跃然纸上,人狼羊菜渡河问题,图11,19/94,FWGC,FWG,FWC,FGC,FG,O,C,G,W,WC,FWGC,FWG,FWC,FGC,FG,O,C,G,W,WC,人狼羊菜渡河问题,返 回,图12,20/94,图矩阵表示方法,邻接矩阵,关联矩阵,边矩阵,邻接次序表,返 回,21/94,v,1,v,2,v,5,v,6,v,7,v,4,v,3,a,b,j,k,c,g,h,i,d,f,e,邻接矩阵,图13,22/94,无向图邻接矩阵：,A=(a,ij,)n,n,，其中,无向图邻接矩阵有何特点？由邻接矩阵是否能作出原图？,想,邻接矩阵,返 回,23/94,关联矩阵,v,1,v,2,v,5,v,6,v,7,v,4,v,3,a,b,j,k,c,g,h,i,d,f,e,图13,24/94,无向图关联矩阵：,M=(m,ij,)n,m,其中,想,无向图关联矩阵有哪些特征？由关联矩阵能否作出原图？,关联矩阵,返 回,25/94,边矩阵,v,1,v,2,v,5,v,6,v,7,v,4,v,3,a,b,j,k,c,g,h,i,d,f,e,返 回,图13,26/94,最短路问题及算法,最短路问题是图论应用基本问题，很多实际,问题，如线路布设、运输安排、运输网络最小费,用流等问题,都可经过建立最短路问题模型来求解,.,最短路定义,最短路问题两种方法：,Dijkstra,和,Floyd,算法,.,1),求赋权图中从给定点到其余顶点最短路.,2),求赋权图中任意两点间最短路,.,27/94,2),在赋权图,G,中，从顶点,u,到顶点,v,含有最小权,定义1,1),若,H,是赋权图,G,一个子图，则称,H,各,边权和 为,H,权,.,类似地，若,称为路,P,权,若,P,(,u,v,),是赋权图,G,中从,u,到,v,路,称,路,P*,(,u,v,),，称为,u,到,v,最短路,3),把赋权图,G,中一条路权称为它,长,，把,(,u,v,),路最小权称为,u,和,v,之间,距离,，并记作,d,(,u,v,).,28/94,1)赋权图中从给定点到其余顶点最短路,假设,G,为赋权有向图或无向图，,G,边上权均非,负若 ，则要求,最短路是一条路，且最短路任一节也是最短路,例 求下面赋权图中顶点,u,0,到其余顶点最短路,图14,29/94,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点最短路,.,1),置 ，对 ，且,.,2),对每个 ，用,代替 ，计算 ，并把到达这个最小值,一个顶点记为 ，置,3),若 ，则停顿；若 ，则用,i+1,代,替,i,，并转,2),.,30/94,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点最短路,.,1),置 ，对 ，且,.,2),对每个 ，用,代替 ，计算 ，并把到达这个最小值,一个顶点记为 ，置,3),若 ，则停顿；若 ，则用,i+1,代,替,i,，并转,2),.,31/94,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点最短路,.,1),置 ，对 ，且,.,2),对每个 ，用,代替 ，计算 ，并把到达这个最小值,一个顶点记为 ，置,3),若 ，则停顿；若 ，则用,i+1,代,替,i,，并转,2),.,32/94,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点最短路,.,1),置 ，对 ，且,.,2),对每个 ，用,代替 ，计算 ，并把到达这个最小值,一个顶点记为 ，置,3),若 ，则停顿；若 ，则用,i+1,代,替,i,，并转,2),.,33/94,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点最短路,.,1),置 ，对 ，且,.,2),对每个 ，用,代替 ，计算 ，并把到达这个最小值,一个顶点记为 ，置,3),若 ，则停顿；若 ，则用,i+1,代,替,i,，并转,2),.,34/94,Dijkstra,算法,求,G,中从顶点,u,0,到其余顶点最短路,.,1),置 ，对 ，且,.,2),对每个 ，用,代替 ，计算 ，并把到达这个最小值,一个顶点记为 ，置,3),若 ，则停顿；若 ，则用,i+1,代,替,i,，并转,2),.,35/94,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点最短路,.,1),置 ，对 ，且,.,2),对每个 ，用,代替 ，计算 ，并把到达这个最小值,一个顶点记为 ，置,3),若 ，则停顿；若 ，则用,i+1,代,替,i,，并转,2),.,36/94,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点最短路,.,1),置 ，对 ，且,.,2),对每个 ，用,代替 ，计算 ，并把到达这个最小值,一个顶点记为 ，置,3),若 ，则停顿；若 ，则用,i+1,代,替,i,，并转,2),.,37/94,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点最短路,.,1),置 ，对 ，且,.,2),对每个 ，用,代替 ，计算 ，并把到达这个最小值,一个顶点记为 ，置,3),若 ，则停顿；若 ，则用,i+1,代,替,i,，并转,2),.,38/94,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点最短路,.,1),置 ，对 ，且,.,2),对每个 ，用,代替 ，计算 ，并把到达这个最小值,一个顶点记为 ，置,3),若 ，则停顿；若 ，则用,i+1,代,替,i,，并转,2),.,39/94,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点最短路,.,1),置 ，对 ，且,.,2),对每个 ，用,代替 ，计算 ，并把到达这个最小值,一个顶点记为 ，置,3),若 ，则停顿；若 ，则用,i+1,代,替,i,，并转,2),.,40/94,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点最短路,.,1),置 ，对 ，且,.,2),对每个 ，用,代替 ，计算 ，并把到达这个最小值,一个顶点记为 ，置,3),若 ，则停顿；若 ，则用,i+1,代,替,i,，并转,2),.,41/94,42/94,定义2,依据顶点,v,标号,l(v),取值路径，使 到,v,最短路中与,v,相邻前一个顶点,w,，称为,v,先驱,点,，记为,z,(,v,),即,z,(,v,)=,w,.,先驱点可用于追踪最短路径,.,例,5,标号过程也,可按以下方式进行：,首先写出左图带权邻接矩阵,因,G,是无向图，故,W,是对称阵,43/94,表2,44/94,续表2,图8,45/94,2),求赋权图中任意两顶点间最短路,算法基本思想,（I）求距离矩阵方法.,（II）求路径矩阵方法.,（III）查找最短路路径方法.,Floyd算法：求任意两顶点间最短路.,举例说明,46/94,算法基本思想,47/94,（I）求距离矩阵方法.,48/94,（II）求路径矩阵方法.,在建立距离矩阵同时可建立路径矩阵R,49/94,（III）查找最短路路径方法.,然后用一样方法再分头查找若：,图16,50/94,（IV）Floyd算法：求任意两顶点间最短路.,51/94,例 2,求下列图中加权图任意两点间距离与路径.,图17,52/94,插入点,v,1,，,得：,矩阵中带“,=,”,项为经迭代比较以后有改变元素,.,53/94,插入点,v,2,，,得：,矩阵中带“,=,”,项为经迭代比较以后有改变元素,.,54/94,插入点,v,3,，,得：,55/94,插入点,v,4,，,得：,插入点,v,5,，,得：,56/94,插入点v,6,，,得：,57/94,故从,v,5,到,v,2,最短路为,8,由,v,6,向,v,5,追溯,:,由,v,6,向,v,2,追溯,:,所以从到最短路径为：,返 回,58/94,最小生成树及算法,许多应用问题都是一个求无向连通图最小生成树问题。比如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市任意两个之间都能够通信，但铺设光缆费用很高，且各个城市之间铺设光缆费用不一样；另一个目标是要使铺设光缆总费用最低。这就需要找到带权最小生成树。,59/94,1)树定义与树特征,定义3,连通且不含圈无向图称为,树,惯用,T,表示,.,树中边称为,树枝,.,树中度为,1,顶点称为,树叶,.,孤立顶点称为,平凡树,.,平凡树,图18,60/94,定理2 设,G,是含有,n,个顶点图，则下述命题等价：,1),G,是树（,G,无圈且连通）；,2),G,无圈，且有,n,-1,条边；,3),G,连通，且有,n,-1,条边；,4),G,无圈，但添加任一条新边恰好产生一个圈,;,5),G,连通，且删去一条边就不连通了（即,G,为,最,最小连通图,）；,6),G,中任意两顶点间有唯一一条路,.,61/94,2）图生成树,定义4,若,T,是包含图,G,全部顶点子图,它又是树,则称,T,是,G,生成树,.,图,G,中不在生成树边叫做,弦,.,定理3,图,G=(V,E),有生成树充要条件是图,G,是连,通证实,必要性,是显然.,62/94,63/94,（II）找图中生成树方法,可分为两种：避圈法和破圈法,A,避圈法,:,深探法和广探法,B,破圈法,64/94,A 避圈法,定理,3,充分性证实提供了一个结构图生,成树方法,.,这种方法就是在已给图,G,中，每步选出一条边使它与已选边不组成圈，直到选够,n,-1,条边为止,.,这种方法可称为“,避圈法,”或“,加边法,”,在避圈法中，按照边选法不一样，找图中生成树方法可分为两种：,深探法,和,广探法,.,65/94,a),深探法,若这么边另一端均已经有标号，就退到标号为,步骤以下：,i),在点集,V,中任取一点,u,ii),若某点,v,已得标号检,端是否均已标号.,若有边,vw,之,w,未标号,则给,w,代,v,，重复ii).,i,-1,r,点,以,r,代,v,重复ii),直到全部点得到标号为止.,给以标号0.,查一端点为,v,各边，另一,w,以标号,i,+1,，记下边,vw,.,令,例3,用深探法求出下列图10一棵生成树,图,1,9,0,1,2,3,4,5,6,7,8,9,10,11,12,13,图20,66/94,3,b),广探法,步骤以下：,i),在点集,V,中任取一点,u,ii),令全部标号,i,点集为,是否均已标号.对全部未标,号之点均标以,i,+1,记下这些,iii)对标号,i,+1,点重复步,步骤ii)，直到全部点得到,给,u,以标号0.,V,i,检验,V,i,VV,i,中边端点,边.,例4,用广探法求出下列图10一棵生成树,图,1,9,1,0,1,2,2,1,3,2,1,2,2,3,4,标号为止.,图,21,67/94,B,破圈法,相对于避圈法，还有一个求生成树方法叫做“,破圈法,”,.,这种方法就是在图,G,中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤直到图,G,中没有圈为止,.,例5,用破圈法求出,下列图一棵生成树,.,图22,68/94,B,破圈法,例6,用破圈法求出下列图另一棵生成树.,不难发觉，图生成树不是唯一.,图23,69/94,3)最小生成树与算法,介绍最小树两种算法：,Kruskal,算法,（或,避圈法,）和,破圈法,.,5,70/94,A,Kruskal,算法（或避圈法）,步骤以下：,1),选择边,e,1,，使得,w(e,1,),尽可能小；,2),若已选定边 ，则从,中选取 ，使得,:,i),为无圈图，,ii),是满足,i),尽可能小权，,3),当第,2),步不能继续执行时，则停顿,.,定理4,由,Kruskal,算法构作任何生成树,都是最小树,.,71/94,例7,用,Kruskal,算法求下列图最小树,.,在左图中 权值,最小边有 任取一条,在 中选取权值,最小边,中权值最小边有,从中选,任取一条边,会与已选边组成圈,故停顿,得,中选取在中选取,中选取,.但 与 都,图24,72/94,B,破圈法,算法2,步骤以下：,1),从图,G,中任选一棵树,T,1,.,2),加上一条弦,e,1,，,T,1,+e,1,中,马上生成一个圈.去掉此,圈中最大权边，得到新,树,T,2,以,T,2,代,T,1,重复2)再,检验剩下弦，直到全,部弦检验完成为止.,例8,用破圈法求下列图最小树.,先求出上图一棵生成树.,加以弦,e,2,得到圈,v,1,v,3,v,2,v,1,去掉最大权边,e,2,得到一棵新,树仍是原来树；,再加上弦e,7,，得到圈 v,4,v,5,v,2,v,4,去掉最大权边e,6,，得到一棵,新树；如此重复进行，直到全,全部弦均已试过,得最小树.返 回,图25,73/94,旅行售货员问题,定义6,设,G=(V,E),是连通无向图，包含图,G,每个,顶点路称为,G,哈密尔顿路,(,Hamilton,路,或,H,路,).,包含图,G,每个顶点圈，称为,G,哈密尔顿圈,(,或,Hamilton,圈,或,H,圈,).,含,Hamilton,圈图称为,哈密尔顿图,(,或,Hamilton,图,或,H,图,).,74/94,旅行售货员问题或货郎担问题,一个旅行售货员想去访问若干城镇，然后回,到出发地,.,给定各城镇之间距离后，应怎样计划,他旅行路线，使他能对每个城镇恰好经过一次,而总距离最小？,它可归结为这么,图论问题：,在一个赋权完,全图中,找出一个最小权,H,圈,称这种圈为,最优圈,.,但这个问题是,NP-hard,问题，即不存在多项式,时间算法,.,也就是说,对于大型网络,(,赋权图,),当前还,没有一个求解旅行售货员问题有效算法，所以,只能找一个求出相当好（不一定最优）解,.,75/94,一个可行方法:,是先求一个,H,圈,然后适当,修改,以得到含有较小权另,一个,H,圈,.,图26,76/94,定义7,若对于某一对,i,和,j,，有,则圈,C,ij,将是圈,C,一个,改进,.,定义8 二边逐次修正法,:,在接连进行一系列修改之后,最终得一个圈,不能,再用此方法改进了，这个最终圈可能不是最优,不过它是比很好，为了得到更高精度这个,程序能够重复几次，每次都以不一样圈开始,.,这种,方法叫做,二边逐次修正法,.,77/94,例9,对下列图,用二边逐次修正法求较优,H,圈.,较优,H,圈:,其权为,W(C,3,)=,192,图27,78/94,分析:,找出这个解好坏可用最优,H,圈权,下界与其比较而得出.即利用最小生成树可得最,优,H,圈一个下界，,方法以下,：,设,C,是,G,一个最优,H,圈，则对,G,任一顶点,v,C-v,是,G-v,路，也,G-v,是生成树.假如,T,是,G-v,最小生成树,且,e,1,是,e,2,与,v,关联边中权最小两条,边,则,w(T)+w(e,1,)+w(e,2,),将是,w(C),一个下界.,取,v=v,3,得,G-v,3,一,最小生成树(实线),其,权,w(T)=122,与,v,3,关联,权最小两条边为,w(T)+w(v,1,v,3,)+w(v,2,v,3,),=,178,.,故最优H圈权,v,1,v,3,和,v,2,v,3,故,w(C),应满足,178,w(C),192,.,返 回,79/94,1.,设某校田径选拔赛共设六个项目标比赛，即跳高，跳远，标枪，铅球，100米和200米短跑，要求每个选手至多参加三个项目标比赛。现有七名选手报名，选手所选项目如表1所表示。现在要求设计一个比赛日程安排表，使得在尽可能短时间内完成比赛,。,田径赛时间安排,练习题,80/94,表,1,参赛选手比赛项目表,81/94,82/94,附录：图论算法matlab实现,83/94,最短路问题,例 某企业在六个城市中有分企业，从,c,i,到,c,j,直接航程票价记在下述矩阵位置上。（表示无直接航路），请帮助该企业设计一张城市,c,1,到其它城市间票价最廉价路线图。,84/94,用矩阵 （为顶点个数）存放各边权邻接矩阵，行向量,pb,、,index1,、,index2,、,d,分别用来存放标号信息、标号顶点次序、标号顶点索引、最短通路值。其中分量,index2(i),存放始点到第点最短通路中第顶点前一顶点序号；,d(i),存放由始点到第点最短通路值。,85/94,Dijkstra,Matlab,程序以下：,M=10000;,a(1,:)=0,50,M,40,25,10;,a(2,:)=zeros(1,2),15,20,M,25;,a(3,:)=zeros(1,3),10,20,M;,a(4,:)=zeros(1,4),10,25;,a(5,:)=zeros(1,5),55;,a(6,:)=zeros(1,6);,a=a+a;,86/94,pb(1:length(a)=0;,pb(1)=1;,index1=1;,index2=ones(1,length(a);,d(1:length(a)=M;d(1)=0;temp=1;,while sum(pb)=2,index=index(1);,end,index2(temp)=index;,end,d,index1,index2,88/94,Floyd,算法,Matlab,程序以下：,clear;,clc;,M=10000;,a(1,:)=0,50,M,40,25,10;,a(2,:)=zeros(1,2),15,20,M,25;,a(3,:)=zeros(1,3),10,20,M;,a(4,:)=zeros(1,4),10,25;,a(5,:)=zeros(1,5),55;,a(6,:)=zeros(1,6);,b=a+a;path=zeros(length(b);,89/94,for k=1:6,for i=1:6,for j=1:6,if b(i,j)b(i,k)+b(k,j),b(i,j)=b(i,k)+b(k,j);,path(i,j)=k;,end,end,end,end,b,path,90/94,最小生成树问题,91/94,prim,算法以下：,clc;clear;,M=1000;,a(1,2)=50;a(1,3)=60;,a(2,4)=65;a(2,5)=40;,a(3,4)=52;a(3,7)=45;,a(4,5)=50;a(4,6)=30;a(4,7)=42;,a(5,6)=70;,a=a;zeros(2,7);,a=a+a;a(find(a=0)=M;,result=;p=1;tb=2:length(a);,while length(result)=length(a)-1,temp=a(p,tb);temp=temp(:);,d=min(temp);,jb,kb=find(a(p,tb)=d);,j=p(jb(1);k=tb(kb(1);,result=result,j;k;d;p=p,k;tb(find(tb=k)=;,end,result,92/94,Kruskal,算法以下：,clc;clear;,M=1000;,a(1,2)=50;a(1,3)=60;,a(2,4)=65;a(2,5)=40;,a(3,4)=52;a(3,7)=45;,a(4,5)=50;a(4,6)30;a(4,7)=42;,a(5,6)=70;,i,j=find(a=0),b=a(find(a=0),data=i;j;b;index=data(1:2,:);,loop=max(size(a)-1;,result=;,用 存放各边端点信息，当选中某一边之后，就将此边对应顶点序号中较大序号改记为此边另一序号，同时把后面边中全部序号为改记为。此方法几何意义是：将序号这个顶点收缩到顶点，顶点不复存在。后面继续寻查时，发觉某边两个顶点序号相同时，认为已被收缩掉，失去了被选取资格。,93/94,while length(result)v2,index(find(index=v1)=v2;,else,index(find(index=v2)=v1;,end,data(:,flag)=;,index(:,flag)=;,end,result,94/94,