2007年全国研究生数学建模竞赛D题.pdf

《2007年全国研究生数学建模竞赛D题.pdf》由会员分享，可在线阅读，更多相关《2007年全国研究生数学建模竞赛D题.pdf（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2007 年全国研究生数学建模竞赛 D 题邮政运输问题这是一条真实的实际问题，是山东大学老师的课题的一部分， 同时又有一定的难度， 因为它对应于著名的数学问题或没有现成对应的数学问题，所以解决它需要较高的创造性。2007 年有 400 多个研究生队选择做这条题目，整体上讲完成情况还比较好。因为参赛队很多，有些队考虑得比课题组全面，有些结果比参考答案还好些。 现在想结合对这条题目的竞赛情况分析大致了解我国研究生数学建模水平的现状， 发现我国研究生教育中的薄弱环节，希望成为研究生教学改革的参考，盼望能够对诸位教授、教练对研究生数学建模的指导有所帮助。因为本文的重点所在，所以 2007年竞赛取得的成

2、绩这里不再多叙述。一一要培养研究生抓住问题本质的能力，要培养研究生抓住问题本质的能力，多一点辩证法，多一点辩证法，高屋建高屋建瓴才会有正确的研究策略瓴才会有正确的研究策略即使不考虑邮包的限制、不考虑里程上的约束、不考虑时间窗的条件，不考虑可能有几辆邮车，并可以在支局之间架设高架桥，第一问也是著名的哈密尔顿问题或最短闭通路问题， 是有时间窗的车辆路径问题。大多数研究生能够抓住问题本质，前进了一大步。既然它属于 NPhard 问题，因此在战术上我们一定要重视困难，不应该刻意追求最优解。因为只有恰当地选择目标，做到力所能及，才能提高研究的效率。另一方面，研究生们应该辨证地看问题， 实际问题本质上属于

3、某一类数学问题并不等同于同类型的纯数学问题； 某一类数学问题目前无法获得理论上的最优解， 并不代表每个实际问题也一定找不到最优解；某一类数学问题目前没有有效的求解方法， 并不说明对某实际问题也没有简便易行的求解方法。增加了约束条件，给出了限制，也减少了可行解，尤其约束条件给得越多，则可行解就越少，前面是“大海捞针” ，现在是“游泳池找针” ，对于具体问题反而可能降低了优化的难度。所以对具体问题应该既见共性又见个性， 不能停留在一般的理论和方法上以至无法深入， 在战略上研究生应该藐视困难， 不轻易放弃最优解，如果能够证明已经找到了最优解则更有价值。因为增加约束条件，实际上提供了附加的信息，甚至暴

4、露出解决问题的“突破口” 。由于具体问题不同，增加的约束条件不同，因此突破口的选择也因问题而异。 具体问题具体分析是研究生们需要着力培养的一种能力。因为有些情况就是因为找不到突破口而无法下手。如第一问增加了每辆邮车运送邮包数量、 行驶时间和邮车速度的限制，显然需要分三车次运送，即把 16 个支局按需要送达和运出邮包的数量，按路程的长度分成三个大小基本相同的集合， 而且集合之间可能是无交的，这样问题就非常简单了。二二 要大力培养研究生对数学模型和对结果的表达能力这一基本要大力培养研究生对数学模型和对结果的表达能力这一基本功功有合适的数学模型是求解问题基础， 才可能借用现成的数学方法或现成的软件来

5、求解，才可能进一步修改完善。如果数学模型自身是有缺陷的，解答不可能是完美的；数学模型自身的描述是不全面的，结果肯定是不理想的；目标函数是不恰当的，结论和实际情况之间就会有距离。甚至同一个实际问题用不同的数学模型来表达， 求解的难度会大不一样。 例如线性规划模型对于 “或” 这类约束条件就很无奈。从竞赛的整体情况看，研究生对数学模型的表达能力还不强。 要给出严格、准确、 全面的数学模型需要苦练基本功。不少研究生队没有能够写出前两问完整的数学模型， 其实只要设置辅助变量就不困难了。除了文字表达之外，对于结果的表达也非常重要。表达应该力求做到一目了然，表达应该尽量直观，表达应该突出重点，表达应该清晰

6、准确。不同的表达方式效果大不一样， 对进一步的思考也有很大的影响。如用图、 表来表达这个问题的结果就令人置信，也容易发现可以改进的方面。应该说研究生队之间在表达上差异还不小。三学科交叉融合、综合运用能力是研究生知识结构中薄弱环节“空车率”是邮政运输评价指标和竞赛题目的瑕疵。 追求降低空车率会出现与目标背道而驰的结果， 但绝大多数研究生队对此熟视无睹，不敢怀疑空车率的正确性，不敢挑战权威。虽然少数研究生队对追求降低空车率与追求最短里程做了对比， 指出了追求降低空车率存在的问题，可惜没有找到更合理的指标。其实邮政运输评价指标“空车率”的本意是希望充分利用邮车的运量，减少车辆轻载行驶，有其合理的方面

7、，只是考虑欠全面，出现了上述不合理的结果。研究生不应将其完全抛弃，而应该取其精华去其糟粕。我们完全可以借鉴物理中效率的概念， 改降低空车率为追求高效率实现取其精华去其糟粕的目的。 邮政运输的效率中总功是邮车每个时刻承载的邮包数与相应的行驶里程乘积的总和， 有用功是每件邮包从区局到目的地支局（或从支局到区局）的最短路里程关于全部邮包求和。 应该说要想到这点并不困难， 而所有研究生队都未能想这一点，说明研究生的思路还不灵活、还不开阔。再如第二问是两个层次的网络优化问题， 估计绝大多数研究生没有学习过该课程，但都能够使用这个模型。遗憾的是竟然没有一个研究生队进行迭代寻优，都是每个层次寻优一次就结束。

8、 无论如何研究生总学习过多变量优化问题的迭代寻优方法， 应该想到可以借鉴。这说明研究生在处理复杂问题时往往不善于站在全局的高度考虑问题，经常陷在具体问题不能自拔以至迷失方向。四研究生分析问题的能力有待提高， 抓住问题的关键才能有的放矢，避免盲目性前已介绍第一问突破口的选择就在于对邮包数量的分析。 第二问由于是两层次优化问题，加之约束条件比较复杂，模型求解有一定难度，如果分析可以发现有些约束实际不起作用， 可以先放弃约束进行优化，得到解后再进行验证就简单得多。两层次优化问题首先要解决先进行哪一层优化？其实很简单， 哪一层容易突破就选那一层先进行优化。 因为区车这个层次，肯定区车的行驶路线要经过县

9、局和最短路上的支局， 而县车的行驶路线必须经过哪些支局几乎无法确定。显然应该先对区车路线进行优化。 而研究生在论文中对此普遍没有进行讨论，显得比较盲目。再如优化的目标显然包括邮车数量最少。 但邮车有区车和县车两种，而减少这两类车的数量之间是相互矛盾的。 邮车数量最少是区车数量少还是县车数量少？如果不分析随便选择就陷入盲目性。 但稍做分析，得到结论并不困难，研究生普遍不进行讨论反映研究生分析问题的能力不足。合理假设在使用不同数量的邮车的条件下，总里程数相差不大（已经为许多队的结果所验证） 。由于区车、县车的工作时间几乎相同，而区车的速度是县车速度的两倍，因此区车所占的比例大，则邮车的平均速度大，

10、邮车的平均行驶里程长，故邮车总数比较小。所以追求邮车总数最小应该多设区车。 另一方面， 由于区车每天行驶两趟，而县局及其附近支局肯定会重复经过，因此每天邮车行驶总里程偏大。 所以若以每天邮车行驶总里程最短为目标则应该选择使用比较少的区车。研究生应该养成善于思考的习惯， 将人脑的特长与计算机优势互补。关于区车和县车的工作时间长短也没有什么队进行讨论。 表面上区车和县车行驶时间必须相互衔接， 因此区车和县车的工作时间相互制约。 但由于区车工作时间题目规定为5 小时， 而县车工作时间=18-6-区车工作时间-邮件整理时间 2*1 5 小时，邮车区车和县车的工作时间几乎相等。五研究生既要善于使用计算机

11、，又不能迷信计算机，要敢于怀疑，要能敏锐地发现结果中的存在问题人的大脑与计算机在功能上有显著的差别。 人善于从整体上看待分析问题，思考、计算问题的速度慢，但比较灵活；而计算机则精于细节，强于计算，但由于受制于人编的程序，比较呆板，看问题缺乏高度，一般不够全面。虽然如此，随着计算机技术的迅速发展，计算机能够解决的问题越来越多， 功能越来越强大，研究生在计算机使用水平不断提高的同时也产生了对计算机过度倚赖的倾向。 从这次竞赛的优秀论文中找出了关于每个问题的“最好的解” ，可能都是计算机寻优的结果。研究生们对此深信不疑，可是通过直接观察，我们都可以发现其中存在的问题，加以改进。关键是习惯于不怀疑，不

12、敢挑战权威，这势必阻碍创新思维、扼杀创新精神。个人认为长此以往对研究生的培养质量必将产生不利的影响，应予以重视。六研究生连贯、全面考虑复杂问题能力有待加强第三问是在可以不用本县的县车给支局运送邮件的情况下寻找减少邮车总里程的方案。它实际上是第二问的延伸。由于支局分布不均匀，有的县中处于偏远地点的支局因为与县局和其他支局相距较远，县车专程去这样的支局大大增加了行驶里程， 甚至要增加一辆邮车。而这样的支局可能与邻县的支局比较靠近， 用邻县的县车给它运送邮件反而可以减少邮车总里程， 甚至少用一辆邮车。这就是第三问的实际背景。如果按这里的思路，问题就会立即集中到少数几个“怀疑对象”边缘支局，因而比较简

13、单，最多借用第二问的程序进行穷举、对比，工作量也不是无法接受。但是参赛研究生队却习惯于孤立地考虑问题， 把一个紧密联系的问题割裂开来，从头开始， 重复劳动。这可能与研究生过去所研究的问题一般规模比较小，或者始终在导师的详细指导下进行研究， 因而不善于连贯地、全面地考虑问题有关。 这样的思维方式对于研究生的成长是不利的，尤其对于科技领军人物的成长更是有害。 应该引起有关人员的注意。即使不考虑问题的连贯性， 借用兵法中 “切忌孤军深入” 的思想，也很容易发现第三问中需要改变运送邮件邮车的支局。 “孤军深入”就是与己方大本营相距比较远， 补给困难，而与敌方大部队相距比较近，容易被敌方切断与大本营的联

14、系，这与第三问几乎完全一致。这时已经是个别支局在两个县中选择一个县的简单问题。 但不少研究生队却是漫无目的地搜寻了一番， 几乎没有什么改进；也有的队仅根据与县局之间的距离进行调整，也不合适；还有的队生搬硬套，采用聚类分析的方法来解决问题，虽然与本问题有一定程度的相似，但追求的目标并不一致，结果也是一般。七研究生面对新问题普遍束手无策， 解决全新问题的整体思路和创造性显得尤为欠缺第四问是第三问的延伸， 在县局重新选择的情况下寻找邮车总里程最小的方案。由于没有一个现成的数学问题与之对应，难度很大。对此参赛研究生队普遍束手无策，不知从何下手。情况与 2008 年 A题唐家山堰塞湖泄洪问题基本相同，

15、研究生解决全新问题的整体思路和创造性急待加强。有研究生队将这个问题抽象为将 73 个点分成 6 类的问题，殊不知这样的分法与 6 的 73 次方，即与 10 的 56 次方有相同的数量级，根本无法优化，因此只有模型，没有好的结果也就在意料之中了。这充分说明研究生还不善于运用解决这类问题的一般研究策略，或者只会纸上谈兵，并未真正掌握。其实对于一个复杂、研究处于起步阶段的问题， 研究的整体思路都是要把这个复杂的问题设法分解为一系列简单问题的串联。 都应该由易到难、 由外及内地逐个加以解决，都应该在简单情况下分析寻找问题的本质与规律， 得到猜想之后进而在逐步复杂的情况下验证、修改原来的猜想，形成新的

16、结论，循环上升，波浪式前进。对研究生提出这样的要求是否太高？请注意这批研究生在全体研究生中是水平比较高的，再说“一个不想当将军的士兵肯定不是好士兵” ，让研究生有比较高的追求目标是好事。对于第四问可以先讨论不改变县界， 只选择县局；再讨论可以适当改变县界，并选择县局的问题，对于实际问题到此应该停止；如果转变为理论研究，还可以讨论同时划分县界、选择县局的问题，也有一定理论价值。若不改变县界，只选择县局，则通过分析，可以将全体支局分成四类：1.最靠近或很靠近区局；2.处于县域的质心或到同县各支局的距离最大值达到最小;3.处于远离区局的县域边缘;4. 处于县域边缘但与区局距离并不算远。 这样把第四个

17、问题变成多步选择， 降低了难度，减少了工作量。稍加分析就可以判断后两类支局不应该被选择为县局。 因为县局的选择既影响区车的行驶路线， 也影响县车的行驶路线 （是几条县车的行驶路线的公共点） ，但如果选择第三、四类支局作为县局，则区车仍然经过第一、二类支局，与择第一、二类支局作为县局相比，区车的行驶方案一定不可能增加， 区车的行驶里程最优值不会更小 （小范围内的最小值一定不小于大范围内的最小值） ；而由于这时县局位于县域的边缘地带，到其他支局的里程总和一般情况只会增加， 不会减少。因此在研究县局选择的起步阶段完全可以不考虑第三、 四类支局。即使限于考虑第一、二类支局，一般性研究仍然有难度，无法下

18、定论。按先易后难的原则，还是先从简单、规则的情况入手。发现第一、二类支局都可能成为县局的最佳选择。例如县域比较大，选择最靠近或很靠近区局的支局作为县局， 可能因为它与有些支局相距比较远，加之县车的速度慢，无法在规定的时间内到达，问题无解。再如某县的支局呈辐射状，显然可以选择第一类支局作为县局， 因为这样区车行驶路线最短， 而区车每天行驶两趟， 因此邮车行驶总里程最短。既然找到两种特殊情况说明在选择县局时第一、 二类支局都必须考虑。下一步就应该研究、 寻找第一、二类支局分别成为县局最佳选择的普遍规律。还是可以先考虑一些支局分布规则、 简单的情况，如果某县内支局间交通路线呈环状或呈正方形网格状，

19、而且离区局最近的支局可以在规定的时间内来回运送邮件到其他支局， 似乎都以最靠近区局的支局作为县局是最优解。反之，最靠近区局的支局是一个孤立点，离其他支局都比较远， 而且该县又无法用一辆县车来完成全县邮件的运送任务，则显然应选择第二类支局作为县局。适当改变县界，并选择县局的问题相当于将第三、 第四两个问题合在一起，可以先改变县界，后选择县局并进行迭代即可，至于既改变县界又选择县局的问题的确与聚类分析有很大的相似之处， 可以按各种距离的定义先进行聚类分析以确定县域的划分， 在县界划定以后再选择县局，同样需要进行迭代寻优。这样并不十分困难的问题为什么会困扰我们众多的研究生呢？恐怕缺少类似的经验是主要

20、原因， 因此加强研究生这方面的训练很有必要。八 有些研究生表现出说理不透， 关键之处没有点到位的情况，严密的逻辑推理能力应该提高，虽然大多数情况下并没有找到各个问题的最优解， 当然就谈不到需要证明。但也有少数问题已经找到了最优解， 但是研究生队都没有说明是最优解，更没有给出严格的证明。尽管对非数学专业的研究生而言， 严格的证明和严密的逻辑推理并非必须，但是对于优秀的研究生、 博士生要进行高水平的科学研究就是另外一回事了。 而且通过对结果的严格论证的确可以发现考虑不周到的地方，寻找出可以改进的方向， 经常这样思考问题对提高敏锐的洞察力也很有帮助。如第二问， 当然既希望使用的邮车总数最少， 也希望

21、邮车的总里程达到最少。一般情况这两个目标之间是相互矛盾的， 不可能同时达到最小值。而且寻找邮车的总里程的最优解是比较困难的， 也是难于给出严格证明的。相比较而言，邮车总数最少容易获得，也可能给出证明。前已说明要邮车总数达到最少， 其中区车应该最多。 每县最多也只需要一辆区车， 因为使用两辆区车一定是重复去县局并且增加总里程（由县局到支局距离一般小于区局到同一支局的距离， 而那些靠近区局的支局在第一辆区车的行驶路线中则必然经过了）显然不可取。 现在已经找到方案使 X3 和 X4 县都只要一辆区车就可以运送全县邮件到相应支局，因此这里已经是局部最优了。至于其他三个县局，由于距离区局比较远，区车的路

22、线几乎是唯一的，而剩下的支局分布也很散，加之县车速度是区车的一半， 容易证明一辆县车是无论如何无法完成全县的邮件运送任务，所以这三个县都至少需要两辆县车，因此 5+6=11 辆就是第二问关于邮车总数的最优解。严格的证明和严密的逻辑推理也有助于表达能力的提高。 因为在评阅中经常发现研究生对某问题写得并不少，但就是说不到点子上，可以说清楚的问题却总是给人留下疑惑。 经常考虑如何给出最简捷的证明应该成为研究生数学建模活动的一部分。九 要着力培养研究生对待科学研究的严肃的态度和严谨的学风在评审中我们对优秀论文的结果进行了复查。 结果发现不少研究生队的计算结果，如总里程、总时间总是偏少，仔细校对，发现多数是因为有些支局实际上没有邮车到达， 有些里程没有加进去，有些方案时间上也衔接不上。许多研究生队的解释是因为时间太紧， 没有来得及检查，或者是由于疏忽造成的，这应该是基本可信的。但是比较多的队出现这种情况，而且有的队只有总里程，没有路线或方案，这就不得不令人怀疑其中少数或者个别研究生队造假或者抄袭。 我们认为无论是不认真仔细还是造假都是学风问题值得引起有关方面、 有关人士的关注。以上仅是个人的一些看法，很可能有些过激，也肯定不全面，甚至有些观点是错误的，敬请诸位专家、教授批评指正。