乔女--之恋
B题 交巡警服务平台的设置与调度 两点之间距离计算matlab程序 
城市交通巡警平台的设置与调度摘要：关键字：最短路径、效率最高、动态规划、surfer作图、一．问题的重述警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源。就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题的分析 问题一中有三个小问题，分别讨论在现有巡警台不变的情况下，确定出每个巡警台的控制范围，要求在三分钟之内尽可能到达；当有案件发生时，各交巡警按预定的路线到达指定路口封锁该路口，要求我们给出各节点接到指示时他们的行车路线；根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。根据给出的地图和其他数据，运用matlab软件使用Dijkstra算法以及floyd算法，确定出了最短路径，从而可以计算得出每个巡警台所能控制的范围。不仅仅要考虑运行路线的最短和优化性，还要考虑时间尽可能较少的优化。问题二三．基本假设不考虑巡警在实际工作中所出现的故障而导致延误追捕。假设各站点的警力量是平均一致且为一固定值（巡警台人数高峰期和低潮期的平均值为单一均值）。在整个路途中，通过各种通讯工具，走的路程都是最短路程。不考虑巡警车在行驶过程中出现的塞车、抛锚等耽误时间的情况。不考虑警员所消耗的时间。在整个路途中，转弯处不需要花费时间假设逃犯与警察的速度是相同的。假设路径是单向的。变量说明： ： 任意两个标志点 与 间的距离 ： 标志点间的距离组成的距离矩阵 ： 标志点的邻接矩阵 ： 邻接矩阵的元素。 ： 相邻标志点间的距离矩阵。 ： 相邻标志点 与 间的距离 ： 标志点的权值矩阵 ： 标志点间的最短距离矩阵 ： 标志点 与 之间的最短距离。 ： 恒定车速 ： 图中标数与实际比例T： 出警所用最大时间V： 接到报警到到达出事地点所用最大时间L(θ)： 从交巡警平台到达出事地块所行驶的最大路程四、模型定义Dijksta算法：设G=(V，E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 ， 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度⑴。最优化问题：采用问量表示法，例如前面例子中的（H）可以看做是二维问题中的一个向量区的两个分量，即 或 对于n维向量空间Rn中一个向量X的n个分量，即 或 于是前面所描述的求极小值问题可以简记为：minf(X)这里的f(X)称为向量变量的实值函数。设有L个向量变量的实值函数：h1(X)， h2(X)， …，hL(X)给定X后，又可以把这L个实值函数看做是L维空间RL中的一个向量h(X)的L个分量，记为：h(X)=[ h1(X)， h2(X)， …，hL(X)]T。按照这种表示方法，具有L个等式约束的求极小问题可记为： (1-1)其中是subject to 缩写，表示“满足于”，“受…约束”最优化问题有如下形式：一般式： (1-2)向量式： (1-3)式中f(X)称为目标函数(或求它的极小，或求它的极大)。优化过程就是优选X，使目标函数达到最优值：f(X)->Optimizationsi(X)称为不等式约束，它的向量表示法可以写成：s(X)=[ s1(X)， s2(X)， …，sm(X)]Thj(X)称为等式约束X∈Ω，称为集约束，在我们的问题中集约束是无关重要的，这是因为有时Ω≡Rn，不然的话，Ω也可以用不等式约束表达出来，如：对 ，其中 ，此时集约束可以用不等式来代替，如 故今后不再考虑集约束。例如：前面例子球铸成圆柱体， 这个问题的集约是： 实际上都可以用不等式约束来代替： 则 floyd算法： 1，从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。 2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。 3，不可思议的是，只要按排适当，就能得到结果。邻接矩阵：邻接矩阵（Adjacency Matrix）：是表示顶点之间相邻关系的矩阵。设G=(V，E)是一个图，其中V={v1，v2，…，vn}。G的邻接矩阵是一个具有下列性质的n阶方阵： ①对无向图而言，邻接矩阵一定是对称的，而且对角线一定为零，有向图则不一定如此。 ②在无向图中，任一顶点i的度为第i列所有元素的和，在有向图中顶点i的出度为第i行所有元素的和，而入度为第i列所有元素的和。③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。 五．模型的建立与求解对于问题一，模型求解：根据我们建立的模型，我们进行了编程，主要代码如下：（1）Dijkstra算法的C++代码：#includevoid main(){ int infinity=100，j，i，n，k，t，**w，*s，*p，*d; cout<<"input the value of n:"; cin>>n; cout<>w[i][j]; for(s[0]=1，i=1;id[k]+w[k][j])) {d[j]=d[k]+w[k][j];p[j]=k;} } cout<<"从源点到其它顶点的最短距离依次如下："; for(i=1;i#include using namespace std; #define MAX_VERTEX_NUM 10 //最大顶点个数#define TRUE 1#define FALSE 0#define INFINITY 32767 /* 用整型最大值代替∞ */typedef char VERTYPE;typedef struct{ VERTYPE vexs[MAX_VERTEX_NUM]; //顶点向量 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum，arcnum; //图的当前顶点数和弧数}mgraph， * MGraph;typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //存放路径长度typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //存放路径，P[0][1][]表示顶点0到顶点1的路径，经过哪个点P[0][1][i]就是TRUE。void init_mgraph(MGraph &g) //初始化图{ g=(MGraph)malloc(sizeof(mgraph)); g->vexnum=0; g->arcnum=0; for(int i=0;ivexs[i]=0; for(i=0;iarcs[i][j]=INFINITY;}void add_vexs(MGraph &g) //增加顶点{ cout<<"请输入顶点的个数:"<>g->vexnum; cout<<"请输入顶点的值"<vexnum;i++) { cin>>g->vexs[i]; }}void add_arcs(MGraph &g) //增加边{ cout<<"请输入边的个数:"<>g->arcnum; VERTYPE ch1，ch2; int row，col，weight; for(int i=0;iarcnum;i++) { cin>>ch1>>ch2>>weight; for(int j=0;jvexnum;j++) { if(g->vexs[j]==ch1) { row=j; } if(g->vexs[j]==ch2) { col=j; } } g->arcs[row][col]=weight; //有向带权图只需把1改为weight }}void creat_mgraph(MGraph &g) //创建图 { add_vexs(g); //增加顶点 add_arcs(g); //增加边}void print_mgraph(MGraph &g) //打印图{ for(int i=0;ivexnum;i++) cout<<" "<vexs[i]<<" "; cout<vexnum;i++) { cout<vexs[i]<<" "; for(int j=0;jvexnum;j++) { cout<arcs[i][j]<<" "; } cout<vexnum; ++v) for(w=0; wvexnum; ++w) { D[v][w] = g->arcs[v][w]; for(u=0; uvexnum; ++u) //初始化 P[v][w][u] = FALSE; if(D[v][w] < INFINITY) //从v到w有直接路径 { P[v][w][v] = TRUE; //起点 P[v][w][w] = TRUE; //终点 }//if }//for for(u=0; uvexnum; ++u) for(v=0; vvexnum; ++v) for(w=0; wvexnum; ++w) { if(u==v || v==w || w==u) continue; if(D[v][u] + D[u][w] < D[v][w]) //从v经u到w的一条路径更短 { D[v][w] = D[v][u] + D[u][w]; for(i=0; ivexnum; ++i) P[v][w][i] = P[v][u][i] || P[u][w][i]; }//if }}void print_PathMatrix(MGraph &g， PathMatrix &P) //打印路径矩阵{ cout<<" "; for(int i=0;ivexnum;i++) cout<vexs[i]<<" "; cout<vexnum;i++) { for(int j=0;jvexnum;j++) { cout<"<vexnum;k++) cout<vexnum;i++) cout<<" "<vexs[i]<<" "; cout<vexnum;i++) { cout<vexs[i]<<" "; for(int j=0;jvexnum;j++) { cout<节点30，大约需要8分钟，也就是说犯罪嫌疑人在3分钟之后已经离开A区，进入C区，所以此时我们应该考虑C区巡警台的围捕问题。经计算可以得出，出动173，174 号平台的警力封锁216，299号节点即可。情况二：犯罪嫌疑人还在A区，可供他选择也就是两个方向，第一小方面是往左边逃跑（如情况二图一），也就只有三种可能出项的情况，通过计算可以得出，巡警台15封锁28号路口，10平台封锁26路口，14平台封锁14路口即可。另一方面是往右边逃跑（如情况二图二），通过计算得出，2，3，4号巡警台往最近的路口处进行封堵就可以达到围捕成功。 （图P） 七．优化结果分析及误差分析： 误差主要体现在距离计算上面，某些站点之间距离不方便计算。为了计算方便，也设定路径是单向的。还有每个巡警台的工作效率和警力是不一致，不是恒定的。假设模型为了实现方便，假定逃犯的速度与警力的速度是一致的，但从实际看，逃犯速度不是恒定不变的而一个完善合理的计划，还应包含一个着眼与长期的计划，由于时间限制，我们也没有深入研究这个问题，但可以作为今后努力的方向。巡警台发生故障的考虑：在实际操作中，巡警台工作发生故障是一个很大的影响因素，我们应该进一步考虑在调度系统中如何反映与处理故障，以及对路线安排有何影响。 八．模型的评价上文从巡警台的选址，路线的效率最大化以及巡警台中警员的调度，花费最小化这些方面进行了分析，建立了一个多目标的非线性的数学模型。成功地通过实验和数据分析得出较为准确和可行性高的结果。九、参考文献： 十、附录：
2011 高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮 件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问 题 我们知道，抄袭别人的成果是违反竞赛规则的， 如果引用别人的成果或其他 公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正 文引用处和参考文献中明确列出 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性如有违反竞 赛规则的行为，我们将受到严肃处理 我们参赛选择的题号是（从 A/B/C/D 中选择一项填写） ： 我们的参赛报名号为（如果赛区设置报名号的话） ： 所属学校（请填写完整的全名） ： 参赛队员 (打印并签名) ： 指导教师或指导教师组负责人 (打印并签名)： 日期： 日 C 年 月 赛区评阅编号（由赛区组委会评阅前进行编号）： 2010 高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 交巡警平台设置的优化模型 摘要 在充分理解题意的基础上， 我们提出了合理的假设通过对问题的深入分析， 我们将本题归结为一个带有约束条件的优化问题 鉴于路线的复杂程度，我们没有采用常规的 Dijkstra 算法，而采用了动态 规划的方法其基本思想是通过 LINGO 编程得到一个路口到其他路口的最优路径 寻找出不能设为交警平台的路口 针对问题一（只考虑线路的网络系统） ，我们建立了模型一，并通过 LINGO 编 程得到从任意一个路口到其他路口的最短距离，从中筛选出大于 120 米的距离， 统计成表二，再根据各路口到离其最远的地块的最短路径分析，得出 A、M 不能 设为交巡警平台 针对问题二， 我们将问题一中 LINGO 编程所得结果通过 EXCEL 统计出从各路 口到各个地块的最小距离，并将其存为数据文件（见表三）接着用 matlab 编程 求出各路口到离其最远地块的最小距离（见表四） ，观察结果得出出警至最远地 块且用时最短的最小距离为 85 米的三个路口 C、H、I 针对问题三，根据题意设出最优原则，结合表五逐一进行筛选得到最优交巡 警平台设置路口 B 最后模型的建立有效的改善了交巡警在执行任务中的效率，同时也可运用到 其他最优选址中，并且可将该模型算法拓展模型在其他领域的适用范围 关键词：动态规划 最优路径 交巡警平台 LINGO 1 一、问题的背景 面对各种突发事件， 即使在科技高度发达的今天， 也有显得束手无策的时候， 许多国家政府、科学家为预防事故，保障生命财产安全作了一定的工作，例如澳 大利亚在 1993 年 1 月九成立了应急管理署（EMA） ，负责处理自然、人为、技术 等方面的灾害，在事故或灾害发生时，及时、有效地迎对各种重大紧急事件和灾 害 近十年来，我国科技带动生产力不断发展，国家经济实力不断增强，然而另 一方安全生产形势却相当严峻，每年因各类生产事故造成大量的人员伤亡、经济 损失尤其是在一些大目标点，作为人类经济、文化、政治、科技信息的中心， 由于其“人口集中、建筑集中、生产集中、财富集中”的特点，一旦发生重大事 故，将会引起相当惨重的损失为了保障安全生产、预防各类事故我国正在各省 （市）目标点逐步设立交巡警平台 2010 年 2 月 7 日，一只名为“交巡警”的全新警种在重庆诞生这一警种拥 有包括枪支在内的“高精尖”装备，代替过去的交警和巡警交巡警平台是 将刑事执法、 治安管理、 交通管理、 服务群众四大职能有机融合的新型防控体系 在人流量极大、治安状况比较复杂、交通持续比较混乱的事故多发带产生强大的 司法制衡力、社会治安的驾驭力、打击罪犯的冲击力保证在事故发生的第一时 间赶到现场大力的减少了社会上各种混乱行为的发生使居民的生命财产安全 得以保障 二、问题重述 如图 1 所示为重庆市某街区草图，街区内有上下平行 5 条路，左右平行 7 条 路路宽忽略不计，路长可从图中得知图中标数与实际比例为 1:25，单位为米 若在此街区内部设立一交巡警平台，巡警出动到到达出事点不能超过 5 分钟此 处假定到达出事地块边缘即为到达出事地点并规定路上行驶时间不得超过 3 分 钟，警车车速恒为 60 千米/小时那么我们针对题目给出以下三个问题： 图1 重庆市某街区草图 2 问题一：哪些路口不能设交巡警平台？ 问题二：哪个路口设为交巡警平台可使出警至最远地块且用时最短？并陈述 理由 问题三：若地块（4） （16）为事件多发区，则交巡警平台该设在何处？为什 么要设在此处，并由此给出答案
全国大学生数学建模竞赛B题个人见解：# `7 t' S4 @+ g7 h7 k6 A- m/ U2 s* `; j2 /# j1 R这个题目一看就知道是个优化问题；' I- q9 R1 T! V， E5 ~， `# i1、第一问有三段话，每一段其实是对方案的一次帅选；针对第一段内容，傻子都知道首先建立3分钟区域圈，然后可以得出一些方案，这里可能得出好几个甚至无数个方案，不过不要担心；! ^) ?/ @2 m' _$ l |2 {$ n至于筛选规则，提醒下大家：不要筛没了，也不要留的太多（一般情况下，晒到处理不好，方案没了）! x5 y7 ^4 l3 `& W第二段主要让你给出调度方案，就是一个配置问题，设计或者选用合适算反来解决是王道！: X8 b4 Z8 Z$ {/ T第三段是要你添加一些点，这个应该不难做吧，可以参考下图论的那些个经典算法； f" C) y& D1 w% p2 M， H2 v5 /" Q， e- p本题还有其他的解题思路：就是通过建立目标规划模型解决！重点还是实现上啦，其实图论及目标规划很简单，关键是求解算法及实现，这个大家可得花功夫奥！8 M7 h/ V0 x( v) J- { Z' `/ F" Q8 l0 V2 x: I" X2、这一问其实是一个全局的配置问题；过多的我也不能做解释了，大家自己思考吧，找出一些问题，尤其是区域边界处的设点拥挤问题；: a2 }1 E% S- R5 j9 p% w5 V6 D下面是给你一个问题，让你给出一个方案，这个问题是个资源调配问题，把握两个原则：时间最短、围堵区域最小。
