灾情巡视的最短路 数学建模

灾情巡视路线的数学模型

摘 要

本文研究的是根据某县的乡（镇）、村公路网示意图，如何在不同条件下制定出最佳灾情巡视方案的问题。

针对问题一：首先将公路网转化为一张无向赋权图并构造其邻接矩阵，然后根据Dijkstra算法求出任意两点间的最短距离及O点到其余顶点的最短路，最短路构成了一棵以O为树根的最小生成树，将干枝分为三组，每组各顶点间的最短路构成一个完备加权图，再建立混合整数规划模型求其最佳H圈。再逐步调整，使三组中路程较长者减小，最后得到三个组路程分别为204.9km、208.8km和205.3km，最长路程为208.8km，路程均衡度为1.9%，总路程为619km。

针对问题二:依题意至少需要4组，根据问题一中得到的最小生成树将顶点分为4组，利用问题一中的算法，求出每组的最佳H圈，然后逐步调整，使四组中用时较长者减小，最后得到四个组所用时间分别为21.9h、22.41h、22.12h和21.66h，最长时间为22.41h，时间均衡度为3.3%。

针对问题三:根据O点到最远点的距离确定时间上界，然后根据时间上界和到O点的距离由远及近确定最优巡视路线，得最优方案为分23组，巡视时间为6.43h，具体路径见问题三解答。

针对问题四：以问题二中所得结果为例，固定T，t和V中的两个量，改变一个量，求巡视时间与该变量间的关系，巡视时间与T，t和V的曲线图见解答四。

关键词：Dijkstra算法、最小生成树、加权完备图、最佳H圈、整数规划

1.问题重述

1.1问题背景

今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 1.2需要解决的问题

问题一:若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。

问题二:假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。

问题三:在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。

问题四:若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。

2.模型的假设

假设一:各组在巡视过程中，路途通畅，无任何延误时间。 假设二:各组行驶车速都相同，并且匀速行驶。

假设三:非本组巡视的乡（镇）或村只是路过，不作停留。

3.符号的说明

符号 T t V wij dij Zk L α sjk sj 符号说明 在乡(镇)的停留时间 在村的停留时间 汽车的速度 两相邻点i和j的距离 点i和点j的最短距离 第k组的最佳H圈的路程 第一问三个组中路程最大者 路程均衡度 第k组的巡视时间 几个组巡视时间的最大者，即完成巡视任务所需时间 4.问题分析

针对问题一:问题一是多个推销员问题，我们首先考虑对乡(镇）、村这些点进行分组，然后安排三组人进行巡视，将多个推销员问题转化为单个推销员问题。首先根据公路网图建立一个邻接矩阵储存相邻顶点间的距离，然后根据所得的邻接矩阵用Dijkstra算法求出任意两个顶点间的最短距离及O点到其余顶点间的最短路，再根据O点到其余顶点的最短路用Matlab画出以O为树根的最小生成树(程序见附录一)，由最小生成树的树枝将顶点分为三组，根据每组各点间的最短

距离，构造一个完备加权图，即在一个完备加权图里面求最佳H圈，为TSP问题。再建立一个整数规划模型表示TSP问题，求解得出最佳H圈的路程和其对应的路径，最后逐步调整，是三组中巡视路程最长的减小，可得到一个近似最优解。

针对问题二，首先根据单个组的最小巡视路程和在各个停留点所需的总的停留时间计算出至少应分4个组，考虑到该图中乡(镇)和村分布均匀，故首先将52个要巡视的顶点平分为4组，然后如问题一求出每个组的最佳H圈的路程，根据改组的最佳H圈的路程和停留的时间可算出其巡视时间，然后逐步调整，使四个组中巡视时间最大的减小，可得到一个近似最优解。

针对问题三，在巡视人员充足的前提下，设计最佳巡视路线。先根据问题一中 得到的O点到最远点的距离确定巡视时间上界，然后再不超过时间上界的前提下，由远及近设计巡视路线，使巡视时间尽可能接近时间上界。

针对问题四，可以第二问的结果为例进行分析，固定T,t和V中的两个量，改变一个量，绘制出完成巡视任务所需时间随各个量得变化曲线图，观察其对完成巡视任务所需时间的影响，并进行分析。

5.数据分析

首先根据题目所给公路网图建立一个邻接矩阵，然后根据邻接矩阵用Dijkstra算法算出O点到其余顶点间的最短路，根据最短路可用Matlab函数画出以O为树根的最小生成树(程序见附录一)，如下图，将树枝从左至右依次编号为①、②、③、④、⑤、⑥，

6.问题一的解答

6.1模型一的建立

问题一是多个推销员问题，可以转化为最佳H圈问题，再建立整数规划模型求解最佳H圈的路程及路径。首先根据邻接举证用Dijkstra算法求出任意两点间的最短距离及O点到其余顶点间的最短路，根据最短路画出以O为树根的最小生成树。Dijkstra算法如下：

Dijkstra算法：求G中从顶点u0到其预定点的最短路。 S：具有永久标号的顶点集。

对每一个顶点，定义两个标记(l(v),z(v)),其中： L(v):表示从顶点u0到v的一条路的权。 Z(v):v的父亲点，用以确定最短路的路线。 算法的过程就是在每一步改进这两个标记，使最终的l(v)为从顶点u0到v的最短路的权。输入为带权邻接矩阵W。

用上述算法求出的l(v)就是u0到v的最短路的权，从v的父亲点标记z(v)追溯到u0，就得到u0到v的最短路的路线。

如上图，可看出从O出发的共有六个干枝，将这六个干枝进行分组，分组时遵循以下三个准则。

准则一:尽量使长的干枝和短的干枝分为一组。 准则二:尽量把相邻干枝上的点分为一组。

准则三:尽量使使同一枝干及其分支上的点分为一组

根据该原则确定一个分组形式：(①⑥),(②③),(④⑤)。然后分别求每个组的最佳H圈。为求最佳H圈，应首先由给定的图G=(V,E)构造一个以V为顶点集的完备图权，即

,

的每条边(x,y)的权等于顶点x与y在途中最短路的

，这样就把在G中寻找最佳推销员回路问

题转化为在完备加权图G’中寻找最佳H圈，即TSP问题，我们将其转化为混合整数规划模型，建立了模型一。

6.1.1确定目标函数

6.1.1.3建立整数规划模型寻找最佳H圈

首先引入0-1整数变量:，

则目标函数为:

6.1.2确定约束条件

巡视i后必须要有一个即将巡视的确切乡(镇)或村；巡视j前必须要有一个刚刚巡视过的确切乡(镇)或村。用下面的两组约束分别实现上面的两个条件。

到此得到一个指派问题的整数规划模型，但这两个条件对于TSP来说并不充分，只是必要条件。因此要在原模型的基础上附加充分的条件以避免产生子巡回的方法。把额外变量

附加到问题中，可把这些变量看作是连续的（这

些变量在最优解中取整数值）。现附加下面形式的约束条件

综上所述，有以下约束条件:

6.1.3综上所述，得到问题一的最优化模型

6.2模型一的求解

由以上模型得到调整前和经过两次调整后的结果，整理如下表：

(单位：km) 第1组 第2组 第3组 总路程 均衡度 最长路程 调整前 237.5 191.1 125.5 554.1 47.2% 237.5 第一次调整 216.5 191.1 188.7 596.3 12.8% 216.5 第二次调整 204.9 208.8 205.3 619 1.9% 208.8 得到的第二次调整后的路线及各组路程，总路程，均衡度整理如下表： (单位：km) 组路程 总路程 均衡度 最长路程 路线(用红色标记的点为停留点) 别 O-2-5-6-7-E-11-G-13-14-H-12-F-1 204.9 10-F-9-E-8-E-7-6-5-2-O 619 1.9% 208.8 O-M-N-25-20-L-19-J-18-I-15-I-12 208.8 6-17-22-K-21-23-24-27-26-P-O O-2-3-D-4-D-3-C-B-34-35-32-30-3 205.3 Q-28-Q-29-R-31-33-A-1-O

7.问题二的解答

7.1模型二的建立

由题知，有17个乡镇，35个村，巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时，所以，总停留时间为

(小时),计算得出单个组的巡视时最小H圈的路程为508.2km，为

设有x个分组，则有，得x>3.43，故取x=4，即分四组进行

巡视，

分组时遵循以下四项准则:

准则一:尽量使长的干枝和短的干枝分为一组。 准则二:尽量让各组的停留时间相同。 准则三:尽量把相邻干枝上的点分为一组。

准则四:尽量将同一干枝上的点分在一组，且能形成环路。 7.1.1确定目标函数

完成巡视的时间取决于四个组中最长的巡视时间，故目标函数为 min sj=（max（sjk））,k=1,2,32,4 7.1.2确定约束条件 sjk<24,k=1,2,3,4

7.13综上所述，得到问题二的最优化模型 min（max（sjk））,k=1,2,32,4 sjk<24,k=1,2,3,4 7.2模型二的求解

由以上模型求得调整前和调整后的结果整理如下表： 第一组 第二组 第三组 第四组 总路程 乡镇的停留点个数 调整前 村的停留点数 路程(km) 巡视所用时间(h) 乡镇的停留数 调整后 村的停留数 路程(km) 巡视所需时间（h） (km) 时间均衡度 最长时间（h） 5 8 3 10 5 8 4 9 663.6 12.30% 23.12 136.5 149.7 179.2 198.2 21.9 5 8 20.277 4 10 23.12 4 9 22.663 4 8 668.2 3.33% 22.409 136.5 154.3 179.2 198.2 21.9 22.409 22.12 21.663 所得调整后的四组路线，巡视时间等整理如下表：

组别 1 2 3 4 路线(用红色标记的点为停留点) O-1-A-33-31-R-29-Q-30-32-35-34-B-C-O O-M-25-21-K-17-16-17-22-23-24-N-26-27-28-P-O O-M-25-20-L-19-J-18-I-15-14-13-G-11-E-7-6-5-2-O O-2-3-D-4-8-E-9-F-12-H-12-F-10-F-9-E-7-6-5-2-O 路程停留时行驶时巡视时（km) 间（h） 间（h） 间(h） 136.5 154.3 179.2 198.2 18 18 17 16 3.90 21.9 4.41 22.41 5.12 22.12 5.66 21.66 8.问题三的解答

8.1从O点巡视H点的最短时间是所有最短时间中最长的，其距离为77.5km，算

出时间为小时，因此，T=2h，t=1h，V=35km/h时，若巡视

人员足够多，完成巡视的最短时间为6.43小时。

在最短时间的限制下，完成巡视的最佳路线应满足以下条件： （1）每个组巡视的总时间不能超过最短时间

小时，

（2）所有的点都必须访问到，不能漏点， （3）所需巡视组数要尽量小。 在寻求最优路线时，从距离O点较远的点开始搜索比较容易，因为到这些点的路线比较少。

具体方法如下：

第一步：依据最小生成树算出从O点到每一点的最短距离。

第二步：找出其中最大的一个，算出从O点到最短路巡视所需时间ti，并求 第三步：若

。

，则这一组只能访问这一点；若

，则在余下的点中找出

距离O点最远的点，根据条件看这一组能否巡视这一点。 第四步：若能巡视则算出

，转到第三步。

，

第五步：若不能，则依次判断次远点、第三远点···满足总巡视时间不超过 就让这组巡视这一点，直到

，然后再从第二步开始。

通过以上方法找到最优解是23组，如下表：

8.2模型三的求解 路线(用红色标记的点为停留点) 时间 第1组 第2组 第3组 第4组 第5组 第6组 第7组 第8组 第9组 第10组 第10组 第12组 第13组 第14组 第15组 第16组 第17组 第18组 第19组 第20组 第21组 第22组 第23组 O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-0 O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-0 O-M-25-21-K-18-I-15-I-18-K-17-16-17-K-21-25-M-0 O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O O-2-5-6-7-E-9-F-10-F-9-E-8-E-7-6-5-2-O O-2-5-6-7-E-11-G-11-E-7-6-5-2-O O-M-25-21-K-18-I-18-K-21-25-M-O O-2-5-6-7-E-11-E-7-6-5-2-O O-2-5-6-L-E-9-F-9-E-7-6-5-2-O O-2-5-6-L-19-J-19-L-6-5-2-O O-M-25-21-K-17-16-17-K-21-25-M-O O-M-25-21-K-18-K-21-25-20-25-M-O O-P-26-N-23-22-23-N-24-N-26-P-O O-2-5-6-7-E-8-E-7-6-5-2-3-D-4-D-3-2-O O-2-5-6-L-6-5-2-O-M-O O-1-A-34-35-34-A-33-A-1-O O-R-29-Q-30-Q-29-R-O O-M-25-M-O-P-26-N-26-P-O O-R-31-32-31-R-O O-P-26-27-26-P-28-P-O O-2-3-D-3-2-O-C-O O-1-A-1-B-1-O O-2-3-2-5-2-O-M-O-P-26-N-23-N-26-P-O 9.问题四的解答

6小时26分 6小时9分 6小时19分 5小时51分 6小时13分 5小时35分 5小时29分 6小时12分 6小时9分 6小时6分 6小时3分 6小时13分 5小时12分 6小时0分 6小时17分 5小时29分 6小时2分 6小时3分 5小时44分 5小时40分 5小时25分 6小时9分 5小时51分 9.1模型四的建立

根据题意，假设巡视组数定为四组，以问题二中的分组方案为例，固定T，t和V中的两个量，改变其中一个量，求巡视时间与该变量间的关系，通过MATLAB求解得到如下巡视时间随三个变量的变化而变化的图(程序见附录一):

图中三个红色的点位于一条直线上，分别代表T=2小时，t=1小时，V=35千米/小时时，对应问题二的巡视时间22.409h，即为问题二的解。 显然，由下图得出以下结论：

(1)当固定t、V时，巡视时间随T的增大而增大

(2)当固定T、V时，巡视时间随t的增大而增大，且随t增大得比随T增大地 快

(3)当固定T、t时，巡视时间随V的增大而减小

更进一步分析，可看出，当V低于20km/h后，巡视时间急剧增加，当V高于50km/h后，再增加对减小巡视时间作用很小，故从效率和安全两个角度综合考虑，汽车速度V应不低于20km/h，应不高于50km/h

11.模型的模型的评价、改进及推广

11.1模型评价

模型优点：

(1)用均衡度量化分组的均衡性。

(2)综合多种算法的思想进行求解，使所得模型在灾情巡视方面有科学的指

导意义。

模型缺点：第三问用经验来调整的，如果可以通过编程求解则更好。 11.2模型改进

由于实际情况中，各个乡（镇）、村的受灾情况不同，故应根据受灾的严重程度来分配巡视时的停留时间，可先将每个巡视点的受灾程度量化，建立T，t关于受灾程度的函数，然后分组巡视，求最佳巡视路线。 11.3模型推广

所建模型还可用于公安执勤人员的最优巡回路线、流水作业、生产线的顺序问题以及老师任课班级负荷分配等问题。

12.参考文献

[1] 赵静,但琦,数学建模与数学实验,北京:高等教育出版社,2008.

[2] 薛定宇，陈阳泉，高等应用数学问题的MATLAB求解，北京：清华大学

出版社，2008.

13.附录

附录一：Matlab程序

%dijkstra.m

function [d,path]=dijkstra(b,s,t) [n,m]=size(b);ix=(b==0);

visited(1:n)=0;dist(1:n)=inf;parent(1:n)=0;dist(s)=0;d=inf;

for i=1:(n-1)

ix=(visited==0);vec(1:n)=inf;vec(ix)=dist(ix); [a,u]=min(vec);visited(u)=1; for v=1:n

if (b(u,v)+dist(u)

dist(v)=dist(u)+b(u,v);parent(v)=u; end end end

if parent(t)~=0

path=t;d=dist(t); while t~=s

p=parent(t);path=[p,path];t=p; end end %主程序

clear,clc

format short g a=inf*ones(53);

a(1,[18 18+33 18+34 18+1 2])=[8.8 7.4 11.5 10.3 12.2]; a(2,[1 18+34 3 18+1])=[12.2 17.6 11.0 5.9]; a(3,[2 18+3 15 18+1])=[11.0 7.9 11.5 11.2];

a(4,[18+5 18+3 18+4 18+7])=[11.3 8.2 12.7 15.1]; a(5,[18+11 18+7 18+8 18+9])=[14.2 7.2 8.0 7.8]; a(6,[18+12 18+9 18+10])=[12.2 5.6 10.8]; a(7,[18+13 18+11 18+12])=[8.6 6.8 7.8]; a(8,[18+14 18+12])=[9.9 10.2];

a(9,[18+15 18+16 18+18 10 18+13])=[8.8 11.8 8.2 15.8 16.4]; a(10,[18+13 9 18+18 18+19 18+11])=[9.8 15.8 8.2 8.1 13.2]; a(11,[18+17 18+22 18+21 18+18])=[9.8 10.1 4.1 9.2]; a(12,[18+19 18+20 18+6 18+7])=[7.2 5.5 11.8 14.5];

a(13,[18+25 14 15 18+5 18+6])=[12.0 14.2 19.8 11.4 9.5]; a(14,[18+23 18+24 18+26 13 18+25])=[7.9 13.2 10.5 14.2 8.8]; a(15,[13 16 18 18+1 3 18+2])=[19.8 10.1 12.9 6.0 11.5 9.2]; a(16,[18+26 18+28 18+29 15])=[10.5 12.1 15.2 10.1];

a(17,[18+28 18+30 18+29])=[8.3 7.7 7.2];

a(18,[18+29 18+31 1 15])=[7.9 9.2 8.8 12.9]; a(19,[15 1 2 3])=[6.0 10.3 5.9 11.2]; a(20,[18+5 15 18+3])=[8.3 9.2 4.8]; a(21,[18+2 3 4])=[4.8 7.9 8.2]; a(22,[4 18+8])=[12.7 20.4];

a(23,[18+6 13 18+2 4])=[9.7 11.4 8.3 11.3]; a(24,[12 13 18+5 18+7])=[11.8 9.5 9.7 7.3]; a(25,[12 18+6 4 5])=[14.5 7.3 15.1 7.2]; a(26,[5 18+4])=[8.0 20.4]; a(27,[6 5])=[5.6 7.8]; a(28,6)=10.8;

a(29,[7 10 5])=[6.8 13.2 14.2]; a(30,[8 7 6])=[10.2 7.8 12.2];

a(31,[18+14 9 10 7])=[8.6 16.4 9.8 8.6]; a(32,[8 18+15 18+13])=[9.9 15 8.6]; a(33,[18+14 9])=[15 8.8]; a(34,[18+17 9])=[6.8 11.8];

a(35,[18+22 11 18+16])=[6.7 9.8 6.8]; a(36,[10 9 11])=[8.2 8.2 9.2];

a(37,[10 18+20 12])=[8.1 9.3 7.2];

a(38,[18+21 18+19 18+25 12])=[7.9 9.3 6.5 5.5]; a(39,[11 18+23 18+25 18+20])=[4.1 9.1 7.8 7.9]; a(40,[18+17 11 18+23])=[6.7 10.1 10.0];

a(41,[18+21 18+22 18+24 14])=[9.1 10.0 8.9 7.9]; a(42,[18+23 14 18+27])=[8.9 13.2 18.8];

a(43,[18+20 18+21 14 13])=[6.5 7.8 8.8 12.0]; a(44,[14 18+27 16])=[10.5 7.8 10.5];

a(45,[18+24 18+26 18+28])=[18.8 7.8 7.9]; a(46,[18+27 16 17])=[7.9 12.1 8.3]; a(47,[16 17 18])=[15.2 7.2 7.9]; a(48,[17 18+32])=[7.7 10.3];

a(49,[18 18+32 18+33])=[9.2 8.1 7.3];

a(50,[18+30 18+31 18+35 18+33])=[10.3 8.1 14.9 19]; a(51,[18+31 18+32 18+35 1])=[7.3 19 20.3 7.4]; a(52,[2 1 18+35])=[17.6 11.5 8.2];

a(53,[18+34 18+33 18+32])=[8.2 20.3 14.9];

e=a(15,:);a(2:15,:)=a(1:14,:);a(1,:)=e;f=a(:,15);a(:,2:15)=a(:,1:14);a(:,1)=f;

a1=tril(a);a2=triu(a);a2_zhuanzhi=a2';duicheng_yanzheng=a1-a2_zhuanzhi;

b=a;zdjl=zeros(53);path=zeros(53,11);jl_path=zeros(53,12);

for m=1:length(b)

for n=1:length(b)

zdjl(m,n)=dijkstra(b,m,n); if m==n

zdjl(m,n)=0; end

if m==1&&n>1

[zdjl(m,n) p]=dijkstra(b,m,n); path(n,1:length(p))=p; end end end

jl_path=[[1:53]' zdjl(:,1) path] zdjl

%画最小生成树的程序

a1=1;b1=4;w1=11.5;

a2=[1 20 21 5 20 23 24 13 37 11 31 24 25 6 6 29 6 27 7 7 30]; b2=[20 21 5 22 23 24 13 37 11 31 32 25 6 26 29 8 27 7 28 30 9];

w2=[9.2 4.8 8.2 12.7 8.3 9.7 11.8 7.2 8.1 9.8 8.6 7.3 7.2 8.0 14.2 6.8 7.8 5.6 10.8 12.2 10.2];

a3=[1 14 43 43 39 12 35 12 36 10];b3=[14 43 38 39 12 35 34 36 10 33];

w3=[19.8 12.0 6.5 7.8 4.1 9.8 6.8 9.2 8.2 8.8];

a4=[1 16 16 44 44 15 15 41 ];b4=[16 46 44 45 15 42 41 40]; w4=[10.1 12.1 10.5 7.9 10.5 13.2 7.9 10.0];

a5=[1 18 47 17 18 49];b5=[18 47 17 48 49 50];w5=[7.9 7.9 7.2 7.7 9.2 8.1];

a6=[1 19 19 2 2 52];b6=[19 3 2 51 52 53];w6=[6.0 7.9 10.3 7.4 11.5 8.2];

R=sparse([a1 a2 a3 a4 a5 a6],[b1 b2 b3 b4 b5 b6],[w1 w2 w3 w4 w5 w6]);

R(53,53)=0;h=view(biograph(R,[],'ShowWeights','on')); %第一问程序

zdjl_12=zdjl([1 4 5 6 7 8 9 11 13 20:32 37],[1 4 5 6 7 8 9 11 13 20:32 37]);

zdjl_34=zdjl([1 10 12 14 15 16 33:36 38:46],[1 10 12 14 15 16 33:36 38:46]);

zdjl_56=zdjl([1 2 3 17 18 19 47:53],[1 2 3 17 18 19 47:53]); zdjl_12_1=zdjl([1 6 7 8 9 11 13 20 23:32 37],[1 6 7 8 9 11 13 20 23:32 37]);

zdjl_56_1=zdjl([1 2 3 4 5 17 18 19 21 22 47:53],[1 2 3 4 5 17 18 19 21 22 47:53]);

zdjl_12_tzh=zdjl([1 6 7 8 9 20 23:32],[1 6 7 8 9 20 23:32]); zdjl_34_tzh=zdjl([1 10 11 12 13 14 15 16 33:37 38:45],[1 10 11 12 13 14 15 16 33:37 38:45]);

zdjl_56_tzh=zdjl([1 2 3 4 5 17 18 19 21 22 46:53],[1 2 3 4 5 17 18 19 21 22 46:53]); %第二问程序

zdjl_1=zdjl([1 2 3 4 17 18 19 47:53],[1 2 3 4 17 18 19 47:53]); zdjl_2=zdjl([1 12 15 16 34 35 39:46],[1 12 15 16 34 35 39:46]); zdjl_3=zdjl([1 8 10 11 13 14 24 29 31 32 33 36 37 38],[1 8 10 11 13 14 24 29 31 32 33 36 37 38]);

zdjl_4=zdjl([1 5 6 7 9 20:23 25:28 30],[1 5 6 7 9 20:23 25:28 30]);

zdjl_1_tzh=zdjl([1 2 3 4 17 18 19 47:53],[1 2 3 4 17 18 19 47:53]);

zdjl_2_tzh=zdjl([1 12 14 15 16 34 35 39:46],[1 12 14 15 16 34 35 39:46]);

zdjl_3_tzh=zdjl([1 8 10 11 13 23 24 29 31 32 33 36 37 38],[1 8 10 11 13 23 24 29 31 32 33 36 37 38]);

zdjl_4_tzh=zdjl([1 5 6 7 9 20:22 25:28 30],[1 5 6 7 9 20:22 25:28 30]); %第三问程序

[jl index]=sort(zdjl(:,1));jl_index=[jl index]

sj=[2*77.5/35+2;2*72.7/35+1+1;(69.9+8.8+11.8+60.3)/35+1+1;(67.3+12.2+5.6+49.5)/35+1+1;

(65.9+10.8+5.6+7.8+8.0+49.7)/35+1+1;2*62.7/35+2;2*61.1/35+2;2*55.9/35+1+1+1;

2*55.1/35+2+1;2*54.3/35+1+2;2*53.5/35+1+2;(52.9+9.2+4.1+7.9+38.3)/35+1+1+1;(49+10.0+8.9+44.3)/35+1+1;

(41.7+8+12.3+8.1+34.9)/35+2+1;(39+11.8+9.5+19.8)/35+2+2;(36+8.2+11.5+7.4+23.7)/35+1+1+1;2*35.7/35+1+2+1;(31.8+8.8+10.5+20.6)/35+1+2+1;

(30.2+8.1+9.2+12.9)/35+1+1+2;(28.4+7.9+12.1+10.1)/35+1+1+2;(22.2+8.2+7.9+11.5)/35+2+2;(16.3+12.2+5.9+6.0)/35+2+2+1;

(9.2+4.8+4.8+8.3+11.4+14.2+7.9+39)/35+1+1+1]; SJ=[round(sj) round(60*rem(sj,1))] %第四问程序

T=0.1:0.1:6;t=0.1:0.1:6;V=3.1:1:60;

sj_max_T=max([5*T+8+136.5/35;4*T+10+154.3/35;4*T+9+179.2/35;4*T+8+198.2/35]);

sj_max_t=max([5*2+8*t+136.5/35;4*2+10*t+154.3/35;4*2+9*t+179.2/35;4*2+8*t+198.2/35]);

sj_max_V=max([5*2+8+136.5./V;4*2+10+154.3./V;4*2+9+179.2./V;4*2+8+198.2./V]);

plot(T,sj_max_T,'m',t,sj_max_t,'g',V/10,sj_max_V,'b');grid on

legend('最短巡视时间随T的变化曲线','最短巡视时间随t的变化曲线','最短巡视时间随V的变化曲线');

xlabel('T（小时） t（小时） V（10千米/小时)');ylabel('最短巡视时间(小时)');

title('最短巡视时间随T,t和V的变化曲线');hold on

h=stem([1 2 3.5],[22.409 22.409 22.409],'fill','-.'); set(get(h,'BaseLine'),'LineStyle',':'); set(h,'MarkerFaceColor','red');

附录二：Lingo程序

model: sets:

city/1..53/:u; link(city,city): dist, x;

endsets

n=@size(city); data:

!只需输入最短路矩阵 enddata

min=@sum(link:dist*x); @for(city(k):

@sum(city(i)|i#ne#k:x(i,k))=1; @sum(city(j)|j#ne#k:x(k,j))=1; );

@for(city(i)|i#gt#1:

@for(city(j)|j#gt#1#and#i#ne#j: u(i)-u(j)+n*x(i,j)<=n-1); );

@for(city(i)|i#gt#1:u(i)<=n-2); @for(link:@bin(x)); end

本文来源：https://www.bwwdw.com/article/3n73.html