数学建模社区-数学中国

标题: 2011年全国赛B题思路分析（个人意见，请勿喷水） [打印本页]
作者: 安树庭    时间: 2011-9-12 23:14
标题: 2011年全国赛B题思路分析（个人意见，请勿喷水）
本帖最后由 安树庭 于 2011-9-13 00:27 编辑 ! P+ g2 b" G6 J# \& J5 N

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

/ X3 H. k2 b- v- P( h4 m2 M" R/ ^' s5 q2 t5 M5 J
   问题2.1建模过程没有什么好说的，但是我们组考虑了这么一个问题，单单建立一个评价模型，最后得出来的结论应该只是一个建议而已，那么如果具体这个措施是不是还需要建立模型计算呢？比如说发现 C地区应该增设服务平台，那么结果是不是只需要说C需要增接平台呢 还是计算出需要增加多少个平台，在哪些地方增加呢？我们组借用问题1.3的模型确定了这些区需要在哪些地方增加平台....感觉这一点做的还不错
. ]- Q# G! A1 ~0 W+ c   问题2.2实在不好说，就把我们组的维度原理贴出来吧  如图所示 QQ截图未命名.jpg
: y1 C8 K5 _9 H/ o; I3 Z3 d
! `" ?  z# U! x5 s1 s0 D/ \  c$ P      希望大家可以多多交流
作者: 安树庭    时间: 2011-9-12 23:29
顶一个  呵呵
作者: baivfhpiaqg    时间: 2011-9-12 23:33
有一个大疑问……不知道大家怎么想( }! M- [" z. A8 c' q) S& O
问题一中给出了A区是尽量要求3分钟内到达的# Z( ~. g' _; Q% a
但是其他区并非重点城市，所以不一定也都需要3分钟内到达吧。。。* u  `- j, k. \9 @4 \* {6 L( S9 [
这一点纠结了很久。。。
作者: 安树庭    时间: 2011-9-13 00:06
baivfhpiaqg 发表于 2011-9-12 23:33
8 J  I* g7 k4 s! c4 \/ a有一个大疑问……不知道大家怎么想% K/ Z# g5 Z; I4 m+ a2 E
问题一中给出了A区是尽量要求3分钟内到达的8 c) I6 U, }5 h2 ?) x
但是其他区并非重点城市， ...

1 a, V# M: p4 o: }* y我觉得你这个想法很好，但是怎么说呢，应该不需要纠结这个问题吧  即时不是重点城市，群众的财产安全，人身安全是同等重要的，**的职责要是同样的  所以也应该尽早到达事发现场
作者: 安树庭    时间: 2011-9-13 11:56
怎么都没人呢？难道还在睡觉？
作者: wangdeq    时间: 2011-9-13 12:12
庭哥的啊，都上首页啦！！顶一个~！
作者: jerrybond6    时间: 2011-9-13 12:40
楼主犀利，  我把第一问(3)做挫了 主要是没有时间考虑太多了
作者: ljzx    时间: 2011-9-13 12:55
baivfhpiaqg 发表于 2011-9-12 23:33 ; U* L5 ?0 m; c- ]( t6 F1 G1 x
有一个大疑问……不知道大家怎么想
: V; K" U7 `5 z( a/ C问题一中给出了A区是尽量要求3分钟内到达的# H9 Q0 l1 m! ^4 f0 _" t/ s8 ]/ r
但是其他区并非重点城市， ...
7 E$ S# _- H/ z0 n
但是3分钟可能是个一般标准，也可以5分钟吧
作者: 安树庭    时间: 2011-9-13 13:30
ljzx 发表于 2011-9-13 12:55 7 b$ F* t% A0 ~6 ?2 }
但是3分钟可能是个一般标准，也可以5分钟吧
# a) N- U2 y6 }1 ~7 E
你的想法也有道理  数模本身就应该有很多自己发挥的空间  不过由于这个是竞赛 ，可能很重要的一点就是看组委会的评判标准了 呵呵
作者: baivfhpiaqg    时间: 2011-9-13 14:19
ljzx 发表于 2011-9-13 12:55 # @! t. T) j  |# [
但是3分钟可能是个一般标准，也可以5分钟吧

' c7 L* r" E" i4 l, o- O! _我们的做法是结合各区人口密度和各区平台个数给出各个区所能承受的最短服务时间的
作者: 332059488    时间: 2011-9-13 14:30
作者: jingtao0621    时间: 2011-9-13 14:55
1.1我们用的是边分配，很同意楼主的说法，呵呵
作者: 安树庭    时间: 2011-9-13 15:00
jingtao0621 发表于 2011-9-13 14:55 3 ]" a4 n. F0 }) N/ `
1.1我们用的是边分配，很同意楼主的说法，呵呵
0 _' ]0 D- [. c: x" U9 _
恭喜你  边分配就对了  呵呵
作者: ≮风の殇逝≯    时间: 2011-9-13 15:01
wangdeq 发表于 2011-9-13 12:12
3 P4 {. q- Y: Y8 P0 Z3 s2 r; N4 }庭哥的啊，都上首页啦！！顶一个~！

6 R+ O3 n/ K' g) @! H顶庭哥，虽然我做的只是A题
作者: 安树庭    时间: 2011-9-13 15:01
jingtao0621 发表于 2011-9-13 14:55
* H1 \% E' v$ Y! n5 j- F' G1.1我们用的是边分配，很同意楼主的说法，呵呵

8 f2 N6 E& ?) D- m) X你是顾问团成员？你是老师？？
作者: jingtao0621    时间: 2011-9-13 15:10
安树庭 发表于 2011-9-13 15:00
  M+ |9 W- k# B6 _, l& t恭喜你  边分配就对了  呵呵

3 s: {- U& g8 S0 O. k! [# b- bO(∩_∩)O谢谢！我原来是老师，今年要去进修了
作者: tanfei    时间: 2011-9-13 15:28
最短服务时间与各区人口密度相关
作者: 安树庭    时间: 2011-9-13 15:45
jingtao0621 发表于 2011-9-13 15:10 % v: x; ?) D( h7 V/ @. `7 |
O(∩_∩)O谢谢！我原来是老师，今年要去进修了
2 l2 Y' {4 `# @) V6 ^& n5 b
那就是恭喜你和你们学校了 呵呵
作者: 安树庭    时间: 2011-9-13 16:26
baivfhpiaqg 发表于 2011-9-13 14:19
9 k# y; E+ X# P' w+ {: Q7 r我们的做法是结合各区人口密度和各区平台个数给出各个区所能承受的最短服务时间的
) @5 X4 X" ~7 Y( B: `
人口密度是一个方面  人口密度越大服务平台数目应该越多    你觉得考虑人均占有服务平台数目这个想法怎么样？
作者: 安树庭    时间: 2011-9-13 16:58
..........这个很抽象
作者: 851581755    时间: 2011-9-13 18:19
ooooooooooooo
作者: Namtsolaker    时间: 2011-9-14 01:37
有道理，顶一下！！！
作者: lxb198408    时间: 2011-9-14 08:53
顶啊。。。。。。。。。。。。。。
作者: zju_daniel    时间: 2011-9-14 13:25
baivfhpiaqg 发表于 2011-9-13 14:19 / t9 c. x2 C/ T  g' x8 m) y5 J
我们的做法是结合各区人口密度和各区平台个数给出各个区所能承受的最短服务时间的

7 ]$ Z- I1 R/ n7 r' ~* N% E记得我们队算出来有些区的承受时间好像达到7——8分钟的样子，只有A区可以约束到3分钟。。。。
作者: baivfhpiaqg    时间: 2011-9-14 14:31
zju_daniel 发表于 2011-9-14 13:25 + H! b+ V7 e; f
记得我们队算出来有些区的承受时间好像达到7——8分钟的样子，只有A区可以约束到3分钟。。。。
  U: ~# w: h! [* P
我们算出来的是5～8都有……: q4 T3 k& r7 ^' P/ u3 W/ x
看来都差不多的。。
: @" \( {! ~$ W* h, @( K不过好象组委评阅的标准里没涉及到我们这方面。。8 e6 S0 M1 F' l
不知道会不会被无视……
作者: 安树庭    时间: 2011-9-14 21:14
wangdeq 发表于 2011-9-13 12:12
' c- ~1 U7 G- |) D2 F; i5 I庭哥的啊，都上首页啦！！顶一个~！
$ w( A  B2 h9 j4 `1 G* g9 ?
你是 wdq？
作者: 相信、未来    时间: 2011-9-14 22:02
悲剧了，照楼主说快速全封锁理解给理解错了，我一直以为目标函数是总时间最短就用了匈牙利算法，指导老师还一直说没错.......
作者: beiyiwangdesha    时间: 2011-9-14 22:41
弄的现在还没休息过来
作者: 安树庭    时间: 2011-9-14 22:42
相信、未来 发表于 2011-9-14 22:02
' ]1 B; A; }: x1 n悲剧了，照楼主说快速全封锁理解给理解错了，我一直以为目标函数是总时间最短就用了匈牙利算法，指导老师还 ...
. u7 S7 s# r' V" Y- S  V
不啊  这个只是我们组的看法  不是官方意见  你们的老师也有可能是对的   你们的结果是多少？
作者: 安树庭    时间: 2011-9-14 22:42
beiyiwangdesha 发表于 2011-9-14 22:41
' ^2 L/ [. J1 m& ]弄的现在还没休息过来
3 _* d0 \. V( t( b. S
呵呵  那就继续好好休息啊
作者: beiyiwangdesha    时间: 2011-9-14 22:44
安树庭 发表于 2011-9-14 22:42 ) Y. T+ p6 s' a. R& P' i; X
不啊  这个只是我们组的看法  不是官方意见  你们的老师也有可能是对的   你们的结果是多少？

: U( J3 B$ K* j( Y关键关键是还不知道有没有结果
作者: 安树庭    时间: 2011-9-14 22:45
beiyiwangdesha 发表于 2011-9-14 22:44 0 t( r6 `3 i( s( P0 k1 {  L& y
关键关键是还不知道有没有结果
, D% e: l& n, k& J
....你们做的结果是多少呢？
作者: /飞得更高/    时间: 2011-9-14 23:47
作者: /飞得更高/    时间: 2011-9-14 23:47
这样啊，这道题就是以重庆为背景的……
作者: /飞得更高/    时间: 2011-9-14 23:48
加油吧，希望有一个好成绩……
作者: wangdeq    时间: 2011-9-15 10:25
安树庭 发表于 2011-9-14 21:14 1 Y$ \# p7 _4 l5 q; ]* s) t
你是 wdq？

3 A; J4 v2 g2 p0 F0 A5 m这不显然！！~~！
作者: liubei999    时间: 2011-9-15 17:19
在地图上标序号，可以使用matlab编程标序，然然后对图进行放大，就可使用，很直观。
/ f# D3 e* t9 Z. J在1.3中楼主分析的很对，对于工作量的定义，可以考虑使用节点的案发量除以节点的度。
作者: leeca165    时间: 2011-9-16 22:43
听你说  你还建的可以呢~~我们这组差多了
- x% t& f5 ~' T2 @  L/ Z" q( t) w
作者: 安树庭    时间: 2011-9-16 22:45
leeca165 发表于 2011-9-16 22:43 , W7 Q5 j9 ]3 t- M
听你说  你还建的可以呢~~我们这组差多了
* \  E4 D1 @& L4 [- h, f
论文搞的太急了 没有表达好......
作者: jerrybond6    时间: 2011-9-16 23:03
相信、未来 发表于 2011-9-14 22:02
$ |/ a8 G. c# C2 L) H- g悲剧了，照楼主说快速全封锁理解给理解错了，我一直以为目标函数是总时间最短就用了匈牙利算法，指导老师还 ...

) Z6 L5 L2 i  _" q用时间最短应该用 KM算法吧 你记混了吧
作者: zju_daniel    时间: 2011-9-17 08:53
相信、未来 发表于 2011-9-14 22:02 $ t$ F! q6 F  t& }; v7 C+ F+ w$ n2 Y8 a+ P
悲剧了，照楼主说快速全封锁理解给理解错了，我一直以为目标函数是总时间最短就用了匈牙利算法，指导老师还 ...

/ y  M% V$ e' ^你们还有指导老师啊？？。。。。。
  x! [: @2 ]1 y7 x3 p
作者: zju_daniel    时间: 2011-9-17 08:56
baivfhpiaqg 发表于 2011-9-14 14:31
/ _, N" ~/ A1 O, m0 K; D我们算出来的是5～8都有……. @: I' j8 r: r3 A
看来都差不多的。。
, p* e( O: o4 F5 @不过好象组委评阅的标准里没涉及到我们这方面。。

8 X# l! }6 p! T" j6 M涉及到了吧。。。这个值应该是做2-1的前提吧~个人感觉+ t& C8 c; d; V
作者: jean890915    时间: 2011-9-17 13:41
正解！！！！！
作者: 忠武穆    时间: 2011-9-17 15:56
楼主强！我们组果断选作A题！
作者: tpkeen    时间: 2011-9-17 18:02
  、、、、、、、、、、、、、、
作者: tpkeen    时间: 2011-9-17 18:30
怎么都没人呢？难道还在睡觉？
  J9 b, g8 R7 i+ h, z
作者: 安树庭    时间: 2011-10-9 22:00
jerrybond6 发表于 2011-9-13 12:40
# T4 N) H0 G, u% m5 n楼主犀利，  我把第一问(3)做挫了 主要是没有时间考虑太多了

& i9 q: H* {2 h8 x4 |  e你们赛区的成绩出来没？
作者: zhuyulin    时间: 2011-10-10 15:06
学校选上国赛的6个b题1个a题的，当时选急了8 K( ?' [, L5 p' U
作者: chenyidian    时间: 2011-10-21 15:18
lz厉害哈，不愧是泡了很多年的坛子
作者: 桑小饭    时间: 2012-7-5 09:28
求出邻接矩阵后怎么标出点啊用maatlab可以把图像坐标读出来吗？
作者: 迓韬    时间: 2012-7-11 23:42
好，就是错别字太多了。
作者: 江湖小虾米    时间: 2013-7-21 00:12
楼主分析得比较透彻
作者: _自带BGM的男人    时间: 2013-7-21 17:59
完全不懂的新手给你回复一个吧，我攒点经验
作者: Rain的雨    时间: 2013-7-23 13:29
顶，顶，的
作者: 笑看夕阳东升    时间: 2013-7-23 15:00
看一看，感觉思路还是不错的
作者: 涂卡铅笔    时间: 2013-7-29 13:35
分析的不错
作者: 千叶迦南    时间: 2013-7-30 15:54
但是我们队做的时候考虑的太复杂，整篇论文都是用模拟退火，直接导致编程工作量很大，还好及时写完了
作者: 镇关西    时间: 2013-8-1 21:50
大赞，顶了
作者: limiraning    时间: 2013-8-8 21:02
嗯嗯，被画图困了好久，才发现画不画图影响不大、、
作者: 张彼得    时间: 2013-8-12 22:01
有用 有用
作者: 爱学习的孩纸    时间: 2013-8-19 16:41




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5