附录一：Matlab程序
%dijkstra.m
function [d,path]=dijkstra(b,s,t) [n,m]=size(b);ix=(b==0);
visited(1:n)=0;dist(1:n)=inf;parent(1:n)=0;dist(s)=0;d=inf;
for i=1:(n-1)
ix=(visited==0);vec(1:n)=inf;vec(ix)=dist(ix); [a,u]=min(vec);visited(u)=1; for v=1:n
if (b(u,v)+dist(u) dist(v)=dist(u)+b(u,v);parent(v)=u; end end end if parent(t)~=0 path=t;d=dist(t); while t~=s p=parent(t);path=[p,path];t=p; end end %主程序 clear,clc format short g a=inf*ones(53); a(1,[18 18+33 18+34 18+1 2])=[8.8 7.4 11.5 10.3 12.2]; a(2,[1 18+34 3 18+1])=[12.2 17.6 11.0 5.9]; a(3,[2 18+3 15 18+1])=[11.0 7.9 11.5 11.2]; a(4,[18+5 18+3 18+4 18+7])=[11.3 8.2 12.7 15.1]; a(5,[18+11 18+7 18+8 18+9])=[14.2 7.2 8.0 7.8]; a(6,[18+12 18+9 18+10])=[12.2 5.6 10.8]; a(7,[18+13 18+11 18+12])=[8.6 6.8 7.8]; a(8,[18+14 18+12])=[9.9 10.2]; a(9,[18+15 18+16 18+18 10 18+13])=[8.8 11.8 8.2 15.8 16.4]; a(10,[18+13 9 18+18 18+19 18+11])=[9.8 15.8 8.2 8.1 13.2]; a(11,[18+17 18+22 18+21 18+18])=[9.8 10.1 4.1 9.2]; a(12,[18+19 18+20 18+6 18+7])=[7.2 5.5 11.8 14.5]; a(13,[18+25 14 15 18+5 18+6])=[12.0 14.2 19.8 11.4 9.5]; a(14,[18+23 18+24 18+26 13 18+25])=[7.9 13.2 10.5 14.2 8.8]; a(15,[13 16 18 18+1 3 18+2])=[19.8 10.1 12.9 6.0 11.5 9.2]; a(16,[18+26 18+28 18+29 15])=[10.5 12.1 15.2 10.1]; a(17,[18+28 18+30 18+29])=[8.3 7.7 7.2]; a(18,[18+29 18+31 1 15])=[7.9 9.2 8.8 12.9]; a(19,[15 1 2 3])=[6.0 10.3 5.9 11.2]; a(20,[18+5 15 18+3])=[8.3 9.2 4.8]; a(21,[18+2 3 4])=[4.8 7.9 8.2]; a(22,[4 18+8])=[12.7 20.4]; a(23,[18+6 13 18+2 4])=[9.7 11.4 8.3 11.3]; a(24,[12 13 18+5 18+7])=[11.8 9.5 9.7 7.3]; a(25,[12 18+6 4 5])=[14.5 7.3 15.1 7.2]; a(26,[5 18+4])=[8.0 20.4]; a(27,[6 5])=[5.6 7.8]; a(28,6)=10.8; a(29,[7 10 5])=[6.8 13.2 14.2]; a(30,[8 7 6])=[10.2 7.8 12.2]; a(31,[18+14 9 10 7])=[8.6 16.4 9.8 8.6]; a(32,[8 18+15 18+13])=[9.9 15 8.6]; a(33,[18+14 9])=[15 8.8]; a(34,[18+17 9])=[6.8 11.8]; a(35,[18+22 11 18+16])=[6.7 9.8 6.8]; a(36,[10 9 11])=[8.2 8.2 9.2]; a(37,[10 18+20 12])=[8.1 9.3 7.2]; a(38,[18+21 18+19 18+25 12])=[7.9 9.3 6.5 5.5]; a(39,[11 18+23 18+25 18+20])=[4.1 9.1 7.8 7.9]; a(40,[18+17 11 18+23])=[6.7 10.1 10.0]; a(41,[18+21 18+22 18+24 14])=[9.1 10.0 8.9 7.9]; a(42,[18+23 14 18+27])=[8.9 13.2 18.8]; a(43,[18+20 18+21 14 13])=[6.5 7.8 8.8 12.0]; a(44,[14 18+27 16])=[10.5 7.8 10.5]; a(45,[18+24 18+26 18+28])=[18.8 7.8 7.9]; a(46,[18+27 16 17])=[7.9 12.1 8.3]; a(47,[16 17 18])=[15.2 7.2 7.9]; a(48,[17 18+32])=[7.7 10.3]; a(49,[18 18+32 18+33])=[9.2 8.1 7.3]; a(50,[18+30 18+31 18+35 18+33])=[10.3 8.1 14.9 19]; a(51,[18+31 18+32 18+35 1])=[7.3 19 20.3 7.4]; a(52,[2 1 18+35])=[17.6 11.5 8.2]; a(53,[18+34 18+33 18+32])=[8.2 20.3 14.9]; e=a(15,:);a(2:15,:)=a(1:14,:);a(1,:)=e;f=a(:,15);a(:,2:15)=a(:,1:14);a(:,1)=f; a1=tril(a);a2=triu(a);a2_zhuanzhi=a2';duicheng_yanzheng=a1-a2_zhuanzhi; b=a;zdjl=zeros(53);path=zeros(53,11);jl_path=zeros(53,12); for m=1:length(b) for n=1:length(b) zdjl(m,n)=dijkstra(b,m,n); if m==n zdjl(m,n)=0; end if m==1&&n>1 [zdjl(m,n) p]=dijkstra(b,m,n); path(n,1:length(p))=p; end end end jl_path=[[1:53]' zdjl(:,1) path] zdjl %画最小生成树的程序 a1=1;b1=4;w1=11.5; a2=[1 20 21 5 20 23 24 13 37 11 31 24 25 6 6 29 6 27 7 7 30]; b2=[20 21 5 22 23 24 13 37 11 31 32 25 6 26 29 8 27 7 28 30 9]; w2=[9.2 4.8 8.2 12.7 8.3 9.7 11.8 7.2 8.1 9.8 8.6 7.3 7.2 8.0 14.2 6.8 7.8 5.6 10.8 12.2 10.2]; a3=[1 14 43 43 39 12 35 12 36 10];b3=[14 43 38 39 12 35 34 36 10 33]; w3=[19.8 12.0 6.5 7.8 4.1 9.8 6.8 9.2 8.2 8.8]; a4=[1 16 16 44 44 15 15 41 ];b4=[16 46 44 45 15 42 41 40]; w4=[10.1 12.1 10.5 7.9 10.5 13.2 7.9 10.0]; a5=[1 18 47 17 18 49];b5=[18 47 17 48 49 50];w5=[7.9 7.9 7.2 7.7 9.2 8.1]; a6=[1 19 19 2 2 52];b6=[19 3 2 51 52 53];w6=[6.0 7.9 10.3 7.4 11.5 8.2]; R=sparse([a1 a2 a3 a4 a5 a6],[b1 b2 b3 b4 b5 b6],[w1 w2 w3 w4 w5 w6]); R(53,53)=0;h=view(biograph(R,[],'ShowWeights','on')); %第一问程序 zdjl_12=zdjl([1 4 5 6 7 8 9 11 13 20:32 37],[1 4 5 6 7 8 9 11 13 20:32 37]); zdjl_34=zdjl([1 10 12 14 15 16 33:36 38:46],[1 10 12 14 15 16 33:36 38:46]); zdjl_56=zdjl([1 2 3 17 18 19 47:53],[1 2 3 17 18 19 47:53]); zdjl_12_1=zdjl([1 6 7 8 9 11 13 20 23:32 37],[1 6 7 8 9 11 13 20 23:32 37]); zdjl_56_1=zdjl([1 2 3 4 5 17 18 19 21 22 47:53],[1 2 3 4 5 17 18 19 21 22 47:53]); zdjl_12_tzh=zdjl([1 6 7 8 9 20 23:32],[1 6 7 8 9 20 23:32]); zdjl_34_tzh=zdjl([1 10 11 12 13 14 15 16 33:37 38:45],[1 10 11 12 13 14 15 16 33:37 38:45]); zdjl_56_tzh=zdjl([1 2 3 4 5 17 18 19 21 22 46:53],[1 2 3 4 5 17 18 19 21 22 46:53]); %第二问程序 zdjl_1=zdjl([1 2 3 4 17 18 19 47:53],[1 2 3 4 17 18 19 47:53]); zdjl_2=zdjl([1 12 15 16 34 35 39:46],[1 12 15 16 34 35 39:46]); zdjl_3=zdjl([1 8 10 11 13 14 24 29 31 32 33 36 37 38],[1 8 10 11 13 14 24 29 31 32 33 36 37 38]); zdjl_4=zdjl([1 5 6 7 9 20:23 25:28 30],[1 5 6 7 9 20:23 25:28 30]); zdjl_1_tzh=zdjl([1 2 3 4 17 18 19 47:53],[1 2 3 4 17 18 19 47:53]); zdjl_2_tzh=zdjl([1 12 14 15 16 34 35 39:46],[1 12 14 15 16 34 35 39:46]); zdjl_3_tzh=zdjl([1 8 10 11 13 23 24 29 31 32 33 36 37 38],[1 8 10 11 13 23 24 29 31 32 33 36 37 38]); zdjl_4_tzh=zdjl([1 5 6 7 9 20:22 25:28 30],[1 5 6 7 9 20:22 25:28 30]); %第三问程序 [jl index]=sort(zdjl(:,1));jl_index=[jl index] sj=[2*77.5/35+2;2*72.7/35+1+1;(69.9+8.8+11.8+60.3)/35+1+1;(67.3+12.2+5.6+49.5)/35+1+1; (65.9+10.8+5.6+7.8+8.0+49.7)/35+1+1;2*62.7/35+2;2*61.1/35+2;2*55.9/35+1+1+1; 2*55.1/35+2+1;2*54.3/35+1+2;2*53.5/35+1+2;(52.9+9.2+4.1+7.9+38.3)/35+1+1+1;(49+10.0+8.9+44.3)/35+1+1; (41.7+8+12.3+8.1+34.9)/35+2+1;(39+11.8+9.5+19.8)/35+2+2;(36+8.2+11.5+7.4+23.7)/35+1+1+1;2*35.7/35+1+2+1;(31.8+8.8+10.5+20.6)/35+1+2+1; (30.2+8.1+9.2+12.9)/35+1+1+2;(28.4+7.9+12.1+10.1)/35+1+1+2;(22.2+8.2+7.9+11.5)/35+2+2;(16.3+12.2+5.9+6.0)/35+2+2+1; (9.2+4.8+4.8+8.3+11.4+14.2+7.9+39)/35+1+1+1]; SJ=[round(sj) round(60*rem(sj,1))] %第四问程序 T=0.1:0.1:6;t=0.1:0.1:6;V=3.1:1:60; sj_max_T=max([5*T+8+136.5/35;4*T+10+154.3/35;4*T+9+179.2/35;4*T+8+198.2/35]); sj_max_t=max([5*2+8*t+136.5/35;4*2+10*t+154.3/35;4*2+9*t+179.2/35;4*2+8*t+198.2/35]); sj_max_V=max([5*2+8+136.5./V;4*2+10+154.3./V;4*2+9+179.2./V;4*2+8+198.2./V]); plot(T,sj_max_T,'m',t,sj_max_t,'g',V/10,sj_max_V,'b');grid on legend('最短巡视时间随T的变化曲线','最短巡视时间随t的变化曲线','最短巡视时间随V的变化曲线'); xlabel('T（小时） t（小时） V（10千米/小时)');ylabel('最短巡视时间(小时)'); title('最短巡视时间随T,t和V的变化曲线');hold on h=stem([1 2 3.5],[22.409 22.409 22.409],'fill','-.'); set(get(h,'BaseLine'),'LineStyle',':'); set(h,'MarkerFaceColor','red'); 附录二：Lingo程序 model: sets: city/1..53/:u; link(city,city): dist, x; endsets n=@size(city); data: !只需输入最短路矩阵 enddata min=@sum(link:dist*x); @for(city(k): @sum(city(i)|i#ne#k:x(i,k))=1; @sum(city(j)|j#ne#k:x(k,j))=1; ); @for(city(i)|i#gt#1: @for(city(j)|j#gt#1#and#i#ne#j: u(i)-u(j)+n*x(i,j)<=n-1); ); @for(city(i)|i#gt#1:u(i)<=n-2); @for(link:@bin(x)); end