选址问题,是现代地理学研究的主要问题之一。选址问题涉及人类生产、生活、文化、娱乐等各个方面。选址问题的数学模型取决于两个方面的条件:可供选址的范围、条件;怎样判定选址的质量。本节的讨论仅限于选址的范围是一个地理网络,而且选址位置位于网络图的某一个或几个顶点上。对这样的选址问题,根据其选址的质量判据,可以将其归纳为求网络图的中心点与中位点两类问题。四、中心点选址问题例:某县要在其所辖的 6 个乡镇之一修建一个消防站,为 6 个乡镇服务,要求消防站至最远乡镇的距离达到最小。?中心点选址问题的质量判据使最佳选址位置所在的顶点的最大服务距离为最小。中心点选址问题适宜于医院、消防站点等一类服务设施的布局问题。设G=( V,E)是一个无向简单连通赋权图, 连接两个顶点的边的权值代表它们之间的距离,对于每一个顶点 v i,它与各个顶点之间的最短路径长度为d i1,d i2,…,d in。这些距离中的最大数称为顶点 v i 的最大服务距离,记为 e(v i)。那么,中心点选址问题,就是求网络图 G的中心点,使得)( min )( 0ii iveve? 0iv ?中心点选址问题的数学描述例:假设某县下属的 6个乡镇及其之间公路联系如图所示。每一顶点代表一个乡镇;每一条边代表连接两个乡镇之间的公路,每一条边旁的数字代表该条公路的长度。现在要设立一个消防站,为全县的 6个乡镇服务。试问该消防站应该设在哪一个乡镇(顶点)? 解:第 1 步:用标号法求出每一个顶点 v i 至其他各个顶点 v j 的最短路径长度 d ij(i,j= 1,2,…,6), 并将它们写成如下的距离矩阵?????????????????????????????????????????? 027474 205256 750343 423036 754303 463630 66 65 64 63 62 61 56 55 54 53 52 51 46 45 44 43 42 41 36 35 34 33 32 31 26 25 24 23 22 21 16 15 14 13 12 11dddddd dddddd dddddd dddddd dddddd ddddddD 第2 步:求每一个顶点的最大服务距离。显然,它们分别是矩阵 D 中各行的最大值,即: e(v 1)=6,e(v 2)=7,e(v 3)=6,e(v 4)=7,e(v 5)=6 ,e(v 6)=7。第3 步:判定。因为 e(v 1)=e(v 3)=e(v 5)= min{ e(v i )}=6, 所以 v 1,v 3,v 5 都是中心点。也就是说,消防站设在 v 1,v 3,v 5中任何一个顶点上都是可行的。?中位点选址问题的质量判据使最佳选址位置所在的顶点到网络图中其他各个顶点的最短路径距离的总和(或者以各个顶点的载荷加权求和)达到最小。五、中位点选址问题?中位点选址问题的数学描述设G=( V,E)是一个简单连通赋权无向图,连接两个顶点的边的权值为该两顶点之间的距离;对于每一个顶点 v i(i=1, 2,…,n), 有一个正的负荷 a(v i),而且它与其他各顶点之间的最短路径长度为 d i1, d i2,…,d in。那么,中位点选址问题,就是求图 G的中位点,使得 0iv???? nj ijji ii idvavSvS 1 0)( min )( min )( 例:某县下属 7 个乡镇,各乡镇所拥有的人口数 a(v i)(i =1 ,2,…,7 ), 以及各乡镇之间的距离 w ij (i,j =1 ,2,…,7) 如图所示。现在需要设立一个中心邮局,为全县所辖的 7 个乡镇共同服务。问该中心邮局应该设在哪一个乡镇(顶点)? 解: 第1 步:用标号法求出每一个顶点 v i 至其他各个顶点 v j 的最短路径长度 d ij(i,j= 1,2,…,7 ), 并将其写成如下距离矩阵??????????????????????? 77 76 75 74 73 72 71 67 66 65 64 63 62 61 57 56 55 54 53 52 51 47 46 45 44 43 42 41 37 36 35 34 33 32 31 27 26 25 24 23 22 21 17 16 15 14 13 12 11ddddddd ddddddd ddddddd ddddddd ddddddd ddddddd dddddddD ???????????????????????
案例六设施选址案例4 来自淘豆网m.daumloan.com转载请标明出处.
