1、网络链站网络结点网络中心拐角障碍1 1）链：）链：链的属性包括阻强和需求量。链的属性包括阻强和需求量。4 42 2555535352)2)拐点：拐点：属性有阻力，如拐弯的时间和限制。属性有阻力，如拐弯的时间和限制。m m条弧相连共有转弯个数条弧相连共有转弯个数N N：L3L334L1L1L2L2停靠点停靠点站点：直接在相应的结点上附上需求量属性，负站点：直接在相应的结点上附上需求量属性，负为下卸，正值为装载为下卸，正值为装载.中心：属性为资源最大容量、服务范围和服务延中心：属性为资源最大容量、服务范围和服务延迟数（在其它中心达到某个数量时才提供服务）。迟数（在其它中心达到某个数量时才提供服务）
2、。学校学校V5V0V4V1V3V21006030101020505V5V0V4V21003010第一步只考虑下图：第一步，考虑与第一步，考虑与V V0 0直接相连的点直接相连的点,并计算它们之并计算它们之间的距离：间的距离：0 10 30 1000 10 30 100通过比较，通过比较，mindistancev0v2=10,（v0-v2)即即v v0 0与与V V2 2间距离最小，为间距离最小，为1010。V5V0V4V21003010第二步，我们把与第二步，我们把与v v2直接连通的点考虑进来。这时直接连通的点考虑进来。这时V0V0跟跟v2v2直接连通到的点直接连通到的点v v3 之间的最小
3、距离不再是无穷大。之间的最小距离不再是无穷大。而是而是mindistancevmindistancev0vv2+disv+disv2vv3。这时这时V0V0与各点的距离变为：与各点的距离变为：0 10 60 30 100除除1010以外，以外，3030是最小的（是最小的（V V0与与V V4间的距离）。间的距离）。V5V0V4V3V2100301050第三步，我们把与第三步，我们把与v v4直接连通的点考虑进来。直接连通的点考虑进来。这时这时V V0与各点的距离变为：与各点的距离变为：0 10 50 30 90除除10,3010,30以外，以外，5050是最小的（是最小的（V V0与与V V3
4、间的距离）间的距离）。V5V0V4V3V21003010506020第四步，我们把与第四步，我们把与v v3直接连通的点考虑进来。直接连通的点考虑进来。这时这时V V0与各点的距离变为：与各点的距离变为：0 10 50 30 60除除10,3010,30以外，以外，5050是最小的（是最小的（V V0与与V V3间的距离）。间的距离）。V5V0V4V1V3V21006030101050520起点起点终点终点最短路径最短路径路径长路径长度度v0v1无无v2(v0,v2)10v3(v0,v4,v3)50v4(v0,v4)30v5(v0,v4,v3,v5)60 中心点选址问题中，最佳选址位置的中心点
5、选址问题中，最佳选址位置的判定标准，是使其所在的顶点与图中其它判定标准，是使其所在的顶点与图中其它顶点之间的最大距离达到最小。顶点之间的最大距离达到最小。这个选址问题实际上就是求网络图的这个选址问题实际上就是求网络图的中心点问题。这类选址问题适宜于中心点问题。这类选址问题适宜于医院、医院、消防站等服务设施的布局问题消防站等服务设施的布局问题。设设G G=(=(V V,E E)是一个无向赋权连通图，其中是一个无向赋权连通图，其中V V=v v1 1,v v2 2,v vn n，E=E=e e1 1,e e2 2,e en n。连接两个顶点的。连接两个顶点的边的权值代表该两顶点之间的距离。边的权值
6、代表该两顶点之间的距离。对于每个顶点对于每个顶点v vi i，它与各顶点之间的最短路径长度为，它与各顶点之间的最短路径长度为d di i1 1,d di i2 2,d dinin。顶点。顶点v vi i的最大服务距离是这几个最短的最大服务距离是这几个最短路径长度中的最大值，记为路径长度中的最大值，记为e e(v vi i0 0)。e e(v vi i0 0)=)=maxmax(d di i1 1,d di i2 2,d dinin)那么，中心点选址问题，就是求图那么，中心点选址问题，就是求图G G的中点的中点v vi i0 0，使得，使得该顶点的最大服务距离达到最小，即该顶点的最大服务距离达到
7、最小，即 e e(v vi i0 0)=)=minmin e e(v vi i)例如，某县要在其所辖的例如，某县要在其所辖的8 8个乡镇之一修建一个乡镇之一修建一个消防站，为个消防站，为8 8个乡镇服务，要求消防站至最个乡镇服务，要求消防站至最远乡镇的距离达到最小。远乡镇的距离达到最小。v6v8v1v7v5v4v2v389363253757首先，用首先，用Dijkstra算法计算出每一个顶点算法计算出每一个顶点vi至其它各顶点至其它各顶点vj的最短路径长度的最短路径长度dij(i,j=1,2,6)，写出距离矩阵：，写出距离矩阵：其次，求距离矩阵中每行的最大值，即各个顶点其次，求距离矩阵中每行的
8、最大值，即各个顶点的最大服务距离，得的最大服务距离，得e(v1)=14,e(v2)=15,e(v3)=20,e(v4)=12,e(v5)=15,e(v6)=17,e(v7)=12,e(v8)=20最后计算最大服务距离的最小值。显然，最后计算最大服务距离的最小值。显然，e(v4)=e(v7)=mine(vi)。所以，消防站应建在。所以，消防站应建在v4或或v7点所在的乡镇即可。点所在的乡镇即可。541862358341462317365482917求最小值求最小值图 邻域统计图 邻域分析窗口类型图8.37 邻域统计对话框分类区统计过程图分类区图层被统计数据统计结果，淡蓝色值为分类区代码分类区统计
9、对话框1、2类合类合并为并为b，3、4类合类合并为并为a2、3类合类合并为并为c，1、4类合类合并为并为d工作选择工作选择可供选择的单位可供选择的单位P P1 1 P P2 2，P Pn n 贡贡献献收收入入发发展展声声誉誉工工作作环环境境生生活活环环境境目标层目标层准则层准则层方案层方案层目标层目标层O(选择旅游地选择旅游地)P2黄山黄山P1桂林桂林P3北戴河北戴河准则层准则层方案层方案层C3居住居住C1景色景色C2费用费用C4饮食饮食C5旅途旅途选择旅游地选择旅游地如何在如何在3 3个目的地中按照景色、个目的地中按照景色、费用、居住条件等因素选择费用、居住条件等因素选择.检验：计算一致性比例检验：计算一致性比例CRCR，CR0.1CR0.1CR0.1，认为判断矩阵不符，认为判断矩阵不符合一致性，判断矩阵需要重新构建。合一致性，判断矩阵需要重新构建。
