数学模型算法.ppt

数学模型算法
Tsinghua University
Uncertainty Theory Laboratory
*
第1页，本讲稿共16页
Tsinghua University
Uncertainty Theory 数学模型算法
Tsinghua University
Uncertainty Theory Laboratory
*
第1页，本讲稿共16页
Tsinghua University
Uncertainty Theory Laboratory
*
1、求距离矩阵的方法
2、求路径矩阵的方法
3、查找最短路路径的方法
（一）算法的基本思想
（三）算法步骤
第2页，本讲稿共16页
Tsinghua University
Uncertainty Theory Laboratory
*
算法的基本思想
第3页，本讲稿共16页
Tsinghua University
Uncertainty Theory Laboratory
*
算法原理—— 求距离矩阵的方法
第4页，本讲稿共16页
Tsinghua University
Uncertainty Theory Laboratory
*
算法原理—— 求路径矩阵的方法
在建立距离矩阵的同时可建立路径矩阵R．
即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径．
第5页，本讲稿共16页
Tsinghua University
Uncertainty Theory Laboratory
*
i
j
算法原理—— 查找最短路路径的方法
pk
p2
p1
p3
q1
q2
qm
则由点i到j的最短路的路径为：
第6页，本讲稿共16页
Tsinghua University
Uncertainty Theory Laboratory
*
算法步骤
第7页，本讲稿共16页
自定义floyd函数
function [d,r]=floyd(w)
n=length(w);
for i=1:n
for j=1:n
d(i,j)=w(i,j);
r(i,j)=j;
end
end
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)=k;
end
end
end
end
第8页，本讲稿共16页
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页
选址问题--中心问题
clear;
w=[0,3,inf,inf,inf,inf,inf;3,0,2,inf,,,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,3,inf,inf;inf,,2,3,0,4,inf;inf,,inf,inf,4,0,;inf,inf,inf,inf,inf,,0];
[d,r]=floyd(w)
S=max(d’) %求矩阵各列的最大值
s=min(S)
第10页，本讲稿共16页
Tsinghua University
Uncertainty Theory Laboratory
*
S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=, S(v5)=7, S(v6)=7, S(v7)=
S(v3)=6,故应将消防站设在v3处。
第11页，本讲稿共16页
Tsinghua University
Uncertainty Theory Laboratory
*
选址问题--重心问题
第12页，本讲稿共16页
Tsinghua University
Uncertainty Theory Laboratory
*
clear;
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,in