数学建模最短路问题课件

数学建模最短路数学建模最短路问题课件件pptppt图图 论论 的的 基基 本本 概概 念念一、一、图图 的的 概概 念念1 1图图的定的定义义2 2顶顶点的次数点的次数 3 3子子图图二、二、图图 的的 矩矩 阵阵 表表 示示1 1 关关联联矩矩阵阵2 2 邻邻接矩接矩阵阵返回返回定定义义有序三元有序三元组组G=(V,E,)称称为为一个一个图图,如果：如果：图图的定的定义义定定义义定定义义返回返回顶顶点的次数点的次数例例2 2 在一次聚会中，史密斯先生和他太太邀在一次聚会中，史密斯先生和他太太邀请请四四对对夫妻参加晚会。每个人到的夫妻参加晚会。每个人到的时时候，房候，房间间里的一些人都要与里的一些人都要与别别的一些人握手。当然，每个人都不会与自己的配偶握手，也不会跟同一的一些人握手。当然，每个人都不会与自己的配偶握手，也不会跟同一个人握手两次。个人握手两次。之后，史密斯先生之后，史密斯先生问问每个人和每个人和别别人握了几次手，他人握了几次手，他们们的答案都不一的答案都不一样样。那么史密斯太太和。那么史密斯太太和别别人握了几次手呢？人握了几次手呢？返回返回例例1 1 在一次聚会中，在一次聚会中，认识认识奇数个人的人数一定是偶数。奇数个人的人数一定是偶数。由由图图可知，可知，8 8号的配偶是号的配偶是0 0号。号。7号的配偶是号的配偶是1号。号。6号的配偶是号的配偶是2号。号。5号的配偶是号的配偶是3号。号。史密斯太太是史密斯太太是4号，所以史密斯太太和号，所以史密斯太太和别别人握了人握了4次手。次手。返回返回邻邻接矩接矩阵阵注：假注：假设图为简单图设图为简单图返回返回最最 短短 路路 问问 题题 及及 其其 算算 法法一、一、基基 本本 概概 念念二、固二、固 定定 起起 点点 的的 最最 短短 路路三、每三、每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路返回返回基基 本本 概概 念念返回返回返回返回求求图图的最小生成的最小生成树树最常用的两种算法：最常用的两种算法：（1）Prim算法算法（2）Kruskal算法算法注意：在一个加注意：在一个加权连权连通通图图G中，中，权权最小的那棵生成最小的那棵生成树树称称为图为图G的最小生成的最小生成树树。返回返回Prim算法思想：算法思想：输输入加入加权图权图的的带权邻带权邻接矩接矩阵阵（1）建立初始候）建立初始候选边选边集集B，；（2）从候）从候选边选边中中选选取最短取最短边边（u,v），），；（3）调调整候整候选边选边集集B；（4）重复（）重复（2）、（）、（3）直到）直到T含有含有n-1条条边边。Prim算法的算法的实现过实现过程程45231 1 1 12 3 4 58 inf 1 5439453527236实现实现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);endwhile 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 endendKruskal算法思想：算法思想：假假设给设给定了一个加定了一个加权连权连通通图图G，G的的边边集合集合为为E，顶顶点个数点个数n，则则假假设设最小生成最小生成树树T中的中的边边和和顶顶点均涂点均涂为红为红色，其余色，其余为为白色。初始白色。初始时时G中的中的边边均均为为白色。白色。（1）将所有的）将所有的顶顶点涂成点涂成红红色；色；（2）在白色）在白色边边中，挑中，挑选选一条一条权权最小的最小的边边，使其与，使其与红红色色边边不形成圈，将不形成圈，将该该白色白色边边涂涂红红。（3）重复（）重复（2）直到）直到n-1条条红红色色边边，这这n-1条条红红色色边边就构成了最小生成就构成了最小生成树树T的的边边集合。集合。注意：在用注意：在用Kruskal算法求最小生成算法求最小生成树时树时，在第（，在第（2）步判断是否形成圈在程序）步判断是否形成圈在程序实现时实现时比比较较麻麻烦烦。实现实现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;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,cKruskal实现过实现过程：程：初始化后排序：初始化后排序：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;求最短路径的最常用的两种算法：求最短路径的最常用的两种算法：（1）Dijkstra算法算法（2）Floyd算法算法注意：普通路径注意：普通路径长长度定度定义为该义为该路径所包含的全体路径所包含的全体边边的的长长度之和。度之和。最短路径是指在最短路径是指在图图中，从中，从顶顶点点u到到顶顶点点v的路径中普通路径的路径中普通路径长长度最短的路径称度最短的路径称为为u到到v的最短路径。的最短路径。固固 定定 起起 点点 的的 最最 短短 路路最短路是一条路径，且最短路的任一段也是最短路最短路是一条路径，且最短路的任一段也是最短路 假假设设在在u0-v0的最短路中只取一条，的最短路中只取一条，则则从从u0到其余到其余顶顶点的最短路将构成一棵以点的最短路将构成一棵以u0为为根的根的树树 因此因此,可采用可采用树树生生长长的的过过程来求指定程来求指定顶顶点到其余点到其余顶顶点的最短路点的最短路算法步算法步骤骤：TO MATLAB(road1)1 2 34 5 6 7 8返回返回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；while kl(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;end end end end l,z%求求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 endlv=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每每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路1求距离矩求距离矩阵阵的方法的方法2求路径矩求路径矩阵阵的方法的方法3查查找最短路路径的方法找最短路路径的方法（一）算法的基本思想（一）算法的基本思想（三）算法步（三）算法步骤骤返回返回（二）算法原（二）算法原理理算法的基本思想算法的基本思想返回返回算法原理算法原理 求距离矩求距离矩阵阵的方法的方法返回返回算法原理算法原理 求路径矩求路径矩阵阵的方法的方法在建立距离矩在建立距离矩阵阵的同的同时时可建立路径矩可建立路径矩阵阵R 即当即当k被插入任何两点被插入任何两点间间的最短路径的最短路径时时，被，被记录记录在在R(k)中，依次求中，依次求 时时求得求得 ，可由，可由 来来查查找任何点找任何点对对之之间间最短路的路径最短路的路径返回返回)(n nRi j算法原理算法原理 查查找最短路路径的方法找最短路路径的方法pkp2p1p3q1q2qm则则由点由点i到到j的最短路的路径的最短路的路径为为：返回返回算法步算法步骤骤 TOMATLAB(road2(floyd)返回返回Folyd算法的算法的MATLAB实现实现：functionD,R=floyd(a)n=size(a,1);D=afor i=1:n for j=1:n R(i,j)=j;endendfor 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 在命令窗口中在命令窗口中输输入：入：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)一、一、可化可化为为最短路最短路问题问题的多的多阶阶段决策段决策问题问题二、二、选选 址址 问问 题题1 中心中心问题问题2 重心重心问题问题返回返回可化可化为为最短路最短路问题问题的多的多阶阶段决策段决策问题问题返回返回 选选址址问题问题-中心中心问题问题 TO MATLAB(road3(floyd)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处.返回返回 选选址址问题问题-重心重心问题问题返回返回实验实验作作业业 生生产产策略策略问题问题：现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率.生产率过高，导致产品大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去获利的机会.可见，生产部门在生产过程中必须时刻注意市场需求的变化，以便适时调整生产率，获取最大收益.某生产厂家年初要制定生产策略，已预知其产品在年初的需求量为a=6万单位，并以b=1万单位/月速度递增.若生产产品过剩，则需付单位产品单位时间（月）的库存保管费C2=0.2元；若产品短缺，则单位产品单位时间的短期损失费C3=0.4元.假定生产率每调整一次带有固定的调整费C1=1万元，问：工厂应如何制定当年的生产策略，使工厂的总损失最小？返回返回谢谢大家！