选址问题及最佳巡视路线的数学模型

end

%做n次迭代，每次迭代都更新D和path

for k=1:n

fori=1:n

for j=1:n

if D(i,k)+D(k,j)

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

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

end

end

end

end

第二问源程序：

clear;clc;

%计算任意两社区间的最短路

a=input('输入带权邻接矩阵：');

[D,path]=floyd1(a);

v=500/60;t=3;f=ones(1,24);A=zeros(24);b=ones(24,1);

for j=1:24

fori=1:24

%判断派出所j能否在3分钟内赶到事发地i

if D(i,j)<=v*t

A(i,j)=1;

end

end

end

%求能覆盖所有社区的最少派出所数量

[x,fval]=bintprog(f,-A,-b)

%求各派出所管辖社区编号

c=find(x~=0),h1=find(A(:,c(1))~=0),

h2=find(A(:,c(2))~=0),h3=find(A(:,c(3))~=0)

第三问源程序：

clear;clc;

a=input('输入带权邻接矩阵：');

[D,path]=floyd1(a);

length=size(D,1);

%连续执行30次模拟退火算法

fori=1:30

R1=inf;

%随机生成一个路线经过点的顺序

zhixu=randperm(length);

f=juli(zhixu,D);

tmax=120;tmin=0.001;down=0.95;

t=tmax;

%模拟退火开始，初始温度120，结束温度0.001，温度下降速率0.95

while t>tmin

for n=1:500

newzhixu=zhixu;

e=ceil(rand(1,2)*length);

temp=newzhixu(e(1));

newzhixu(e(1))=newzhixu(e(2));

newzhixu(e(2))=temp;

newf=juli(newzhixu,D);

ifnewf

zhixu=newzhixu;f=newf;

elseif rand

zhixu=newzhixu;f=newf;

end

end

t=t*down;

end

%把本次模拟退火求出的近似最优哈密顿圈划分成三段

[L1,L2,L3,fval]=huafen(zhixu,D);

%按最大最小化原则逐步筛选出更好的哈密顿圈

%并记录其经最佳三分法得到的三个子哈密顿圈

iffval(4)

LL1=L1;LL2=L2;LL3=L3;ffval=fval;

end

end

LL1,LL2,LL3,ffval

划分哈密顿圈的函数文件：

function [L1,L2,L3,fval]=huafen(zhixu,D)

%划分哈密顿圈

%L1,L2,L3分别为三个子圈

%fval记录三个子圈的权及其中的最大权值

i=find(zhixu==22);

ifi~=1

nzhixu(1:25-i)=zhixu(i:24);

nzhixu(26-i:24)=zhixu(1:i-1);

zhixu=nzhixu;