数学建模校内热身赛论文.doc

数学建模论文参赛队员：甘煦、李正威、张彦旎班级：金融SY1101比赛时间：2013年4月4日9：002013年4月7日，上午9：00武汉理工大学第十二届数学建模校内热身邀请赛2013年武汉理工大学第十二届数学建模校内热身邀请赛承 诺 书 我们仔细阅读了武汉理工大学第十二届数学建模校内热身邀请赛的竞赛细则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们的参赛报名号为： 参赛队员 (签名) ： 队员1： 甘煦 队员2： 李正威 队员3： 张彦旎 武汉理工大学第十二届数学建模校内热身邀请赛 编 号 专 用 页 选择的题号： A 参赛的编号： （以下内容参赛队伍不需要填写） 竞赛评阅编号： 【摘 要】 论文题目和摘要动物园规划该问题属于最路径问题，最短路径问题在实际生活中有广泛的应用，在商业利润估算、生产生活、道路建设与规划等方面都有重要意义。本题讨论的是动物园道路最优设计问题：在满足任意两入口之间最短道路长不大于两点连线的1.5倍的条件下，建立相应最短道路模型，使得修建总道路长度最短。又因动物园边界存在已经修建好的道路，且不计入修建总长度，所以应尽量利用边界道路。对于问题一：先不考虑在动物园内建设道路，仅利用边界道路，利用“两个入口最短道路长不超过两点连线1.5倍”的条件找出所有满足条件的情况，然后再把那些必须要利用交叉点的情况逐一验证讨论，找出所有满足条件“两个入口最短道路长不超过两点连线1.5倍”的路径建设方式，通过比较，找出路径最短的情况。对于问题二：利用问题一的结果，可直接利用边界道路实现的情况在此仍然可行，再把问题一中必须通过交叉点连接的情况进行进一步优化，列出各种满足要求的情况，逐一比较找出最优线路。在具体操作时，应先考虑海洋馆的位置对问题一的结果是否会产生影响。最后对该问题进行进一步探讨，考虑到更多与实际情况相符合的情景，并给出大致解题思路关键词：最短路径、穷举法、逐步分类讨论、道路规划、matlab、LINGO、prim算法一、问题重述 改革开放以来，作为中部最大城市的武汉，在经济发展上取得巨大成果。为了响应国家中部崛起战略，营造美好家园，武汉市政府近期决定建造一个矩形动物园。为方便游客游玩，动物园设计规划决策者想在已经建好道路的矩形动物园的四边上设置8个入口；内部有四个交叉点，分别是：。现在请你建立一个模型，在两个入口最短道路长不超过两点连线1.5倍的情况下，如何使道路总长最短？（总长中不计入矩形四边的长度，新修的路与矩形四边的连接只能在入口处，不能在矩形的其他位置） 矩形动物园的基本参数及各个路口坐标为：长：1000米 ，宽：500米图1是动物园入口图，图2是一种可能的规划，但不是最优化的问题一：根据以上信息给出你的计算方法并算出最短总长问题二：如果在中间设一个矩形海洋馆，如图3，海洋馆的四个点坐标为：，要求道路不能穿过海洋馆，但可以到达四边，以此绕过海洋馆，那最短长度又是多少呢？ 图1矩形动物园及其入口图 图2可能的一种情况（但不是最优） 图三 有海洋馆的示意图二、问题分析2.1、问题一的分析 分析哪些点不能通过现成的边界道路实现： 先计算出“8个入口点两两之间的直线距离”，然后计算出“8个入口点两两之间的边界路径距离”。 “8个入口点两两之间的边界路径距离8个入口点两两之间的直线距离1.5”-不需要通过交叉点设计路线。 “8个入口点两两之间的边界路径距离8个入口点两两之间的直线距离1.5”-需要通过交叉点设计路线。入口点两两之间的直线距离表(）M1M2M3M4M5M6M7M8M10150700934.08707.11505.6502.5160.08M20550790.57610.33505.59538.52279.51M30320.16538.52800.39901.39809.71M40471.7862.05982.341007.78M50425550707.55M60125413.82M70378.32M80注：代表上表中Mi行Mj列的元素（i,j=1、2、3、4、5、6、7、8）入口点两两之间的边界路径距离表（）M1M2M3M4M5M6M7M8M1015070011501800775650225M2055010001650925800375M30450110014751350925M40650107512001375M50425550975M60125525M70425M80注：代表上表中Mi行Mj列的元素（i,j=1、2、3、4、5、6、7、8） 找出不满足条件：1.5的i与j的组合，为“M1M5、M1M6、M2M5、M2M6、M3M5、M3M6”，这6种情况不能直接利用边界道路，即要引入交叉点。然后专门考虑上述6种连接方式与交叉点的组合，找出最优路径。具体考虑上述6种情况时，将可能的各种情况逐一列出，分别比较后，找出最优方案。（具体符号意义见下表一）2.2、问题二的分析 在问题二中，引入了海洋馆，并且海洋馆位于动物园内固定位置，所以对问题一中已经讨论过的是否能利用边界道路的情况不产生影响，仍然只需要考虑“M1M5、M1M6、M2M5、M2M6、M3M5、M3M6”这6种情况，并且在问题一的设计方式下有些线路与海洋馆没有交点，固也不会对那一段道路产生影响，所要考虑的只是与海洋馆有交点的几条路径，进行局部优化。进行局部优化时，如果满足要求的情况较多，可考虑利用matlab或LINGO软件进行求解。 3、 模型假设1、 假设实际建设中各条道路都是直线，也不会因为施工障碍而影响原规划。2、 各路口尺寸不计，将各个路口都看做点，不影响规划。3、 假设所有点或线都在同一平面内，不考虑台阶及其他因素影响。4、 假设题中所给数据或图形都真实可靠。5、 假设动物园中海洋馆四周都已有修成的路。6、 动物园内新修的道路与四周的连接只能与8个路口相通，而不能连接到四周的其他点。7、 除题目要求外，道路规划不考虑任何其他客观因素。四、模型符号说明表示动物园各入口及交叉点的横坐标，（i=1、2、38）入口与入口间的直线距离(m)（i、j=1、2、38）入口与入口间的边界路径距离（m）（i、j=1、2、38）入口（交叉点）与入口（交叉点）之间直线距离（m）(i=1、2、3、5、6；i=9、10、11、12时分别对应A、B、C、D)入口（交叉点）与入口（交叉点）的间接通路距离(m)（9到12分别代表A、B、C和D）（表一）五、模型的建立与求解 5.1、模型一的建立与求解思路：先讨论M1、M2到M6的各种情况，再在这些情况下，对M1、M2到M5的各种情况进行分类，最后再对M3到M5、M6在上面各种情况下继续分类。具体实施步骤：在上述分析中已知只有“M1M5、M1M6、M2M5、M2M6、M3M5、M3M6”这6种情况不能利用边界道路，下面对其规划方式进行讨论：在上述6种情况中，涉及到的门只有M1、M2、M3、M5、M6，下面将这5个点分别与A、B、C、D四个门之间的距离都算出来：6个门与交叉点两两之间的距离表（）M1M2M3M5M6ABCDM10150700707.11505.6408.89223.6538.5590M20550610.33505.59375206.16403.1447.6M30538.52800.39665.68632.46282.8416.1M50425371.65500300152.1M60145.77301.04520.2427.2A0182391.3326B0400403.9C0152.1D01、 现考虑M1到M6的距离与M2到M6的距离之和：有前面的讨论知，此时必须要借助交叉点的作用，固M1、M2至少有一个要连到B或A，因为BM1BM2，AM1AM2，所以应选择M2与A或B相连接而不选择M1与A或B相连。M2到M6无论是通过“M2BM6”路径，还是通过“M2AM6”路径，或者通过路径“M2BAM6”，都不会违反条件“两个入口最短道路长不超过两点连线1.5倍”(以下简称1.5倍条件)，记路径“M2BM6”为，路径“M2AM6”为，路径“M2BAM6”为。现考虑路径对于从M1到M6是否满足“1.5倍条件”，因为M1M6=505.6，1.5505.6=758.4（该数值为本类情况的约束条件）。按路径得到由M1到M6的行走路径总长为M1M2+BM2+BM6=653.2758.4（满足“1.5倍条件”）；按路径得到由M1到M6的行走路径总长为M1M2+AM2+AM6=670.77758.4（满足“1.5倍条件”）；按路径得到由M1到M6的行走路径总长为M1M2+BM2+BA+AM6=683.93758.4（满足“1.5倍条件”）。所以上述三种情况都满足“1.5倍条件”。由于无论其后按连接方式如何都不会影响“路径比路径、路径更长”的结论，所以下面不再考虑路径，而仅考虑路径、路径。 2、现在考虑M1、M2到M5，由于M1到M5总是要先到M2，再按M2到M5的方式到达M5，所以现在只需考虑M2到M5的最短距离问题。M2到M5的直线距离为的1.5倍为610.331.5=915.50（该数值为本类情况的约束条件）、在路线的条件下，M2到M5有2种连接方式：路线：M2BM5，算出其总路径长为BM2+BM5=706.16915.50（满足条件）；路线：M2BDM5，算出其总路径长为BM2+BD+DM5=762.16915.50（满足条件）、在路线的条件下，M2到M5有2种连接方式：路线：M2AM5，算出其总路径长为AM2+AM5=746.65915.50（满足条件）；路线：M2ADM5，算出其总路径长为AM2+AD+DM5=853.1915.50（满足条件） 或者不依赖路线、而产生一种新连法：M2DM5，算出其总路径长为DM2+DM5=599.7915.50（满足条件）至此M1、M2分别到M5、M6的各种符合要求的情况已列出：、。下面讨论M3到M5、M6的各种情况：M3到M5的距离的1.5倍为：538.521.5=807.78；M3到M6的距离的1.5倍为：800.391.5=1200.59（这2个数值为本类情况的2个约束条件） 、在的情况下（即如图一所示）M3到M5有3种连接方式：方式：M3CM5，由于不能在交叉点之外的地方交叉，固M3到M6只能按如下方式到达：M3CM5M6，算出M3到M6的总路径长为：CM3+CM5+M5M6=1007.21200.59，算出M3到M5的总路径长为：CM3+CM5=582.2807.78，上述条件都满足。方式：M3DM5，由于不能在交叉点之外的地方交叉，固M3到M6只能按如下方式到达：M3DM5M6，算出M3到M6的总路径长为：DM3+DM5+M5M6=993.11200.59，算出M3到M5的总路径长为：CM3+CM5=568.2DM3+DM5，所以最优为：，具体如图二。DBB、在的情况下（即如图三所示），先考虑M3到M6的方式，假设M3到M6时经过了A点（由“交叉点只能在A、B、C、D”条件知：前一步是D点）该种情况课并入中，在下面具体讨论。所以现在M3到M6只有2种方式：M3CDM5M6；M3DM5M6，由上面的中的讨论已知，这2种情况都满足“1.5倍条件”显然M3DM5M6更优。得到在的情况下的最优情况，如图四。、在的情况下（即如图五所示），当考虑M3到M5时，在、的讨论中已经知道M3DM5要优于M3CM5且满足条件，故选择M3DM5，如图六所示，此时M3到M6已经存在可行路径（即M3DM5M6），所以图六即为在的情况下的最优解。、在的情况下（即如图七所示），同样在考虑M3到M5时，选择路径M3DM5（即如图八所示），同，此时也满足了M3M6可按要求到达。所以在的情况下的最优情况即为图八所示情况。、在的情况下，在不考虑M2到M6到底是按方式还是按方式时，其路径如图九，显然此时保证M3到M5、M6可以按要求到达。且已知“M2BM6”优于“M2AM6”，所以此时最优路径如图十所示。 3、所以各种情况下最优的情况已经求出，即分别如图二、图四、图六、图八、图十所示，将这5种情况比较，得出最优解。设每种情况的总路长分别为：、。=301.04+206.16+403.9+152.1+416.1=1479.3=145.77+375+371.65+152.1+416.1=1460.62=145.77+375+326+152.1+416.1=1414.97即最小，所以图八所示的情况为最优解【结果】最优设计路线图如下：DA最短总长为：AM6+AM2+AD+DM2+DM3=145.77+375+326+152.1+416.1=1414.97。5.2、模型二的建立与求解 由于加入了海洋馆，所以先讨论问题一的设计方案是否有路线会穿过海洋馆，如果没有，则直接按照问题一的方案进行建设，而不会产生冲突；如果有路线会穿过海洋馆，则要进一步进行局部优化。 以动物园左下角顶点为坐标原点，以M1M2所在的直线为X轴，以M8所在的直线且与X轴垂直的直线为Y轴建立平面直角坐标系，算出线段DM3的直线方程为：9Y+14X=11200。将(700，225)带入该直线方程得70014+2259=11825 11200，所以在DM3上方，即加入海洋馆后对问题一不产生影响。所以问题二的最优方案与问题一相同，最短长度仍然为1414.97。六、模型的优化与进一步探索问题一是该优化问题的关键，求出问题一后则问题二可在问题一的基础上进行改进得到。由于该问题中，在问题二里面海洋馆的位置固定，并且不影响第一问的结果，固问题二变的很容易，如果将问题二的条件改为海洋馆位置不固定，则需要分情况进行讨论，当在问题一的规划基础下，如果有某一条边与海洋馆有交点，则需进行局部优化。具体可按如下方式考虑（下面仅提供一种可能的情况，并将其求解思路做一简要介绍，具体情况不一一讨论）：可能的一种情况：DAHGEF海洋馆四个顶点分别为E、F、G、H，并且DM3穿过了海洋馆，所以需要对DM3这条路线进行局部优化，由于海洋馆四周已经存在道路，应充分利用。所以以D为圆心做圆与EH边相切，切点即为连接点，同样以M3为圆心做圆与正方形EFGH的某一点相切（本图为G点），该点即为M3与海洋馆的连接点。这样便得到新的最优方案。可能的另一种情况（海洋馆将交叉点包含在内）；交叉点D被海洋馆覆盖，固交叉点D将不再存在，只剩下A、B、C三个交叉点，仍然可通过上述类似方法找出各种可能的情况，然后逐一进行比较，找出总路径最短的方案。不过可能随着海洋馆位置的变动，有些情况会使各种可能的情况变的相对较多，而不宜再采用人工的方法将其一一列出，这是可考虑利用matlab或LINGO软件进行求解。附录提供了一种可能情况下的编程程序。七、模型的评价与推广 7.1、模型优点没有利用较为深奥的计算机语言，通过数学逻辑进行人工推算，降低了对计算机的依赖，在没有计算机的场合该方法占到了很大优势。引入图表、矩阵、平面直线方程等数学工具，使模型变的相对简单，也更有说服力。对于整体考虑较为困难的问题，通过逐步筛选，使满足条件的可能变的越来越少，最后达到可以人工计算的目的。最后对问题进行进一步探讨，考虑现实生活中可能出现的各种场合，使模型使用范围更广。模型运用的数学知识较为基础，容易理解。 7.2、模型缺点 模型至始至终都围绕“1.5倍条件”，该条件在现实生活中应用并不广泛，从而降低了模型的适用范围。该模型没有用到计算机方面的编程知识，从而可能在实际建模过程中会比较复杂，计算量较大。模型是基于多种假设所建立的，和实际情况还有一些差距。例如：道路为直线、在施工工程中完全可以按照规定方案进行等，均不太符合实际。 7.3、模型推广 虽然本文主要讨论的是动物园内部道路建设问题，但我们使用的方法适用于大部分的最短路问题，包括网络的布局、城市道路及修建、公共场所的修建等问题。该模型对节约社会资源，方便人们活动等各个方面的问题有重大意义。参考文献1姜启源，谢金星，叶俊. 数学模型（第三版）M. 北京：高等教育出版社，20032薛定宇，陈阳泉.高等应用数学问题的Matlab求解M.北京：清华大学出版社,20083赵焕臣，许树柏，和金生。层次分析法，科学出版社，19864王莲芬，许树柏。层次分析法引论，中国人民大学出版社，1990附录（“探讨六”中相关程序段）问题一：在maltab 运行如下程序: clear x=100 250 800 1000 600 175 50 0 700 700 825 825;y=0 0 0 250 500 500 500 125 350 225 225 350; for i=1:12 for j=1:12 if i=j S(i,j)=sqrt(x(i)-x(j)2+(y(i)-y(j)2); end end end disp(邻接矩阵为) disp(S);得到12个点每个点的距离邻接矩：0 0.1500 0.7000 0.9341 0.7071 0.5056 0.5025 0.1601 0.6946 0.6408 0.7591 0.80510.1500 0 0.5500 0.7906 0.6103 0.5056 0.5385 0.2795 0.5701 0.5031 0.6175 0.67310.7000 0.5500 0 0.3202 0.5385 0.8004 0.9014 0.8097 0.3640 0.2462 0.2264 0.35090.9341 0.7906 0.3202 0 0.4717 0.8620 0.9823 1.0078 0.3162 0.3010 0.1768 0.20160.7071 0.6103 0.5385 0.4717 0 0.4250 0.5500 0.7075 0.1803 0.2926 0.3553 0.27040.5056 0.5056 0.8004 0.8620 0.4250 0 0.1250 0.4138 0.5460 0.5927 0.7058 0.66710.5025 0.5385 0.9014 0.9823 0.5500 0.1250 0 0.3783 0.6671 0.7058 0.8223 0.78940.1601 0.2795 0.8097 1.0078 0.7075 0.4138 0.3783 0 0.7353 0.7071 0.8310 0.85510.6946 0.5701 0.3640 0.3162 0.1803 0.5460 0.6671 0.7353 0 0.1250 0.1768 0.12500.6408 0.5031 0.2462 0.3010 0.2926 0.5927 0.7058 0.7071 0.12500 0.1250 0.17680.7591 0.6175 0.2264 0.1768 0.3553 0.7058 0.8223 0.8310 0.1768 0.1250 0 0.12500.8051 0.6731 0.3509 0.2016 0.2704 0.6671 0.7894 0.8551 0.1250 0.1768 0.1250 0M1 M2 M3 M4 M5 M6 M7 M8 A B C D加上约束条件：1) 对角线元素 lii(i=112)设为inf以保证prim算法求解最小生成树时不产生自身到自身的回路 2)由于题目中给出的条件说可以利用公园四周的边且不计入道路总长所以当两入口的边界路线长度小于等于连线距离的1.5倍时我们令这两个入口对应的邻接矩阵元素为0以保证这些边界线在最短路径范围内算的矩阵如下：a=inf 0 0 0 0.7071 0.5056 0 0 0.6946 0.6408 0.7591 0.8051; 0 inf 0 0 0.6103 0.5056 0.5385 0 0.5701 0.5031 0.6175 0.6731; 0 0 inf 0 0.5385 0 0 0 0.3640 0.2462 0.2264 0.3509; 0. 0 0 inf 0 0 0 0 0.3162 0.3010 0.1768 0.2016; 0.7071 0.6103 0.5385 0 inf 0 0 0 0.1803 0.2926 0.3553 0.2704; 0.5056 0.5056 0 0 0 inf 0 0 0.5460 0.5927 0.7058 0.6671; 0 0.5385 0 0 0 0 inf 0 0.6671 0.7058 0.8223 0.7894; 0 0 0 0 0 0 0 inf 0.7353 0.7071 0.8310 0.8551; 0.6946 0.5701 0.3640 0.3162 0.1803 0.5460 0.6671 0.7353 0 0.1250 0.1768 0.1250; 0.6408 0.5031 0.2462 0.3010 0.2926 0.5927 0.7058 0.7071 0.1250 0 0.1250 0.1768; 0.7591 0.6175 0.2264 0.1768 0.3553 0.7058 0.8223 0.8310 0.1768 0.1250 0 0.1250; 0.8051 0.6731 0.3509 0.2016 0.2704 0.6671 0.7894 0.8551 0.1250 0.1768 0.1250 0;运用prim算法： function T c=Primf(a)a=inf 0 0 0 0.7071 0.5056 0 0 0.694