短路问题实验

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学模型与数学实验,图论模型,实验目的,实验内容,2、会用Matlab软件求最短路,1、了解最短路的算法及其应用,1、图 论 的 基 本 概 念,2、最 短 路 问 题 及 其 算 法,3、最 短 路 的 应 用,4、实验作业,固 定 起 点 的 最 短 路,最短路是一条路径，且最短路的任一段也是最短路,假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树,因此,可采用树生长的过程来求指定顶点到其余顶点的最短路,算法步骤：,u,1,u,2,u,3,u,4,u,5,u,6,u,7,u,8,w=;,function l,z=Dijkstra(W)n=size(W,1);for i=1:n l(i)=W(1,i);z(i)=1;end i=1;while il(j)+W(j,i)l(i)=l(j)+W(j,i);z(i)=j;if jD(i,k)+D(k,j),D(i,j)=D(i,k)+D(k,j);,path(i,j)=path(i,k);,end,end,end,end,p=sp;,mp=sp;,for k=1:n,if mp=ep,d=path(mp,ep);,p=p,d;,mp=d;,end,end,d=D(sp,ep);,path=p,一、可化为最短路问题的多阶段决策问题,二、选 址 问 题,1、中心问题,2、重心问题,例：,企业要制定一台重要设备更新的五年计划，目标是使总费用（购置费用和维修费用之和）为最小。此设备在各年初价格及使用期中所需维修数据如下：,解：,用点vi表示年初。（i=1,2,6），v,6,表示第五年底。弧a,ij,=（v,i,，v,j,）表示第i年初购置设备使用到第j年初的过程。对应的权期间发生的购置费用和维修费用之和。原问题转变为从v,1,到v,6,的一条最短路。,v1,v2,v3,v4,v5,v6,16,22,18,17,17,16,30,41,59,31,23,41,30,22,23,选址问题-中心问题,S(v,1,)=10,S(v,2,)=7,S(v,3,)=6,S(v,4,)=8.5,S(v,5,)=7,S(v,6,)=7,S(v,7,)=8.5,S(v,3,)=6,故应将消防站设在,v,3,处。,选址问题-重心问题,实验作业,可在下面两个题中任选其一,1.下表为某工程的全部工序以及工序时间与 紧前工序，,工 序,A,B,C,D,E,F,G,H,I,J,K,工序时间（天）,2,4,7,3,10,2,4,3,2,3,2,紧前工序,/,A,A,A,B,C,D,K,E,F,D,H,G,I,B,请完成以下问题：,1）.给出工程网络图；,2）.计算完成整个工程至少需要多少天（总工期）。,3）.请问不误总工期的前提下，工程H可否延误？,最多能够延误多少天？,2、选址问题,现准备在7个居民点中设置一银行，,路线与距离如下图，问设在哪个点，可使,最大服务距离最小？若设两个银行点呢？,