灾区应急运输.docx

应急运输交通路线设计摘要由于突发的战争和自然灾害会对供水供电、通信系统及交通网络等等造成很大的影响，如果不能及时处理其所带来的损失将不堪设想。所以完善运输交通路线拥有十分重大的意义。在第一问中，我们通过聚类分析模型利用SPSS软件求出分类。再通过Floyd算法求任意两点的最短路径长度，我们得到各类中离类中其它点距离和最短的一个顶点作为集散中心点。在第二问中，由第一问中已得的最短路径长度，我们通过数据联系图像可以很轻易地求出最短路径的路线。在第三问中，我们认为题目所求的目标为求解经过尽可能长的路径且不能重复，每经过一条边便加上其权值即其运输能力，最后求得一个最大运输能力。由此，我们小组通过c++ 以及小组自己设计的一个算法通过穷举所有可能性暴力有哪些信誉好的足球投注网站求得最大运输能力。第四问中，我们将关键路线理解为第三问中所求的最大运输能力所经过的路线。于是我们将第三问中的代码进行修改从而求得具体路线。然后通过联系最短路径以及关键路径求得需要交通管控的道路节点。第五问中我们针对两种不同的情况：最快到达目的地和尽可能大的运输量制定了两种应对方案。针对第六问我们基于前几问再联系生活实际对于方案的可靠性进行了评估，然后对于该交通运输网络提出自己的看法以及一些建议和意见。关键词：聚类分析、 Floyd算法、 关键路径、 图论 1、问题重述鉴于突发的战争或者自然灾害等等会对供水供电、通信系统以及交通运输等等造成的损失，故建立完善的交通运输以及应对方案显得尤为重要。现针对于A地的交通网络图，求解临时集散物资中心点的位置、相应最短路径、最大运输能力、关键路径等问题。2、模型的假设及符号说明2.1 模型假设假设一：假设各顶点之间路径长度一定，且只能通过路径到达各点。假设二：假设各道路运输能力一定，不考虑外部因素影响。假设三：各定点可经过多次，道路只能经过一次。2.2 符号说明顶点个数：V第i个点到第j个点的最短距离：点与点之间的距离：类的个数：k3、问题分析本文研究的是对于A地交通网络的规划和设计，要求在灾害发生的情况下，A地各地都能由优化的交通网络部署通往各地或者由各地获得物资支持。问题一要求我们要求我们建立四个临时物资集散中心，我们将其理解为将A地划分为四个子类，其中各子类中各顶点间距离尽可能小而类间距离尽可能大，于是我们通过聚类分析完成了分类。然后由类中各点找到一点离类中其余个点距离和最短的一点作为临时物资集散中心。问题二要求我们求出最短路径，我们通过第一问中已经求得的个顶点之间的最短路径长度可以很轻易的求得最短路径。问题三中，我们对于题目的理解是经过尽可能长的路径且遍不重复，每经过一条边便加上相应的权值即其运输能力，最后求得一个最大值即为最大运输能力。我们运用图论相关知识，暴力有哪些信誉好的足球投注网站最后求得一个最大值。问题四中，我们将关键路径理解为最大运输能力所经过的路线，通过对第三问中的代码修改便可轻易地得到答案。然后联系最短路径以及关键路径找出需要交通管控的道路节点。问题五，我们将最坏情况理解为一条或者多条道路发生长时间的堵塞或者遭受损坏无法通行，此时寻找替代该路线的次优解。在问题六中，研究运输方案的可靠性，联系实际，考虑多方面因素对运输方案给出一个评价，最后通过小组的讨论给出一些意见和建议。4、模型的建立和求解4.1 问题一：4.1.1 模型原理及SPSS的实现聚类分析是根据事物本身的特性研究个体分类的方法。其依据是同一类中个体有较大的相似性，不同类的个体差异较大。进行聚类分析有很多种方法，如动态聚类法、分解法等。系统聚类分析方法主要又有两种，一种是“快速聚类分析方法”，另一种是“层次聚类分析方法”。聚类分析的形式也分为两种，对样本进行分类，称为Q型聚类；对研究对象的观察变量进行分类，称为R型聚类。本文使用快速聚类分析方法的Q型聚类。在本题中共有V个顶点，则有X=为统计样本资料矩阵。其中，为第i个点到第j个点的最短距离，样本之间的亲疏度可以用V维2空间中点与点之间的距离表示。常用的计算方法有：欧氏距离、Chebychev距离等。本文使用欧氏距离公式计算，其公式为 快速聚类分析的一般过程及SPSS实现：根据实际解决问题的需要，确定聚类成多少类（k类）。确定k个类的初始类中心点。可以由用户指定k组m维数据作为初始类中心点；也可以由SPSS根据样本数据的情况，选择k个有代表性的样本数据作为样本数据的初始类中心点。计算所有样本点到k个类中心点的欧氏距离，SPSS按照k个类中心点距离最短原则，把所有样本分派到各中心点所在的类中，形成一个新的k类，完成一次迭代过程。SPSS重新确定k个类的类中心点，SPSS计算每个类中各个变量的变量值均值，并以均值点作为新的类中心点。重复（4）、（5）两步的计算过程，直到达到指定的迭代次数或终止迭代的判断要求为止。4.1.2模型的求解首先我