参加2018数学建模历程及比赛总结

2018年11月11日

数学建模结束了。

从9月13号晚上20:00开始,到9月16号晚上20:00结束。其实结束时间是9月16号晚22:00,因为在20点到22点之间还可以上传一次论文,所以直到22点才算结束。

第一个晚上

比赛的第一个晚上,也就是9月13号20点,这个时间点我们用于选题,并没有实际做题。A题是用来构建工作服模型,B题是RGV的动态调度模型。

A题是题目是很短很直白的,从题意上可以确定,只要把第一问的模型建立并求解,那第二、三问基于第一问的基础上可以随便做,困难在于第一问的模型能否建立,建好的模型能否求解。

初看上去B题的信息量太大了,每一个过程都有各种条件限制着,但是貌似只是个编程模拟问题?

在暑假培训时,我们队伍并没有特意的选题偏向。就我而言,是知道A题一般是有固定答案,偏工程类,要有各种数学模型;而B题是没有固定答案,但需要从各个角度看待问题,并把自己看待问题的角度写到论文里。

这一个晚上,我们对两道题查各种资料,首先可以确定A题跟热传导有关,只要建立热传导模型,那么便可以做出来。而B题是RGV的动态调度模型,从找到的资料看,是个NP问题,一般用遗传算法来求解。看着看着,小组讨论的重心就确定了A题,但我期间还是恋恋不舍的看着B题,因为对两道题,我的想法是A题在热传导建模、求解是一道坎,过去了会很轻松,过不去就一点办法都没有,做这道题需要冒很大的险;而B题虽然信息量大,但是至少可以用贪心策略来保证我们有一个解,哪怕这个解不是特别好。

我让两个队友只看A题,而我两道题都得看,因为我知道,如果确定了A题,我会很依赖她们,而B题就是道编程题,在编程方面是完全依赖于我的。

这个晚上,队友在问我,我们要选哪题,那会,我说选A题,虽然说了选A题,我内心还是很纠结。之后就是各种查A题资料。

第一天

指导老师过来给我们参赛队来统计我们的选题情况,第一次我跟他说我们组还不确定,后来30分钟后也就是8:30左右,我就跟他说,我们组,确定B题。

为什么又要改了第一天晚上确定的题目?我们又分析了遍,第一,A题的坎没把握通过,虽然我知道我队友的数学能力并不差,但是A题涉及到两个难点:在极短时间内学习热传导并建立模型,对这个模型进行求解。第二,我可以通过编程保证B题一定有答案,然后只需要研究怎么把论文写得漂亮就能拿奖。第三,还处于第一天早上,在这个点最终定下题目就不会影响后续。

确定后我们就只看B题。在上午,我们三人看题就看了好久,因为里面涉及的信息量过多:

  • RGV的工作原理
  • 一个阶段工作过程
  • 两个阶段的工作过程
  • 故障的产生及出现故障的处理
  • 如何评价算法的优劣性实用性

在看完题目后,就开始在网络上查找各种资料。

好在网上对这种过程的处理也有大量研究,关键词就是RGV动态调度,而且里面有有涉及到故障发生的处理办法。难点在于这是个NP问题,多用遗传算法来求解。

其实,我之所以能保证一定有结果,是因为B题一看上去,用贪心+模拟的方法来求解的话,那这道题就是妥妥的三个大模拟,以贪心来做调度策略,然后模拟RGV在这几个小时内的行走路线,结果就出来了。但是在第一天的时候,想到后面还有两天时间,我还想试着寻找一种比贪心更好的策略。

用别人发表的论文里提到的遗传算法,我发现自己在短时间内并不能做,第一是遗传算法里变量的确定,而且网上的论文里是给定个数的,在给点个数的情况下用这些作为变量,然后使这些变量满足题目的约束条件这种方案理论上是可行,但要在数模比赛三天内做出来,还要保证论文的优质,用遗传算法这种方案并不是很稳。

这天晚上,我已经做出了一道工序下RGV的调度结果,期间做得也不是很顺利,频频出bug,一定是我好久没做这种模拟题了,手生,还是靠队友手算前几个数据来跟我的程序结果对拍。

第二天

我处在写代码加debug状态,并且第一道工序的调度情况从头到尾都是1-8循环,这样我和我队友都在质疑这个结果的准确性,心理感觉不靠谱,虽然总个数在一个很合理的范围内。

求解两道工序时,首先要确定个数和位置,即安排多少台CNC作为第一道工序,安排多少CNC作为第二道工序,并且确定这些CNC的分布情况,当然要满足工作的顺序要求。

看到这个,很快想到了状压DP,这当然不是道DP题,只是利用了二进制枚举所有CNC分布的所有子集的思想,然后对枚举出来的每一种状态结合贪心策略来求出该状态下的产品个数,看哪一种状态得到的结果最优,就可以得到CNC的分布了。

而对于出现故障的情况,由于我使用的贪心策略加模拟的算法,因此当某台CNC出现故障时,只需要稍微改一下代码,把那个故障时间记录下来,并且把那台CNC的使用时间相当于延长了一部分。故障的产生,也是对每一个产品,在进入CNC加工时,都用产生随机数的方法来进行概率模拟。

嗯,求解,丝毫没有难度。但是中间出现个bug卡了我好久,怎么检查都没发现错误,但是数据看着就有问题,而且队友完全不擅长编程。好在队友给力,鼓励我,并通过手算协助我找bug。

这天晚上需要编程求解的都已经求出来了,也着手写第二问了。在晚上1点多的时候机房还有很多人在拼命,我确认跟我的队友们回去睡觉了。

回到宿舍的时候我并没有立即入睡,发现我还是很有精神,可能是因为有点激动。也在这个晚上把第二问的论文框架搭建好了。肝到四点左右入睡。这一期间,我也把第一问的算法求解步骤补充完整,因为我的两个队友一个主负责建模,另一个主负责写论文,而写论文的队友对算法并不熟悉,还是得靠我来写作。

第三天

七点多起来了,就立马去吃早餐去机房。给队友看了我昨晚挑灯夜战的成果。这一天我们都在写论文,建模的队友也在完善第一问模型的几个约束条件。第二问也涉及到几个小问题,还要我们定义作业效率。我们的定义较粗糙,就直接用当前数量与理想情况下的比值作为效率。而实用性这些在当时回答的也很局限,没有从多个角度进行探讨。现在想想也许是当时太过疲劳了。

我们三点多才完成论文的初稿,而且这个时候是没写摘要的,我们都知道摘要很重要。五点多才把摘要写完,然后又是陆续进行完善。整个论文不知怎的写了二十二页,后来嫌长,删成了二十页多一点。至今都不知道当时是怎么写了这么长的论文,要知道,暑假培训模拟期间写的论文有个十七八页都已圆满,而且还是网上存在好多国奖论文的情况下。

到了七点已经没有心思写论文了,就准备提交了。最后在七点四十分就匆匆提交。

后来回头看,当时就该好好利用八点到十点这还可以提交一次的机会,在这两个小时内也许可以达到一个新高度,因为赛后反思的时候,还是能想起论文中存在的不少小问题。

后记

感觉这次全国赛比较水,做起来就像三道大模拟题。也许是运气太好了,接触到这种编程实现完全没有难度的题。

还记得首次接触数学建模是在校赛,那时没什么经验,混了个校赛二等奖。在那之前对数学建模都是道听途说,兴趣并不大。然后参加了一个月的暑期培训,期间有半个月的基础知识,以及半个月的模拟训练。我感觉前半个月的基础知识于我而言根本学不到什么,因为培训内容都偏向简单,没有什么太有深度的东西,期间我也就没怎么跟老师的培训,主要研究各种智能算法的使用。但后半个月的模拟训练就非常重要,从中可以体会一篇论文的写作过程,队友间的协作过程,以及有意识地训练自己对时间、比赛节奏的把握。

培训期间当了一个月的班长,并不是我主动去当,老师在大家面前直接点我的名字让我当班长时我还是很懵逼的。迎接而来的是每天来得比任何同学都要早,走得比任何同学都要晚,而这,只是因为机房的钥匙归我管。还要维护纪律以及卫生。在建模培训当的这个班长,我是尽职尽责的。

对于队伍内的培训方面,我们队伍在组建之初就已经确立了拿国奖的目标,嗯,反正我是这么跟她俩说的,我们的目标就是拿国奖。然后是对建模、论文、编程的分工,队伍每个人都要主负责一项,副负责一项,这样看来我们队伍的实力就很完美了,一个数学很强负责建模,一个编程并不差,再一个队友虽然没什么特别的亮点,但是只要热爱并能认真负责,安排来写论文总归可以。期间队伍每个成员还要大量看往年优秀的论文,从中学习,比如我负责编程,我就只需要关注往年里都用到了什么算法,有什么优劣,自己能否实现等偏向算法的部分,还有算法的描述方式。作为队长,哪方面都要涉及,哪怕某个方面不是特别擅长,像我就不是很擅长建模部分,这有利于培养一个全局观,而且庆幸的是我的副负责论文部分,也刚好弥补了主负责论文队友不会算法的不足。

回想我们这个队伍是怎么组起来的,感觉我太幸运了。在校赛期间就随便组了个队,然后校赛结束后我问那两个队友是否有谁要离开这个队伍。一个队友说不,另一个发了个QQ的摇手表情,问题来了,我理解成他的意思是“再见”,以为他要离开了,也不想再说什么了,在此期间又有个数学很好的队伍找上了我说跟我组队,便“抛弃”了原来那个队友,跟后来找我的这个组队了,后来才知道他的意思不是“再见”,而是“不”,特尴尬。在任职班长期间,我也了解到有些队伍组建得并不顺利,而我有这两位队友,感觉还是很幸运的。

后后记

数模结果出来了,国赛二等奖。在意料之中,但还是带着点小惊喜。感谢我那两位优秀的队友,感谢无私培训的指导老师。

去打赏

您的支持将鼓励我们继续创作!

[微信] 扫描二维码打赏

[支付宝] 扫描二维码打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注