2011年全国赛B题思路分析（个人意见，请勿喷水）

安树庭

* O3 y# L" j, D5 U7 U
      这个题目有点令人蛋疼，首先就是图形的复杂性就吓跑了很多人，我感觉今年A，B题选题的比例差距应该有点大....我们学校20个队只有2个队做B题，听说武汉大学30%的队做B题。
8 u' ~  n! S1 Q' |6 H     首先对附图中的点进行编号就是一个技巧的体现，我不知道有没有组会按照那个坐标一个个的标........囧.......事实上根据附件2 sheet2中的工作表起点和节点可以确定一个领结矩阵，从而可以利用MATLB直接标出所有点  做题之前我很蛋疼为什么附图上不直接标号给我们要我们自己蛋疼  后来标出来了才发现，标点之后的图很难看，图太小 点太多太密集，终于明白了.....
' D/ l' O* G/ I2 T/ l: K      在1.1问中，我认为交巡警管理的应该是路段，所以不应该包括空白区域，所以用覆盖（原覆盖，正六边形覆盖，矩形覆盖）都不是很合理的；而有些组运用各种原则或者算法确定20个服务平台分别管辖哪些路口节点是有一定道理的，但是也存在一定的漏洞，比如说abcd四个点依次相连，b归a管辖，c归d管辖，哪些线路bc归谁管辖呢？此类由于点管辖分配所得的方案会出现这个特殊问题，也就是部分路段没有平台管辖，明显是不符合实际情况。   针对这个情况（我们总结了有3种清醒），有2种解决方案，1是对于特殊性重新处理（也是我们论文中使用的方法）2是直接不要用点分配模型，直接建立边分配模型，我们在后来的计算中发现这个模型实际上更符合实际情况，但是由于时间关系，没有写上去，很遗憾.....
% F9 A/ M" o1 [      在1.2问中，可以建立图论模型或者优化模型，我们用的优化模型，在目标函数的确定上是个耐人询问的问题，要求封锁时间最短，目标函数应该是最后被封锁的路口所用的时间最短，而不是平均封锁时间最短。    基于这个目标函数，建立了极大极小模型，模型的求解就没有什么说的   后来想想，如果用图论，会不会避开这个目标函数？由于对图论建模不是很懂，所以不敢贸然尝试。
- b* F- y" m; [) ^& ]7 E' o     在1.3问中，我们建立了多目标规划模型，有3个目标：平均工作量方差最小，平均出境时间方差最小，封锁要到交通要道需要的时间最短（这个题目很有意思，1.3问承接1.2问，1.2问暗示1.3问）。在本问中，有2个地反复需要注意
% b+ Z7 }" r2 n& a* Z7 }. W    一个就是工作量的定义，我们用的是平台到其管辖点的距离成宜这个管辖点的发案率  后来交卷了发现这个定义有待商榷。从概率论的角度，一个节点是发生案件的概率为0，题目中给了路口节点的发案率只是为了表述上的简单，后来我们提出了一种对发案率的看法（当然没有在论文里显示）。考虑路线     A——B——C假设B的发案率是f（B），AB的距离为L1，BC的距离为L2，那么路段AB的发案率应该等于L1/（L1+L2）*f（B），同理BC的发案率等于L2/（L1+L2）*f（B），   这样就把点转化成了路段  更具有实际意义，而在问题1.1中已经把路段归属做了确定，从而就可以定义工作量了；
    另外一个就是模型的求解，多目标规划一般有目标加权法和分层排序法 但是这个题目标函数两缸不同，变量太多，限制条件复杂，所以我们采用了启发式算法，最后的结果是增加4个平台，整个服务喜用的性能分别提升了32%和25%左右（大致这个数字，具体的忘记了）。


* W: P: O; }, L   问题2.1建模过程没有什么好说的，但是我们组考虑了这么一个问题，单单建立一个评价模型，最后得出来的结论应该只是一个建议而已，那么如果具体这个措施是不是还需要建立模型计算呢？比如说发现 C地区应该增设服务平台，那么结果是不是只需要说C需要增接平台呢 还是计算出需要增加多少个平台，在哪些地方增加呢？我们组借用问题1.3的模型确定了这些区需要在哪些地方增加平台....感觉这一点做的还不错
& t% V+ r& }! s( g   问题2.2实在不好说，就把我们组的维度原理贴出来吧  如图所示

% h- X5 n6 j" d' a- A. @      希望大家可以多多交流

安树庭

顶一个  呵呵

baivfhpiaqg

有一个大疑问……不知道大家怎么想
7 f0 t7 F6 M( k% V5 @% e0 K问题一中给出了A区是尽量要求3分钟内到达的
但是其他区并非重点城市，所以不一定也都需要3分钟内到达吧。。。
3 z8 \/ o, H' \这一点纠结了很久。。。

安树庭

baivfhpiaqg 发表于 2011-9-12 23:33
# n: Z9 e+ |; _/ z1 [' S0 ^2 [有一个大疑问……不知道大家怎么想
问题一中给出了A区是尽量要求3分钟内到达的
( A4 R8 \: z, z但是其他区并非重点城市， ...

. G, c  Q1 O4 F- |我觉得你这个想法很好，但是怎么说呢，应该不需要纠结这个问题吧  即时不是重点城市，群众的财产安全，人身安全是同等重要的，**的职责要是同样的  所以也应该尽早到达事发现场

安树庭

怎么都没人呢？难道还在睡觉？

wangdeq

庭哥的啊，都上首页啦！！顶一个~！

jerrybond6

楼主犀利，  我把第一问(3)做挫了 主要是没有时间考虑太多了

ljzx

baivfhpiaqg 发表于 2011-9-12 23:33
有一个大疑问……不知道大家怎么想
3 m+ _% b, O; c' z. a- T! n9 e问题一中给出了A区是尽量要求3分钟内到达的
4 j% i: g7 p7 K" G/ V8 H+ h' R, |但是其他区并非重点城市， ...

但是3分钟可能是个一般标准，也可以5分钟吧

安树庭

ljzx 发表于 2011-9-13 12:55
, _  N5 I4 L5 K: B但是3分钟可能是个一般标准，也可以5分钟吧

你的想法也有道理  数模本身就应该有很多自己发挥的空间  不过由于这个是竞赛 ，可能很重要的一点就是看组委会的评判标准了 呵呵

baivfhpiaqg

ljzx 发表于 2011-9-13 12:55
& ^# W& b. p& j7 R# [) d* r' N但是3分钟可能是个一般标准，也可以5分钟吧

我们的做法是结合各区人口密度和各区平台个数给出各个区所能承受的最短服务时间的