参考文献
[1] 姜启元，《数学模型》第四版，北京：高等教育出版社，2011年
附录
Solution.m clc;
clear all;
A=xlsread('cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls','全市交通路口节点数据','b2:c583');
X=A(:,1); Y=A(:,2);
serve_plat=xlsread('cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls','全市交巡警平台','b2:b81');
city_out=xlsread('cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls','全市区出入口的位置','b2:b18');
road_start=xlsread('cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls','全市交通路口的路线','a2:a929');
road_end=xlsread('cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls','全市交通路口的路线','b2:b929');
name=xlsread('cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls','全市交巡警平台','a2:a81');
plat_location=A(serve_plat,:); city_out_location=A(city_out,:);
plot(city_out_location(:,1),city_out_location(:,2),'*',plat_location(:,1),plat_location(:,2),'r+');
legend('全市出口位置','全市平台位置'); hold on
for i=1:length(road_start)%%%%%%plot this city's routine
plot([X(road_start(i)),X(road_end(i))],[Y(road_start(i)),Y(road_end(i))]);
end
plot(362,443,'o');
%%%%%%%%%%%%%%%%%next transform the graph into matrix%%%%%%%%%%%%%% D=ones(582);
8
for i=1:582%%%%i 表示路口的节点编号%%%%%%%%%%%% m=find(road_start==i); N=road_end(m);
D(i,N)=sqrt(abs(X(i)^2+Y(i)^2-X(N).^2-Y(N).^2)); end
D(D==1)=inf;%%%%%%%%至此矩阵生成完毕
D(logical(eye(size(D))))=0;%将对角矩阵变为0
%%%%%%%%%%look for the shortest road to the city_out for every serve_plat————useing Floyd%%%%%%%%%%%%%%%%%
m=length(serve_plat); n=length(city_out);
distance=ones(m,n);%%%%%%initial the distance Path=cell(m,n);
[Dis,path]=floyd(D); for i=1:size(Dis,1)-1 for j=i+1:size(Dis,1)
if eq(Dis(i,j),Dis(j,i))==0
Dis(i,j)=min(Dis(i,j),Dis(j,i)); Dis(j,i)=Dis(i,j); end end end
[Dis,path]=floyd(Dis); for i=1:size(Dis,1)-1 for j=i+1:size(Dis,1)
if eq(Dis(i,j),Dis(j,i))==0
Dis(i,j)=min(Dis(i,j),Dis(j,i)); Dis(j,i)=Dis(i,j); end end end
for i=1:m for j=1:n
[distance1
path1]=router(Dis,path,serve_plat(i),city_out(j));
distance(i,j)=distance1; Path(i,j)= {path1}; end end
[Matching,Cost] = Edmonds(distance); [m n]=find(Matching==1); re=[];
9
for i=1:length(m)
re=[re distance(m(i),n(i))]; end
long=max(re);
time=long*1e5/(1e6)/60; bihao=serve_plat(m); Time=re/600;
function [Matching,Cost] = Edmonds(a) Matching = zeros(size(a)); num_y = sum(~isinf(a),1); num_x = sum(~isinf(a),2); x_con = find(num_x~=0); y_con = find(num_y~=0);
P_size = max(length(x_con),length(y_con)); P_cond = zeros(P_size);
P_cond(1:length(x_con),1:length(y_con)) = a(x_con,y_con); if isempty(P_cond) Cost = 0; return end
Edge = P_cond;
Edge(P_cond~=Inf) = 0;
cnum = min_line_cover(Edge);
Pmax = max(max(P_cond(P_cond~=Inf))); P_size = length(P_cond)+cnum; P_cond = ones(P_size)*Pmax;
P_cond(1:length(x_con),1:length(y_con)) = a(x_con,y_con); exit_flag = 1; stepnum = 1; while exit_flag switch stepnum case 1
[P_cond,stepnum] = step1(P_cond); case 2
[r_cov,c_cov,M,stepnum] = step2(P_cond); case 3
[c_cov,stepnum] = step3(M,P_size); case 4
[M,r_cov,c_cov,Z_r,Z_c,stepnum] step4(P_cond,r_cov,c_cov,M);
case 5
[M,r_cov,c_cov,stepnum] = step5(M,Z_r,Z_c,r_cov,c_cov);
10
=
case 6
[P_cond,stepnum] = step6(P_cond,r_cov,c_cov); case 7
exit_flag = 0; end end
Matching(x_con,y_con) = M(1:length(x_con),1:length(y_con)); Cost = sum(sum(a(Matching==1))); function [D,path]=floyd(a)
%floyd算法通用程序，输入a为赋权邻接矩阵 %输出为距离矩阵D,和最短路径矩阵path n=size(a,1); D=a;
path=zeros(n,n); for i=1:n for j=1:n
if D(i,j)~=inf path(i,j)=j; end end end
for k=1:n for i=1:n for j=1:n
if D(i,k)+D(k,j) function [P_cond,stepnum] = step1(P_cond) P_size = length(P_cond); for ii = 1:P_size rmin = min(P_cond(ii,:)); P_cond(ii,:) = P_cond(ii,:)-rmin; end stepnum = 2; function [r_cov,c_cov,M,stepnum] = step2(P_cond) P_size = length(P_cond); r_cov = zeros(P_size,1); c_cov = zeros(P_size,1); 11