所以
?w(c)?min
i142：均衡度a最小:
我们定义a?maxw(ci)?w(cj)maxw(ci)为该分组的实际均衡度，显然0?a?1。a越
maxw(ci)?w(cj)maxw(ci)小说明分组的均匀性越好。因此mina?所以我们建立了以下目标函数：
?4??w(ci)?min?1 ?
?mina?maxw(ci)?w(cj)?maxw(ci)?
6.2.2确定约束条件
在加权图G中，将顶点集V划分为V1 , V2, V3，V4,则G的三个子图为G[V1], G[V2],
G[V3], G[V4]需满足一下几个条件：
1:顶点O包含在每个顶点集Vi 中，即O ?Vi，i=1,2,3,4
2：顶点集Vi为V（G）的子集，即
?V14i?V(G)
3:在加权图G中，G的三个子图G[V1], G[V2], G[V3] ,G[V4],必须形成一条
?p??xij?1,j?N;?i?1?p
?x?1,i?N?ij?j?1?4:每个组在巡视的过程中，往返的时间不能超过24小时即：
w(ci)?24 aiT?bit?V6.2.3综上所述得到问题二的最优化模型为
?4??w(ci)?min?1 ?
maxw(c)?w(c)ij?mina??maxw(ci)?
11
??O?Vi，i?1,2,3,4?4???Vi?V(G)?1?p s.t??xij?1,j?N;
?i?1?p??xij?1,i?N?j?1?w(ci)?aiT?bit??24V?
6.3问题二的解答
根据我们确定的分组原则把最小生成树大致分成四组，在Lingo中依次求出每组的最优哈密尔顿回路（详见附录2）。再依据均衡度的大小进行调整，最后得到的结果为近似最优解。
通过对最小生成树分三组后，得到以下最优路径如图10：
编号 巡视路线 O->C->B->34->35->32->30->Q->29->R->31->33->A->1->O O->P->28->27->26->N->24->23->22->17->16->17->K->21->25->M->O O->M->25->21->K->18->I->15->14->H->12->G->11->G->13->J->19->L->20->25->M 路程 136.5 154.3 203.9 153.4 行走 时间 等待 时间 总时间 1 2 3 4 3.90 4.41 5.83 4.38 18 18 18 15 21.90 22.41 23.83 19.38 O->2->3->P->4->8->E->9->F->10->F->9->E->7->6->5->2->O 图10
时间均衡度a1?23.83?19.38?100%?18.67#.83203.9?136.5路径均衡度a2??100%?33.06 3.9
最佳巡视路线图为：
12
图12
7.问题三的解答
7.1模型的建立
7.1.1确定目标函数
在问题三中， T , t和V同二没有改变，在巡视人员足够多的情况下要求求出巡视的最短时间。分析的，在人员足够的情况下，我们给每个镇（乡）或村都分派一名巡视员 。每个巡视员所走的路线该点与O点之间的最短路径，巡视时间为往返时间加上访问点权时间。对他们巡视时间进行比较，当巡视时间最长的巡视员返回时，其他巡视员都已近返回。所以巡视时间最长的即为要求的最短时间，因此我们确定的目标函数为：
min(maxKi)?max2Soi?ki V7.1.2确定约束条件
13
巡视人员从O点出发径直走向i点，在这个过程中Soi为两点之间权值最小值：
2(n) minSoi,Soi,?,Soi
??若巡视员访问某点权的时间Ki与maxKi之差大于一小时，则可考虑访问一个村。若大于两小时以上则可考虑访问多个村或镇，但附加访问的村或镇所用的时间Ki仍小于maxKi则
0?maxKi?Ki?1?Ki'?Ki,?K'?K?1,1?maxKi?Ki?2ii???Ki'?Ki?aiT?(maxKi?Ki?aT)t ?maxKi?Ki?2???Ki'?maxKi
综上所述得到问题三的最优化模型为
min(maxKi)?
max2Soi?ki V0?maxKi?Ki?1?Ki'?Ki,?K'?K?1,1?maxKi?Ki?2ii???Ki'?Ki?aT?(maxKi?Ki?aT)t ?maxKi?Ki?2???Ki'?maxKi
7.2模型的求解
首先我们通过Dijkstra算法算出O点距离其它52各点的权值最小值，通过
比较发现点H距离O点最小权值最大，H又恰好为一个镇，综上二者可知从O点
2S2?77.5?2?6.43 径直访问H点所用的时间最长，最长时间为KOH?oi?k?V35所以在人员足够多的情况下，完成巡视的最短时间为6.43
1
6 11 55.9 21 39.6 31
2 9.2 12 67.3 22 49 32 3 14 13 64.1 23 39 33 4 34.9 14 72.7 24 44.3 34 5 17.5 15 69.9 25 31.8 35 6 27.2 16 60.3 26 20.6 36
14
7 34.5 17 53.5 27 28.4 A 8 49.7 18 52.9 28 22.2 B 9 49.5 19 46.2 29 20.8 C 10 65.9 20 38.3 30 35.7 D
22.1 30.2 23.7 27.8 36 0 E F G H I J 41.7 55.1 62.7 77.5 61.1 54.3 P Q R 10.1 28 12.9 16.3
K 43.7 11.9 L 39 11.5 M 19.8 22.2 N 31.1
图13：Dijkstra算法算出O点距离其它52各点的权值最小值
通过Matlab编程求解（详见附录3,4 ）在上述条件下求得共需要29组巡
视人员最优的巡视方案如下： 编号 巡视路径 1 O,2,5,6,7,E,9,F,10,F,9,E,7,6,5,2,O 2 0.2,5,6,L,19,J,13,14,13,J,19,L,6,5,2,O 3 0,c,0 4 O,2,5,6,7,E,9,F,9,E,7,6,5,2,O 5 O,2,5,6,7,E,11,G,11,E,7,6,5,2,O 6 O,2,5,6,7,E,9,F,12,H,12,F,9,E,7 ,6,5,2 ,O 7 O.M,25,21,K,18,I,18,K,21,25,M,O 8 O,2,5,6,L,19,J,19,L,6,5,2, O 9 O,2,5,6,L,19,J,19,L,6,5,2,O 10 0,2,3,2,0 11 O,2,3,D,4,D,3,2,O 12 O,2,5,6,5,2,O 13 O,2,5,6,7,E,8,E,7,6,5,2,O 14 O,2,5,6,7,E,9,E,7,6,5,2,O 15 O,M,25,21,K,17,K,21,25,M,O 16 O,M,25,21,K,18,K,21,25,M,O 17 O,2,5,6,L,19,L,6,5,2, O 18 O,P,26,N,23,22,23,N,26,P,O 19 O,P,26,N,23,N,26,P,O 20 O,53,29,53, O 21 O,53,29,Q,30,Q,29,53,O 22 O,53,31,32,31,53, O 23 O,1,A,33,A,1,O 24 O,1,A,34,35,34,A 25 O,2,5,6,7,E,11J,19,20,25,M,O 26 O,2,5,6,7,E,9,F,12,G,13,J,19L,6,5,2,O 27 O,M,25,21,K,18,I,15,I,16,17,K,21,25,M O 28 O,P,26,N,24,27,26,P,O 29 O,1,B,1,O,P,28,P,O 图14
15
停留地点 12 14 C F G H I J K 2,3 D,4 5,6 7,8 E,9 M,17 25,21,18 L,19 P,22 26,N,23 R,29 Q,30 31,32 1,A,33 34,35 11,20 12,13 15,16 24,27 B.28 所需时间 4.765714286 5.154285714 2.657142857 5.148571429 5.582857143 6.428571429 5.491428571 5.102857143 4.497142857 2.8 4.994285714 3.554285714 4.84 5.828571429 6.057142857 6.022857143 5.64 5.8 6.228571429 4.188571429 5.04 3.725714286 5.354285714 4.057142857 4.471428571 4.391428571 4.585714286 3.802857143 4.314285714