第8講 最短路問題實(shí)驗(yàn)

數(shù)學(xué)模型與數(shù)學(xué)實(shí)驗(yàn)

圖論模型1實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容2、會(huì)用Matlab軟件求最短路1、了解最短路的算法及其應(yīng)用1、圖論的基本概念2、最短路問題及其算法3、最短路的應(yīng)用4、實(shí)驗(yàn)作業(yè)2固定起點(diǎn)的最短路最短路是一條路徑，且最短路的任一段也是最短路．假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u(píng)0為根的樹．因此,可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路．3算法步驟：4u1u2u3u4u5u6u7u85w=[];function[l,z]=Dijkstra(W)

n=size(W,1);

fori=1:n

l(i)=W(1,i);

z(i)=1;

end

i=1;

whilei<=n

forj=1:n

6ifl(i)>l(j)+W(j,i)

l(i)=l(j)+W(j,i);

z(i)=j;

ifj<i

i=j-1;

end

end

end

i=i+1;

end

7floyd算法的基本思想8算法原理——求距離矩陣的方法9算法原理——求路徑矩陣的方法在建立距離矩陣的同時(shí)可建立路徑矩陣R．即當(dāng)vk被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求時(shí)求得，可由來查找任何點(diǎn)對(duì)之間最短路的路徑．10ij算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：11算法步驟12a=[];n=size(a,1);D=a;path=zeros(n,n);fori=1:n

forj=1:n

ifD(i,j)~=inf

path(i,j)=j;%j是i的后續(xù)點(diǎn)

end

endendfork=1:n

fori=1:n

forj=1:n

ifD(i,j)>D(i,k)+D(k,j)

D(i,j)=D(i,k)+D(k,j);

13path(i,j)=path(i,k);

end

end

endendp=[sp];mp=sp;fork=1:n

ifmp~=ep

d=path(mp,ep);

p=[p,d];

mp=d;

endendd=D(sp,ep);path=p14一、可化為最短路問題的多階段決策問題二、選址問題1、中心問題2、重心問題15例：企業(yè)要制定一臺(tái)重要設(shè)備更新的五年計(jì)劃，目標(biāo)是使總費(fèi)用（購置費(fèi)用和維修費(fèi)用之和）為最小。此設(shè)備在各年初價(jià)格及使用期中所需維修數(shù)據(jù)如下：16解：用點(diǎn)vi表示年初。（i=1,2,…6），v6表示第五年底。弧aij=（vi，vj）表示第i年初購置設(shè)備使用到第j年初的過程。對(duì)應(yīng)的權(quán)期間發(fā)生的購置費(fèi)用和維修費(fèi)用之和。原問題轉(zhuǎn)變?yōu)閺膙1到v6的一條最短路。17v1v2v3v4v5v616221817171630415931234130222318

選址問題--中心問題19S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故應(yīng)將消防站設(shè)在v3處。20

選址問題--重心問題21實(shí)驗(yàn)作業(yè)

可在下面兩個(gè)題中任選其一1.下表為某工程的全部工序以及工序時(shí)間與緊前工序，工序ABCDEFGHIJK工序時(shí)間（天）247310243232緊前工序/AAABC,D,KE,FDHG,IB請(qǐng)完成以下問題：1）.給出工程網(wǎng)絡(luò)圖；2）.計(jì)算完成整個(gè)工程至少需要多少天（總工期）。3）.請(qǐng)問不誤總工期的前提下，工程H可否延誤？最多能夠延誤多少天？222、選址問題