數(shù)學(xué)模型算法

數(shù)學(xué)模型算法TsinghuaUniversityUncertaintyTheoryLaboratory1第1頁，共16頁，2023年，2月20日，星期六TsinghuaUniversityUncertaintyTheoryLaboratory21、求距離矩陣的方法2、求路徑矩陣的方法3、查找最短路路徑的方法（一）算法的基本思想（三）算法步驟第2頁，共16頁，2023年，2月20日，星期六TsinghuaUniversityUncertaintyTheoryLaboratory3算法的基本思想第3頁，共16頁，2023年，2月20日，星期六TsinghuaUniversityUncertaintyTheoryLaboratory4算法原理——求距離矩陣的方法第4頁，共16頁，2023年，2月20日，星期六TsinghuaUniversityUncertaintyTheoryLaboratory5算法原理——求路徑矩陣的方法在建立距離矩陣的同時(shí)可建立路徑矩陣R．即當(dāng)vk被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求時(shí)求得，可由來查找任何點(diǎn)對之間最短路的路徑．第5頁，共16頁，2023年，2月20日，星期六TsinghuaUniversityUncertaintyTheoryLaboratory6ij算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：第6頁，共16頁，2023年，2月20日，星期六TsinghuaUniversityUncertaintyTheoryLaboratory7算法步驟第7頁，共16頁，2023年，2月20日，星期六自定義floyd函數(shù)function[d,r]=floyd(w)n=length(w);fori=1:nforj=1:nd(i,j)=w(i,j);r(i,j)=j;endendfork=1:nfori=1:nforj=1:nifd(i,k)+d(k,j)<d(i,j)d(i,j)=d(i,k)+d(k,j);r(i,j)=k;endendendend第8頁，共16頁，2023年，2月20日，星期六clear;w=[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];[d,r]=floyd(w)第9頁，共16頁，2023年，2月20日，星期六

選址問題--中心問題clear;w=[0,3,inf,inf,inf,inf,inf;3,0,2,inf,1.8,2.5,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,3,inf,inf;inf,1.8,2,3,0,4,inf;inf,2.5,inf,inf,4,0,1.5;inf,inf,inf,inf,inf,1.5,0];[d,r]=floyd(w)S=max(d’)%求矩陣各列的最大值s=min(S)第10頁，共16頁，2023年，2月20日，星期六TsinghuaUniversityUncertaintyTheoryLaboratory11S(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處。第11頁，共16頁，2023年，2月20日，星期六TsinghuaUniversityUncertaintyTheoryLaboratory12

選址問題--重心問題第12頁，共16頁，2023年，2月20日，星期六TsinghuaUniversityUncertaintyTheoryLaboratory13clear;w=[0,3,inf,inf,inf,inf,inf;3,0,2,inf,inf,4,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,1,inf,inf;inf,inf,2,1,0,4,inf;inf,4,inf,inf,4,0,1.5;inf,inf,inf,inf,inf,1.5,0];[d,r]=floyd(w)q=[3,2,7,1,6,1,4];fori=1:7m1=0;forj=1:7m1=m1+q(j)*d(i,j);endm(i)=m1;endmmin(m)第13頁，共16頁，2023年，2月20日，星期六TsinghuaUniversityUncertaintyTheoryLaboratory14d=

03.00005.00008.00007.00007.00008.50003.000002.00005.00004.00004.00005.50005.00002.000003.00002.00006.00007.50008.00005.00003.000001.00005.00006.50007.00004.00002.00001.000004.00005.50007.00004.00006.00005.00004.000001.50008.50005.50007.50006.50005.50001.50000m=13278709270106130ans=70第14頁，共16頁，2023年，2月20日，星期六TsinghuaUniversityUncertaintyTheoryLaboratory15實(shí)驗(yàn)八、最佳災(zāi)情巡視路線（節(jié)選部分）實(shí)驗(yàn)內(nèi)容：求出下圖中O到其它各點(diǎn)的最短路線（要求求出最短路線及其最短距離）（節(jié)選了教材上337面圖中的16個(gè)點(diǎn)