内容发布更新时间 : 2024/5/8 11:01:35星期一 下面是文章的全部内容请认真阅读。
问题一、二、三均需要计算出两社区间距离矩阵D，记录对应的最短路径，以便分区时作为参考条件。最短路径算法主要由改善的floyd-warshall算法实现，最后获得由任意两城市间距离矩阵D和对应的最短路径。算法具体原理如下： 1）利用社区间道路信息，构造邻接矩阵L。 若城市i和j间无直接连通的道路，则令(i,j)元素aij为正无穷大；否则
aij(i?1,2,...n,j?1,2,...n)为i和j直接连通的道路长度。
社区间道路信息可知n是24，根据社区间道路信息表可以得出邻接矩阵为L，见附录1。
2)获得两社区间距离矩阵D。
D、R的?i,j?元素分别表示为Dij、Rij?i?1,2,L,24;j?1,2,L,24?，对于所有的城市i、j和k，如果Dij则令Dij?Dik?Dkj，Rij?k（表?Dik?Dkj，
示从城市i到j要经过城市k，若Rij?0，表示两城市可直达）。经过matlab和lingo软件编程计算的出矩阵D和R，见附录2
其流程图如下：
两社区间距离矩阵D 构造邻开始 接矩L结束 社区间最短路径矩阵R
阵 图6.1改善的floyd-warshall算法流程图
7问题1的解答
7.1模型的建立
该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵；然后，用0-1规划的穷举法获得模型目标函数的最优解。 1) 目标函数的确立：
为使得居民与最近煤气站之间的平均距离最小，只要各社区居民在满足区域要求的条件下，在各个社区的每个居民都去煤气缴费站的情况下，居民的平均路径最短，因此只要求出所有居民到离社区附近的缴费站的总路程最小，然后除以个社区居民所有人数。故目标函数为：
2)约束条件的确立
(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个煤气缴费站，所以有约束条24?Pi?11?3
(3)只有在社区i设置缴费点，社区j的居民才有可能去社区i缴费；如果不在社区i设置缴费点，社区j的居民不可能去社区i缴费。因此Pi?0，?ij?0；
?0或者?ij?1，?ij?P即存在约束条件： i,i?1,2....,24,j?1,2...,24。3）模型流程图如下：
Pi?1,?ij7.2综上所述得到最优化模型
(1)目标函数 (2)约束条件
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分钟内有警察（警车的时速为
50km/h）到达事发地，则公安局最大行驶的路程为：
N为需要设置派出所的个数，要使派出所能够在满足要求的情况下覆盖整
个区域，则
当N?4时，可以随意的选取多种方案，但是很多社区可以可以同时满足两
个或者三个派出所，且个别排除所管辖范围很小，甚至只有一个社区，造成成本和资源的浪费，因此可以推断需要设置三个派出所，但这需要下面模型的验证。
8.2模型的建立
模型建立的方法是在问题1中改进而来的，只是目标函数发生改变，为：
min24N
增加了一个约束条件：
?D?ij?25，即保证警察在3分钟内到达事发地。
ijj?18.3综上所述,我们得到问题一的模型
目标函数：min约束条件为：
N
8.4模型的求解与分析
8.4.1求解结果
用MATLAB软件编程计算（见附录三，模拟程序二）应设派出所三个，有三种设置方案。
方案一：派出所位置应设在社区K，D，W；其管辖范围为：
表8-1派出所管辖范围 派出所管辖人口数总路程（单管辖范围
位置 （千人） 位：千米） 100 D D，Q，R，V，T，C,S,E 115 W A，B，F，G，I，L，X,W,U 361 73 K H，J，K，M，N，P，Y 方案二：派出所位置应设在社区K，R，W；其管辖范围为:
表8-2派出所管辖范围
派出所管辖人口数总路程（单位：
管辖范围
位置 （千人） 千米）
72 368 R D，Q，R，V，T，S
132 W A，B，C,F，G，I，X,W,U,E 84 K H，J，K，M，N，P，Y,L
方案三：派出所位置应设在社区K，Q，W；管辖范围如下表所示：
表8-3派出所管辖范围
派出所管辖人口数总路程（单
管辖范围
位置 （千人） 位：千米）
100 Q D，Q，R，S，T，V，C，U
104 W A，B，E，F，G，I，X，W 357 84 K H，J，K，L，M，N，P，Y 8.4.2结果分析和最佳方案选择
根据以上三种方案的表8-1、8-2、8-3对比可以看出： （1） 方案一和方案二其管辖范围的人口分布量不均匀；
（2） 尤其是方案二的派出所设置点在W区，管辖范围的人口量较大，给W区
派出所带来较大的工作负荷，影响工作效率。而R区的管辖范围的人口量较小，工作量较少；
（3） 方案一，二，三其人口均衡度分别是36.52%、45.45%、19.23%，故第三
种方案的均衡度最好；
（4） 根据每种方案的其总路程来看，其第三种方案的总路程最小，使总体效率
得到提高。
根据以上分析可以确定方案三为最佳方案，派出所的位置分别设置在Q区、W区、K区，其管辖范围图如下：
Q7R12S20109DV7T159U88J66N派出所一611109C1511W22BE81410F11G10IL109M1215K11派出所三811Y825H2416X18815派出所二231919P图
A288.1
9问题3的简答
9.1模型的建立
(1)均衡度分析 实际路程均衡度:?0?max|?(li)??(lj)|i,jmax?(li)i?为最大容许均衡度，显然0≤?0≤1，?0越小，说明分组的均衡度越好。
(2)目标函数的确定
将社区公路示意图抽象为一个赋权连通图G(V,E)，再把图G分成三个子图
Gk（k=1,2,3）,在每个子图中寻找最佳回路Lk（k=1,2,3），lk为回路Lk的各边
权之和。要使总路程最短且各组又尽可能均衡的巡视路线，要使总路程最短，可以尽量让每个子图的边权w(ei)之和lk最小，确定目标函数：
易知，上式两个目标函数相互矛盾，不可能同时达到。然而，要使总路程最短，可以尽量让每个子图的边权之和lk最小，又边权为w(ei)，n为每个子图中社区的总数，则有：
9.3综上所述,我们得到问题一的模型