高教社杯全国大学生数学建模竞赛B题题目改变参考答案

1、交巡警服务平台的设置与调度优化分析摘 要本文综合应用了Floyd算法，匈牙利算法，用matlab计算出封锁全市的时间为1.2012小时。并在下面给出了封锁计划。为了得出封锁计划，首先根据附件2的数据将全市的道路图转为邻接矩阵，然后根据邻接矩阵采用Floyd算法计算出该城市任意两点间的最短距离。然后从上述矩阵中找到各个交巡警平台到城市各个出口的最短距离，这个最短距离矩阵即可作为效益矩阵，然后运用匈牙利算法，得出分派矩阵。根据分派矩阵即可制定出封锁计划：96-151,99-153,177-177,175-202,178-203,323-264,181-317, 325-325,328-328，38

2、6-332,322-362,100-387,379-418,483-483, 484-541,485-572。除此以外，本人建议在编号为175的路口应该设置一个交巡警平台，这样可以大大减少封锁全市的时间，大约可减少50%。关键词: Floyd算法 匈牙利算法 matlab 一、问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台

3、的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：警车的时速为60km/h, 现有突发事件，需要全市紧急封锁出入口，试求出全市所有的交巡警平台最快的封锁计划，一个出口仅需一个平台的警力即可封锁。二、模型假设1、假设警察出警时的速度相同且不变均为60。2、假设警察出警的地点都是平台处。3、假设警察接到通知后同时出警，且不考虑路面交通状况。三、符号说明及一些符号的详细解释 存储全市图信息的邻接矩阵 任意两路口节点间的最短距离矩阵 规划矩阵 两路口节点标号之间直达的距离 从路口到路口的最短距离 从号平台到号出口的最短距离 取0

4、或1，表示第号平台去封锁号出口在本文中经常用到，通常表示路口的编号，但是在，不再表示这个意思，表示第个交巡警平台，交巡警平台的标号与附件中给的略有不同，如第21个交巡警平台为附件中的标号为93的交巡警平台，本文的标号是按照程序的数据读取顺序来标注的，在此声明；表示第个出口，如：第5个出口对应于附件中的路口编号为203的出口。但在论文给出的结果中使用的是附件中给的标号。四、问题分析本题要求交巡警平台最快的封锁计划，即可以在最短的时间内完成全市的封锁。全市共有17个出口，80个交巡警平台，这就要求我们在这个80个平台中选出17个作为出警平台，使这17个出警平台比任意其他的17个出警平台都能在更短时

5、间内完成全市的封锁。那么这17个平台分别取封锁哪个出口即是我们要求的。由于出警时的速度都是60，那么本题的核心就变为了最短路问题了，有最短的路径，就会有最短的时间。但是作为一个封锁计划，一定是全市各个出警平台同时开始封锁，那么我们只需求出这17个出警平台用时最多的那个最为本题要求的封锁时间。这样我们的思路就非常明确了：首先我们先求出80个交巡警平台到每一个出口的距离，这样就有了一个的距离矩阵。然后我们开始对这80个交巡警平台进行任务分配，一个出口分一个平台，使每个平台到出口的距离之和最短。这个即匈牙利算法中的任务匹配问题了。这样问题便得到了解决。五、模型建立及求解5.1模型的准备1.为了便于分

6、析，以及给读者更直观的理解，根据附件2中的“全市交通节点数据”可以画出下图：图1 全市交通图2.将上述图转化为邻接矩阵，把数据存储在邻接矩阵中，如下矩阵所示，其中表示两路口节点标号之间直达的距离，当两路口节点标号之间有连接两点的路线时，记为两者之间的距离，若没有有连接两点的直达的路线，则记为。 5.2 问题模型建立及求解：5.2.1 模型的建立由上面的邻接矩阵，根据Floyd算法可以算出任意两个路口节点标号之间的最短距离，得到如下的距离矩阵其中表示从路口到路口的最短距离。 根据交巡警平台路口编号以及出口位置的路口编号，我们从中提取出交巡警平台与各个出口之间的距离矩阵：为方便叙述，我们在此引入矩

7、阵，与上面的矩阵具有相同的大小，即为分配矩阵。其中，取0或1，表示第号平台去封锁号出口。封锁全市的出口的所用的距离为 我们要求最短距离，所以目标函数为：由于一个出口只能由一个交巡警平台去封锁，所以应满足条件；而且一个交巡警平台只能封锁一个或者零个出口，所以应满足条件。综上，可以建立模型如下： 5.2.2 模型的求解5.2.2.1 距离矩阵的求解（Floyd算法）输入：邻接矩阵A输出：最短距离矩阵D1) 初始化：2) For k:1 to n For i:1 to n For j:1 to n If then ;3) 算法结束5.2.2.2 分配矩阵的求解本题明显是任务分配问题，所以便直接采用现

8、有的算法匈牙利算法直接求解1。输入：距离矩阵(即效益矩阵)输出：分配矩阵Step1:变换效益矩阵,使新矩阵中的每行每列至少有一个.（1）行变换:找出每行最小元素,再从该行各元素中减去这个最小元素.（2）列变换:从所得新矩阵中找出每列中的最小元素,再从该列各元素中减去这个最小元素. Step2:进行试指派,以寻找最优解.（1）逐行检查从第一行开始,如果该行只有一个零元素,就对这个零元素打上括号,划去与打括号零元素同在一列的其他零元素,如果该行没有零元素,或有两个或多个零元素（已划去的不计在内）,则转下行.打括号的意义可理解为该项任务已分配给某人.如果该行只有一个,说明只能有唯一分配.划掉同列括号

9、零元素可理解为该任务已分配,此后不再考虑分配给他人.当该行有两个或更多的零元素时,不计括号内的,其理由是至少有两个分配方案,为使以后分配时具有一定的灵活性,故暂不分配.(2）逐列检查在行检查的基础上,由第一列开始检查,如果该列只有一个零元素,就对这个零元素打括号,再划去与打括号零元素同行的其它零元素.若该列没有零元素或有两个以上零元素,则转下一列.（3）重复（1）、（2）两步后,可能出现以下三种情况: 每行都有一个零元素标出括号,显然打括号的零元素必然位于不同行不同列,因此得到最优解. 每行每列都有两个或两个以上的零,这表示对这个人可以分配不同任务中的任意一个.这时可以从所剩零元素最少的行开始

10、,比较这行各零元素所在列中元素的个数,选择零元素少的那列这个零元素打括号,划掉同行同列的其他它零元素,然后重复前面的步骤,直到所有都作了标记. 矩阵中所有零都作了标记,但标有()的元素个数少于个,则转下步.Step3:做最少的直线覆盖所有零元素,以确定该系数矩阵中能找到最多的独立0元素. 对没有（）的行打; 对打的行上所有含元素的列打; 再对打的列上有（）的行打; 重复上两步,直到过程结束; 对没有打的行划横线,对所有打的列划垂线.这就得到了能覆盖矩阵中所有元素的最少直线数.Step4:非最优阵的变换零元素的移动.（1）在没有被直线覆盖的所有元素中,找出最小元素;（2）所有未被直线覆盖的元素都

11、减去这个最小元素;（3）覆盖线十字交叉处的元素都加上这个最小元素;（4）只有一条直线覆盖的元素的值保持不变.Step5:回到Step2,反复进行,直到矩阵中每行每列都有一个打（）的元素为止,即找到最优解.通过Matlab编程，我们得到如下结果：交巡警平台路口编号封锁城市出口路口编号两者之间的距离（mm）96151136.743316999153137.77270331771770175202720.6915699178203260.9737384323264280.7569901181317389.995992532532503283280386332170.1597281322362295.

12、2729349100387192.0129215379418227.40813284834830484541270.0635828485572136.4331338479578341.7491166全部封锁的时间为上表中的最大距离（720.6915699）除以速度60 0mm/h(按比例尺等效过后的速度)，为1.2012小时，显然不合常理，通过观察上表的最后一列，我们发现720.6915699远远大于周围的数，如果能够减小这个数，那么封锁整个城市的时间就会降下来。从这个结果显示来看：在编号为175的路口应该设置一个交巡警平台，这样可以大大减少封锁全市的时间。下表给出每个出口被封锁所花费的时间：

13、出口路口位置所用封锁时间（h）1510.2279061530.22962117702021.2011532030.4349562640.4679283170.649993325032803320.28363620.4921223870.3200224180.37901448305410.4501065720.2273895780.569582六、模型的评价与推广6.1模型优点1、对题目所给数据大部分都进行了合理的应用和处理，对于实际问题理解的较为到位。2、模型建立的思路简单清晰，算法较为灵活、执行效率教高。3、模型能应用于其他种类的应急设施设置，整个模型有很好的通用性。6.2模型缺点1、在整个

14、模型中我们都把所有的平台或者出口想象成一个点，这是在显示中不可能的。2、模型中我们没有交通的堵塞的问题，认为出警速度是一致的。参考文献1 姜启元，数学模型第四版，北京：高等教育出版社，2011年附录Solution.mclc;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(cumcm

15、2011B附件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_l

16、ocation=A(city_out,:);plot(city_out_location(:,1),city_out_location(:,2),*,plat_location(:,1),plat_location(:,2),r+);legend(全市出口位置,全市平台位置);hold onfor i=1:length(road_start)%plot this citys routine plot(X(road_start(i),X(road_end(i),Y(road_start(i),Y(road_end(i);endplot(362,443,o);%next transform the

17、 graph into matrix%D=ones(582);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);endD(D=1)=inf;%至此矩阵生成完毕D(logical(eye(size(D)=0;%将对角矩阵变为0%look for the shortest road to the city_out for every serve_platuseing Floyd%m=length(serve_plat);n=length(c

18、ity_out);distance=ones(m,n);%initial the distancePath=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 endendDis,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)

19、=0 Dis(i,j)=min(Dis(i,j),Dis(j,i); Dis(j,i)=Dis(i,j); end endendfor 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; endendMatching,Cost = Edmonds(distance);m n=find(Matching=1);re=;for i=1:length(m) re=re distance(m(i),n(i);endlon

20、g=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:len

21、gth(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);

22、 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,

23、r_cov,c_cov); case 6 P_cond,stepnum = step6(P_cond,r_cov,c_cov); case 7 exit_flag = 0; end endMatching(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,和最短路径矩阵pathn=size(a,1);D=a;path=zeros(n,n);for i=1:n for j=1:n

24、 if D(i,j)=inf path(i,j)=j; end endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j) P_size; jj = 1; ii = ii+1; end if ii P_size; exit_flag = 0; end end if row = 0 stepnum = 6; zflag = 0; Z_r = 0; Z_c = 0; else M(row,col) = 2; if sum(find(M(row,:)=1) = 0 r_cov(row) = 1; zcol = find(M(row,:)=1); c_cov(zcol) = 0