各社区人口统计图30 2520人口/千人151050 ABCDEFGHIJKLMNPQRSTUVWXY社区
图5.1
根据表5.1和图5.1可以看出W，Q两个社区人口量最多，且从该社区出发的道路数比较多，很可能是煤气缴费站的设置点，同时也是派出所设置点；K社区人口量也比较多，且连接各道路距离比较大，因此，K点可能是派出所设置点。这些是从图形和图标表面直观得出的，需要建模去验证。
6求最短路径
问题一、二、三均需要计算出两社区间距离矩阵D，记录对应的最短路径，以便分区时作为参考条件。最短路径算法主要由改善的floyd-warshall算法实现，最后获得由任意两城市间距离矩阵D和对应的最短路径。算法具体原理如下： 1）利用社区间道路信息，构造邻接矩阵L。 若城市i和j间无直接连通的道路，则令(i,j)元素aij为正无穷大；否则
aij(i?1,2,...n,j?1,2,...n为)i和j直接连通的道路长度。
?a11a12...a1n??aa...a?L??21222n?
????????an1an2?ann?社区间道路信息可知n是24，根据社区间道路信息表可以得出邻接矩阵为
L，见附录1。
2) 获得两社区间距离矩阵D。
D、R的?i,j?元素分别表示为Dij、Rij?i?1,2,?,24;j?1,2,?,24?， 对于所有的城市i、j和k，如果Dij?Dik?Dkj，则令Dij?Dik?Dkj，Rij?k（表
示从城市i到j要经过城市k，若Rij?0，表示两城市可直达）。经过matlab和lingo软件编程计算的出矩阵D和R，见附录2
其流程图如下：
构造邻开始 接矩L两社区间距离矩阵D 结束 社区间最短路径矩阵R
阵 图6.1 改善的floyd-warshall算法流程图
7问题1的解答
7.1模型的建立
该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵；然后，用0-1规划的穷举法获得模型目标函数的最优解。 1) 目标函数的确立：
为使得居民与最近煤气站之间的平均距离最小，只要各社区居民在满足区域要求的条件下，在各个社区的每个居民都去煤气缴费站的情况下，居民的平均路径最短，因此只要求出所有居民到离社区附近的缴费站的总路程最小，然后除以个社区居民所有人数。故目标函数为：
??RD?jij2424ijmini?1j?124
j?Rj?12)约束条件的确立
(1)若?ij?0表示社区j不到社区i缴费，?ij?1表示社区j到社区i缴费，根据模型假设（4）可知，每个社区的居民只能到附近最近的一个缴费站缴费，
24因此可有约束条件：??ij?1，j=1,2,…24。
i?1 (2)若Pii?0表示不在社区i设置煤气缴费站，P条件为：
?1表示在社区i设置煤气缴
费站，根据模型假设（3）可知，只能在社区设置3个煤气缴费站，所以有约束24i?1 (3)只有在社区i设置缴费点，社区j的居民才有可能去社区i缴费；如果不在
?P1?3
社区i设置缴费点，社区j的居民不可能去社区i缴费。因此Pi?0，?ij?0；
?0或者?ij?1，?ij?Pi,i?1,2....,24,j?1,2...,24。即存在约束条件： 3）模型流程图如下：
社区间主要道路Floyd算法Pi?1,?ij各社区居民数选择其中三个社区建缴费站社区间的最短路径和最短路径距离矩阵确定各社区所属缴费站0-1规划穷举法计算平均距离获得最优解进一步讨论模型的有效性和推广性
7.2综上所述得到最优化模型
(1)目标函数
??RD?jij2424ijminS?i?1j?124
j?Rj?1(2)约束条件
?24?ij?1,?ij??0,1??i??1?24???Pi?3,Pi??0,1?i?1,2...,24,j?1,2...24 ?i?1??ij?Pi??
7.3求解与结果分析
该模型为线性规划模型，我们采用Matlab和LINGO程序求解（见附录三，模拟程序一），用实现0-1规划法求得缴费点、对应的各缴费区域，求得最小距离加权和，并求出其平均距离，其结果如下表：
表7-1
缴费站位置
Q
W M
缴费社区
D，Q，R，S，T，V
A，B，C，E，F，G，I，W，X H，J，K，L，M，N，P，V，Y
最小距离加权和是337.3千米，目标函数的最优解，即居民与最近的缴费点之间平均距离的最小值11.7118百米。
8问题2的简答
8.1问题推断
根据上面求最短路径求出的任意两点的最短距离矩阵D,可以看出K到S的最短距离最长，Dks?66百米，要使能在3分钟内有警察（警车的时速为
L?500/60*3?25（百米）
50km/h）到达事发地，则公安局最大行驶的路程为：
Dks?2.64 LN为需要设置派出所的个数，要使派出所能够在满足要求的情况下覆盖整
个区域，则
N?3
当N?4时，可以随意的选取多种方案，但是很多社区可以可以同时满足两
个或者三个派出所，且个别排除所管辖范围很小，甚至只有一个社区，造成成本和资源的浪费，因此可以推断需要设置三个派出所，但这需要下面模型的验证。
8.2模型的建立
模型建立的方法是在问题1中改进而来的，只是目标函数发生改变，为：
min24N
增加了一个约束条件：
?D?ij?25，即保证警察在3分钟内到达事发地。
ijj?18.3综上所述,我们得到问题一的模型
目标函数：min约束条件为：
N
?24?ij?1,?ij??0,1??i??1?24??P?N,P??0,1??i?1ii ????Pi?ij?24?Dij?ij?25??j?18.4模型的求解与分析
8.4.1求解结果
用MATLAB软件编程计算（见附录三，模拟程序二）应设派出所三个，有三种设置方案。
方案一：派出所位置应设在社区K，D，W；其管辖范围为：