數(shù)學(xué)建模2011B題-交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度-程序

1、問題一(1):管轄區(qū)域的分配：求解最大結(jié)合覆蓋模型function dyt1.1disp(sprintf('正在載入相關(guān)數(shù)據(jù).');Node_data=xlsread('F:數(shù)學(xué)建模第二期培訓(xùn)第一題B2.xls',1,'b2:c93'); %載入A區(qū)路口節(jié)點(diǎn)的左邊數(shù)據(jù)Routine_data=xlsread('F:數(shù)學(xué)建模第二期培訓(xùn)第一題B2.xls',2,'a2:b144'); %載入路線節(jié)點(diǎn)標(biāo)號(hào)數(shù)據(jù)Record_data = cell(92,1); %創(chuàng)建包體，用來保存92個(gè)節(jié)點(diǎn)，每點(diǎn)的最大覆蓋區(qū)域count

2、= 0;%更急路線節(jié)點(diǎn)標(biāo)號(hào)數(shù)據(jù)創(chuàng)建鄰接矩陣for i = 1 :92 Node_index = Routine_data(find(Routine_data(:,1)=i),2); Node_index = Routine_data(find(Routine_data(:,2)=i),1);Node_index; Node_index = Node_index(find(Node_index <=92); n = length( Node_index); count = count + n; Record_datai = zeros(n,2); for j = 1 : n Record_

3、datai(j,1) = Node_index(j); Record_datai(j,2) = 100*sqrt(Node_data(i,1) - Node_data(Node_index(j),1)2+(Node_data(i,2) - Node_data(Node_index(j),2)2); endendAdjoin_matrix = zeros(count,3); % 鄰接矩陣index_adj = 1;for i = 1 :92 n1,n2 = size(Record_datai); n = n1; for j = 1 : n Adjoin_matrix(index_adj,:) =

4、 i,Record_datai(j,1),Record_datai(j,2); index_adj = index_adj + 1; endend%根據(jù)鄰接矩陣數(shù)據(jù)創(chuàng)建圖論的稀疏矩陣a1=Adjoin_matrix(:,1)'a2=Adjoin_matrix(:,2)'a3=Adjoin_matrix(:,3)'DG=sparse(a1,a2,a3);%建立稀疏矩陣，圖論求解for i=1:92 for j=1:92 if DG(i,j)=0 DG(i,j)=inf; if i=j DG(i,j)=0; end end endendfor k=1:92 for i=1:

5、92 for j=1:92 if DG(i,k)+DG(k,j)<DG(i,j) DG(i,j)=DG(i,k)+DG(k,j); end end endendPatrol_range=cell(20,1);for i=1:20 for j=1:92 if(DG(i,j)<=3000) Patrol_rangei=Patrol_rangei,j; end endendPatrol_distribution=Patrol_range; %復(fù)制原始數(shù)據(jù)Patrol_cover=cell(92,1); %定義交集Cover=;Isolated=; %定義孤立點(diǎn)for i=1:92 c=;

6、 for j=1:20 m=length(Patrol_rangej); for l=1:m if(Patrol_rangej(l)=i) c=c,j; %保存i節(jié)點(diǎn)所對(duì)應(yīng)的所有可能的交通巡警點(diǎn) end end end m=length(c); if(m>1) %如果大于1，說明有交集，先去除，不分配 Cover=Cover,i; Patrol_coveri=c; %保存交集 for k=1:m find(Patrol_distributionc(k)=i); Patrol_distributionc(k)=Patrol_distributionc(k)(find(Patrol_dist

7、ributionc(k)=i);%預(yù)分配只屬于自己的交通節(jié)點(diǎn) end end if(m=0) Isolated=Isolated,i; endendPatrol_xin=Patrol_distribution; %進(jìn)行B類節(jié)點(diǎn)的的分配for i=1:92 m=length(Patrol_coveri); Distance_linshi=; if(m>=1) for j=1:m Distance_linshi(j)=DG(i,Patrol_coveri(j); end m0=min(Distance_linshi); for k=1:20 if DG(i,k)=m0 f=k; end en

8、d Patrol_xinf=Patrol_xinf,i; endendm=length(Isolated); %對(duì)孤立點(diǎn)進(jìn)行分配for i=1:m for j=1:20 dist(j)=DG(Isolated(i),j); end m0,m1=min(dist); Patrol_xinm1=Patrol_xinm1,Isolated(i);endsave Patrol_xin.mat;問題一（2）：求解圍堵13條要道的方案程序1：！求圍堵的方案與最快時(shí)間sets: AA/1.20/; cross/1.13/; links(AA,cross): dis, x; Endsets !數(shù)據(jù)的定義部分;

9、 data:dis=22236.1516028.479286.81219293.4421096.2122501.7522893.219001.1619515.8112083.445880.93511850.114885.21720463.9214129.727388.06317394.6919197.472060321120.9717228.9317743.5810311.213982.18610309.546035.06818352.2712767.236025.56616032.1917834.9719240.5119009.3215117.2815631.928199.566093.84

10、8197.8844393.38521997.3815008.518266.85318273.4820076.2621481.7922654.4316226.9115535.348102.9764860.9767395.86935017628.1912969.636227.96716234.5917749.5219155.0618285.2411306.8710615.293182.9339421.1192475.8265255.07517658.7813000.216258.55216265.1817780.1119185.6518315.8311337.4510645.883213.5189

11、451.7042506.4115337.33214914.9410901.224159.55914166.1915036.2716441.8115571.998570.2188015.457583.09527352.7111290.2027991.72214092.519433.9432692.28212698.9114213.8415619.3814749.5610228.0310493.183060.825885.4343099.4678677.28313010.718274.2021532.5411539.1713132.0514537.5913667.769775.72210724.4

12、13492.3044725.6924199.419336.6687586.58512775.666956.679510.6937707.9189113.4568243.63514194.8615143.557911.44610149.828618.55314760.83791.3538337.29811395.035072.3323269.5574675.0953805.27418633.2319581.9112349.8114588.1813056.9119199.16011950.2814543.268685.3166882.5416477.0023591.6321781.4522730.

13、1315498.0317736.4116205.1422347.385977.0025973.2812714.942708.314905.53855002385.37222808.322375716524.916120.8217232.0121331.7911950.2806741.6623264.9665067.7416473.288358.65218049.9218916.6811484.3210147.5412191.4215358.5117029.6113298.086556.42116563.0517150.9418556.4817686.664751.8425700.5254401

14、.4729749.5735108.57911810.114543.266741.662010006.6311809.413214.9415100.3111308.2612175.024742.6553405.8775449.7618616.85321892.1114903.248161.5818168.2119970.9821376.5222549.1618657.1219523.8712091.514755.70312798.627820.52524247.1818514.4811772.8221779.4523582.2324987.7624904.2321012.1921526.8314

15、094.478366.94613699.266734.36222546.5316961.4810219.8220226.4522029.2323434.7623203.5819311.5319826.1812393.827639.28111998.615033.70926945.821213.1114471.4524478.0826280.8527686.3927602.8623010.8222319.2514886.8911065.5714179.786448.88;enddata !目標(biāo)函數(shù); min=max(links(i,j):x(i,j) * dis(i,j); !需求約束; for

16、(cross(j):sum(AA(i): x(i,j)=1); for(AA(i):sum(cross(j): x(i,j)<=1); !整數(shù)約束; for(links(i,j):bin(x(i,j);程序2：fuction zudj1.2A=zeros(20,13);for i=1:20 A(i,1)=DG(i,12); A(i,2)=DG(i,14); A(i,3)=DG(i,16); A(i,4)=DG(i,21); A(i,5)=DG(i,22); A(i,6)=DG(i,23); A(i,7)=DG(i,24); A(i,8)=DG(i,28); A(i,9)=DG(i,29)

17、; A(i,10)=DG(i,30); A(i,11)=DG(i,38); A(i,12)=DG(i,48); A(i,13)=DG(i,62);end問題一（3）：管轄區(qū)域的確定：求解集合覆蓋模型并使工作量最均衡程序1：function junheng1.2c=;for x=1:72 c(x)= fenpei(x);endc 程序2：function c=fenpei(x)disp(sprintf('正在載入相關(guān)數(shù)據(jù).');Node_data=xlsread('F:數(shù)學(xué)建模第二期培訓(xùn)第一題B2.xls',1,'b2:c93'); %載入A區(qū)路口

18、節(jié)點(diǎn)的左邊數(shù)據(jù)Routine_data=xlsread('F:數(shù)學(xué)建模第二期培訓(xùn)第一題B2.xls',2,'a2:b144'); %載入路線節(jié)點(diǎn)標(biāo)號(hào)數(shù)據(jù)load B.mat;Record_data = cell(92,1); %創(chuàng)建包體，用來保存92個(gè)節(jié)點(diǎn)，每點(diǎn)的最大覆蓋區(qū)域count = 0;%更急路線節(jié)點(diǎn)標(biāo)號(hào)數(shù)據(jù)創(chuàng)建鄰接矩陣for i = 1 :92 Node_index = Routine_data(find(Routine_data(:,1)=i),2); Node_index = Routine_data(find(Routine_data(:,2)=

19、i),1);Node_index; Node_index = Node_index(find(Node_index <=92); n = length( Node_index); count = count + n; Record_datai = zeros(n,2); for j = 1 : n Record_datai(j,1) = Node_index(j); Record_datai(j,2) = 100*sqrt(Node_data(i,1) - Node_data(Node_index(j),1)2+(Node_data(i,2) - Node_data(Node_index

20、(j),2)2); endendAdjoin_matrix = zeros(count,3); % 鄰接矩陣index_adj = 1;for i = 1 :92 n1,n2 = size(Record_datai); n = n1; for j = 1 : n Adjoin_matrix(index_adj,:) = i,Record_datai(j,1),Record_datai(j,2); index_adj = index_adj + 1; endend%根據(jù)鄰接矩陣數(shù)據(jù)創(chuàng)建圖論的稀疏矩陣a1=Adjoin_matrix(:,1)'a2=Adjoin_matrix(:,2)&#

21、39;a3=Adjoin_matrix(:,3)'DG=sparse(a1,a2,a3);%建立稀疏矩陣，圖論求解for i=1:92 for j=1:92 if DG(i,j)=0 DG(i,j)=inf; if i=j DG(i,j)=0; end end endendPatrol_range=cell(24,1);D_24=B(x,:); %B為可能的分配情況，共有48中，每次從中選取1中可能，本次選取的事第13中可能for k=1:92 for i=1:92 for j=1:92 if DG(i,k)+DG(k,j)<DG(i,j) DG(i,j)=DG(i,k)+DG(

22、k,j); end end endendfor i=1:24 for j=1:92 dist(j)=DG(D_24(i),j); end for j=1:92 if(dist(j)<=3000) Patrol_rangei=Patrol_rangei,j; end endendsave Patrol_range;%求解交集和預(yù)分配問題load Patrol_range.mat; %載入數(shù)據(jù) Patrol_distribution=Patrol_range; %復(fù)制原始數(shù)據(jù)Patrol_cover=cell(92,1); %定義交集Cover=;Isolated=; %定義孤立點(diǎn)for i

23、=1:92 c=; c2=; for j=1:24 m=length(Patrol_rangej); for l=1:m if(Patrol_rangej(l)=i) c=c,j; %保存i節(jié)點(diǎn)所對(duì)應(yīng)的所有可能的交通巡警點(diǎn) c2=c2,D_24(j); end end end m=length(c); if(m>1) %如果大于1，說明有交集，先去除，不分配 Cover=Cover,i; Patrol_coveri=c2; %保存交集 for k=1:m find(Patrol_distributionc(k)=i); Patrol_distributionc(k)=Patrol_dis

24、tributionc(k)(find(Patrol_distributionc(k)=i);%預(yù)分配只屬于自己的交通節(jié)點(diǎn) end end if(m=0) Isolated=Isolated,i; endendsave Patrol_distribution.mat; %完成預(yù)分配，對(duì)于交集和孤立交點(diǎn)另外考慮save Patrol_cover.mat; %保存交集所對(duì)應(yīng)的可能交通巡警點(diǎn)load Patrol_cover.mat;load Patrol_distribution.mat;load Patrol_range.mat;%初始化預(yù)分配中每個(gè)交通巡警點(diǎn)的發(fā)案次數(shù)Occurrence=xls

25、read('F:數(shù)學(xué)建模第二期培訓(xùn)第一題B2.xls',1,'e2:e93'); %A區(qū)每個(gè)交通節(jié)點(diǎn)的發(fā)案次數(shù)Standard_occurrence=sum(Occurrence)/24Patrol_occurrence=zeros(24,1);for i=1:24 m=length(Patrol_distributioni); a=0; if(m>=1) for j=1:m a=a+Occurrence(Patrol_distributioni(j); end Patrol_occurrence(i)=a; endendPatrol_xin=Patrol

26、_distribution; %進(jìn)行交集分配for i=1:92 m=length(Patrol_coveri); Distance_linshi=; if(m>=1) for j=1:m Distance_linshi(j)=DG(i,Patrol_coveri(j); end A=Sort_vector(Distance_linshi); %記錄最小值的相對(duì)位置 h=length(Distance_linshi); for j=1:h linshi_canshu=find(D_24=Patrol_coveri(A(j,2); Patrol_occurrence(linshi_cans

27、hu); Patrol_coveri(A(j,2); if(Patrol_occurrence(linshi_canshu)<=(Standard_occurrence+0.62) Patrol_xinlinshi_canshu=Patrol_xinlinshi_canshu,i; Patrol_occurrence(linshi_canshu)=Patrol_occurrence(linshi_canshu)+Occurrence(i); break; end if(j=h) i end end endendPatrol_occurrencec=var(Patrol_occurrenc

28、e);save Patrol_xin.mat;程序3：function chulia=1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20;I=28 29;J=38 39,40;K=48,61;L=87 88 89 90 91 92;m=0;for i=1:2 for j=1:3 for k=1:2 for l=1:6 m=m+1; B(m,:)=a,I(i) J(j) K(k) L(l); DD(m,:)=I(i) J(j) K(k) L(l); end end endendsave B;程序4：function A=Sort_vector(X

29、) %創(chuàng)建子函數(shù)供調(diào)用a=length(X);for i=1:am0,weizhi=min(X);A(i,1)=m0;A(i,2)=weizhi;X(weizhi)=inf;End問題二（1）計(jì)算現(xiàn)有節(jié)點(diǎn)工作量，不均衡度和C類節(jié)點(diǎn)個(gè)數(shù)，以判斷合理性：程序1：function Mcm2.1Node_data=xlsread('F:數(shù)學(xué)建模第二期培訓(xùn)第一題B2.xls',1,'b2:c583');Routine_data=xlsread('F:數(shù)學(xué)建模第二期培訓(xùn)第一題B2.xls',2,'a2:b929');Record_data =

30、 cell(582,1);count = 0;for i = 1 :582 Node_index = Routine_data(find(Routine_data(:,1)=i),2); Node_index = Routine_data(find(Routine_data(:,2)=i),1);Node_index; n = length( Node_index); count = count + n; Record_datai = zeros(n,2); for j = 1 : n Record_datai(j,1) = Node_index(j); Record_datai(j,2) =

31、 100*sqrt(Node_data(i,1) - Node_data(Node_index(j),1)2+(Node_data(i,2) - Node_data(Node_index(j),2)2); endendAdjoin_matrix = zeros(count,3); % 鄰接矩陣index_adj = 1;for i = 1 :582 n1,n2 = size(Record_datai); n = n1; for j = 1 : n Adjoin_matrix(index_adj,:) = i,Record_datai(j,1),Record_datai(j,2); index_

32、adj = index_adj + 1; endend%創(chuàng)建圖論的稀疏矩陣及其圖論的求解a1=Adjoin_matrix(:,1)'a2=Adjoin_matrix(:,2)'a3=Adjoin_matrix(:,3)'DG=sparse(a1,a2,a3);%建立稀疏矩陣，圖論求解for i=1:582 for j=1:582 if DG(i,j)=0 DG(i,j)=inf; if i=j DG(i,j)=0; end end endendfor k=1:582 for i=1:582 for j=1:582 if DG(i,k)+DG(k,j)<DG(i,j

33、) DG(i,j)=DG(i,k)+DG(k,j); end end endendWeizhi_all=xlsread('F:數(shù)學(xué)建模第二期培訓(xùn)第一題B2.xls',3,'b2:b81');a=length(Weizhi_all);Patrol_range=cell(a,1);for i=1:a for j=1:582 dist(j)=DG(Weizhi_all(i),j);%求圖中任意兩個(gè)節(jié)點(diǎn)之間的最短距離 end for j=1:582 if(dist(j)<=3000) Patrol_rangei=Patrol_rangei,j; end enden

34、dsave Patrol_range;load Patrol_range.mat; %載入數(shù)據(jù)Patrol_distribution=Patrol_range; %復(fù)制原始數(shù)據(jù)Patrol_cover=cell(582,1); %定義交集Cover=;Isolated=; %定義孤立點(diǎn)a=length(Weizhi_all);for i=1:582 c=; c2=; for j=1:a m=length(Patrol_rangej); for l=1:m if(Patrol_rangej(l)=i) c=c,j; %保存i節(jié)點(diǎn)所對(duì)應(yīng)的所有可能的交通巡警點(diǎn) c2=c2,Weizhi_all(j)

35、; end end end m=length(c); if(m>1) %如果大于1，說明有交集，先去除，不分配 Cover=Cover,i; Patrol_coveri=c2; %保存交集 for k=1:m find(Patrol_distributionc(k)=i); Patrol_distributionc(k)=Patrol_distributionc(k)(find(Patrol_distributionc(k)=i);%預(yù)分配只屬于自己的交通節(jié)點(diǎn) end end if(m=0) Isolated=Isolated,i; endendsave Patrol_distribut

36、ion.mat;%完成預(yù)分配，對(duì)于交集和孤立交點(diǎn)另外考慮save Patrol_cover.mat;%保存交集所對(duì)應(yīng)的可能交通巡警點(diǎn)load Patrol_cover.mat;load Patrol_distribution.mat;load Patrol_range.mat;%初始化預(yù)分配中每個(gè)交通巡警點(diǎn)的發(fā)案次數(shù)Occurrence=xlsread('F:數(shù)學(xué)建模第二期培訓(xùn)第一題B2.xls',1,'e2:e583'); %A區(qū)每個(gè)交通節(jié)點(diǎn)的發(fā)案次數(shù)a=length(Weizhi_all);Standard_occurrence=sum(Occurrence

37、)/asum(Occurrence);Patrol_occurrence=zeros(a,1);for i=1:a m=length(Patrol_distributioni); a=0; if(m>=1) for j=1:m a=a+Occurrence(Patrol_distributioni(j); end Patrol_occurrence(i)=a; endendPatrol_xin=Patrol_distribution; %進(jìn)行交集的分配for i=1:582 m=length(Patrol_coveri); Distance_linshi=; if(m>=1) fo

38、r j=1:582 dist(j)=DG(i,j); end for j=1:m Distance_linshi(j)=dist(Patrol_coveri(j); end A=Sort_vector(Distance_linshi); %記錄最小值的相對(duì)位置 h=length(Distance_linshi); for j=1:h linshi_canshu=find(Weizhi_all=Patrol_coveri(A(j,2); Patrol_occurrence(linshi_canshu); Patrol_coveri(A(j,2); if(Patrol_occurrence(lin

39、shi_canshu)<=(Standard_occurrence+8.5) Patrol_xinlinshi_canshu=Patrol_xinlinshi_canshu,i; Patrol_occurrence(linshi_canshu)=Patrol_occurrence(linshi_canshu)+Occurrence(i); break; end if(j=h) i; end end endend%對(duì)孤立點(diǎn)進(jìn)行分配m=length(Isolated);for i=1:m for j=1:20 D(j)=DG(Isolated(i),j); end Isolated(i);

40、m0,m1=min(D); m1; Patrol_xinm1=Patrol_xinm1,Isolated(i); Patrol_occurrence(m1)=Patrol_occurrence(m1)+Occurrence(Isolated(i);endPatrol_occurrence; %每個(gè)警力點(diǎn)的工作量length(Patrol_occurrence);var(Patrol_occurrence)a,b=max(Patrol_occurrence);zuidazhi=a;b;Weizhi_all(b);save Patrol_xin.mat;程序2：！建立01矩陣function jl

41、jz2.1AG=zeros(138,502);for i=1:138 for j=1:502 dist(j)=DG(lsolated(i),j); if(dist(j)<=3000) AG(i,j)=1; end endend程序3：function chulia=1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20;I=28 29;J=38 39,40;K=48,61;L=87 88 89 90 91 92;m=0;for i=1:2 for j=1:3 for k=1:2 for l=1:6 m=m+1; B(m,:)=a,I(i) J

42、(j) K(k) L(l); DD(m,:)=I(i) J(j) K(k) L(l); end end endendsave B;程序4：function A=Sort_vector(X) %創(chuàng)建子函數(shù)，共調(diào)用使用a=length(X);for i=1:am0,weizhi=min(X);A(i,1)=m0;A(i,2)=weizhi;X(weizhi)=inf;endlingo程序：程序5：！靜態(tài)增加服務(wù)臺(tái)的方案求解：sets: AA/1.138/; cross/1.502/:x; links(AA,cross): a; Endsets data: a = FILE(F:數(shù)學(xué)建模第二期培訓(xùn)第

43、一題新建文件夾第二問選擇表.xls); TEXT('result1.txt') = x; enddata 27 程序6：！動(dòng)態(tài)的求解方案：sets: AA/1.582/; cross/1.582/:x; links(AA,cross): a; Endsets data: a = FILE(F:數(shù)學(xué)建模第二期培訓(xùn)第一題新建文件夾第二問data3.txt); TEXT('result7.txt') = x; enddata min =sum(AA(i):if(sum(cross(j):a(i,j)*x(j)#eq#0,1,0); sum(cross(j): x(j)=80; for(cross(i):bin(x(i);問題二（2）：求解最佳圍堵方案程序1：% function weidu%找出最佳的圍堵方案clear;load DG.mat;load Xunjinwz1.mat;xun_gs = length(Xunjinwz);dist=graphshortestpath(DG,32);%求圖中任意個(gè)節(jié)點(diǎn)到案發(fā)點(diǎn)的最短距離for t = 6:30 Anfadian=; for j = 1 :582 if(dist(j) <= t*1000 & (t - 1)*1000 <=dist(j) ) Anfadian=Anfadia