Node数值与地图中字符的对应表
Node 字符 Node 字符 Node 1 O 11 J 21 2 A 12 K 22 3 B 13 L 23 4 C 14 M 24 5 D 15 N 25 6 E 16 P 26 7 F 17 Q 27 8 G 18 R 28 9 H 19 1 29 10 I 20 2 30 字符 Node 字符 Node 字符 Node 字符 3 31 13 41 23 51 33 4 32 14 42 24 52 34 5 33 15 43 25 53 35 6 34 16 44 26 7 35 17 45 27 8 36 18 46 28 9 37 19 47 29 10 38 20 48 30 11 39 21 49 31 12 40 22 50 32
6.问题一的解答
针对问题一我们建立模型一 6.1模型一的建立 6.1.1确定目标函数
根据题意，根据题目信息，我们将巡视路线图抽象为一个赋权无向连通图
G?V,E?，现要分三组进行巡视，则需要将G?V,E?分成三个子图Gi?i?1,2,3?，在每个子图GI中寻找路程最小的回路Si?1,2,3?，于是我们以汽车行驶总路程和各组行驶路程的均衡度为目标函数：
?MinS ???s6.1.2 确定约束条件
各组行驶路线路程最小值：
MinSi,?i?1,2,3?
则行驶路线总路程最小值：
MinS??MinSi
i3根据路线巡视图可知，除县政府意外有52个巡视点，则各组巡视点之和应该满足
?Vi3i?52
且各组行驶路程的均衡度?s应该小于0.1才算比较均衡即
?s?Max?Si??Min?Si??0.1
Max?Si?
6.1.3 综上所述，得到问题一的模型
?MinS ???s3??MinS??MinSii??Max?Si??Min?SI?s.t??s?
Max?Si???3??Vi?52?i
6.2 模型一的求解 6.2.1确定准则
为了设计出更为合理的巡视路线，我们规定了以下准则 准则一：尽量使同一支干上集分支上的点分在同一组； 准则二：尽量使相邻干支上的点分到同一组； 准则三：尽量将长的干支与短的干支分到同一组 6.2.2求解过程
在以上准则前提下，我们根据最小树分块原则，将图G?V,E?初步分块成三个子图Gi?i?1,2,3?，提出了三种设计方案，每种方案是在前种方案基础上进行调整，最终确定方案三时最佳的。 设计方案一：
我们根据分组原则确定第一条分组方案，方案一如下