最佳灾情巡视路线

建模案例：最佳灾情巡视路线

这里介绍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进行粗步划分后，求

出各部分的近似最佳推销员回路的权，再进一步进行调整，使得各部分满足均衡性条件（3）.

图11-10 O点到任意点的最短路图（单位：公里）

从O点出发去其它点，要使路程较小应尽量走O点到该点的最短路.故用图论软件包求出O点到其余顶点的最短路，这些最短路构成一棵O为树根的树，将从O点出发的树枝称为干枝，见图１１－１0，从图中可以看出，从O点出发到其它点共有6条干枝，它们的名称分别为①，②，③，④，⑤，⑥.

根据实际工作的经验及上述分析，在分组时应遵从以下准则：

准则一：尽量使同一干枝上及其分枝上的点分在同一组；

准则二：应将相邻的干枝上的点分在同一组；

准则三：尽量将长的干枝与短的干枝分在同一组.

由上述分组准则，我们找到两种分组形式如下：

分组一：（⑥，①），（②，③），（⑤，④）

分组二：（①，②），（③，④），（⑤，⑥）

显然分组一的方法极不均衡，故考虑分组二.

对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视路线.使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图11-10中树上的边的H圈作为其第2步输入的初始圈.

分组二的近似解见表1.

因为该分组的均衡度0α=()()()=-=-=9

.2415.1259.2413,2,121i i C Max C C ωωω54.2%

所以此分法的均衡性很差.

为改善均衡性，将第Ⅱ组中的顶点C ，2，3，D ，4分给第Ⅲ组（顶点2为这两组的公共点），重新分组后的近似最优解见表2.

因该分组的均衡度=0α()===4.2163

,2,113i i C Max ω11.69% 所以这种分法的均衡性较好.

问题二 当巡视人员在各乡（镇）、村的停留时间一定，汽车的行驶速度一定，要在24小时内完成巡视，至少要分几组及最佳的巡视路线.

由于T=2小时，t=1小时，V=35公里/小时，需访问的乡镇共有17个，村共有35个.计算出在乡（镇）及村的总停留时间为17?2+35=69小时，要在24小

时内完成巡回，若不考虑行走时间，有: 2469

(i 为分的组数).得i 最小为4，故至少要分4组.

由于该网络的乡（镇）、村分布较为均匀，故有可能找出停留时间尽量均衡

的分组，当分4组时各组停留时间大约为25.174

69=小时，则每组分配在路途上的时间大约为24-17.25=6.75小时.而前面讨论过，分三组时有个总路程599.8公里的巡视路线，分4组时的总路程不会比599.8公里大太多，不妨以599.8公里

来计算.路上时间约为17358.599=小时，若平均分配给4个组，每个组约需4

17=4.25小时〈6.75小时，故分成4组是可能办到的.

现在尝试将顶点分为4组.分组的原则：除遵从前面准则一、二、三外，还应遵从以下准则：

准则四：尽量使各组的停留时间相等.

用上述原则在图11-10上将图分为4组，同时计算各组的停留时间,然后用算法一算出各组的近似最佳推销员巡回，得出路线长度及行走时间，从而得出完成巡视的近似最佳时间.用算法一计算时，初始圈的输入与分三组时同样处理.

这4组的近似最优解见表3.

加框的表示此点只经过不停留.

该分组实际均衡度0α==-74

.2269.2174.22 4.62% 可以看出，表3分组的均衡度很好，且完全满足24小时完成巡视的要求.

数学建模优秀论文灾情巡视路线的数学模型

精心整理 灾情巡视路线的数学模型 摘要 本文解决的是灾情巡视路线的设计问题。由于路线图可看成网络图因此此问题可转化为在给定的加权网络图中寻找从给定点Ｏ出发行遍所有顶点至少一次再回到点Ｏ使得总权（路程或时间）最小的问题。然后针对具体问题，采用一些启发式算法，建立模型进行求解。 对于问题一：基于设计分三组巡视时使总路程最短且各组尽可能均衡的巡视路线的要求我们采用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,求出完成巡视的最短时间为小时,并用较为合理的分组的准则,

灾情最优路线设计 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的允许变化范围,并得出了这三个变量的关系式,并由此对分三个组的情况进行了具体讨论。 关键词：最佳推销员回路问题哈米尔顿回路赋权图近似算法均衡度

全国数学建模大赛历年题目分析以及参赛成功方法

全国数学建模大赛历年题目分析以及参赛成功方法 数学建模竞赛的赛题分析 1. CUMCM历年赛题简析 2. “彩票中的数学”问题 3. 长江水质的评估、预测与控制问题 4. 煤矿瓦斯和煤尘的监测与控制问题 5. 其他几个数学建模的问题 数学建模竞赛的规模越来越大,水平越来越高； 竞赛的水平主要体现在赛题水平； 赛题的水平主要体现： （１）综合性、实用性、创新性、即时性等； （２）多种解题方法的创造性、灵活性、开放性等； （３）海量数据的复杂性、数学模型的多样性、求解结果的不唯一性等。 纵览16年的本科组32个题目(专科组13个)，从问题的实际意义、解决问题的方法和题型三个方面作一些简单的分析。 一、CUMCM历年赛题的简析 1. CUMCM 的历年赛题浏览： 1992年:(Ａ)作物生长的施肥效果问题(北理工：叶其孝） (B)化学试验室的实验数据分解问题（复旦：谭永基） 1993年:(Ａ)通讯中非线性交调的频率设计问题（北大:谢衷洁） (Ｂ)足球甲级联赛排名问题（清华：蔡大用）

1994年:(Ａ)山区修建公路的设计造价问题（西电大：何大可） (Ｂ)锁具的制造、销售和装箱问题（复旦:谭永基等）1995年:(Ａ)飞机的安全飞行管理调度问题（复旦:谭永基等） (Ｂ)天车与冶炼炉的作业调度问题（浙大:刘祥官等） 一、CUMCM历年赛题的简析 1. CUMCM 的历年赛题浏览： 1996年:(A)最优捕鱼策略问题（北师大：刘来福） (B)节水洗衣机的程序设计问题（重大：付鹂） 1997年:(A)零件参数优化设计问题（清华：姜启源） (B)金刚石截断切割问题（复旦：谭永基等） 1998年:(A)投资的收益和风险问题（浙大：陈淑平） (B)灾情的巡视路线问题（上海海运学院:丁颂康） 1999年:(A)自动化机床控制管理问题（北大：孙山泽） (B)地质堪探钻井布局问题（郑州大学：林诒勋） (C)煤矸石堆积问题（太原理工大学：贾晓峰） 一、CUMCM历年赛题的简析 1. CUMCM 的历年赛题浏览： 2000年:(A)DNA序列的分类问题（北工大：孟大志） (B)钢管的订购和运输问题（武大：费甫生） (C)飞越北极问题（复旦：谭永基） (D)空洞探测问题（东北电力学院：关信） 2001年:(A)三维血管的重建问题（浙大：汪国昭）