灾情巡视路线
灾情巡视路线
摘要
本文讨论了由某县的赋权交通网络图确定分组进行灾情巡视的最佳路线规划问题。
对于问题一，对所给的赋权网络图要求分三组（路）巡视，得到总路程最短且各组尽可能均衡的巡视路线，可转化为三个售货员的最佳旅行售货员问题。本文先用MATLAB软件编程计算得到加权网络图的最小生成树，按每块近似有相等总路程的标准将最小生成树分成三块，每一块都转化为一个最佳旅行售货员问题。再确定总路程最短且满足各组尽可能均衡的路线的目标函数，然后对目标函数进行调整改进，比较得到最终的双目标最优化模型，最后确定的最佳行驶路线
目要求。因此首先考虑分四组的情况。在分三组的基础上根据分组原则将图大致划分为4个子图。同样以巡视路程最短和时间均衡度最小为目标函数，各巡视时间小于24小时作为约束条件建立多目标规划模型。然后采用类似于问题一的分
间为最短时间，根据最短路径树，从远到近，依次巡视各村镇，在所用时间不大于最短时间的前提下，各组尽可能多的巡视几个村镇，进行分组确立巡视点，并对已巡视过的点进行逐个剔除。通过分组优化对比等，得出最佳分组情况及巡视
响的只是整个巡视时间。我们利用MATLAB 编程画图得到T 、t 、V 与巡视时间的关系曲线。观察曲线发现：(1)当停留时间t 不变时，随着行驶速度的增加，巡视所用的时间越来越短。在保证安全的行驶过程中，适当加快行驶速度，可以减少花费在路途中的时间。(2)停留时间t 与巡视时间呈线性关系，在保持V 不变时，巡视最短的时间min T 与停留时间t 成正比关系，即无论停留时间t 取何值，对min T 的影响都较大。
关键词：最小生成树多目标规划最佳路线
一、问题重述
如图为某县的乡（镇）、村公路网示意图。该县遭受水灾，为考察灾情、组织自救，县领导决定带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。现有如下问题：
县公路网络示意图
1. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
2. 假定巡视人员在各乡（镇）停留时间 T=2 小时，在各村停留时间 t=1小时，汽车行驶速度 V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。
3. 在上述关于 T,t和 V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。
4. 若巡视组数已定（比如三组），要求尽快完成巡视，讨论T，t和 V改变对最佳巡视路线的影响。
二、模型假设
1、若汽车只是路过乡村，则不考虑汽车穿越乡村的时间。
2、假设汽车行驶速度稳定不变。
3、假设无其它意外情况
三、符号说明
四、问题的分析
本文是领导巡视受灾县,并求最佳巡视路线的数学建模问题，题中已给出该县公路的网络图，要求在不同的题目要求下，得到灾情巡视的最佳分组方案和路线。
若将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中旅行售货员的一类问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权（路程或时间）最小. 本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又可使边上的权之和达到最小的闭路，即最佳旅行售货员问题。
对于问题一,要求分三组（路）巡视，得到总路程最短且各组尽可能均衡的巡视路线，可转化为三个售货员的最佳旅行售货员问题。先用MATLAB 软件编程计算得到加权网络图的最小生成树，按每块近似有相等总路程的标准将最小生成树分成三块，每一块都转化为一个最佳旅行售货员问题。再确定总路程最短且满足各组尽可能均衡的路线的目标函数，最后对目标函数进行调整改进，比较得到最终的双目标最优化模型。
对于问题二，由于T =2小时，t =1小时，V =35公里/小时,需访问的乡镇共有17个，村共有35个。计算出在乡(镇)及村的总停留时间为1723569?+=小时，要在24小时内完成巡回，若不考虑行走时间，有:69/i<24(i 为分的组数). 得i 最小为4，所以至少要分4组。于是将题目转化为四个售货员的最佳旅行售货员问题，再用与问题一类似的方法运用MATLAB 软件编程计算求解，即可得到问题二的结果。如果部分组的用时大于24小时，则调整分组方式；若所有组的用时均大于24小时则再考虑多加一组。直到找到相对均衡条件下的最佳路线。
对于问题三，考虑在人员足够多的情况下，求出最短的巡视时间。假设一个小组只巡视一个点的情况下，则去巡视离O 点最远的点所花时间最长。我们以巡视小组中所耗时间最长的小组所用时间作为这次整个巡视的最短时间。要使这次巡视时间最短，则要求去巡视离点O 最远的点所花时间最小，由题目所给图可知，离O 点最远的点为H ，所以就以巡视H 所花时间作为min T 。当此小组只巡视时，min T 最小。在不超过min T 的情况下，根据其他小组的剩余时间确定沿途是否巡视其他点。其中巡视原则为：
（1）当一组人员巡视完规定点后时，在剩余时间允许的情况下，优先考虑原巡视点附近而距离O 较远的点；
（2）最大限度使用剩余时间，主要考虑原则（1）。按照此原则，逐个巡视，直至巡视完所有点。
对于问题四，若巡视组数已定，则每个小组的最短路径就已确定，T 、t 、V 改变只影响的是整个的巡视时间。要求尽快完成巡视，即巡视时间要尽可能小。巡视时间包括到巡视点的行驶时间和在巡视点的停留时间。行驶时间主要取决于速度V ，而停留时间由T 、t 决定。所以此问题讨论的是当T 、t 、V 改变时对巡视时间的影响，即对T 、t 、V 的影响分析。
五、模型的建立与求解
由题目可知，共有53个乡（镇）和村，即在赋权网络图），，（W E V G 中共有53个点. 其中)53(},,{21==n v v v V n 表示图G 的53个节点，}{ij e E =表示相关联的两点j i ,的边集，}{ij w W =表示相关联两点j i ,间的权值。定义决策变量ij r ：
??
?=两点不相关
表示两点相关联
表示j i j i r ij ,0
,1
其中相关联表示j i ,两点之间有权值，不相关表示j i ,之间没有权值。将这些
点和权值生成图G 的矩阵，对于不相关的两点权值作为无穷大处理。用MATLAB 编写程序，得出该网络图G 的最小生成树。画出的图形如下图所示。
最小生成树图
5.1问题一模型的建立与求解 5.1.1模型的建立
通过问题一的分析，建立多目标规划模型。 （1）三组巡视的总路线最短：
∑=3
1
min
i i
c
（2）巡视路线尽量均衡：
)
max()
min()max(min i i i c c c -=α
上式两个目标函数相互矛盾，不可能同时达到最好。而α越小，表示均衡度越好。设当0.1α<时，认为均衡度比较好，满足均衡要求。 5.1.2模型的求解
通过增环、扩环、换枝等方法，对子图内部进行适当调整优化，找出多种方案进行对比，寻找出最佳巡视回路，得到结果如下表：
根据上表数据，得到分组路程均衡度为203.5-200.4
=
100%=1.52%203.5
α?.
本题的分组路程均衡度为1.52%，说明本题分组路程均衡性很好，满足题目要求的均衡路线，总路程为607.4公里。各小组的巡视路线如下图.其中绿色表示第一组，红色表示第二组，蓝色表示第三组。
各小组巡视路线图
5.2问题二模型的建立与求解 5.2.1模型的建立
由前面对问题二的分析可知，要满足条件，最少要分成4组进行灾情巡视。先按4组建立模型并求解，若分成4组仍无法满足，则继续考虑增加巡视组数。要求巡视时间与总路程长度均达到最小. 得出目标函数：
??
???
∑=αmin min 4
1
i i
c 外加巡视时间不超过24小时的约束条件：
241,2,3,4i
i c t mT nt i V
=++<=（其中） 5.2.2模型的求解
依据该县地图的最小生成树图首先将图形大致的分为四组,然后采用类似于问题一的分组规则进行优化调整.显然，该问要求在时间尽量短的条件下，使总的行驶路程最短。同样可以得到多个满足条件的解,现在仅将多组巡视方案中时
定义最小生成树的分支上未分组的点中到O 最远的点为N V ，次最远点为
1-N V ，依此类推，直至离O 最近的点1V 。O 点到点N 的时间记为n T ，停留时间记为N t 。将N V 看成第一组，再根据约束条件判断N V V V ,...,21分组情况，判别方法如下：
（1）若1-++≤≤+N N N N N N t t T T t T ，则点N V 应单独分在一组；若
1min -++≥+>N N N N N t t T t T T ，则N V 和1-N V 分为一组。同理，可依此类推判断,...,32--N N V V 直至待判点不能和前面已判点分在一组。
（2）再在分支上未分组的点中找到离O 最远的点，作为下一组，用上述同样的方法判断，直至所有节点分组完。按以上求解过程，逐步求解可得以下共分
5.4问题四模型的建立与求解 完成所有巡视所用最短时间：
mt nT V
S T ++=min min
以问题一中的第一组为例，其中7,10,4.2001===n m km S 。为了方便讨论，将T ，t 统一作为时间变量，设)2(==b bt T ，则上式可以改写为：
t bn m V
S T )(min
++=
（1）当停留时间t 不变时，利用matlab 作图得到巡视所用最短时间min T 与行驶速度V 的关系图如下：
由V T -min 图可以知道，随着行驶速度的增加，巡视所用的最短时间越来越短。在保证安全的行驶过程中，适当加快行驶速度，可以减少花费在路途中的时间。而速度过小时，对min T 的影响较大，这个时候可以考虑重新分组。 （2）当保持h km V /35=不变时，利用matlab 作图得到的巡视所用最短时间min T 与停留时间t 的关系图如下：
t T -min 图
由t T -min 图可以知道，在保持V 不变时，巡视最短的时间min T 与停留时间t 成正比关系，即无论停留时间t 取何值，对min T 的影响都较大，当停留时间小范围波
动时，也需重新考虑分组。
六、模型的评价与推广
6.1优点：
1）本模型运用最小生成树的方法，将区域大致分为三个部分，使求解简化；
2）采用均衡度的表达式，使模型检验合理方便；
3）模型运用网络图的表示方法给出了灾情最佳巡视路线，不仅缩短了时间，还考虑了各个组巡视的均衡度，对考察灾情、组织自救起到了很大的作用。
6.2缺点：
1）运用MATLAB软件求得最小生成树图后，寻找各个组的巡视路线得最优解工作量较大。
2）问题四中，在对T、t、V的灵敏度分析中，只对其变化作了定性分析，而未作定量分析。
七、参考文献
[1]姜启源，数学建模（第三版）[M]，北京：高等教育出版社，2003
[2]韩中庚，数学建模方法及其应用[M]，北京：高等教育出版社，2005
[3]王庆波，最佳灾情巡视路线[J]，哈尔滨工业大学学报，第31卷第2期，1999年4月
八、附录
程序一
最小生成树的程序：
clc,clear
a=zeros(53);
a(50,1 )=6.0;a(50,53)=12.9;a(50,38)=11.5;a(50,2)=9.2;a(50,48)=19.8;a(50,51)=10.1;
a(1,36)=10.3; a(1,37)=5.9;a(1,38)=11.2;
a(2,3)=4.8;a(2,5)=8.3;
a(3,38)=7.9;a(3,39)=8.2;a(4,39)=12.7;a(4,8)=20.4;
a(5,48)=11.4;a(5,39)=11.3;a(5,6)=9.7;
a(6,48)=9.5;a(6,7)=7.3;a(6,47)=11.8;
a(7,39)=15.1;a(7,40)=7.2;a(7,47)=14.5;a(8,40)=8.0;
a(9,40)=7.8;a(9,41)=5.6;a(10,41)=10.8;
a(11,45)=13.2;a(11,40)=14.2;a(11,42)=6.8;
a(12,42)=7.8;a(12,41)=12.2;a(12,43)=10.2;
a(13,44)=16.4;a(13,45)=9.8;a(13,42)=8.6;a(13,14)=8.6;
a(14,15)=15;a(14,43)=9.9;a(15,44)=8.8;
a(16,17)=6.8;a(16,44)=11.8;a(17,22)=6.7;a(17,46)=9.8;
a(18,46)=9.2;a(18,45)=8.2;a(18,44)=8.2;
a(19,20)=93;a(19,47)=7.2;a(19,45)=8.1;
a(20,21)=7.9;a(20,25)=6.5;a(20,47)=5.5;
a(21,23)=9.1;a(21,25)=6.5;a(21,46)=4.1;
a(22,23)=10.0;a(22,46)=10.1;a(23,24)=8.9;a(23,49)=7.9;
a(24,27)=18.8;a(24,49)=13.2;a(25,49)=8.8;a(25,48)=12.0;
a(26,27)=7.8;a(26,51)=10.5;a(26,49)=10.5;a(27,28)=7.9;
a(28,52)=8.3;a(28,51)=12.1;
a(29,52)=7.2;a(29,53)=7.9;a(29,51)=15.2;
a(30,32)=10.3;a(30,52)=7.7;
a(31,32)=8.1;a(31,33)=7.3; a(31,53)=9.2;
a(32,33)=19;a(32,35)=14.9;a(33,36)=7.4;
a(34,35)=8.2;a(34,36)=11.5;a(34,13)=17.6;
a(37,38)=12.2;a(36,53)=8.8;a(37,38)=11.0;a(44,45)=15.8;a(48,49)=14.2;
a=a+a';
a(find(a==0))=inf;
result=[];
p=1;
tb=2:length(a);
while length(result)~=length(a)-1
temp=a(p,tb);temp=temp(:);
d=min(temp);
[jb,kb]=find(a(p,tb)==d);
j=p(jb(1));k=tb(kb(1));
result=[result,[j;k;d]];
p=[p,k];
tb(find(tb==k))=[];
end
result
程序二
题二.县城到O到各点的距离程序及结果
model:
sets:
cities/A35,A34,A33,A32,A31,A30,A29,A28,A27,A26,A25,A24,A23,A22,A21,A20,A19,A18,A1 7,A16,A15,A14,A13,A12,A11,A10,A9,A8,A7,A6,A5,A4,A3,A2,A1,R,Q,P,N,M,L,K,J,I,H,G,F,E, D,C,B,A,O/:fl;
roads(cities,cities)/A35,A34 A35,A33 A35,A32 A34,B A34,A A32,A33 A31,A33 A33,A A32,A31 A30,A32 A31,R A30,Q A29,R Q,A29 A29,P A27,A28 Q,A28 A28,P A27,A26 A24,A27 A26,P N,A26 A21,A25 A20,A25 N,A25 A25,M A24,A23 A24,N A22,A23 A23,A21 A23,N A17,A22 A22,K A21,A20 K,A21 A19,A20 A20,L A19,L J,A19 A18,K A18,J I,A18 A16,A17
A17,K A16,I A15,A14 A15,I A14,A13 H,A14 A13,J A13,I A13,G H,A12 A12,G A12,F J,A11 G,A11 A11,E A10,F F,A9 A9,E A8,A4 A8,E A7,A6 L,A7 E,A7 A7,D A6,A5 M,A6 L,A6 A5,A2 M,A5 D,A5 A4,D A3,A2 D,A3 A3,C A2,O C,A1 B,A1 A,A1 A1,O A,R R,O P,O N,M M,O I,J C,B C,O/:w,p;
endsets
data:
w=8.2 20.3 14.9 17.6 11.5 19 7.3 7.4 8.1 10.3 9.2 7.7 7.9 7.2 15.2 7.9 8.3 12.1 7.8 18.8 10.5 10.5 7.8 6.5 8.8 12 8.9 13.2 10 9.1 7.9 6.7 10.1 7.9 4.1 9.3 5.5 7.2 8.1 9.2 8.2 8.2 6.8 9.8 11.8 15 8.8 8.6 9.9 9.8 16.4 8.6 10.2 7.8 12.2 13.2 6.8 14.2 10.8 5.6 7.8 20.4 8 7.3 14.5 7.2 15.1 9.7 9.5 11.8 8.3 11.4 11.3 12.7 4.8 8.2 7.9 9.2 11.2 5.9 10.3 6 8.8 12.9 10.1 14.2 19.8 15.8 11 11.5; enddata
n=@size(cities); fl(n)=0;
@for(cities(i)|i#lt#n:fl(i)=@min(roads(i,j):w(i,j)+fl(j)));
@for(roads(i,j):p(i,j)=@if(fl(i)#eq#w(i,j)+fl(j),1,0));
end
Feasible solution found.
Total solver iterations: 0
V ariable Value
N 53.00000
FL( A35) 36.00000
FL( A34) 27.80000
FL( A33) 23.70000
FL( A32) 30.20000
FL( A31) 22.10000
FL( A30) 35.70000
FL( A29) 20.80000
FL( A28) 22.20000
FL( A27) 28.40000
FL( A26) 20.60000
FL( A25) 31.80000
FL( A24) 44.30000
FL( A23) 39.00000
FL( A22) 49.00000
FL( A21) 39.60000
FL( A20) 38.30000
FL( A19) 46.20000
FL( A18) 52.90000
FL( A17) 53.50000
FL( A16) 60.30000
FL( A15) 69.90000
FL( A14) 72.70000
FL( A13) 64.10000
FL( A12) 67.30000
FL( A11) 55.90000
FL( A10) 65.90000
FL( A9) 49.50000
FL( A8) 49.70000
FL( A7) 34.50000
FL( A6) 27.20000
FL( A5) 17.50000
FL( A4) 34.90000
FL( A3) 14.00000
FL( A2) 9.200000
FL( A1) 6.000000
FL( R) 12.90000
FL( Q) 28.00000
FL( P) 10.10000
FL( N) 31.10000
FL( M) 19.80000
FL( L) 39.00000
FL( K) 43.70000
FL( J) 54.30000
FL( I) 61.10000
FL( H) 77.50000
FL( G) 62.70000
FL( F) 55.10000
FL( E) 41.70000
FL( D) 22.20000
FL( C) 11.50000
FL( B) 11.90000
FL( A) 16.30000
FL( O) 0.000000 程序三
问题四编程（以第一问第一组为例）
t1=1;
s=200.4;
m=7;
n=10;
b=2;
v=15:0.5:100;
T=s./v+(a*m+n)*t1;
plot(v,t);
xlabel('V');
ylabel('T');
v=35;
s=200.4;m=7;
n=10;
b=2;
t1=0:0.2:2;
T=s./v+(a*m+n)*t1; plot(t1,T);
xlabel('t1');
ylabel('Tˊ')
数学建模优秀论文灾情巡视路线的数学模型
精心整理 灾情巡视路线的数学模型 摘要 本文解决的是灾情巡视路线的设计问题。由于路线图可看成网络图因此此问题可转化为在给定的加权网络图中寻找从给定点Ｏ出发行遍所有顶点至少一次再回到点Ｏ使得总权（路程或时间）最小的问题。然后针对具体问题，采用一些启发式算法，建立模型进行求解。 对于问题一：基于设计分三组巡视时使总路程最短且各组尽可能均衡的巡视路线的要求我们采用Dijkstra算法，通过对初始圈进行二边逐次修正,处理三组的巡视路线长度，用lingo软件求解出较优方案。定义分组的均衡度系数a检验分组均衡度，在均衡度为a=0.0751时得到分三组（路）巡视时，总路程最短且各组尽可能均衡的巡视路线见附表1。
1.问题重述 1.1问题背景 今年夏天某县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。附录一中给出了该县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。 1.2本文需解决的问题 问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你 认为最佳的巡视路线。 2.1 2.2
路线。 因此问题就转化为一个图论问题，即在给定的加权网络图中，寻找从给定点Ｏ出发，行遍所有顶点至少一次再回到Ｏ点，使得总权（路程或时间）最小。此即多个推销员的最佳推销员回路问题。基于以上分析，运用图论知识和图论软件包进行求解，再利用均衡度分析对得到的分组路线进行微调，均衡度越小表示路线越均衡，微调后即可得到相对较优的分组路线。可认为这样设计的分组方法和巡回路线能使总路线近似最短。 针对问题二：在问题一的基础上添加了巡视组在各乡镇停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时等条件，要求在24小时内完成巡视的最少分组数以及相应的最佳巡视路线。首先，由图中数据初步计算后判断分成四组可行，再针对分组为四组的情况进行线路设计，仍将问题转化为图论问题，运用问题一的求解方法，得到分为四组的路线，在通过均衡度分析之后得出近似最优巡视路线。 针对问题三：在问题二中关于T,t和V的假定下且巡视人员足够多时，要求在最短时间完成巡
灾情巡视路线地数学模型
最优灾情巡视路线 摘要 关键字 1问题重述 下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 问题三：在上述关于T , t和v的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和v改变对最佳巡视路线的影响。 2问题假设与符号说明 2.1问题假设 假设一：假设在巡视过程中不考虑天气、故障等因素的影响 假设二：假设路线上的公路没有被洪水冲断，可以供巡视工作使用。假设三：假设在巡视工程中，经过邻县村时，不做任何时间的耽搁。 2.2符号说明
3问题分析 本题给出了某县的道路交通网络图，要求的是在不同条件下，灾情巡视的最佳分组方案和路线。这是一类图上的点的遍历性问题，也就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。点的遍历性问题在图论中属于哈密顿问题和旅行推销员问题类似。如果巡视人员只分一组，巡视路线是指巡视人员从县政府O 出发，走遍各乡（镇）、村最后又回到县政府。我们可以把该题抽象为图论的赋权连通问题，即有一赋权无向连通图(,)G V E ，且O V ∈。两村之间的公路长度即为无向图的边权()w e 。寻找最佳巡视路线，即在图(,)G V E 中找到一条包含O 点的回路，它至少经过所有的顶点一次且使得总路程（总时间） 最短。 针对问题一：如果将巡视人员分成三组，每组考察全县的一个区域，使所有乡（镇）、村都考察到，实际上就是将图(,)G V E 分为三个连通的子图i G ，且每个子图都与O 点相连，然后在每个子图中寻找到一条含O 点的最佳回路。针 对三组巡视成员，需对该县分为三个区域。我们采用Prim 算法通过++C 编程求 出G 图的最小树形图，然后将树形图分成三个区域，最后，采用哈密顿回路法求解每个子图内的最佳巡视路线。 针对问题二： 完成巡视的时间应是各组巡视中最长的时间，要想提高巡视的效率则应尽量使各组的巡视时间接近，反映在G 图分块时应尽量均衡。 4数据的分析与处理 5问题一的解答 5.1模型一的准备 现要分三组巡视，则需要把图G 分成三个子图(1,2,3)i G i =，在每个子图i G 中寻 找最佳回路(1,2,3)i L i =。因为最小生成树中能包含图G 中所有的顶点E ，而且最小
《系统工程案例分析》课程实践作业题
《系统工程案例分析》课程实践作业题 1、大学图书馆使用效率调查研究 图书馆是高校的信息中心，为读者用户提供设施资源、文献资源及信息检索资源等服务，其使用效率的高低直接反映了学员的自我学习能力。为分析图书馆的使用效率，需对图书馆设施、文献及信息检索资源现状等进行调查。 要求利用系统工程的相关理论和方法，设计一种方便可行且准确度较高的方法，对本校图书馆使用效率进行调查研究，并调查结果进行分析。
2、医院眼科病床的合理安排的问题 医院就医排队是大家都非常熟悉的现象，例如，患者到门诊就诊、到收费处划价、到药房取药、到注射室打针、等待住院等，往往都需要排队等待接受某种服务。 考虑某医院眼科病床的合理安排的问题。 该医院眼科门诊每天开放，住院部共有病床79张。该医院眼科手术主要分四大类：白内障、视网膜疾病、青光眼和外伤。白内障手术较简单，而且没有急症。目前该院是每周一、三做白内障手术，此类病人的术前准备时间只需1、2天。做两只眼的病人比做一只眼的要多一些，大约占到60%。如果要做双眼是周一先做一只，周三再做另一只。 外伤疾病通常属于急症，病床有空时立即安排住院，住院后第二天便会安排手术。其他眼科疾病比较复杂，有各种不同情况，但大致住院以后2-3天内就可以接受手术，主要是术后的观察时间较长。这类疾病手术时间可根据需要安排，一般不安排在周一、周三，并不考虑在急症范围内。 该医院考虑病床安排时可不考虑手术条件的限制，但在通常情况下白内障手术与其他眼科手术（急症除外）不安排在同一天做。当前该住院部对全体非急症病人是按照FCFS（First come, First serve）规则安排住院，但等待住院病人队列却越来越长，通过数学建模的方法来合理安排住院部的病床，完成下列问题，以提高对医院资源的有效利用。 问题一：试分析确定合理的评价指标体系，用以评价该问题的病床安排模型的优劣。 问题二：试就该住院部当前的情况，建立合理的病床安排模型，以根据已知的第二天拟出院病人数来确定第二天应该安排哪些病人住院。并对你们的模型利用问题一中的指标体系作出评价。 问题三：作为病人，自然希望尽早知道自己大约何时能住院。能否根据当时住院病人及等待住院病人的统计情况，在病人门诊时即告知其大致入住时间区间。 问题四：若该住院部周六、周日不安排手术，请你们重新回答问题二，医院的手术时间安排是否应作出相应调整? 问题五：有人从便于管理的角度提出建议，在一般情形下，医院病床安排可采取使各类病人占用病床的比例大致固定的方案，试就此方案，建立使得所有病人在系统内的平均逗留时间（含等待入院及住院时间）最短的病床比例分配模型。
灾情巡视路线最优化的方案(刘)
约束最优路线的模拟退火解法 说明：以98年全国大学生数模竞赛中的B 题（即“灾情巡视路线”）为例，介绍能解一类较广泛的约束最优路线问题的方法??模拟退火法[1] 。该法对“灾情巡视路线”这类有约束以及“（一般）旅行推销员”、“中国邮递员”等无约束组合优化问题均能求得较好的近似解，具有适用范围广和可拓展的优点。 一、问题描述 对于最短路、最大流、中国邮递员、旅行推销员等最优路线问题，常采用各自不同的方法求解。若在这些问题中再加入一些约束条件，则原方法往往不再有效，如98年大学生数模竞赛中的B 题就是如此。我们设计的方法较好地解决了这一问题。现以98年B 题为例，介绍该法及其实现。下面为该题文字部分，并称其四问分别为问题1至问题4： 下图（略）为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。 今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 １．若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 ２．假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里／小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 ３．在上述关于T ，t 和V 的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 ４．若巡视组数已定（如三组），要求尽快完成巡视，讨论T ，t 和V 改变对最佳巡视路线的影响。 二、问题分析及模型的建立 因为是分组巡视（不妨设分N 组），要直接确定一个组巡视哪些地点是困难的。由于将各组巡视的路线连接起来可看成一条N 次相继从县城出发又回到县城的路线，这样，多组巡视就化成了单组巡视。经分析，我们认为前3问及第4问计算部分都是组合规划中的约束优化问题，均属以模型 ()()()n j x g m i x h st x f j i ,,2,1,0,,2,1,0.min ?=≥?== （I ） 为基础的约束最优路线模型。下面根据各问的要求，分别对4个问题进行具体讨论。 对于问题1，如果选取总路程最短的所有巡视路线中最均衡的，一般这一路线仍会很不均衡。故除了要总路程短，另需“均衡”提出一定的要求，即组间巡视路线的长度差不大于某给定值L 。还有路线能够分成3次从县城O 出发再回到O 、各组经过地点的并集为所有顶点的集合只之约束。模型如下： () A P L f f N n st f f F n i i =≤-=-+≤≤ 1min max min max .min λ (II) 其中F 为巡视总路程，N 为要求的分组数（本问N=3），n 是优化过程中路线的实际分组数，f max 和f min 分别为n 组中最长和最短组的巡视路程，P i 为第i 组巡视地点的集合，A 是所有顶点的集合。约束条件(f max -f min )≤L 用来保证各组路程基本均衡，
建模案例：最佳灾情巡视路线
建模案例：最佳灾情巡视路线 1998年全国大学生数学模型竞赛B题中的两个问题. 一、问题 今年夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线. 1．若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线. 2．假定巡视人员在各乡（镇）停留时间T=2h，在各村停留时间t=1h，汽车行驶速度V=35km/h.要在24h内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线. 乡镇、村的公路网示意图见图1. 图1 二、假设 1．汽车在路上的速度总是一定，不会出现抛锚等现象； 2．巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；3．每个小组的汽车行驶速度完全一样； 4．分组后，各小组只能走自己区内的路，不能走其他小组的路（除公共路外）. 三、模型的建立与求解 将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边
上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点O 出发，行遍所有顶点至少一次再回到O 点，使得总权（路程或时间）最小，此即最佳推销员回路问题. 在加权图G 中求最佳推销员回路问题是NP —完全问题，我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下： 算法一 求加权图G （V ，E ）的最佳推销员回路的近似算法： 1． 用图论软件包求出G 中任意两个顶点间的最短路，构造出完备图 ),(E V G ''，()E y x '∈?,， ()(),,G x y mind x y ω=； 2． 输入图G '的一个初始H 圈； 3． 用对角线完全算法产生一个初始H 圈； 4． 随机搜索出G '中若干个H 圈，例如2000个； 5． 对第2、3、4步所得的每个H 圈，用二边逐次修正法进行优化，得到近似最佳H 圈； 6． 在第5步求出的所有H 圈中，找出权最小的一个，此即要找的最佳H 圈的近似解. 由于二边逐次修正法的结果与初始圈有关，故本算法第2、3、4步分别用三种方法产生初始圈，以保证能得到较优的计算结果. 问题一 若分为3组巡视，设计总路程最短且各组尽可能均衡的巡视路线. 此问题是多个推销员的最佳推销员回路问题.即在加权图G 中求顶点集V 的划分12,,,n V V V L ，将G 分成n 个生成子图[][][]12,,...,n G V G V G V ，使得 （1）顶点i V O ∈, i =1，2，3,…,n ； （2）()G V V n i i ==Y 1 ； （3）()(),max max i j i j i i C C C ωωαω-≤，其中i C 为i V 的导出子图[]i V G 中的最佳推销员回路，()i C ω为i C 的权，i ，j =1，2，3,…,n ； （4）()1n i i C ω=∑取最小. 定义 称()()() ,0max max i j i j i i C C C ωωαω-=为该分组的实际均衡度.α为最大容 许均衡度. 显然100≤≤α，0α越小，说明分组的均衡性越好.取定一个α后，0α与α满足条件（3）的分组是一个均衡分组.条件（4）表示总巡视路线最短. 此问题包含两方面：第一，对顶点分组；第二，在每组中求最佳推销员回路，即为单个推销员的最佳推销员问题. 由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故多个推销员的问题也不存在多项式时间内的精确算法.而图中节点数较多，为53个，我们只能去寻求一种较合理的划分准则，对图１进行粗步划分后，求出各部
灾情巡视路线模型
灾情巡视路线模型 摘要 本文研究的是考察灾情最佳巡视线路设计的问题，属于多旅行商问题，为此我们建立了网络图模型。利用最小生成树图形和最短路树图形相结合，通过分析、计算比较得出最优解。 对于问题一，我们建立赋权网络图。利用matlab编程得到此网络图的最小生成树图和最短路径树图，以两图相重合的部分作为分区的界限，将整个网络图分为三个分区。以总路程最短和均衡度最小作为目标函数建立多目标规划模型，利用哈密顿算法编写matlab程序求得各组最优巡回路线(见附表1)。 对于问题二，基于对问题一结果的分析，发现分三组的情况下，不能满足题目要求。因此我们首先考虑分四组的情况。在分三组的基础上根据分组原则将图大致划分为4各子图。同样以巡视路程最短和时间均衡度最小为目标函数，各巡视时间小于24小时作为约束条件建立多目标规划模型。利用哈密顿算法编程求得各组最佳巡视路线及巡视时间（见附表2）。 对于问题三，在巡视人员足够多的情况下，巡视距离O点最远的点所用的时间为最短时间，根据最短路径树，从远到近，依次巡视各村镇，在所用时间不大于最短时间的前提下，各组尽可能多的巡视几个村镇，进行分组确立巡视点，并对已巡视过的点进行逐个剔除。通过人工记录，得出分组情况及巡视路线（见附表3），最短时间为6.4286小时。 对于问题四，在组数固定时，则各组的最短路径就已确定，T、t、V改变影响的只是整个巡视时间。我们利用matlab编程画图得到T、t、V与巡视时间的关系曲线。观察曲线发现：①当速度V较小时，V的变化对巡视时间的影响较大；②停留时间t与巡视时间呈线性关系，无论t取何值，对巡视时间影响都较大。此两种情况下都需适当调整分组。 关键词最小生成树最短路径树赋权网络图哈密顿算法
数学建模经典案例：最佳灾情巡视路线
建模案例：最佳灾情巡视路线 这里介绍1998年全国大学生数学模型竞赛B题中的两个问题. 一、问题 今年夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线. 1．若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线. 2．假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时.要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线. 乡镇、村的公路网示意图见图11-9. 图11-9 二、假设 1．汽车在路上的速度总是一定，不会出现抛锚等现象； 2．巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；3．每个小组的汽车行驶速度完全一样； 4．分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外. 三、模型的建立与求解
将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点O 出发，行遍所有顶点至少一次再回到O 点，使得总权（路程或时间）最小，此即最佳推销员回路问题. 在加权图G 中求最佳推销员回路问题是NP —完全问题，我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下： 算法一 求加权图G （V ，E ）的最佳推销员回路的近似算法： 1． 用图论软件包求出G 中任意两个顶点间的最短路，构造出完备图 ),(E V G ''，()E y x '∈?,， ()()y x Mind y x G ,,=ω； 2． 输入图G '的一个初始H 圈； 3． 用对角线完全算法（见[23]）产生一个初始H 圈； 4． 随机搜索出G '中若干个H 圈，例如2000个； 5． 对第2、3、4步所得的每个H 圈，用二边逐次修正法进行优化，得到近似最佳H 圈； 6． 在第5步求出的所有H 圈中，找出权最小的一个，此即要找的最佳H 圈的近似解. 由于二边逐次修正法的结果与初始圈有关，故本算法第2、3、4步分别用三种方法产生初始圈，以保证能得到较优的计算结果. 问题一 若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线. 此问题是多个推销员的最佳推销员回路问题.即在加权图G 中求顶点集V 的划分n V V V ,.......,21，将G 分成n 个生成子图[][][]n V G V G V G ,......,21，使得 （1）顶点i V O ∈ i=1，2，3……n （2）()G V V n i i == 1 （3）()() ()αωωω≤-i i j i j i C Max C C Max ,，其中i C 为i V 的导出子图[]i V G 中的最佳推销员 回路，()i C ω为i C 的权，i ，j=1，2，3……n （4）()Min C n i i =∑=1ω 定义 称()()()i i j i j i C M a x C C M a x ωωωα-=,0为该分组的实际均衡度.α为最大容许均 衡度. 显然100≤≤α，0α越小，说明分组的均衡性越好.取定一个α后，0α与α满足条件（3）的分组是一个均衡分组.条件（4）表示总巡视路线最短. 此问题包含两方面：第一、对顶点分组；第二、在每组中求最佳推销员回路，即为单个推销员的最佳推销员问题. 由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故多个推销员的问题也不存在多项式时间内的精确算法.而图中节点数较多，为53个，我们只能去寻求一种较合理的划分准则，对图１1－9进行粗步划分后，求
最佳灾情巡视路线模型
最佳灾情巡视路线模型 【摘要】“图论”是组合数学的分支，它与其他的数学分支，如群论、矩阵论、拓扑学，数值分析有着密切的联系。在其它科学领域，如计算机科学、运筹学、电网络分析、化学物理以及社会科学等方面图论也具有越来越重要的地位，并已取得丰硕的成果。而且，图论的理论和方法在数学建模中也有重要应用。本文概述了一些常用的图论方法和算法，并通过举例（灾情巡视路线）说明其在数学建模中的应用。 【关键词】图论灾情巡视Hamilton回路数学模型 预备知识 定义1 完全图：如果图G中每一对不同的顶点恰有一条边连接，则称此图为完全图。定义2 连通图：如果对图G=（V，E）的任何两个顶点u与v，G中存在一条（u-v）路。则称G是连通图。 定义3 加权图：边上有数的图称为加权图。在加权图中，链（迹、路）的长度为链（迹、路）上的所有边的权植的和。 定义4 Hamilton回路：图G中的一个回路C称为一个Hamilton回路如果C含有G 的所有顶点。含有Hamilton回路的图称为Hamilton图。 定义5 欧拉回路：经过图G的每条边的迹称为欧拉迹，如果这条迹是闭的，则称这条闭迹为G的欧拉回路。 一数学建模中常用的图论方法 1 迪克斯特拉算法（Dijkstra） 1.1问题来源 在加权图中，我们经常需要找出两个指定点之间的最短路，通常称为最短路问题。解决最短路问题的方法之一就是迪克斯特拉算法。 1.2基本思路 假定P：V 1→V 2 →…V i →…→V j →…→V k 是从V 1 到V k 的最短路，则它的子 路V i →…→V j 一定是从V i 到V j 的最短路。否则从V 1 出发沿路p走到V i ，,然后 沿V i 到V j 的最短路走到V j 再沿路P从V j 到V k ，这样得到一条新的从V 1 出发到 V k 的路，其长度小于P，与P是最短路的假设矛盾。
数学建模优秀赛题-图论的相关赛题
数学建模图论问题 B题灾情巡视路线 下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。 今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 1.若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2.假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行 驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 3.在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少； 给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 4.若巡视组数已定(如三组)，要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线 的影响。 B题：乘公交，看奥运 我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同时考虑公汽与地铁线路，解决以上问题。 3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。 【附录1】基本参数设定 相邻公汽站平均行驶时间(包括停站时间)：3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)
灾情巡视路线的数学模型
最优 摘要 关键字 1问题重述 下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 问题三：在上述关于T , t 和v 的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T ，t 和v 改变对最佳巡视路线的影响。 2问题假设与符号说明 2.1问题假设 假设一：假设在巡视过程中不考虑天气、故障等因素的影响 假设二：假设路线上的公路没有被洪水冲断，可以供巡视工作使用。 假设三：假设在巡视工程中，经过邻县村时，不做任何时间的耽搁。 2.2符号说明 G （V,E ） 赋权连通图； i G 赋权连通图的第i 个子图(1,2,)i = ，k i L 子图i G 中的最佳回路； i C 最佳回路i L 的各边权之和 ij W 第i 个乡、村到第 j 个乡、村的距离(j 1,2,53)i = ，， ij X 某组从城市i 到城市j 时为1，无巡视组视为0 3问题分析
本题给出了某县的道路交通网络图，要求的是在不同条件下，灾情巡视的最佳分组方案和路线。这是一类图上的点的遍历性问题，也就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。点的遍历性问题在图论中属于哈密顿问题和旅行推销员问题类似。如果巡视人员只分一组，巡视路线是指巡视人员从县政府O 出发，走遍各乡（镇）、村最后又回到县政府。我们可以把该题抽象为图论的赋权连通问题，即有一赋权无向连通图(,)G V E ，且O V ∈。两村之间的公路长度即为无向图的边权()w e 。寻找最佳巡视路线，即在图(,)G V E 中找到一条包含O 点的回路，它至少经过所有的顶点一次且使得总路程（总时间）最短。 针对问题一：如果将巡视人员分成三组，每组考察全县的一个区域，使所有乡（镇）、村都考察到，实际上就是将图(,)G V E 分为三个连通的子图i G ，且每个子图都与O 点相连，然后在每个子图中寻找到一条含O 点的最佳回路。针对三组巡视成员，需对该县分为三个区域。我们采用Prim 算法通过++C 编程求 出G 图的最小树形图，然后将树形图分成三个区域，最后，采用哈密顿回路法求解每个子图内的最佳巡视路线。 针对问题二： 完成巡视的时间应是各组巡视中最长的时间，要想提高巡视的效率则应尽量使各组的巡视时间接近，反映在G 图分块时应尽量均衡。 4数据的分析与处理 5问题一的解答 5.1模型一的准备 现要分三组巡视，则需要把图G 分成三个子图(1,2,3)i G i =，在每个子图i G 中寻 找最佳回路(1,2,3)i L i =。因为最小生成树中能包含图G 中所有的顶点E ，而且最小 树的边权是相邻两顶点间的距离，它描述了顶点之间的相近程度，故可以采用最小生成树进行分组。 本模型的主要思想是：首先采用Prim 算法得到G 图的最小生成树，然后基于最小生成树生成一个可行的巡视路线，求得路线的最优总路程为。 采用Prim 算法求解最小生成树步骤如下： （1）输入加权连通图G 的带权邻接矩阵((,))n n A a i j ?=； （2）建立初始候选边表, B T ←?； （3）在候选边表中选出最短边(,),(,)u v T T u v ←?； （4）调整候选边表B ；
1998年全国大学生数学建模竞赛题
B题灾情巡视路线 下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。 今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 (1) 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 (2) 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 (3) 在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。(4) 若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。 灾情巡视路线模型 摘要 本文将求最佳巡视路线间题转化为图论中求最佳推销员回路（哈米尔顿回路）的问题,并用近似算法去寻求近似最优解。对赋权图中的路径分组问题定义了均衡度用以衡量分组的均衡性。对问题1和问题2先定出几个分的准则进行初步分组,并用近似算法求每一组的近似最佳推销员回路,再根据均衡度进行微调,得到较优的均衡分组和每组的近似最佳推销员回路。对问题1，运用求任意两点间最短路的Floyd算法,得出总路程较短且各组尽可能均衡的路线,各组的巡视路程分别为公里,公里,公里,总路程公里。对问题2,证明了应至少分为4组,并求出了分为4组时各组的较优巡视路线,各组的巡视时间分别为小时,小时,小时,小时。对问题3,求出完成巡视的最短时间为小时,并用较为合理的分组的准则,
灾情巡视路线程序word版本
灾情巡视路线程序
9附录附录一：Kruskal最小树成法程序 clear all %图论最小生成树Kruskal避圈算法 %w为邻接矩阵 w=[ 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10.3 5.9 11.2 inf inf inf inf inf inf inf inf inf inf inf 6 inf inf inf ; inf 0 4.8 inf 8.3 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8.2 inf inf inf ; inf 4.8 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7.8 8.2 inf inf inf inf inf inf inf inf inf inf inf inf inf inf ; inf inf inf 0 inf inf inf 20.4 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 12.7 inf inf inf inf inf inf inf inf inf inf inf inf inf inf ; inf 8.3 inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 11.3 inf inf inf inf inf inf inf inf 11.4 inf inf inf inf inf ; inf inf inf inf 9.7 0 7.3 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 11.8 9.5 inf inf inf inf inf ;inf inf inf inf inf 7.3 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 15.1 7.2 inf inf inf inf inf inf 14.5 inf inf inf inf inf inf ; inf inf inf 20.4 inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8 inf inf inf inf inf inf inf inf inf inf inf inf inf ; inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7.8 5.6 inf inf inf inf inf inf inf inf inf inf inf inf ; inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10.8 inf inf inf inf inf inf inf inf inf inf inf inf ; inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 14.2 inf 6.8 inf inf 13.2 inf inf inf inf inf inf inf inf ; inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 12.2 7.8 10.2 inf inf inf inf inf inf inf inf inf inf ;
灾情最优路线设计 1998年数模A题
重大灾情最优巡查路线设计
承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：广东商学院 参赛队员(打印并签名) ：1. 邓思文 2. 苏境财 3. 吴妙 指导教师或指导教师组负责人(打印并签名)：戴宏亮 日期： 2012 年 8 月11 日赛区评阅编号（由赛区组委会评阅前进行编号）：
2010高教社杯全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：
重大灾情最优巡查路线设计 摘要 灾情巡视对于受灾地的救援工作有着重要意义，快速了解受灾地的情况，有利于加快援救工作，所以研究最佳巡视路线有着重要意义。本文针对最佳路线及相关问题做出如下解答： 针对问题一，基于MTSP数学模型，运用了遗传算法，建立了最佳巡视路线模型，通过matlab编程，求解得出总路程最短且相对均衡的3组巡视路线，各组巡视路线如下： 第一组：O→P→26→27→28→Q→30→Q→29→R→A→33→31→32→35→34→D→1→O 第二组：O→M→25→20→L→19→J→18→I→15→I→16→17→22→K→21→23→24→N→26→P→O 第三组：O→C→3→D→4→8→E→9→F→10→F→12→H→14→13→G→11→E →7→6→5→2→O 针对问题二，通过估计方法估量组数范围，再利用问题一中所使用模型，对输入矩阵进行加权修改，构成定向时间矩阵，并通过matlab计算出结果，最后针对计算结果中的误差，验证估计结果是否正确，结果显示4组为最少组数。 针对问题三，首先计算出最远结点的最近距离，得到最小时间为6.44小时，再利用“就远原则”，得到最少组数为24组。 关键词：MTSP数学模型遗传算法定向时间矩阵就远原则
数学建模论文之灾情巡视路线
最佳灾情巡视路线问题的研究 摘要 本文分析的是最佳的巡视路线问题，我们用Kruskral 算法对原路线图进行处理，求得其最小生成树，并以巡视总路程、各组巡视时间和路程（时间）均衡度为目标函数建立模型，通过图论软件包、Matlab 软件求解，并对结果进行均衡度检验，设计出了最佳巡视路线，而且对影响最佳巡视路线的因素进行了定量分析。 针对问题一：问题一我们运用了用Kruskral 算法对原路线图进行处理，求得其最小生成树，提出了分块准则，我们根据分块准则，建立了以巡视总路程和路程均衡度为目标函数的多目标标模型，并通过分析比较和路程均衡度检验，最终得出了最佳巡视路线，此时巡视总路程公里5.622=S ，路程均衡度为%3.6=s α具体巡视路线见表三。 针对问题二：我们通过分析可知在此种情况下至少需分四组巡视，并在题一得出的最小生成树的基础上，提出分块准则，建立了以个组巡视总时间和时间均衡度为目标函数的多目标模型，并通过分析比较和时间均衡度检验，得出了最佳巡视路线，此时25.2124.22,27.22,05.224321====T T T T 小时，小时小时小 时，时间均衡度%7.6=t α，具体巡视路线见图二。 针对问题三：我们通过图论软件包求出了所有的点到点O 的最短距离，以及离O 最远的点为H 点，我们以巡视H 点的最短时间为各组各组巡视时间的上限，运用图论软件包和自己分析判断，最终制订了最佳巡视路线，此分组组数为23组，具体数据和巡视路线见表五。 针对问题四：我们假设该问题是已经定分为三组的情形，且在乡镇停留时间为在村停留时间整数倍情况下讨论V t T 和，的改变对最佳巡视路线的影响。由问题一的求解结果可知，第三组巡视路线较第一组、第二组巡视路线长，所以我们只讨论在V t T 和，改变时对第三组巡视路线的影响进行分析以说明问题。最终得出结论：停留时间的改变对最佳巡视路线影响较大；汽车时速的改变对最佳巡视路线的确定影响较小。 关键词：Kruskral 算法 图论软件包 最小生成树 1.问题重述
1998年全国大学生数学建模竞赛题
1998年全国大学生数学建模竞赛题目 B题灾情巡视路线 下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。 今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 (1) 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 (2) 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 (3) 在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。(4) 若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。 灾情巡视路线模型 摘要 本文将求最佳巡视路线间题转化为图论中求最佳推销员回路（哈米尔顿回路）的问题,并用近似算法去寻求近似最优解。对赋权图中的路径分组问题定义了均衡度用以衡量分组的均衡性。对问题1和问题2先定出几个分的准则进行初步分组,并用近似算法求每一组的近似最佳推销员回路,再根据均衡度进行微调,得到较优的均衡分组和每组的近似最佳推销员回路。对问题1，运用求任意两点间最短路的Floyd算法,得出总路程较短且各组尽可能均衡的路线,各组的巡视路程分别为216.4公里,191.1公里,192.3公里,总路程599.8公里。对问题2,证明了应至少分为4组,并求出了分为4组时各组的较优巡视路线,各组的巡视时间分别为22.74小时,22.59小时,21.69小时,22.54小时。对问题3,求出完成巡视的最短时间为6.43小时,并用较为合理的分组的准则,分成22个组对问题4，研究了在不影响分组的均衡条件下, T,t,V的允许变化范围,并得出了这三个变量的关系式,并由此对分三个组的情况进行了具体讨论。 关键词：最佳推销员回路问题哈米尔顿回路赋权图近似算法均衡度