数学建模～最短路问题ppt省公共课一等奖全国赛课获奖课件.pptx

最短路问题最短路问题二、最小生成树问题及其解法二、最小生成树问题及其解法三、最短路问题及其解法三、最短路问题及其解法一、图论基本概念一、图论基本概念第1页图图 论论 基基 本本 概概 念念一、一、图图 概概 念念1 1图定义图定义2 2顶点次数顶点次数 3 3子图子图二、二、图图 矩矩 阵阵 表表 示示1 1 关联矩阵关联矩阵2 2 邻接矩阵邻接矩阵返回返回第2页定义定义有序三元组有序三元组G=(V,E,)称为一个图称为一个图,假如：假如：图定义图定义第3页定义定义定义定义第4页第5页返回返回第6页顶点次数顶点次数第7页例例2 2 在一次聚会中，史密斯先生和他太太邀请四对夫妻在一次聚会中，史密斯先生和他太太邀请四对夫妻参加晚会。每个人到时候，房间里一些人都要与别一些人参加晚会。每个人到时候，房间里一些人都要与别一些人握手。当然，每个人都不会与自己配偶握手，也不会跟同握手。当然，每个人都不会与自己配偶握手，也不会跟同一个人握手两次。一个人握手两次。之后，史密斯先生问每个人和他人握了几次手，他们答案之后，史密斯先生问每个人和他人握了几次手，他们答案都不一样。那么史密斯太太和他人握了几次手呢？都不一样。那么史密斯太太和他人握了几次手呢？返回返回例例1 1 在一次聚会中，认识奇数个人人数一定是偶数。在一次聚会中，认识奇数个人人数一定是偶数。第8页由图可知，由图可知，8 8号配偶是号配偶是0 0号。号。7号配偶是号配偶是1号。号。6号配偶是号配偶是2号。号。5号配偶是号配偶是3号。号。史密斯太太是史密斯太太是4号，所以史密斯太太和他人握了号，所以史密斯太太和他人握了4次手。次手。返回返回第9页邻接矩阵邻接矩阵注：假设图为简单图注：假设图为简单图第10页返回返回第11页最最 短短 路路 问问 题题 及及 其其 算算 法法一、一、基基 本本 概概 念念二、固二、固 定定 起起 点点 最最 短短 路路三、每三、每 对对 顶顶 点点 之之 间间 最最 短短 路路返回返回第12页基基 本本 概概 念念第13页返回返回第14页返回返回求图最小生成树最惯用两种算法：求图最小生成树最惯用两种算法：（1）Prim算法算法（2）Kruskal算法算法注意：在一个加权连通图注意：在一个加权连通图G中，权最小那棵生中，权最小那棵生成树称为图成树称为图G最小生成树。最小生成树。第15页返回返回Prim算法思想：算法思想：输入加权图带权邻接矩阵输入加权图带权邻接矩阵（1）建立初始候选边集）建立初始候选边集B，；（2）从候选边中选取最短边（）从候选边中选取最短边（u,v），），；（3）调整候选边集）调整候选边集B；（4）重复（）重复（2）、（）、（3）直到）直到T含有含有n-1条边。条边。第16页Prim算法实现过程算法实现过程45231 1 1 12 3 4 58 inf 1 5439453527236第17页实现实现Prim算法算法MATLAB程序：程序：a=0 8 inf 1 5;8 0 6 inf 7;inf 6 0 9 10;1 inf 9 0 3;5 7 10 3 0;T=;e=0;v=1;n=5;sb=2:n;%1代表第一个红点，代表第一个红点，sb代表明代表明点集。点集。for j=2:n%结构初始候选边集合结构初始候选边集合 b(1,j-1)=1;b(2,j-1)=j;b(3,j-1)=a(1,j);end第18页while size(T,2)n-1 min,i=min(b(3,:);%在候选边中找最短边。在候选边中找最短边。T(:,size(T,2)+1)=b(:,i);e=e+b(3,i);v=b(2,i);v表示新涂红点。表示新涂红点。temp=find(sb=b(2,i);sb(temp)=;b(:,i)=;for j=1:length(sb)%调整候选边调整候选边 d=a(v,b(2,j);if db(3,j)b(1,j)=v;b(3,j)=d;end endend第19页Kruskal算法思想：算法思想：假设给定了一个加权连通图假设给定了一个加权连通图G，G边集合为边集合为E，顶点个，顶点个数数n，则假设最小生成树，则假设最小生成树T中边和顶点均涂为红色，其中边和顶点均涂为红色，其余为白色。初始时余为白色。初始时G中边均为白色。中边均为白色。（1）将全部顶点涂成红色；）将全部顶点涂成红色；（2）在白色边中，挑选一条权最小边，使其与红色边）在白色边中，挑选一条权最小边，使其与红色边不形成圈，将该白色边涂红。不形成圈，将该白色边涂红。（3）重复（）重复（2）直到）直到n-1条红色边，这条红色边，这n-1条红色边就条红色边就组成了最小生成树组成了最小生成树T边集合。边集合。注意：在用注意：在用Kruskal算法求最小生成树时，在第（算法求最小生成树时，在第（2）步判断是否形成圈在程序实现时比较麻烦。步判断是否形成圈在程序实现时比较麻烦。第20页实现实现Kruskal算法算法MATLAB程序：程序：%加权图存放结构采取边权矩阵加权图存放结构采取边权矩阵b(i,j)m3b=1 1 1 2 2 3 3 4 2 4 5 3 5 4 5 5 8 1 5 6 7 9 10 3;B,I=sortrows(b,3);B=B;m=size(b,2);n=5;t=1:n;k=0;T=;c=0;第21页for i=1:m if t(B(1,i)=t(B(2,i)%判断第判断第i条边是否与树中边形成条边是否与树中边形成圈。圈。k=k+1;T(k,1:2)=B(1:2,i);c=c+B(3,i);tmin=min(t(B(1,i),t(B(2,i);tmax=max(t(B(1,i),t(B(2,i);for j=1:n if t(j)=tmax t(j)=tmin;end end end if k=n-1 break;endendT,c第22页Kruskal实现过程：实现过程：初始化后排序：初始化后排序：B=1 4 1 2 2 1 3 3 4 5 5 3 5 2 4 5 1 3 5 6 7 8 9 10；第一轮：第一轮：tmin=1;tmax=4;t=1 2 3 1 5;第二轮：第二轮：tmin=4;tmax=5;t=1 2 3 1 1;第三轮：第三轮：t(1)=t(5)直接进入下一轮直接进入下一轮第四轮：第四轮：tmin=2;tmax=3;t=1 2 2 1 1;第五轮：第五轮：tmin=1;tmax=2;t=1 1 1 1 1;第23页求最短路径最惯用两种算法：求最短路径最惯用两种算法：（1）Dijkstra算法算法（2）Floyd算法算法注意：普通路径长度定义为该路径所包含全体边长注意：普通路径长度定义为该路径所包含全体边长度之和。度之和。最短路径是指在图中，从顶点最短路径是指在图中，从顶点u到顶点到顶点v路径中普通路径中普通路径长度最短路径称为路径长度最短路径称为u到到v最短路径。最短路径。第24页固固 定定 起起 点点 最最 短短 路路最短路是一条路径，且最短路任一段也是最短路最短路是一条路径，且最短路任一段也是最短路 假设在假设在u0-v0最短路中只取一条，则从最短路中只取一条，则从u0到其余到其余顶点最短路将组成一棵以顶点最短路将组成一棵以u0为根树为根树 所以所以,可采取树生长过程来求指定顶点到其余顶点最可采取树生长过程来求指定顶点到其余顶点最短路短路第25页第26页算法步骤：算法步骤：第27页 TO MATLAB(road1)第28页第29页 1 2 34 5 6 7 8返回返回第30页Dijkstra算法算法MATLAB实现：实现：w=0 2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;.8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;.inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0 n=size(w,1);w1=w(1,:);%赋初值赋初值 for i=1:n l(i)=w1(i);z(i)=1;end s=;s(1)=1;u=s(1);k=1；第31页while kl(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;end end end end l,z 第32页%求求v*ll=l;for i=1:n for j=1:k if i=s(j)ll(i)=ll(i);else ll(i)=inf;end end end第33页lv=inf;for i=1:n if ll(i)lv lv=ll(i);v=i;end end lv,v s(k+1)=v k=k+1 u=s(k)endl,z第34页每每 对对 顶顶 点点 之之 间间 最最 短短 路路1求距离矩阵方法求距离矩阵方法2求路径矩阵方法求路径矩阵方法3查找最短路路径方法查找最短路路径方法（一）算法基本思想（一）算法基本思想（三）算法步骤（三）算法步骤返回返回（二）算法原（二）算法原理理第35页算法基本思想算法基本思想返回返回第36页算法原理算法原理 求距离矩阵方法求距离矩阵方法返回返回第37页算法原理算法原理 求路径矩阵方法求路径矩阵方法在建立距离矩阵同时可建立路径矩阵在建立距离矩阵同时可建立路径矩阵R 即当即当k被插入任何两点间最短被插入任何两点间最短路径时，被统计在路径时，被统计在R(k)中，依次中，依次求求 时求得时求得 ，可由，可由 来查找来查找任何点对之间最短路路径任何点对之间最短路路径返回返回)(n nR第38页i j算法原理算法原理 查找最短路路径方法查找最短路路径方法pkp2p1p3q1q2qm则由点则由点i到到j最短路路径为：最短路路径为：返回返回第39页算法步骤算法步骤第40页 TOMATLAB(road2(floyd)返回返回第41页Folyd算法算法MATLAB实现：实现：functionD,R=floyd(a)n=size(a,1);D=afor i=1:n for j=1:n R(i,j)=j;endend第42页for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);end end end k,D,Rend 第43页在命令窗口中输入：在命令窗口中输入：a=0 9 inf 3 inf;9 0 2 inf 7;inf 2 0 2 4;3 inf 2 0 inf;inf 7 4 inf 0;floyd(a)第44页一、一、可化为最短路问题多阶段决议问题可化为最短路问题多阶段决议问题二、二、选选 址址 问问 题题1 中心问题中心问题2 重心问题重心问题返回返回第45页可化为最短路问题多阶段决议问题可化为最短路问题多阶段决议问题第46页第47页第48页返回返回第49页 选址问题选址问题-中心问题中心问题 TO MATLAB(road3(floyd)第50页S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处.返回返回第51页 选址问题选址问题-重心问题重心问题返回返回第52页试验作业试验作业 生产策略问题生产策略问题：当代化生产过程中，生产部门面临突出问题之一，便是怎样选取合理生产率.生产率过高，造成产品大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去赢利机会.可见，生产部门在生产过程中必须时刻注意市场需求改变，方便适时调整生产率，获取最大收益.某生产厂家年初要制订生产策略，已预知其产品在年初需求量为a=6万单位，并以b=1万单位/月速度递增.若生产产品过剩，则需付单位产品单位时间（月）库存保管费C2=0.2元；若产品短缺，则单位产品单位时间短期损失费C3=0.4元.假定生产率每调整一次带有固定调整费C1=1万元，问：工厂应怎样制订当年生产策略，使工厂总损失最小？返回返回第53页第54页