2011高教社杯全国大学生数学建模竞赛B题论文设计

wordwordPAGEPAGE10/14摘要本文就某市的实际情况与需求，合理的建立了有关交巡警服务平台设置与调度的模型，通过图论模型、规划模型以与计算机程序的结合，对题中所述问题进展了求解，获得了比拟满意的结果。对于问题一，首先将出警时间的约束转换为距离约束，分别利用朴素的覆盖点集以与微变量逐次调控的方法，得出了该问题的预分配方案以与最后的优化方案。0-1match来标记每个交巡警服务平台是否参与道路的封锁。如此当封锁路口时，需要全部13MATLAB得目标函数为：maxi

[cost(i,j)match(i,j)]}，得到一个最优的调度方案，封堵j1完成的最短时间约为8分钟。第三个子问题作为对第一个子问题的优化补充，我们基于前面的结果对各站点的工作量进展尽量的均衡分配，根据再分配的结果，在满足各个服务站点工作量平42,57,62,904务站。对于问题二，采取与问题一的第三个子问题一样的原如此和任务要求，针对全市现有的服务平台数量进展平台管辖X围的分配，分配原理与问题一的第一个子问题根本类似，只是数据规模的一个扩大问题。而在后来的模型优化过程中，我们引入人口密度的因素，对现有服务平台管辖X围进展重新分配。并利用工作量的均衡性来度量设置方案合理性。最后，对于问题二的最后一个子问题，我们建立了最优围堵方案模型。考虑到警力根底上改良方案，在那些未被围住的点继续以3的围堵方案。关键词：0-1规划变量微调工作量均衡度一、问题重述X试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：〔111A20XX3对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进13路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际25〔2〕针对全市的具体情况，按照设置交巡警服务平台的原如此和任务，分解决方案。P3源的最优围堵方案。二、问题假设每个交巡警平台的职能与警力的配置一样；不考虑警车启动与停止，路上受到阻碍所花费的时间；假设巡警都按最短路径到达各案发路口；假设犯罪案件都在路口上发生；道路均为双向；假设城区内道路无限速；假设犯罪案件不会在同一时间内发生多起；交巡警服务平台的节点的犯罪案件的解决不花费时间；假设犯罪车辆逃跑与警车的追赶速度一样；三、符号说明s1v1v：嫌疑人逃跑的平均速度；20t：警车到达案发路口的时间限制；0li：各点到管辖它的交巡警平台的距离；：各点的发案率；z：各节点到管辖它的交巡警服务平台的距离；ixiiyiid：两节点之间的距离；cost〔i，j：i，j四、模型预处理〔1〕交巡警服务平台的管辖X围：3点。由于警车的时速均衡且为60km/h，所以可以将时间限制转换为距离限制，由于s1

vt1

，可求出交巡警在时间限制内管辖X围的最大半径为3km。为了2〔2〕交巡警服务平台布置的合理性：A区不同地域节点的密度不同，而且发案率也不一样，所以工作量可以表示为li与的乘积，Ali

X围以交点为单位，按照工作量均优均衡状态。五、问题一的解决由于两节点间的距离公式为：d

C(xx)2(yy)2(xx)2(yy)2i j i j交巡警服务可管辖的节点编号平台编号1424344636465666768697071727374757677787980818283240414243446465666768697071727374757677783383940434454556364656667686970757645455565758606263646566676875767753032334647484950515253565758596163032474849505152535657585961730313233343546474849830313233343536374546474849525356931323334353637454610无1121252627281224252813212223241426153116323334353637454617404142434467686970717273747818426869717273747576777879808182838485868788899091921963646566676869707172737475767778798081828384858687888990919220808182838485868788899091表1对于表1，有以下四种特殊情况：X有些节点没有被交巡警服务平台所管辖；有些交巡警服务平台没有管理任何节点；3km3km。1X对于3，暂不考虑，在问题1的第三小问中解决。4，1113km1交巡警服务平台编号1可管辖的节点编号无12，28,29,38,39,61,92交巡警服务平台编号1可管辖的节点编号无238697173747578328294454556768764575860626364656654953647485051525659730328无9无10无112627122561132122232414391531163435363745461777798018无19无20818283848586878889909192表二X决。20130-1matchij0路口所花费的时间应尽可能短。当封锁路口时，需要全部13所需要的时间来决定。借助MATLAB程序〔见附录2〕来解决此问题，由上文可得目标函数为：max{ni

[cost(i,j)match(i,j)]}约束条件为：

j1每一个服务站最多出动去一个路口〔i，j每个通往其他区的路口都要有相应的服务站的警车去封锁；各节点警力到达封锁路口所花费的时间应尽可能短。C3,165,307,2910,1212,2313,2214,2115,28〔16,1419,3820,62所以结论为：1.2.6.8.9.17.18号平台的警车队没有任务，3号平台的警车队去16号节点，448号节点，530号节点，748号节点，1012号节点，11号平台的警24号节点，1223号节点，13号节点，1421号节点，152814号节点，1938号节点，20628分钟。工作量对A区20个平台的管辖X下让工作量小的服务平台分担工作量大的服务平台所管辖的路口。分成三步进展：3kmX划归到现有服务平台的管辖X围中；X上两步预处理好后，根据模型预处理的〔2〕中的公式，算出各交巡警服工作量达到最优均衡。交巡警服务平台编号可管辖的节点编号交巡警服务平台编号可管辖的节点编号1697779802717374757834455676876457606263646566549535465051525658597303233474861835363745469313410261122122713232425142115282916383940174142437072188487888990911981828320858692表三20过程分成三步进展：找出工作量较大的交巡警服务平台，找出其管辖的节点；根据附件1的图节点的实际距离小于3km；根据问题1.1和问题1.2的步骤，以交巡警服务平台与节点距离3km之内，各的节点。以上三步进展完毕后，可得到共要添加4警服务平台的节点的编号为42,57,62,90。六、问题二的解决研究交巡警服务平台设置的合理性：此题有两个判别合理性的原如此：1.警车能在3min内赶到案发节点；巡警服务平台的工作量均衡度尽量小。对1的合理性判断：区编号A交巡警3min内不能赶到的节点编号282938396192全城剩下的51.1区编号A交巡警3min内不能赶到的节点编号282938396192B122123124151152153C183199200201202203205206207208209210215238239240247248251252253257259261262263264268269285286287288299300301302303304312313314315316317318319D329330331332336337339344362369370371E387388389390391392393395407408409411412413417418419420438439443445446451452455458459464469471474486487F505506507508509510512513514515516517518519522523524525526527529533540541559560561566569574575578580表四由表四可得，共有138个节点交巡警不能在3min内赶到，数量太多。所以按原如此1，交巡警服务平台设置是不合理的。对2的合理性的判断：根据模型预处理的〔2Ai

l与问题1中的方法，可以求得各iABABiCDEF编号A编号A编号A编号A编号A编号A1i93i166i3.8320i8.7372i5.2475i13.129411.31678.332112.03734.1476133959.51684.73224.43745.547710.749611.51693.43234.23756.14789.55975.617012.93247.93762.64798.769812.117112.43252.23774.24804.77994.31728.33265.13784817.285.01004.517311.53277.63797.44824.4917410.13286.73802.54833.3101758.73816.24843.8111768.138210.34853.3121772.238310.0131783848.31417913.03859.11518013.03866.3161816.21718212.2181920表五由表五可得，交巡警服务平台工作量不均衡，其中工作量最大的是7号，工作量为40.4；101.62，置是不合理的。综上述，现有的交巡警服务平台的设置情况是较不合理的。交巡警服务平台设置的优化方案：3min务平台的工作量尽量均衡。1383min1得到新增加的最小交巡警服务台数目与其位置，从而得到优化。P点发生案件3犯罪现场的逃离方式向四周随机逃跑。由于3分钟内嫌疑人逃跑的最大距离为vtX围，而交巡警在接到报警去围堵嫌疑人时又需要花2 0费3分钟的时间。也就是说从开始逃跑到交巡警到达围堵地点的过程中，嫌疑人共有6分钟的逃跑时间，逃跑的距离为2v2

t。在警车出动围堵路口的过程中，0vt的根底上继续逃跑。为了实现成功围堵，要将嫌疑人所有2 0X可能逃跑所经过的路口。从而实现成功围堵。七、模型评价本文缺点：问题解决时的步骤过于繁琐，数据处理的工作量太大，导致结果不准确；际情况不符；居民的安全；2.2方法。本文优点：所建模型解决了交巡警服务平台的的出警问题，追捕嫌疑人的封堵路口问况有较好的参考作用。八、参考文献【1，2013/8/142C，2011【3】【3】屈婉玲，耿素云，X，2008【4】单锋，朱丽梅，田贺民，数学模型，国防工业，2012年附录附录1：#include<stdio.h>#include<stdlib.h>#include<math.h>#defineMAXSIZE#defineMAXJIEDIAN92typedefstruct{floatx[MAXSIZE];floaty[MAXSIZE];floatlast;}pingtai;typedefstruct{floatx[MAXJIEDIAN];floaty[MAXJIEDIAN];floatlast;}jiedian;voidmain(){inti;intj;intm=0;intt[92][20]={0};pingtaiM;floatxpt[20]={413,403,383.5,381,339,335,317,334.5,333,282,247,219,225,280,290,337,415,432,418,444};floatypt[20]={359,343,351,377.5,376,383,362,353.5,342,325,301,316,270,292,335,328,335,371,374,394};for(i=0;i<20;i++){M.x[i]=xpt[i];M.y[i]=ypt[i];}jiedianN;floatxjd[92]={413,403,383.5,381,339,335,317,334.5,333,282,247,219,225,280,290,337,415,432,418,444,251,234,225,212,227,256,250.5,243,246,314,315,326,327,328,336,336,331,371,371,388.5,411,419,411,394,342,342,325,315,342,345,348.5,351,348,370,371,354,363,357,351,369,335,381,391,392,395,398,401,405,410,408,415,418,422,418.5,405.5,405,409,417,420,424,438,438.5,434,438,440,447,448,444.5,441,440.5,445,444};floatyjd[92]={359,343,351,377.5,376,383,362,353.5,342,325,301,316,270,292,335,328,335,371,374,394,277,271,265,290,300,301,306,328,337,367,351,355,350,342.5,339,334,335,330,333,330.5,327.5,344,343,346,342,348,372,374,372,382,380.5,377,369,363,353,374,382.5,387,382,388,395,381,375,366,361,362,359,360,355,350,351,347,354,356,364.5,368,370,364,370,372,368,373,376,385,392,392,381,383,385,381.5,380,360};for(i=0;i<92;i++){N.x[i]=xjd[i];N.y[i]=yjd[i];}for(i=0;i<92;i++)//外层循环节点for(j=0;j<20;j++)//内层循环平台if(sqrt((N.x[i]-M.x[j])*(N.x[i]-M.x[j])+(N.y[i]-M.y[j])*(N.y[i]-M.y[j]))<30)//判断是否小于三千米t[i][j]=1;//三千米以内置为1for(j=0;j<20;j++)//循环平台数{printf("\n%d：",j+1);for(i=20;i<92;i++)//循环节点数{if(t[i][j]==1)//如果三千米以内输出该节点printf("%d",i+1);}}system("pause");}附录2：function[D,path,min1,path1]=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n);fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;end

end

endfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);end

end

end

endifnargin==3min1=D(start,terminal);m(1)=start;i=1;path1=[];whilepath(m(i),terminal)~=terminalk=k+1;m(k)=path(m(i),terminal);i=i+1;end

endm(i+1)=terminal;path1=m;%数据读取acr=xlsread('data','acr');cr=xlsread('data','cr');jd=xlsread('data','jd');mjrk=xlsread('data','mjrk');pt=xlsread('data