表8-1 派出所管辖范围
派出所位置 D W K
管辖范围
D，Q，R，V，T，C,S,E A，B，F，G，I，L，X, W,
U
H，J，K，M，N，P，Y
管辖人口数（千人） 100 115
73
总路程（单位：千米）
361
方案二：派出所位置应设在社区K，R，W；其管辖范围为:
表8-2派出所管辖范围
派出所位置 R W K
管辖范围
D，Q，R，V，T，S A，B，C,F，G，I，X, W, U,E H，J，K，M，N，P，Y,L
管辖人口数（千人） 72 132 84
总路程（单位：
千米） 368
方案三：派出所位置应设在社区K，Q，W；管辖范围如下表所示：
表8-3 派出所管辖范围
派出所位置 Q W K
管辖范围
D，Q，R，S，T，V，C，U A，B，E，F，G，I，X，W H，J，K，L，M，N，P，Y
管辖人口数（千
人）
100 104 84
357 总路程（单位：千米）
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
A28图8.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最小，确定目标函数：
3??min?lk ?k?1?min[max(l)?min(l)]kk?易知，上式两个目标函数相互矛盾，不可能同时达到。然而，要使总路程最
短，可以尽量让每个子图的边权之和lk最小，又边权为w(ei)，n为每个子图中社
区的总数，则有：
minlk??w(ei)i?1ni(?1?,2,n ,) min??maxlk(?)maxlk(mlkin()),k(? ,3)1,29.3综上所述,我们得到问题一的模型
n?minl??(i?1,2,?,n)ki?1w(ei)?? ?max(lk)?min(lk)?min??max(lk)??9.4模型的求解与分析
根据prim算法，用MATLAB软件编程计算得到图的最小生成树（见附录三，
模拟程序三），如下图所示：
Q7109V7TDU9E8CSX16A818BW1198FY11G10I19P8HK11L1088J6N64R365M16
2图9.1最小生成树模型
由于在最优树上,各边权接近,要使最优树分解时, 分解结果尽量均衡，则各子图包含的顶点就应尽量接近（24/3=8）8个，由此得到最优树的分解原则如下：
（1）分解点为W点或尽可能接近W点；
（2）分解所得的三个子图包含的顶点数尽可能接近8个； （3）尽量使分解所得的子图为连通图；
（4）尽量使子图与W的最短路上的点在该子圈内，尽量使各子图内部形成环路。
根据以上原则，选取与W点相近的F点作为分解点，得到分解后的结果图如下图所示：
Q7109V7TDU9E8CSX16A818BW1198FY11G10I19P8HK11L1088J6N64R365M16
2图9.2 分解后的结果图
通过增环、扩环、换枝等方法，对子图内部进行适当调整优化，寻找出最佳巡视回路，运用LINGO软件编程计算得到结果如下表：
表9-1三组巡视路线
路程之和 总路程 118 110 353 125 125-110根据上表数据，得到分组路程均衡度为?=?100%=12%，0?a?1125所以这种分法的均衡性较好。
小组 一 二 三 路线 W,F,G,I,B,X,A,X,W W,C,T,V,U,Q,R,Q,S,D,C,W W,F,L,J,N,M,K,P,H,Y,F,W 10模型的评价、改进以及推广
10.1模型的评价
1）模型的优点
(1）运用了图论的建立寻优模型，建模的方法简单易懂，尽管建模过程中应用了图论的最短路程理论，但仍可以用初等数学的方法解决的问题；
(2)本问题的算法具有普遍性，对更普遍的这一类问题都能用本文的算法解决，只需更改相应的参数值；
(3)模型一采用穷举法，结果可靠；
(4) 建立的规划模型能与实际紧密联系，结合实际情况对问题进行求解，使得模型具有很强的通用性和推广性；
(5) 模型的计算采用专业的数学软件，可信度较高。 2）模型的缺点
（1）因为本题村庄个数较小，之间距离较短，应用历遍的方法仍能应用人工与计算机的结合在短时间内求出解。然而对于复杂的实际问题如果点数很大，间距很大的情况可能耗时很大；
(2)模型和算法的选取比较单一，未能用到更多、更好的优化模型，缺乏与其他模型的对比性；
(3) 其中的穷举法针对本题比较简单，但对实际其他较复杂问题不具有通用性。
10.2模型的改进
模型一可以采用分区模型，大大提高了程序的空间和时间复杂度；也可以用简化模型，用最近邻法大致确定最优解的区域，然后再用穷举法进行求解，相比单纯的穷举法简化了问题规模，又使所做出的模型答案具有信服力。
10.3 模型的推广
本文所用的三个模型可以应用的范围较广，在图形数据处理及简化方面均可运用该模型均作为参考。
这个模型不仅仅适用于居民缴费站的最佳选址问题，它对规划问题的求解都可以起到指导作用。 本题的求解是一个典型的规划问题，我们的模型的使用范围非常广泛，这一解决问题的模型可以推广到其他服务性行业的选址中的方案的确定，例如旅行售货员问题，只不过需要考虑的约束条件和追求的目标有所不同。