数学建模竞赛新手教程.pdf

MATHEMATICALMODELING数模S H U M OSHUMO.COM出品2004.1Vol.1No.1声明本资料仅供参考，文章作者保留全部权力，任何将该资料全部或部分内容用于商业的行为，均须事先征得作者本人同意。转载或传播时，请保持该资料的完整性，并保留该声明。数模MATHEMATICAL MODELING主办：中国数学建模网SPONSORED BY:SHUMO.COM编辑：数模 杂志社COMPILED BY:Mathematical Modeling Editors Group主页：HOMEPAGE:电子邮件：EMAIL:通信地址：湖南长沙国防科大理学院ADDRESS:Science College,NUDT,Changsha Hunan邮政编码：410073POSTALCODE:410073目录经验交流数模之路.王瑛1数学建模竞赛后的思考我也想说.徐子彬3数学建模竞赛新手教程.向为6数学建模竞赛中应当掌握的十类算法.董乘宇12参加数学建模竞赛的十大秘诀.董乘宇15优秀论文电力市场输电阻塞管理模型.杨双红，刘刚，晏琦18电力市场的输电阻塞管理模型.初宁，周严，张锴34输电阻塞管理模型.孙蒙，吴慧云，易勋47奥运会临时超市网点设计.于旭东，詹浩，梁政60北京奥运会迷你超市群规划方案.黄立波，王耀，刘红军78新闻动态2004年高教社杯全国大学生数学建模竞赛成绩揭晓.91III数模2004 年第 1 卷第 1 期数模Vol.1，No.12004 年 11 月Mathematical Modeling2004.11数模之路王瑛（国防科技大学，湖南 长沙410073）我是数学迷，我的两位合作者是编程高手、实践天才。芙蓉国里，国防科大，我们走到一起。三年了，我们努力向前，精诚合作。三年了，我们做了一些事，闯出一条路。作为数学建模小组的一员，我又怎能不感慨万千呢？数学建模真的很难。起初，我们以为只要数学水平够高就行了。然而，2000年的全国赛题给我们上了一课。虽然没参加比赛，但是我们做得实在很差。从入门的角度来看，这是因为我们缺少处理实际问题的经验。比如说，在图上求两点间最短距离应使用Floyd算法，由于我们经验不足，明明知道该怎么办，就是无法在计算机上实现。后来，我们注重解决实际问题的基本功，对多种软件、算法作了深入的研究。尽管如此，一旦碰到问题，我们还是觉得不顺手，特别是很难抓住关键点。为什么，为什么我们精疲力尽却得不出好结果？这是没有站在巨人肩上的缘故！一个偶然的机会，我们认识到这点，开始了对图书馆、Internet的大搜索。渐渐地，我们的信息获取能力大大提高，也明白了文献作为知识的载体的继承性。而我们的任务，就是在前人的基础上更上一层楼，推陈出新。我们付出了汗水，自然会有收获。2001年5月，小组顺利的通过了学校的选拔赛。这是我们第一次成功。可是，前景仍不容乐观。国防科大人才济济，在九月份全国比赛之前，小组随时有被淘汰的可能。于是，我们更加努力，挤出所有课余时间搞数模。五月以后考试比较多，我们复习到深夜，可有时还得搞数学建模，直至天明。时间短，任务重，虽然有指导老师的殷切期望，但是想要交一份完美的论文太难了。小组甚至出现了仅有一页纸的论文。事物皆有两面。在这样的艰难困苦当中，我们的意志得到了锻炼，团体意识大大加强。同时，“唯陈言之务去”的道理也更加为我们所接受。因为数学建模就是创造性的智力活动，空话、套话是没有立足之地的。暑假到了，全年级下连队实习。然而，我们心里始终想着八月底的模拟竞赛，那可是决定参赛人选的一仗。结果，在入选的小组中，我们处于中间的位次。这根本不符合小组的个性，因为我们就应该出类拔萃。私下里，我们却都明白其中的原因。我们太重视那道题目了，以致形成了两种截然不同的思路，又各执己见。由于问题的重要性，分歧与矛盾不断的激化，最终做出了两份报告。兵力分散，实在是很深刻的教训！此后，大家的士气比较低落。一天晚上，指导老师交代竞赛事宜。回来的路上，我的两个伙伴表示了他们的忧虑：“也就是这样了，不过我好没把握。怎么办啊？”我也不知道怎么办，可我不能这么说啊。差不多硬着头皮，我预言着：“如果发挥不好的话，只能拿到全国二等奖。反正也是最后一次了。”最后那句不假思索的话起了奇迹般的作用，它激发了我们背水一战的思想。他们两个都点头。9月24日，全国比赛开始。我们统一思想，迅速选题、入手。“血管的三维重建”，问题很有特色，我们面临着艰难的抉择。因为尽管算法的精确解答十分重要，但是对算法的正确性加以数学证明也是很有吸引力的。深思熟虑之后，我们决定要创新，不因循守旧，毅然投入了算法基础的证明。感谢我的伙伴和我自己，还有所有关心我们的人！一天半之后，一系列精美的证明完成了。我们奠定了算法的数学基础。然后是编程实现，以及痛苦的调试。说它苦，是因为我们已经很累了。但是，一想到人们的期望，一作者简介：王瑛，SHUMO.COM 创始人之一，网站程序员，曾获 2001 年全国大学数学建模竞赛一等奖，现为国防科技大学硕士研究生。2数模2004 年想到付出的努力，一想到机会的难得，我们只有鼓足勇气、坚持到底。三天过去了，很快。那是一段难忘的时光，可是还有更精彩的生活。我们拿了全国一等奖，取得了参加国际比赛的资格。为了军队的荣誉，我们继续向前。国际比赛的题目本身并不难，难在论文必须用英文写。也正是因为这点，中国大学生几乎没有什么好成绩。（国防科大拿过特等奖）基于前人的经验，我们积极准备英文写作，加强英文资料的检索。更重要的是，我们考虑到“一张图胜过千言万语”，而中国人的英语水平毕竟有限，所以图文并茂应该是最佳的信息表达方式。不巧的是，2002年的国际数学建模竞赛正好在春节期间进行。过年也不能休息了，但是我们心无挂碍，一心取胜。当时很投入，我们一点也不觉得苦，只是赶火车回家的时候，却都在公共汽车上睡着了。累也累过，苦也苦过，国际比赛确实是我们一生都珍贵的回忆。第 1 卷第 1 期数模Vol.1，No.12004 年 11 月Mathematical Modeling2004.11数学建模竞赛后的思考我也想说徐子彬（武汉大学，湖北 武汉430072）最近我看到网上不少同学在发数模比赛的牢骚，说评卷不公，诚信上把关不严，并举了一些靠老师或论文获了奖的例子，大有不平之意，对比赛的挑战性和公正性产生怀疑。有人强烈反对指导老师的存在；有人觉得数模比赛的结果不能体现个人真实水平，提出干脆取消得了。另一方面，一些自称获了奖的同学在互相攀比，沾沾自喜，似乎觉得自己已经做了了不起的事情，还想得到更广泛更高度的承认。有人嫌获奖的人数太多了，害怕好容易获的奖变得不值钱了还有人乐此不疲地讨论奖金，保研等可能的收获，简直有些趾高气扬了起来。我不觉得这些很过分，因为参加比赛本来就是为了赢，而结果带来的激动往往会抑制冷静的思考。我也曾经这样过，但现在的我已经完全不能同意他们。很多人已经对这些人的观点做了回击，我也不想在这里再展开了。在我看来，以上想法根本不值得讨论。过分在乎获奖与否根本就没有什么意义，也偏离了比赛原来的目的。CUMCM的规模越来越大，当然有官方宣传的作用，但目的本来是很明确的：那就是在全国推广数学的应用，使得各个专业的学生有机会体验简单的科研活动。美赛是偏商业性的比赛，除了锻炼学生能力，还有向社会征集实际问题解决方案的味道。没有人是真正为了颁奖或分个胜负去搞一个比赛。为了获奖而动手脚不是比赛的耻辱，而是这样做的人自己的耻辱。但我要说的是，上帝总是公平的：不恰当地得到了奖的同时，必然失去了比赛真正重要的奖励。指导老师干预的程度会显著地影响比赛的成绩。这是无可争辩的。但就学习的角度上，老师的过多参与并不能给参赛者本身更多的收获，相反，只有那些坚持用自己的思路和资料，选择自己的角度切入问题的同学，才会在过程和结果中得到更多享受。但现实总是让人尴尬。在这个笃信结果更为重要的时代，人们往往只看奖，这就容易造成如前所述的很多困惑。我也一直认为，全国一等奖本身并没有什么了不起的。一来因为我看到很多同学本来数学和编程的能力都不错，只是在捕捉问题和运用论文表达上缺乏经验才与数模奖失之交臂：他们的个人能力未必亚于大奖获得者，合作也不是不默契。二来即使是在获奖的队伍，每个人所实际做到的贡献也可能相差悬殊。一个成功的团队中的成员往往都被认为不可或缺，但获奖队并不都能达到这一标准。三来由于比赛的时间很短，决定了所做的课题不可能是真正的科研问题，而只能算是某种缩影或预演于是在评奖时，论文的规范化和表达上更容易引起关注也不足为奇。然而，以此就划分出等级来评价整体的优劣，似乎就不够公正了因为它在某种意义上给予那些具有经验的人以绝对的优势，使得即使整个工作并不出色，也能在这样的人物的带领下变得貌似出类拔萃。如果缺乏类似的经验，即使工作本身做得更出色一些，也往往会毫无结果。今年我再次参加了比赛，也拿到了一等。但我承认其实这次主要是依靠经验而不是激情赢得了比赛。我一直问自己，如果比赛本身的挑战性在数模的本色上被削弱，如果老师的加入（或者经验丰富的队友）的作用能够改变获奖结果，那么比赛本身又能带来多少荣誉呢？能够证明自己什么呢？我想这个问题其实也是发牢骚的同学真正想问的问题。我想我终于找到了一个答案，那就是：只要不那么在乎结果，以上问题就都不成其为问题！事实上，没有任何比赛的结果是完美的：即使是GRE这样完全客观题的评分（在流程上应该算是简作者简介：徐子彬，曾获 2004 年 MCM 二等奖，2004 年全国大学生数学建模竞赛一等奖。4数模2004 年单和公正的极限了），也会由于泛滥了的应试者的体力训练而丧失考核的意义。如果结果本身更重要，那么教育作为某种奖励，就会使得同一大学，同一研究院培养出的同学们在很大的程度上具有素质上的相似。但即使是上过清华，留学过美国，就能保证以后一定成功吗？我们看见的不是这样：关键还是在你从中学到过什么。同样是一等奖的同学们在能力方面和水平高低上有极大的差异，这本身也说明了奖项本身不能代表水平。从另一方面看，GRE使人接触了更多的学术英语，名校给予了全面素质提高的机会。而数模比赛本身也是为了鼓励大家运用数学，参与科研，学会合作。现实中很多数学院的同学往往不重视实际工作；工科同学又往往不重视理论的意义；中国大学生普遍缺乏动手做科研，和与同学合作的机会。因此这样的比赛对很多人来说，都算是学习的最好机会和难忘的经历了！CUMCM在组织上已经是我所能想象最好的样子。作为普及性的比赛，它的奖也是鼓励性质而不可能是届定性质的，那些真正用心做的同学一般都能有恰如其分的结果，或者能有机会吸取到难得的教训。这就足够了啊！事实上，比赛什么的结果本来就不重要。大家只要数数小学获过的奖，想想现在拿出去有什么用，就知道现在的奖十年以后有什么用了。申请简历上添上一笔当然光彩，但比起自己实际的水平就不那么关键了。只要不是太在乎奖状，又何必在乎别人是怎么利用指导老师，评委又怎么应该给你评得再高一点呢？如果我们愿意把重点放在过程上，看看在比赛中怎么学会了对数学表达的运用，怎么提高了编程和写作能力，怎么对科研活动产生了熟悉感和亲切感，怎么在训练和比赛遭到变故时保持镇定，产生矛盾后怎么和队友协调，在身体极限情况下怎么克制自己，那么我们就会发现，参赛已经很值得了。一次参赛，终身受益。这不是故弄玄虚，而是真正的有好处的地方。我说过我依靠了一些经验，但这些经验不是对付这些比赛的经验，而是如何理解课题，如何展开课题，如何表达更容易被接受，和如何组织队友做最高效率的配合。这些都是以前的数模活动所帮助我获得的。我能够肯定的是它们还将在未来一直帮助我获得更大的机会和接受更大的挑战。而这次参赛的结果反过来又强化了我的自信，如此而已。作为数学专业的我原来很少接触科研流程和论文写作，但参赛的经历让我改变了自己。我后来做西北大学经济学系的一个远程RA，从中学到了更多东西，起点就是数模。我的一个工科的队友曾说数模让他更深刻的理解了自己的专业，后来他非常热心地投入到本专业的研究课题中，成为为数很少的直接跟研究生做问题的本科生。有人说数模解决的不是真问题，但他们没有看到，只要愿意从数模中学习，就可以一步步地深入到真问题，就可以抓住越来越重要的机会！把握的好，一次机会就能改变一生。这些优点又岂是什么奖项能够代表的呢！最后想再谈谈对诚信问题的看法。指导老师能给予队员的本来只有思路上的指引，当然我也听说有些个别老师是甚至直接参与到细节解题的。有些同学因为别人得到了更多帮助而愤愤不平，但我认为大可不必。原因有三：一、用别人的建议代替自己的思考其实是最吃亏的事情。我想起一个成语叫买椟还珠。参加比赛不是为了赚钱。老师可以起到一定作用，但他能给你的最多就是一个奖，以及产生的依赖心理和作弊的愧疚。他能一直帮助你到你真正工作吗？如果你没有能力参与真正的科研或管理工作，那么这个奖也没有用。如果你有能力，那么你就该看到，只有锻炼自己的想法，才是日后成功的关键。何必鼠目寸光。二、我不认为指导老师的意见就完全是好的意见。很多时候，队员自己的专业和知识背景的丰富是老师所不能比的。老师的参与有时只是代替队员，却未必提高了队员。对于一个开放的问题，着手的角度根本不可能完全重合，在一个新问题上，即使是经验丰富的老师，即使他能够迅速看到问题的某种理解上的关键之处。这一建议也未必比队员自己慢慢摸索出的具有更大的价值除非这个老师在整个过程中参与。三、只有自己的意见，才能被最充分理解和运用。有经验的人会发现，同样的思路，思考的程度直接反映到成果的质量。我认为这就象是上帝赋予思想的印记一样，已经被公平的贴上了专利的标签。不只这样，我还经常发现，尽管我一开始思路未必好，甚至可能走偏，但坚持自己的想法，在最后的展开上常第 1 期徐子彬：数学建模竞赛后的思考我也想说5常有机会获得闪光的突破。这种突破是长时间的对问题整体把握的一系列想法的冲击下才自然产生的。我从来不怕把我的想法和对问题的理解在任何时候告诉任何人，甚至公开（当然我从来没这么做），因为我知道没有人比我更能对这些想法负责到底，也就没有人能利用它们而超过我们。我可能说得太多了。我希望不要有人误以为我在说教什么。我只是觉得，真正有意义的东西不可能是别人给你的，只有靠自己去获得。奖是别人给的，学习经验却是自己获得的。当你面对另一个得了一等奖的人时候，请不要把你和他的奖去比较，请把你的论文和他的论文去比较。当你回顾自己的这段经历时，请不要计较别人对此给过你什么待遇，而应该问问自己究竟收获了哪些东西，以后怎么进一步利用这些东西。第 1 卷第 1 期数模Vol.1，No.12004 年 11 月Mathematical Modeling2004.11数学建模竞赛新手教程向为（国防科技大学，湖南 长沙410073）1数学建模竞赛是什么？路漫漫其修远兮，吾将上下而求索数学建模竞赛，就是在每年叶子黄的时候（长沙的树叶好像一年到头都是绿的）开始的一项数学应用题比赛。大家都做过数学应用题吧，不知道现在的教育改革了没有，如果没有大变化，大家都应该做过。比如说，树上有十只鸟，开枪打死一只，还剩几只，这样的问题就是一道数学应用题（应该是小学生的吧）。正确答案应该是9只，是吧？这样的题照样是数学建模题，不过答案就不重要了，重要的是过程。真正的数学建模高手应该这样回答这道题。“树上有十只鸟，开枪打死一只，还剩几只？”“是无声手枪或别的无声的枪吗？”“不是。”“枪声有多大？”“80100分贝。”“那就是说会震的耳朵疼？”“是。”“在这个城市里打鸟犯不犯法？”“不犯。”“您确定那只鸟真的被打死啦？”“确定。”“OK，树上的鸟里有没有聋子？”“没有。”“有没有关在笼子里的？”“没有。”“边上还有没有其他的树，树上还有没有其他鸟？”“没有。”“有没有残疾的或饿的飞不动的鸟？”“没有。”“算不算怀孕肚子里的小鸟？”“不算。”“打鸟的人眼有没有花？保证是十只？”作者简介：向为，SHUMO.COM 创始人之一，第一任站长兼网站设计师，曾获 2001 年全国大学数学建模竞赛一等奖，现为国防科技大学硕士研究生。编辑注：鸟类是卵生，不会怀孕的，：）第 1 期向为：数学建模竞赛新手教程7“没有花，就十只。”“有没有傻的不怕死的？”“都怕死。”“会不会一枪打死两只？”“不会。”“所有的鸟都可以自由活动吗？”“完全可以。”“如果您的回答没有骗人，打死的鸟要是挂在树上没掉下来，那么就剩一只，如果掉下来，就一只不剩。”不是开玩笑，这就是数学建模。从不同的角度思考一个问题，想尽所有的可能，正所谓智者千虑，绝无一失，这，才是数学建模的高手。然后，数学建模高手的搭档论文写作高手（暂时称为写手吧），会把以上的思想用最好的方式表达出来。一般的写手会直接把以上的文字放到论文里就完了。但是专职的数学建模论文的写手不会这样做，她们会先分析这些思想，归整好条理；然后，她们会试着用图画来深入浅出的表达这些思想，或者再使用一些表格；这些都是在Word中进行，当然，如果有不喜欢Microsoft的朋友或是国粹主义者喜欢用WPS什么的当然也可以。她们都是这一行的专家，相信Word什么的使用技巧，都够她们写一篇论文的了。她们不一定会打字，但是输入公式的速度确是一流的。她们一定会用一种画图软件，不管是Visio还是SmartDraw，她们都会用来明确而清晰的表达自己的思想。好了，有了思想，也有了表达思想的人，还少一样东西实现。屈原老哥就有那么多的怀疑与问题，作为数学建模竞赛的评委当然也不是好骗的，不会那么容易相信高手们的话。所以要一个编程高手实现之（暂时称为程序员吧）。就上面所说的问题，程序员会编一个仿真的程序，实现以上所有的情况。这个程序是这样子的，他对以上所提到的每一种情况提供相应的选项，比如说，我们可以选择枪的声音的分贝数，可以从80到100分贝调节，或者干脆从0到200db均可，调节方式是无级变速方式，当然，电脑太慢，在遍历的时候可能要指定步长，嘿嘿，所以，最好买个好电脑，CPU一定不要用赛扬的，要用奔腾的，另外，为了程序员的安全，还要用液晶的显示器，要有UPS不间断电源，要有健康的座椅哈哈，扯远了。仿真程序会尽一切可能按实际所限制的条件遍历所有的情况，看一看还剩下几只bird。当然，这也不是实践。真的做的绝的，会跑去烈士公园做实验，当然得拿一把枪，可以拿塑料子弹枪。烈士公园离我们学校很近，就在南门嘛。那儿有一个地方养了很多鸽子。虽然不能保证刚好10只鸽子，也不能保证刚好都在树上，但也可以将就着做实验，然后根据实验条件做一些修正。哈哈，这样就完美了把实践结果与仿真结果、理论结果做比较，再修改理论、仿真程序、论文，再做实验、做仿真，再比较，再修改，递归到时间的完结。2建模中的分工与合作有些同学觉得，参加数学建模竞赛的目的就是为了提高一下自己的数学水平，或是别的水平，我不以为然。既然参加数学建模竞赛，其目的就应该是，而且是强烈的目的，去拿一等奖。我们应该如何分工？传统的标准答案是数学、编程、写作。但是对于每一个参加过数学建模竞赛的同学来说，感悟各不相同，所以答案也各不相同。下面是我的一家之言，有经验的朋友也可以一起讨论一下。8数模2004 年分工不用那么明确。但有个前提是大家关系很好。不然的话，很容易产生矛盾。提醒一点，在搞竞赛的那几天，睡不好觉，心情急躁，很容易与搭档们发生冲突。分工太明确了，会让人产生依赖思想，不愿去动脑子。假如写手只是实现一个打字员的功能，把数模高手的思想表达出来，那是不够的，写手要有自己的思想，能够检查对方的错误，能够提出自己的思想。按我的想法，理想的分工是这样的。数学建模竞赛小组中的每一个人，都能胜任其他人的工作，就算小组只剩下她（他）一个人，也照样能够搞定数学建模竞赛。在竞赛中的分工，只是为了提高工作的效率，做出更好的结果，并不是由于能力不适合做别的工作。我一直都这么认为，只有能够独当一面的人，才能更好的与他人合作。其实想想也应该是这样的，在以后的学习、工作、研究中，数学能力、编程能力、论文写作能力，哪一项是可以缺少的呢？当然，现实并非如此。我们很难找到三个这样的人凑到一起。所以，凑合着吧。我给一点儿建议，三个人中，一定要有一个人脑子比较活，善于思考问题，这个人，嗯，勉强归于数学方面吧；一定要有一个人会编程序，能够实现一些算法，这就够了。另外需要有一个论文写的比较好，不过写不好也没关系，也可以学嘛，多看一看别人的优秀论文，多用几次Word，Visio就成了。（强烈推荐一篇论文Word在论文写作中的技巧，这篇文章我这儿有，不过怎么让大家看到呢？我想想，网上应该能搜到吧）。说到看论文啊，我真是觉得，优秀的论文就像 九阴真经 一样，看了之后会让你功力大增的。大家一定要多看，特别是想在数学建模竞赛中取得好成绩的朋友。看过论文之后，明白的不仅仅是论文要怎么写，也在同时学到了作者的思考方式。我建议，有决心的朋友不如背几篇优秀论文。常常有人问，搞数学建模竞赛是不是需要我学习很多知识啊？比如图论、概率论、神经网络、组合数学、小波分析、泛函分析、最优化我的回答是，一门都不用，甚至连高等数学都可以不学，有那么多时间去学这么多课程，还不如把时间拿来去看懂别人的论文呢。很多优秀的论文，其高明之处并不是用了多少数学知识，而是思维比较全面，切合实际，能解决问题或是有所创新。有时候，在论文中可能碰见一些没有学过的知识，怎么办？现学现用呗，在优秀论文中用过的数学知识就是最有可能在数学建模竞赛中用到的，你当然有必要去翻一翻啦。有些同学觉得，参加数学建模竞赛的目的就是为了提高一下自己的数学水平，或是别的水平，我不以为然。既然参加数学建模竞赛，其目的就应该是，而且是强烈的目的，去拿一等奖。这样，才会取得好成绩的。分工就说到这儿，下面讲合作。合作真的很难，哈哈，我也没心得。上次合作做数模，我差点儿被气爆了，可能是我耐性不够吧。我只能说一句话以大局为重。我想，如果合作者中有一个是小MM，肯定就不一样了吧，希望大家合作愉快！3选拨的历程百二秦关终属楚三千越甲定吞吴请允许我引用一下我的搭挡王瑛的文章：数模之路1（略，全文见本期第1页）呵呵，我只能以我们学校为例，说一下数模竞赛的选拨历程了。看过以上文章，相信大家对数模竞赛的选拨应该有所了解。第一轮选拨是在每年的5月1日开始的，为期一周，任何人都可以参加，甚至不用报名，在网上下载了题目做掉上交即可。接着是对选拨出来的同学进行培训，再进行两次选拨，选拨方式主要以做数学建模竞赛的题目为主。最终选定的人会在9月份参加全国大学生数学建模竞赛。在全国竞赛中取得较好成绩的而且原意参加美国数学建模竞赛的同学，会在寒假参加美国数学建模竞赛（可惜不能去美国，只是网上发题）。其实选拔上的人不一定就比没选上的人强多少，关键是个机会，看自己把握了。跟我一屇的一组，在第 1 期向为：数学建模竞赛新手教程9第一次选拔赛中没有被选上，但他们仍然坚持参加后来的培训，最后参加了2001年的全国赛，并取得全国一等奖。对于王瑛的文章，我有很多不同意的地方，也请大家不要太当真，对的地方接受，不对的地方就舍弃。首先，文中提到“数学建模真的很难”，我就不同意。之所以第一次参加比赛没有什么结果，是因为我们没有重视，一点儿准备都没有，事前对数学建模是什么都不太了解，就开始去做全国竞赛题，当然做不出什么。其实数学建模竞赛不过是数学应用题罢了。今天偷偷懒，用了别人的文章。下一章我会详细写一下我们参加全国数学建模竞赛的全过程。4实战2001年9月未，我们终于迎来了全国大学生数学建模竞赛。那时候西山居有一个游戏刚刚出炉，里面有一首歌叫做“爱的废墟”蓝蓝的天空是谁的身体让云掠夺而去留下感情的证据当感情在你的心里慢慢的扭曲我的爱对你是不是委屈加上了恐惧伤心的流星凄凉的逃避留下星星收拾这不负责任的结局是谁把天空撕裂出星星的伤口抹杀了我的自由还有浪漫的温柔如果说天外的雨是星星为我落下的泪滴我不知道在你心里是否还有受伤的痕迹如果说心中的雨是来自一处残破的屋宇我不知道呵护的记忆是否会成为埋藏爱的废墟不知道为什么，我比较喜欢忧伤的感觉，就象这首歌给人的感觉一样，那样容易让人产生力量:)在竞赛开始的前一天，我和两位搭挡就开始往招待所里面搬运必要的作战武器了。列个清单吧：数学手册一套（5册）每一册都有一个拳头那么厚高等数学教科书（国防科大），概率论（复旦大学），数值分析（国防科大），MATLAB的一些参考书，C语言教程（谭浩强的那本），等等等等三台自己的电脑，都是赛扬533、566之类的配置，且均有网卡、UPS不间断电源及网线（当时用的是同轴电缆），一个Modem。软件有MATLAB，Visual C+，Microsoft Word，Windows 2000操作系统（当时还没有学会Visio，其他软件好像就没有什么了）从学院的机关里借了一台HP的Laser Jet 6.0打印机 这么多东西当然不是人力所能承受的，还好学校给了辆不大不小的车。一切准备就绪，我们就入住了学校南门外的招待所里（以前条件一般，具说现在已经改建的上档次了，哈哈，一般人住不上）。老师告诉我们第二天早上8:00从网上Down题目，但不知道是谁传来了一个消息，说晚上就有可能从网上下载到题目。于是整个晚上我们都没有睡安稳，时不时上一下网，看一看能不能下载赛题了。但是最终还是在第二天早上8:00才搞到题目/:)编辑注：本文最初在SHUMO.COM连载，不是一次完成的10数模2004 年数学建模竞赛一般有四道题目，其中有两道是本科组的，两道是专科组的。专科组与本科组有一道题是基本相同的。题目分别是：血管的三维重建，公交车调度问题。这两道题得选一道做。选哪一道呢？仔细研究了一下，我们发现，公交车调度是一个最优化的问题，而血管的三维重建偏重于算法。与是我们三人毫不犹豫的选择了血管的三维重建。附带说一句，原因是什么呢？因为我们曾在一年前也做过一个最优化的问题，那一次是钢管运输问题，做的奇差，于是大家心有余悸，尽量不选这类题目。题目：http:/ BMP文件格式 的书，准备利用C程序把BMP给读出来。刚准备着手去做的时候，我们却意外的发现MATLAB中有现成的函数imread可以用！真是天助我也，马上把所有100张BMP图片给读了进来，把每一个切片图的BMP文件转化为一个512512的0，1矩阵。并利用save函数，打开ASCII开关，把每一个矩阵存都存为了txt的文档。这样，C程序就可以直接使用了。在上面的过程中，我们发觉题中给的BMP的命名不太好，它是0，1，2到99的，我们把这些名字改成了01,02,03,04,.99，把所有的文件名都改成了两位的，方便操作。接下来就是如何得出结果了。首先我们在图书馆里查了很久，看有没有论文解决相类似的问题。不但要查中文的，还要查英文的。顺便说一句，英语真的很重要，在网上，英文更是当之无愧的霸主，想利用网络查找资料，英语不好则寸步难行。我们发现了医学上的CT成像技术有可以借鉴的地方。这些资料不一定有用，但能够很好的开拓我们的思路，花时间在上面是值得的。然后，我们想啊想啊，不停的想来想去，并且用ACDSEE把这100张BMP的图像放幻灯版似的正放倒放，还用像皮什么的模拟成血管，弯来弯去。最后，凭直觉猜测能够被切片包含的半径最大的圆的半径等于原始球（形成包络的球）的半径。于是我们开始了分头的工作，一方面一个人去证明这个结论。另一方面，开始编程实现这个想法。在编写程序的过程中，我们还延伸出了两个假设：可以被切片包含的圆的半径一定小于等于原始球的半径；不能被包含于切片的圆的半径一定大于原始球的半径。呵呵，利用这两个假设，就很容易的用二分法搞定了这个程序。不过程序运行起来可不轻松。我们把程序分到三个机子上工作，每一个机子上算一部分图，这也算是并行式算法了吧。就是这么算，也用了一个晚上的时间。在其间，我们还修改了一点算法，重新算了一遍。的确，算法是要不断改进的，请看这句：“因为所给数据精度有限，所以包含于切片中的以原始球的半径为半径的圆可能不止一个”，这就是在算法实现过程中发现的。一开始，是很难想到这些细节的。还提一个细节，用Windows console程序，或是用DOS程序（Turbo C）编写这个程序很难。因为我们最小就要用到512512的矩阵，在算法编写的过程中，为了方便，还会用到更大的矩阵。但是DOS是不支持这么大的矩阵数组的，所以建议大家都编写32位的Windows程序。我们提了这些假设，要完全科学的证明可真不容易。有时候，他认为理所当然的事情，我认为应该证明出来；我认为逻辑混乱的证明，他确认为完全正确。呵呵，于是，我们争论一会儿，证明一会儿，再交流一会儿，再争论。一次，我争论的冒火，心就好像要爆炸了，心想，这竞赛我不做了！我回学校！我为什么要和你们合作？我为什么要迁就你们？我不干了！我强忍着，没有说话，走到窗前，仰头看了看外面的蓝天，突然间想起了那首歌“蓝蓝的天空，是谁的身体”，我慢慢的哼起来，一刹那，一切都清静了。我默默的坐到电脑旁，继续编起了程序第一天晚上睡了4个小时，那个晚上睡了2个小时。算完之后，就只有一天了。第三天晚上，没有睡觉，因为要赶论文。编辑注：现在称为甲组、乙组第 1 期向为：数学建模竞赛新手教程11由于我们不怎么会用Word，图表的编号、排版都是纯手工的，太苦了，唯有身在其中方能体会呀。经过了大量体力劳动，论文完工了，来不及仔细检查，就打出来上交了。刚交完，我们就发现了的图的编号命名出了点儿错误，唉，大家谨记我们的教训！顺便说一点儿做数学建模题的小经验。1.随时记下自己的假设。有时候在自己很合理的假设下开始了下一步的工作，我们就应该顺手把这个假设给记下来，否则到了最后会搞忘记的。而且这也会让我们的解答更加严谨。2.随时记录自己的想法，并且不留余地的完全的表达自己的思想。在比赛后，老师讲评优秀论文时，有很多同学常常抱怨，这个想法我也想到了的啊，就是没有表达出来，或是没有表达清楚。但常常就是这一点别人没有表达清楚的东西，促成了一篇优秀论文。3.要有自己的特色。这么多数学建模竞赛论文，凭什么让老师们投自己一票？当然得有自己的特色了。通俗点儿，就是要有自己的闪光点。5结束语及荣华之未落兮，相下女之可治新手教程写到今天，也差不多了，后面的，就不应该只是新手教程了，应该是提高教程，我能力不够，写不出来了。还希望有高手能够把教程续继下去。这一系列教程文字拙劣、思想简单，还请大家容忍。我建议大家再看一看 董乘宇写的“数学建模竞赛中应当掌握的十类算法”2（在编程交流版块），好好练习练习。再多做几道数学建模竞赛的题目，再与优秀论文比照比照。常有人问：我觉得自己什么都不会，我不会用MATLAB，我不会用C+，或是我的程序编的不精通，我的数学知识就那么一点儿，我没写过几篇论文，我怀疑自己什么都干不成其实，谁又知道自己一定能拿奖呢？谁能保证什么都会，什么都精通？谁又能保证以完美的状态去参加竞赛呢？不要太苛求自己，不要对自己没有信心。即使面对的是无法超越的崖，也要勇敢的跳过去。不试，你怎么知道呢？没有必要去学那么多的东西，数学建模竞赛，竞赛而已。参考文献1王瑛.数模之路J.数模，2004，1:1-2.2董乘宇.数学建模竞赛中应当掌握的十类算法J.数模，2004，1:12-14第 1 卷第 1 期数模Vol.1，No.12004 年 11 月Mathematical Modeling2004.11数学建模竞赛中应当掌握的十类算法董乘宇（北京邮电大学，北京100876）1十类常用算法数学建模竞赛中应当掌握的十类算法：1.蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。2.数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB作为工具。3.线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件求解。4.图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。5.动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。6.最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。7.网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。8.一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。9.数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。10.图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB进行处理。以下将结合历年的竞赛题，对这十类算法进行详细地说明。2十类算法的详细说明2.1蒙特卡罗算法大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。举个例子就是97年的A题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正作者简介：董乘宇，曾任 SHUMO.COM 论坛“编程交流”版版主，获 2002 年全国大学生数学建模竞赛一等奖。第 1 期董乘宇：数学建模竞赛中应当掌握的十类算法13态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。2.2数据拟合、参数估计、插值等算法数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98年美国赛A题，生物组织切片的三维插值处理，94年A题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的走向进行处理。此类问题在MATLAB中有很多现成的函数可以调用，熟悉MATLAB，这些方法都能游刃有余的用好。2.3规划类问题算法竞赛中很多问题都和数学规划有关，可以说不少的模型都可以归结为一组不等式作为约束条件、几个函数表达式作为目标函数的问题，遇到这类问题，求解就是关键了，比如98年B题，用很多不等式完全可以把问题刻画清楚，因此列举出规划后用Lindo、Lingo等软件来进行解决比较方便，所以还需要熟悉这两个软件。2.4图论问题98年B题、00年B题、95年锁具装箱等问题体现了图论问题的重要性，这类问题算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等问题。每一个算法都应该实现一遍，否则到比赛时再写就晚了。2.5计算机算法设计中的问题计算机算法设计包括很多内容：动态规划、回溯搜索、分治算法、分支定界。比如92年B题用分枝定界法，97年B题是典型的动态规划问题，此外98年B题体现了分治算法。这方面问题和ACM程序设计竞赛中的问题类似，推荐看一下 计算机算法设计与分析（电子工业出版社）等与计算机算法有关的书。2.6最优化理论的三大非经典算法这十几年来最优化理论有了飞速发展，模拟退火法、神经网络、遗传算法这三类算法发展很快。近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场，比如：97年A题的模拟退火算法，00年B题的神经网络分类算法，象01年B题这种难题也可以使