简单距离问题

PAGE0PAGE1 建校选址问题摘要本文针对25个乡镇中建立一所学校的选址问题进行研究。通过对问题中所要建校的要求进行分析，从题中所要求的角度进行建校选址模型的建立。分别建立最远乡镇学生上学最近的模型一和学生上学平均距离最短的模型二。对题中问题1和问题2的解决提供了理论依据。模型一：首先对表中各个乡镇的坐标数据进行处理，获得各个乡镇之间的距离。然后以一个乡镇作为建校乡镇，求得与之对应最远乡镇之间距离。最后在这些距离中求得最小值。该最小值对应的建校乡镇可以使得最远乡镇学生上学最近。模型二：在模型一求得各个乡镇间距离的基础上，以一个乡镇作为建校乡镇，求得各个乡镇学生上学时的平均距离。再在这些距离中求得最小值。该最小值对应的建校乡镇可以使得学生上学平均距离最短。在模型的求解过程中，使用数学软件Matlab和C语言编程求解。运用穷举法的思想，对各个乡镇间的距离以及距离处理时进行编程。用Excel对数据进行分析。得到符合题中所要求的建校乡镇地址。求解得到第12号乡镇作为建校乡镇时，不仅可以使得最远乡镇学生上学最近，还可以使得所有学生上学的平均距离最短。最后对模型进行客观的分析，合理的评价和推广。关键词：最近距离最短平均距离穷举法一．问题重述1.1问题背景百年大计，教育为本。千秋大业，教育为先。强国必先强教。实施新城配套学校建设工程，制定实施基础教育空间布局规划，促进义务教育优质资源均衡合理布局，扩大优质高中资源的覆盖范围。已被国家列入十二五教育规划。一个好的建校选址的方案将对当地教育的发展起到一定的促进作用。1.2问题的提出实际问题：某行政区有25个乡镇，每个乡镇的具体位置（用平面坐标系x，y表示）及高中生人数t，如表1，假设乡镇之间均有直线道路相连，现在一个。乡镇上建立一所高中。1、问高中应建在哪个乡镇，才能够使得最远的乡镇的学生上学最近。2、问高中应建在哪个乡镇，使学生往返学校的平均距离最短。二．问题分析对于建校选址问题，距离是衡量学生上学远近的量度。要解决的实际问题是从距离的不同角度出发，考虑选取所需的建校方案。2.1问题一是从离学校最远的乡镇的学生角度出发，要求学生上学最近的问题。我们需要计算每个乡镇之间的距离，从中任取一个乡镇作为建校乡镇，再选取与其对应的最远乡镇的距离。然后在这些与最远乡镇的距离中选取最小距离，所对应建校的乡镇可以使得最远的乡镇学生上学最近。2.2问题二是从学生往返学校的平均距离的角度出发，要求学生上学最近的问题。我们需要考虑建校乡镇与非建校乡镇的距离和其他乡镇学生的人数两个因素。两者的乘积的二倍是学生上学往返学校的总距离，除以学生的总人数，就是学生往返学校的平均距离。各个乡镇作为建校乡镇时使得学生往返学校的平均距离不同。要在其中选取最小往返学校的平均距离，所对应的乡镇作为建校乡镇，即可使得学生往返学校的平均距离最短。三.模型假设3.1不考虑各乡镇和所建学校的实际尺度，简化为点处理，乡镇在同一水平面上，学校建在乡镇中并用乡镇的坐标点表示。3.2每两个乡镇之间都有直线道路，保持畅通状态。3.3学校只覆盖表中乡镇的学生，不招收表中以外乡镇的学生。每个乡镇的学生人数保持不变，表中乡镇学生只在表中乡镇内建造的学校就学。学生辍学率为0，出勤率为100%。3.4学校的建设不靠虑建造成本和人为因素的影响，只在表中乡镇中只建一所学校。3.5非建校乡镇学生上学的距离为乡镇与建校乡镇之间的直线距离，建校乡镇的学生上学的距离忽略不计。3.6学生往返学校的平均距离只与学生上学时的距离和学生的人数有关，与往返的次数无关。四.模型的建立及求解4.1符号说明符号意义第i乡镇的编号第i乡镇的学生人数第i乡镇的横坐标。第i乡镇的纵坐标从第i乡镇到第j乡镇的直线距离第i乡镇作为建校乡镇时离最远乡镇的距离。所有乡镇的总学生数；Vi乡镇的作为建校乡镇，所有学生上学所需要的总路程；Vi乡镇作为建校乡镇，学生上学往返平均距离；使得最远的乡镇学生上学最近的距离。使学生往返学校的平均距离最短的距离。(i=1，2，3……，25;j=1，2，3……，25)4.2模型的建立题<一>:首先运用两点间的距离公式：可以从中选择出第i乡镇作为建校乡镇时离最远乡镇的距离。再在这些距离中选出最小的距离。该距离所对应的建校乡镇即为能够使得最远的乡镇的学生上学最近的距离。整合以上各式得：所对应的建校乡镇i即为所求的建校乡镇。即能够使得最远的乡镇的学生上学最近的建校乡镇。问题<二>：由题中的表可以求出学生的总人数：然后求出各个乡镇作为建校乡镇时，学生上学时往返的总路程之后求出建校乡镇为时，学生上学往返的平均距离：再在往返平均距离中中选取最小值整合以上相关的各式得：所对应的建校乡镇i使得学生往返学校的平均距离的距离最短。4.3模型的求解问题<一>：由题表1可以将各个乡镇的坐标用Excel绘制成乡镇分布散点图。如图表1所示。图表SEQ图表\*ARABIC1从图表1中可以看出位于乡镇分布的中间区域的乡镇，是建立学校的合适地区。根据两点间距离公式，可以利用数学软件MATLAB编程和C语言编程首先求得各个乡镇之间的距离。程序流程图如下：开始开始i=1把Vi作为建校乡镇i<=25计算与其他各个乡镇之间的距离i++下一个乡镇是否输出各个乡镇之间的距离结束所得到的距离为各个乡镇之间的距离。实际的值为附录中表2所示。进而可以创建一个25*25的矩阵。矩阵中的元素表示乡镇到乡镇矩阵中的元素表示乡镇到乡镇的直线距离。每一行表示乡镇(i=1，2，3……，25)到各个乡镇之间的距离。再使用编程在各行中提取最大值，即建校乡镇与非建校乡镇最远的距离。程序流程图如下所示：开始开始i=1选取乡镇Vi为建校乡镇比较与其他乡镇之间的距离存储最大值i<=25i++下一个乡镇是否输出各个乡镇作为建校乡镇时，所对应的最远乡镇之间的距离结束用编程获得的结果如下：V1V2V3V4V5399.1076359.3603353.4678298.4487430.3480V6V7V8V9V10422.2044400.3612389.3148394.5814393.1545V11V12V13V14V15329.6898260.5613358.9678344.0749347.2204V16V17V18V19V20395.9415280.2596397.1600362.4528283.1461V21V22V23V24V25430.3480340.6426395.7521360.3752401.3322每个数据依次代表着该乡镇作为建校乡镇时，与之最远乡镇之间的距离。将运行的结果数据用Excel绘制成如图表2所示：图表SEQ图表\*ARABIC2图表2反映了不同乡镇作为建校乡镇时，与距离最远乡镇之间距离的变化情况。可以看出V12作为建校乡镇时，建校城镇与最远城镇间的距离最短。进而能够使得最远的乡镇的学生上学最近。最后通过编程实现这些与建校乡镇之间最远的距离中选取最近的距离。程序流程图如图所示：开始开始i<=25i++下一个乡镇是否P1=G1是G1=PiG1>=Pi否输出G1及乡镇i结束记录乡镇i通过编程得到的数据显示，第12乡镇作为建校乡镇时，距离最短，最短为260.5613。与折线图分析所得到的结果是一致的。题<二>：根据表1中学生人数，可以得到学生在不同乡镇的分布的情况。用Excel绘制成柱状分布图，如图表3所示：图表SEQ图表\*ARABIC3通过乡镇学生的分布状况可以直观的看出，学生在不同乡镇之间的分布情况和学生数。通过各个乡镇间学生人数的累加，可以获得学生的总人数。经过计算机编程可以得到总学生人数。程序流程图如下：开始i=1;T=0第i乡镇的学生Ti学生总数T+=Tii<=25否开始i=1;T=0第i乡镇的学生Ti学生总数T+=Tii<=25否是i++下一个乡镇输出T结束在模型建立过程中，在对各个乡镇作为建校乡镇时，学生上学时往返总路程的解题过程中可以看出的求解符合矩阵的乘法。首先把模型二中的量用矩阵表示出来。如：25*1的学生人数矩阵；25*1的所有学生上学所需要的总路程矩阵；25*1的选取不同建校乡镇时，25*1的学生上学往返平均距离矩阵。用25*25的距离矩阵与25*1的学生人数矩阵相乘可以获得学生上学时25*1的单程总距离矩阵，再乘上2，就可以获得25*1的不同乡镇作为建校乡镇时，所有学生上学所需要的总路程矩阵，再除以学生总人数，就可以得到25*1的学生上学往返平均距离矩阵。经过编程可以求得中的各个元素的值，如下所示：A1A2A3A3A5427.5679426.7840420.2174350.1993506.6937A6A7A8A9A10453.2162419.3375471.3659450.6394445.7614A11A12A13A14A15348.9425313.7178410.1610408.1580360.1640A16A17A18A19A20477.7763325.8198485.9021429.9743336.4912A21A22A23A24A25525.2274389.5924478.4761424.2227456.2671使用Excel将数据绘制成如下的折线图：图表SEQ图表\*ARABIC4从图表4中可以看出不同的乡镇作为建校乡镇时，学生上学往返的平均距离的不同，进行比较时不难发现，当第12乡镇作为建校乡镇时，学生往返学校的平均距离最短。当运用计算机编程在这些平均距离中选取最小值，利用穷举法的思想，程序流程图与模型一中对最远乡镇距离中选取最小值的算法相同。此处不再重复。编程运行的结果为：当第12乡镇作为建校乡镇时，学生上学往返的平均距离最短，最短为313.7178。与折线图的分析结果相同。经过两个模型的求解之后，可以发现第12号乡镇作为建校乡镇时，不仅可以使得最远乡镇学生上学最近，还可以使得学生上学的平均距离最短。五．模型的分析5.1模型在建立时，对问题进行简化转化为数学模型过程中，存在着与实际不相符的情况。模型的假设或多或少的会与实际相偏离。在现实生活中，并不是所有的乡镇之间都有直线道路，可能没有道路，也可能不是直线的道路，这就涉及能否到达的0-1规划问题。此外，所有乡镇并不是都在一个水平面上，例如乡镇在山区分布时，我们需要考虑的不仅仅是乡镇的横纵坐标，还需要考虑到乡镇实际的高度。需要建立一个三维的坐标系进行数学建模。通常一个地区要建设一所学校，都会把学校建立在该地图重点发展的乡镇中，因此学校建校选址问题应当要考虑到人为因素的原因。另外，乡镇学生的分布并不只是集中在乡镇中，可能大多分布在城郊地区或偏远郊区。因此，使得在实际建模过程中需要我们抓住主要因素，排除或者弱化次要的因素的影响进行建立模型，来解决我们需要的解决的实际问题。5.2两个模型始终围绕着各个乡镇之间的距离进行建立和求解。这些距离的求解是利用计算机的编程，所运用的算法为穷举法。穷举法，或称为暴力破解法，是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为止。程序编程算法很简洁也很容易。正是利用了计算机运算速度快的优势，使得程序运算时具有简洁高效的特点。5.3在模型一的建立过程中，对于题中问题基本覆盖到。主要从各个乡镇间的距离入手。在乡镇中任取一个乡镇就会获得与其对应的最远乡镇间的距离，再在这些距离中选取最小的距离。这样获得最小的距离所对应的建校乡镇，能够使得最远的乡镇的学生上学最近。所得的结果为之加以证实。所建立的模型基本上可以解决题中这种简单的距离问题。5.4在模型二的建立过程中，建校乡镇选取的要求是使得学生上学往返平均距离最短。考虑到平均距离的影响因素为学生上学总距离和总人数。学生总人数为固定值。所以只需只需考虑学生上学总距离这个因素即可。学生上学的总距离为所有非建校乡镇学生上学距离与人数乘积的和。因此建校学生上学的距离被忽略不计。所以模型的建立，基于了一些实际问题的简化。但这些简化实际问题对现实生活并无太大影响。因为建校乡镇的学生上学距离，肯定比非建校乡镇学生的上学距离要短的多的多，基本上可以忽略。因此模型的建立对解决实际的问题具有一定的客观性。在这些平均距离当中，也存在着“被平均”的问题。即在求解平均距离时，建校乡镇的学生上学距离被忽略时，对于平均距离的影响，人数多的乡镇作为建校乡镇在平均距离上具有优势，而学生人数少的乡镇作在作为建校乡镇时处于劣势。六．模型的评价及推广6.1优点：6.1.1模型原理简单明了，容易理解与运用。模型对于其它的最优距离选址问题同样适用。可以作为基本的模型，从而进行其他功能的拓展。6.1.2本模型对问题的描述精确、合理、推导严谨、理论性强。6.1.3模型的建立中有成熟的理论基础和利用数学软件MATLAB和C语言编程进行求解，可信度较高。建立的模型与实际紧密联系，充分考虑现实学生上学情况,从而使模型更贴近实际，通用性、推广性较强。6.2缺点：6.2.1根据实际问题对象的特征和建模的目的，对问题进行必要的简化过程中，存在着过于简化而与现实不符的问题。6.2.2在实际生活中，学生入学的选择会受到学校的教学质量，学习的设施得的影响，而在模型建立的过程里忽略了这种客观因素的影响。6.2.3在建立学校过程中，没有考虑到成本和人为的干预因素。也没有进行各方因素在建校时所占比重的衡量。6.2.4程序算法过于简单，只适合用于题中的距离计算。对于多种复杂因素影响下时，算法会不适合。6.3模型的推广本模型是为了解决最优建校选址问题，其中抓住距离这个建校最大的影响因素。利用数学软件并有相应程序，操作简单，适用范围广。结合实际出发，将不同因素考虑在内，只要在该模型的基础上进行适当的拓展，论文也同样适用于公益社会方面，如：医院、消防部门、公共设施建设选址和经费问题；公司经营方面，如：策划部门推出方案、财务处选取最少费用等问题参考文献[1]国家中长期教育改革和发展规划纲要（2010－2020年）/link?url=TInBwmapYXcwYv9Yn7azeKOUxkpWmZwBoza_-F8Bf9NmBaLlzeEvLtAFGOLgJaiNjeguCL2MMXVxIDofhS23v_hMPlaaHrNZfr0rAiclWqG[2]城市公共自行车服务系统运行状况和效率分析/view/e25f666d2f60ddccda38a059.html[3]王正盛编写MATLAB数学工具软件实例简明教程[4]数​学​建​模​​学​校​选​址​问​题​模型/view/0370f0cbda38376baf1fae12.html附录：表1乡镇编号XYT1385.4156.6613283.6101.5111364.7141.82754255.8297.239350.0260.34196134.2375.95647110.3333.1786817.0187.1166937.5251.27510163.023.292511326.7216.064512248.8182.944013209.245.438014290.7342.710415339.8188.980016291.1394.925617222.5262.912918262.40.05719296.952.438620137.4197.967321353.815.326022138.690.31712323.7131.24072428735359.575125401.2250241表2：各乡镇之间的距离V1V2V3V4V5V6V7V10306.7886321.0413191.2185399.1076333.4575326.852V2306.7886044.5118260.6748179.4614279.0264233.134V3321.041344.51180246.3095135.0124244.1988196.6597V4191.2185260.6748246.30950258.4478144.8456149.8635V5399.1076179.4614135.0124258.44780177.1243132.1587V6333.4575279.0264244.1988144.8456177.1243049.02091V7326.852233.134196.6597149.8635132.158749.020910V8369.6604108.45765.78282262.95975.14812222.219173.2654V9360.5323156.6375112.7307223.093938.58834157.8004109.5785V10259.3402111.5135154.0417289.2885287.7245353.8739314.349V1183.51078268.7152272.3043107.7973329.6898250.2484246.0516V12139.1088184.1657188.632114.5141260.5613224.4597204.3093V13208.3552137.5593173.7044256.0758299.9111338.903304.2244V14208.8092317.9117302.385257.34335302.1527159.9828180.6553V1555.88068270.6976279.1029137.058347.2204277.9215271.0422V16256.2799359.3603339.5829103.8816320.7123158.0462191.0704V17194.515212.9394198.912247.80565222.5152143.4081132.3514V18199.1295205.6008243.2951297.2733369.6077397.16366.183V19136.711218.8783248.8156248.2262362.4528362.1098337.0639V20251.4154110.396691.82864154.5285150.9057178.0288137.8893V21144.7904283.6168315.5647298.4487430.348422.2044400.3612V22255.550256.1287890.07475237.7887219.3398285.6339244.4437V23362.590766.8588142.34808285.3531131.2574268.4927219.6888V24225.2839328.8453311.501469.90122304.133154.1747179.1558V2594.72698350.6024353.4678152.8692401.3322295.1945302.5366V8V9V10V11V12V13V14V1369.6604360.5323259.340283.51078139.1088208.3552208.8092V2108.457156.6375111.5135268.7152184.1657137.5593317.9117V365.78282112.7307154.0417272.3043188.632173.7044302.3852V4262.959223.0939289.2885107.7973114.5141256.075857.34335V575.1481238.58834287.7245329.6898260.5613299.9111302.1527V6222.219157.8004353.8739250.2484224.4597338.903159.9828V7173.2654109.5785314.349246.0516204.3093304.2244180.6553V8067.29829219.4976311.0455231.838238.788314.8381V967.298290260.258291.3343222.0644268.0196269.2257V10219.4976260.2580252.922181.289151.257344.0749V11311.0455291.3343252.922084.64053207.1488131.7152V12231.838222.0644181.289184.640530143.0888165.2018V13238.788268.019651.257207.1488143.08880308.2686V14314.8381269.2257344.0749131.7152165.2018308.26860V15322.805308.6528242.311230.1001791.19759194.0325161.4474V16343.9646291.4835393.1545182.4077216.1788358.967852.20153V17219.034185.3696246.9744114.268384.21217217.9063104.9728V18308.5896337.1668102.0715225.3675183.404969.93854343.8665V19310.6253326.8177137.0469166.2919139.082287.97892290.3662V20120.8834113.2294176.5657190.1634112.4053168.5571210.8742V21378.0866394.5814190.9635202.5214197.7745147.6996333.4252V22155.4246190.026471.39867226.2346143.940383.66821294.6866V2356.30009120.7909176.2626314.6427230.9608204.3817340.6189V24320.7678272.4498358.6055148.7578180.7906323.712417.10205V25389.3148363.702328.903581.8917166.5178280.58144.2343V15V16V17V18V19V20V21V155.88068256.2799194.515199.1295136.711251.4154144.7904V2270.6976359.3603212.9394205.6008218.8783110.3966283.6168V3279.1029339.5829198.9122243.2951248.815691.82864315.5647V4137.058103.881647.80565297.2733248.2262154.5285298.4487V5347.2204320.7123222.5152369.6077362.4528150.9057430.348V6277.9215158.0462143.4081397.16362.1098178.0288422.2044V7271.0422191.0704132.3514366.183337.0639137.8893400.3612V8322.805343.9646219.034308.5896310.6253120.8834378.0866V9308.6528291.4835185.3696337.1668326.8177113.2294394.5814V10242.3112393.1545246.9744102.0715137.0469176.5657190.9635V1130.10017182.4077114.2683225.3675166.2919190.1634202.5214V1291.19759216.178884.21217183.4049139.0822112.4053197.7745V13194.0325358.9678217.906369.9385487.97892168.5571147.6996V14161.447452.20153104.9728343.8665290.3662210.8742333.4252V150211.6783138.6913204.142143.0827202.6174.1636V16211.67830148.7614395.9415342.5491249.8653384.7434V17138.6913148.76140265.9105223.2613107.0841280.2596V18204.142395.9415265.9105062.73763234.071492.67173V19143.0827342.5491223.261362.737630215.894767.92658V20202.6249.8653107.0841234.0714215.89470283.1461V21174.1636384.7434280.259692.6717367.92658283.14610V22224.0612340.6426191.9114153.2336162.7738107.6067227.8948V23321.323375.5535238.4666272.3805284.3373131.8203349.8554V24178.436735.58258116.4326360.3752307.2438220.5551350.5272V2586.62084181.9836179.165285.9466223.4374268.8956239.4386V22V23V24V25V1255.5502362.5907225.283994.72698V256.1287866.85881328.8453350.6024V390.0747542.34808311.5014353.4678V4237.7887285.353169.90122152.8692V5219.3398131.2574304.133401.3322V6285.6339268.4927154.1747295.1945V7244.4437219.6888179.1558302.5366V8155.424656.30009320.7678389.3148V9190.0264120.7909272.4498363.702V1071.39867176.2626358.6055328.9035V11226.2346314.6427148.757881.8917V12143.9403230.9608180.7906166.5178V1383.66821204.3817323.7124280.58V14294.6866340.618917.10205144.2343V15224.0612321.323178.436786.62084V16340.6426375.553535.58258181.9836V17191.9114238.4666116.4326179.165V18153.2336272.3805360.3752285.9466V19162.7738284.3373307.2438223.4374V20107.6067131.8203220.5551268.8956V21227.8948349.8554350.5272239.4386V220121.9624307.6359307.3481V23121.96240348.8715395.7521V24307.6359348.87150157.8542V25307.3481395.7521157.85420C语言编程解题代码#include<stdio.h>#include<math.h>main(){ //数组x[25]，y[25]中的元素对应乡镇的横坐标和纵坐标 doublex[25]={385.4,83.6,64.7,255.8,0.0,134.2,110.3,17.0,37.5,163.0, 326.7,248.8,209.2,290.7,339.8,291.1,222.5,262.4,296.9,137.4, 353.8,138.6,23.7,287.5,401.2}, y[25]={156.6,101.5,141.8,297.2,260.3,375.9,333.1,187.1,251.2, 23.2,216.0,182.9,45.4,342.7,188.9,394.9,262.9,0.0,52.4,197.9, 15.3,90.3,131.2,359.5,250.0}; //各个乡镇的学生用数组student[25][1]表示 doublestudent[25][1]={613.0,111.0,275.0,393.0,419.0,564.0,786.0,166.0,75.0,925.0,645.0,440.0,380.0,104.0,800.0,256.0,129.0,57.0, 386.0,673.0,260.0,171.0,407.0,751.0,241.0}; doubleAD[25][1]={0.0},Min,total=0.0; //数组AD[25][1]各元素表示学生上学总距离，Min为学生上学总距离的最小值， //total为学生总人数 inti,j,m=0; doubleP[25][25],vp[25],max=0.0,min=0.0;//数组P[25][25]中的元素代表Vi乡镇到Vj乡镇的直线距离//max表示vi乡镇作为建校乡镇时与最远乡镇的距离，//min为i个乡镇作为为建校乡镇时，与最远乡镇的距离中的最小值 //计算相应城镇间的距离 for(i=0;i<25;i++) { for(j=0;j<25;j++) { P[i][j]=sqrt(pow(fabs(x[j]-x[i]),2)+pow(fabs(y[j]-y[i]),2));//两点间的距离公式 } } //输出距离 for(i=0;i<25;i++) { for(j=0;j<25;j++) { printf("%lf\t",P[i][j]); } printf("\n"); } //计算乡镇为Vi使得最远的乡镇的学生上学的距离 for(i=0;i<25;i++) { for(j=0;j<25;j++) { if(P[i][j]>max) { max=P[i][j]; } } vp[i]=max; max=0.0; // printf("乡镇V%d为建校乡镇时使得最远的乡镇的学生上学的距离%lf\n\n",i+1,vp[i]); // printf("%lf\n\n",vp[i]); } //再找到乡镇为Vi使得最远的乡镇的学生