数学建模最短路问题PPT学习教案

1、会计学1数学建模最短路问题数学建模最短路问题定义有序三元组G=(V,E, )称为一个图,如果：图的定义第1页/共53页定义定义第2页/共53页第3页/共53页返回第4页/共53页顶点的次数4()4dv5)(3)(2)(444vdvdvd第5页/共53页例2 在一次聚会中，史密斯先生和他太太邀请四对夫妻参加晚会。每个人到的时候，房间里的一些人都要与别的一些人握手。当然，每个人都不会与自己的配偶握手，也不会跟同一个人握手两次。之后，史密斯先生问每个人和别人握了几次手，他们的答案都不一样。那么史密斯太太和别人握了几次手呢？返回例1 在一次聚会中，认识奇数个人的人数一定是偶数。第6页/共53页由图可知

2、，8号的配偶是0号。7号的配偶是1号。6号的配偶是2号。5号的配偶是3号。史密斯太太是4号，所以史密斯太太和别人握了4次手。返回第7页/共53页邻接矩阵注：假设图为简单图第8页/共53页返回第9页/共53页最 短 路 问 题 及 其 算 法一、 基 本 概 念二、固 定 起 点 的 最 短 路三、每 对 顶 点 之 间 的 最 短 路返回第10页/共53页基 本 概 念第11页/共53页返回第12页/共53页返回求图的最小生成树最常用的两种算法：（1）Prim算法（2）Kruskal算法注意：在一个加权连通图G中，权最小的那棵生成树称为图G的最小生成树。第13页/共53页返回Prim算法思想：

3、输入加权图的带权邻接矩阵（1）建立初始候选边集B， ；（2）从候选边中选取最短边（u,v）， ；（3）调整候选边集B；（4）重复（2）、（3）直到T含有n-1条边。nnjia),(T),(vuTT第14页/共53页45231 1 1 12 3 4 58 inf 1 5439453527236第15页/共53页实现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 %构造初始候选边的

4、集合 b(1,j-1)=1; b(2,j-1)=j; b(3,j-1)=a(1,j);end第16页/共53页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 e

5、ndend第17页/共53页Kruskal算法思想：假设给定了一个加权连通图G，G的边集合为E，顶点个数n，则假设最小生成树T中的边和顶点均涂为红色，其余为白色。初始时G中的边均为白色。（1）将所有的顶点涂成红色；（2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红。（3）重复（2）直到n-1条红色边，这n-1条红色边就构成了最小生成树T的边集合。注意：在用Kruskal算法求最小生成树时，在第（2）步判断是否形成圈在程序实现时比较麻烦。第18页/共53页实现Kruskal算法的MATLAB程序：%加权图的存储结构采用边权矩阵b(i,j)m3b=1 1 1 2 2 3 3

6、 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;第19页/共53页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

7、 end end if k=n-1 break; endendT,c第20页/共53页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;第21页/共53页求最短路径的最常用的两种算法：（1）Dijkstra算法（2）Floyd算法

8、注意：普通路径长度定义为该路径所包含的全体边的长度之和。最短路径是指在图中，从顶点u到顶点v的路径中普通路径长度最短的路径称为u到v的最短路径。第22页/共53页固 定 起 点 的 最 短 路最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路第23页/共53页第24页/共53页算法步骤：第25页/共53页 TO MATLAB(road1)第26页/共53页第27页/共53页 1 2 34 5 6 7 8返回uuuuuuuu第28页/共53页Dijkstra

9、算法的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； 第29页/共53页while

10、 kl(u)+w(u,i) l(i)=l(u)+w(u,i); z(i)=u; end end end end l,z 第30页/共53页%求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第31页/共53页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第32页/共53页每 对 顶 点 之 间 的 最 短 路1求距离矩阵的方法2求路径矩阵的方法3查找最短路路径的

11、方法（一）算法的基本思想（三）算法步骤返回（二）算法原理第33页/共53页算法的基本思想返回第34页/共53页算法原理 求距离矩阵的方法返回第35页/共53页算法原理 求路径矩阵的方法)()0()0(ijrR, jrij)0(在建立距离矩阵的同时可建立路径矩阵R 即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径)(D)(R返回)(Rv第36页/共53页i j算法原理 查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：jqqqpppimk,21, 12返回第37页/共53页算法步骤第38页/共53页 TOM

12、ATLAB(road2(floyd)5333434331543243332344441,0646960243420256420793570RD返回第39页/共53页Folyd算法的MATLAB实现：functionD,R=floyd(a) n=size(a,1);D=afor i=1:n for j=1:n R(i,j)=j; endend第40页/共53页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 第41页/共5

13、3页在命令窗口中输入： 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)第42页/共53页最最 短短 路路 的的 应应 用用一、 可化为最短路问题的多阶段决策问题二、 选 址 问 题1 中心问题2 重心问题返回第43页/共53页可化为最短路问题的多阶段决策问题 例例 1 设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的.若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用.现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少

14、. 已知该种设备在每年年初的价格为：第一年第二年第三年第四年第五年1111121213 使用不同时间设备所需维修费为：使用年限0112233445维修费5681118第44页/共53页第45页/共53页（3）问题转化为顶点Xb1到Xrk6( )的最短路问题.五年的最优购置费为 kbrkd XX1 2 3 4 516, , , ,( )min (,)其中 d(Xb1,Xrk6( )为顶点Xb1到Xrk6( )的最短路的权.第46页/共53页返回第47页/共53页 选址问题-中心问题则kv就是要求的建立消防站的地点此点称为图的中心点中心点 TO MATLAB(road3(floyd)第48页/共5

15、3页05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .42502545 .24720375 .5710530DS(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处. 返回第49页/共53页 选址问题-重心问题返回第50页/共53页实验作业 生产策略问题：现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率.生产率过高，导致产品大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去获利