题目：服务网点的选址问题摘要本文对该乡镇的服务网点的选址问题进行了研究。

解题过程将其转化为一个最优选址的问题。

对于问题一给出了两种解决方案，主要是运用距离矩阵法和重心法。

（一）运用距离矩阵法时，因为每个村的人口数影响选址，所以需要把距离矩阵转换为加权的距离矩阵，其中权就是每个村的人口数。

进而将选点问题转换为任意两点之间的加权距离问题，并用C语言编程的方法来分析得出结果，得出了精确的地点。

（二）运用重心法时，将各村看成是有重量的质点，设各质点的等效重力为G，根据重心的特性，Gd0=∑121d[i]*w[i]。

得到重心坐标：x0=(∑121x[i]*w[i])/(∑121w[i])；y0=(∑121y[i]*w[i])/(∑121w[i])；再用C语言编程的方法来分析得出结果。

对于问题二，虽然每个村子人口增加了一倍，即各个村子的权重增加了一倍，但是各个村子的权重之比没有变化，所以仍在第一问计算出来的加权距离矩阵中计算。

在矩阵中任意选取两行i和j，对于选定的两行，比较每一列中对应的两个数，选取小的那个数，表示就近原则。

共选出十二个数，这十二个数之和记为s[i][j]，总共有C122种情况。

此时s[i][j]表示以点V i+1和V j+1为服务网点的加权距离和。

用C语言程序从C122情况中找出最小s[i][j]。

点V i+1和点V j+1即为所求。

对于问题三，先定义连通路径，把路径转换为矩阵（这里的矩阵和线代中的矩阵完全不同），路径和矩阵一一对应，通过连通路径的性质寻找矩阵的性质和定理。

应用矩阵的性质和定理，经过矩阵变换，最后求得最优行走路线。

关键词：距离矩阵重心法 C语言编程连通路径连通路径的变换一、问题的重述试根据需要解决如下问题：1．目前准备在该乡镇建一个服务网点为各村提供各种服务，那么服务网点应该建在何处？2．假设各村人口增长了一倍，需要建两个服务网点，试确定其位置。

3．从一个服务网点出发，到每个村发放销售广告，最后回到另一个服务网点，试确定最佳行走路线。

二、问题的分析和假设1、因为村子的大小相对于道路的长度可以忽略不计，所以把村里作为点处理。

2、村子里的人越多，那么需要服务的可能性就越大，假设每个人需要服务的可能性相同，那么村里的人数就可以作为权。

3、假设每个村子之间都有道路，而且道路为直线，不存在弯曲路段的情况。

4、每个村子里的人都使用离村子最近的服务网点。

5、每个服务网点到村子的费用，只与距离成正比，且比例系数相同6、对于距离矩阵法：假设服务网点建设在其中一个村子里的；对于重心法：假设服务网点可以假设在该平面的任何地方。

三、符号约定V i：第i村子所在定点；D：各村子之间的最短距离矩阵；d[i][j]:表示点V i+1到点V j+1之间的最短距离；w[i]：表示第i+1村的权；L[i]：表示第i+1村子到其余所有村子的加权距离之和；x[i]:第i+1村子在坐标系上的横坐标；y[i]:表示第i+1村子在坐标系上的纵坐标；x0：表示服务网点在坐标系上的横坐标；y0：表示服务网点在坐标系上的纵坐标；四、模型建立的建立和求解4.1、问题一：单个服务网点的选址问题方法一：距离矩阵法本问题是解决单个服务网点的选址问题，选择最优的服务网点，就是使服务网点的总费用最少，本题中总费用只与服务网点到村子的距离和村子里需要服务的次数有关。

即服务网点需满足，到各村的加权距离和最小。

首先利用C语言编程，算出任意两个结点之间的最短路径；C语言的算法基本思想如下：一、因为任意两个结点之间都有路线，所以定义数组d[i][j]，数组中的变量i 和j都是从0开始的，所以的d[i][j]表示点V i+1到点V j+1间的距离，也就是最短距离。

其数学表达式为：d[i][j]=y[j]))(x[i]*-((x[i]-x[j])x[j])*(y[i]-+y[j])-(y[i]二、因为每个村子的人数不一样，所以每个村子在相同的时间内需要服务的次数也就不一样，人数多的村子需要服务的次数也就相对多一点，所以用人数的数量作为距离的权，记为w[i]。

w[0]:w[1]:w[2]:w[3]:w[4]:w[5]:w[6]:w[7]:w[8]:w[9]:[10]:w[11]=6:10: 8:14:12:7:6:8:10:12:10:11 所以可以认为w[0]=6；w[1]=10；w[2]=8；w[3]=14；w[4]=12；w[5]=7；w[6]=6；w[7]=8；w[8]=10；w[9]=12；w[10]=10；w[11]=11。

三、d[i][j]*w[j]表示点V i到点V j之间的最短加权距离。

用最短加权距离计算才能确定最佳的服务网点地址。

利用双重for循环，可以求解出最短加权距离，每循环一次就输出一个d[i][j]*w[j]。

（具体算法见【附件一】的C语言编程程序）四、L[i]表示第i+1村子到其余所有村子的加权距离之和。

则L[i]=d[i][0]*w[0]+ d[i][1]*w[1]+ d[i][2]*w[2]+……+ d[i][11]*w[11]；用C语言编程算出所有的d[i][j]*w[j]和L[i]，d[i][j]*w[j]组成一个12×12的加权距离矩阵D，L[i]对应的加权距离矩阵D每一行的数据之和。

故其中最小的L[i]对应的村子即为最佳服务网点的地址。

C语言编程程序见【附件一】。

运行结果整理成下表所示：表一、距离矩阵D如表格可知：V11所对应的那行数据之和最小，即L[10]最小，L[10]=446.401386,所以V11所对应的村子（也就是第11个村子）是最佳服务网点。

模型的评价：此方法是建立在假设假设服务网点建设在其中一个村子里的，方法简单易懂，结合加权距离矩阵，就能够轻而易举的求解出最佳的服务网点。

其次，本方法中的权重都比较大，如果直接带入计算会比较麻烦，故把所有的权重都除以100，以简化计算过程。

方法二：重心法问题分析:当问题的假设是服务网点的位置可以建立在该平面上的任一点，而且两点之间都以直线作为计算。

这其实就是一个单一平台中心的选址问题。

一般认为重心法是解决这类问题较为合理的选址方法，并在实际中加以应用，取得了不错的效果。

重心法模型的建立：选址依据的原则是效用最大，成本最低。

本题中成本最低只和服务点到所有村子的加权距离成正比。

本题中总共有12个村子。

分布在不同的坐标点（x[i],y[i]）上，现在假设服务网点的坐标为（x0，y0）。

则L[i]= 121d[i]*w[i];w[i]为每个村子的权重，d[i]表示服务网点到第i+1个村子的距离。

d[i]=y[i])-(y*y[i])-(y+x[i])-(x*x[i])-(x00；平台中心的选址时，应该尽量保证L[i]最小。

（参考文献【1】）为分析重心法存在的问题，必须研究重心法的数值计算公式的推导过程，其推导过程如下：按照重心法，将各村看成是有重量的质点，w[i]为每个质点的等效质量，重心是到各个质点距离最短的点，这样，寻找平台中心的问题就转化为重心的坐标问题。

根据重心法的思路，可以很容易找出重心坐标。

设各质点的等效重力为G，根据重心的特性，可知，等效重量在重心上对原点在XOY平面上产生的力矩等于各个质点对原点在XOY平面产生的力矩，用物理方程表示为：Gd0=∑121d[i]*w[i]将力矩沿X、Y轴分解，重心对X、Y轴产生的力矩，分别等于各个质点对X、Y轴产生的力矩,用下列两式表示Gx0= ∑121x0*w[i]=∑121x[i]*w[i]；Gy0=∑121y0*w[i] =∑121y[i]*w[i]最终得到重心坐标：x0=(∑121x[i]*w[i])/(∑121w[i]);y0=(∑121y[i]*w[i])/(∑121w[i])；由上式就可以求出坐标点（x0，y0），即为各质点的重心。

一般认为该点为平台中心坐标。

模型的求解：利用C语言软件对上述模型编程求解，程序见【附录二】用上面给出的12组数据为例，计算结果为：中心平台坐标为（4.031754,5.646667）。

模型的评价：重心法模型是连续模型，上述这种方法进行中心选址时，存在以下问题：对于重心法，虽然比较简单，但不能求解精确的最优解，与实际有差别。

因为在重心法中，使用了力矩的概念，但参与计算的距离d[i]不是矢量，从而导致求得的结果仅仅是理论上的最优解，并不是精确解，从而得出的结论不可靠。

4-2、两个服务网点的选址问题问题分析：虽然每个村子人口增加了一倍，即各个村子的权重增加了一倍，但是各个村子的权重之比没有变化，即w[0]:w[1]:w[2]:w[3]:w[4]:w[5]:w[6]:w[7]:w[8]:w[9]:[10]:w[11]=6:10:8:1 4:12:7:6:8:10:12:10:11 所以仍然可以认为w[0]=6；w[1]=10；w[2]=8；w[3]=14；w[4]=12；w[5]=7；w[6]=6；w[7]=8；w[8]=10；w[9]=12；w[10]=10；w[11]=11。

所以各个村子的人口数同时增长一倍，对分析结果没有影响。

模型的建立：本问题的解决需要借助问题一中的表一，表一表示的是任意两点的之间的最短加权距离矩阵D，最后一列计算出了每一行数的总和L[j]，其意义就是表示点V j+1（第j+1个村子）到其余的十一个村子的加权最短距离。

以遵守每个村子都使用距离最近的服务网点为前提，现在要从十二个村子里选取两个服务网点，这样就把问题转化成在表一中任意选取两行，对于选定的两行对应的每一列中的两个数，选取小的那个数，总共有十二个数，这十二个数之和记为s[i][j]。

从十二行中选取两行，总共有C122种选法，从中选取最小的s[i][j]，即为点V i+1和点V j+1为最佳服务网点。

上面的选取过程可以通过C语言编程找出最佳服务网点V i+1和点V j+1。

模型的求解：利用C语言程序编程进行求解（程序见附件三），结果分析可得点V10和点V11是最佳服务服务网点，即第10个村子和第11个村子为最佳服务网点。

模型的评价：当假设服务网点是建设在其中两个村子当中的时候，本方法简单易行，而且可以求出精确的地点。

4-3、从一个服务网点出发，到每个村发放销售广告，最后回到另一个服务网点，试确定最佳行走路线。

模型分析：本问题要求从一个服务网点出发，要经过所有的村子，最后到达另一个服务网点。

需要确定的最佳行走路线，也就是使总路程最短；很明显，每个村子只需要去一次，如果去某个村子两次了，那个总路程必定增加。

因为每个村子去而且只去一次，所以本问题和村子的权重不再有关系，仅仅与总路程有关。

下面通过最优连通路径求出最佳行走路线，首先定义连通路径，把路径转换为矩阵（这里的矩阵和线代中的矩阵完全不同），路径和矩阵一一对应，通过连通路径的性质寻找矩阵的性质和定理。