数模随想(转）

daystar · 发表于 2003-10-30 18:47:45

今年的数模竞赛结束了，哪位有什么感想就在这个帖子里面交流一下吧。今年的数模与往年不同，算法的可塑性特别差，A题太泛，赛前就被很多人预测到，而且与以前的传染病模型大同小异，毫无新意；B题所给的实例条件约束条件太多，很难给出一个针对这类问题的一个一般性的算法，发挥空间太小，我和我的兄弟们选择了B题。我们兄弟三人一个负责模型构建和完善，另一个负责数据分析和整理，我主要负责计算和编程。初期阶段我们进行的很顺利，第一天吃晚饭前，我们就给出了一个比较完善的模型，实质上就是一个关于50个变量的线性的整数规划问题，接下来主要是编程计算和优化。几乎在模型出来的同时我就用Matlab作线性规划，得出了一组实数解，问题由此而僵化，我们谁也不能就从实数到整数的过度给出一个好的方案。有的说要用分枝定界法，有的提到0-1规划，到第二天吃晚饭了，问题仍然毫无进展，我再也按捺不住了，在实数解的基础上用C++做了一个优化后的淘汰式搜索算法总算解决了第一问（后来我们把它叫做可回溯贪心算法）。我们算出最小运量为85779.54吨公里，最小车辆数为13辆。但是第二问远没有第一问那么简单，虽然模型很相似，仍然是一个50变量的整数规划问题，但是所需的计算远比第一问复杂，我们那种可回溯贪心算法再也行不通了，我们也因此再一次进入僵局，而且这种可怕的僵局一直持续到第三天晚上8点半。我实在想不通Matlab作为数学软件之王为什么没有提供一个关于整数规划的函数！后来查阅了一些参考书之后才知道整数规划到目前为止除了分枝定界、分割平面、0-1规划和穷举就别无它法了。兴奋的时刻在第三天晚上的8：30，我们终于找到了一个能解决整数规划问题的数学软件Lindo,于是我赶快上网浏览了一下它的语法规则和函数用法，并用它验证了我们第一问的结果，竟然与我们的可回溯贪心算法的结果完全吻合！我真的不能用言语来表达当时我们的兴奋程度，房间沸腾了，我们的一个兄弟当场跳起了扭腰舞。（请不要以为是女生！）我们马上用这个这个Lindo去解决更复杂的第二问，紧张的局面再一次出现了！我们几乎是完全克隆第一问的语言和解法，但Lindo总是给我们报一堆莫名其妙的错误！我们再也没能解决这个问题。时间不多了，其他两个兄弟开始写文档，我继续研究这个问题，也许是老天不帮忙，我们再也没有那么幸运了，一直持续到第四天早上7点，8点就要交卷，我们一直还没能找到一组较较优的整数解。没时间了！我只能用Matlab算了一个实数解再手工整数化了，也算是不幸中的幸运，我竟然手工找到了一组几乎接近理论最优值的整数解，最后的答案是十万三千四百多。
持续72小时的竞赛终于结束了，我总共睡了9个小时的觉，但是临走的时候我们个个都精神饱满，我们尝试了奋斗，好久没有这种塌实的感觉了。特别是跟我一组的两位大四的兄弟，我真的敬佩他们！他们太热爱研究了，为了这次竞赛，他们差点错过了保研的机会。在交卷后的5个小时，他们还要马上飞往清华参加研究生保送面试呢！但是他们已经三天没休息了，交卷后还要马上准备自己的面试材料，他们真的是榜样。无论这次得奖与否，这都将是人生的一次美好回忆。明年，我们再见！明年再战！

tangzw · 发表于 2003-10-30 23:50:48

作者是谁啊?

daystar · 发表于 2003-10-31 00:15:19

我的一同学，湖南大学的

tangzw · 发表于 2003-10-31 00:22:00

你是湖大的?

		自动登录	找回密码
密码			注-册-帐-号