当前位置：文档之家 › 1998年全国大学生数学建模竞赛题

1998年全国大学生数学建模竞赛题

  • 格式：doc
  • 大小：2.28 MB
  • 文档页数：12

下载文档原格式

  / 12

合集下载

数学建模 历年试题及论文

数学建模 历年试题及论文

拟合、规划 图论、层次分析、整数队论、图论 微分方程、优化 非线性规划 非线性规划 随机模拟、图论 多目标优化、非线性规划 图论、组合优化 随机优化、计算机模拟 0-1规划、图论
2000 2000 B题 钢管订购和运输 缺 2000 C题 飞越北极 缺 2000 D题 空洞探测 缺 2001 A题 血管的三维重建 数据 曲线拟合、曲面重建 缺 多目标规划 2001 B题 公交车调度 缺 2001 2001 C题 基金使用计划 缺 2001 D题 公交车调度 缺 2002 A题 车灯线光源的优化设计 非线性规划 Y 2002 B题 彩票中的数学 单目标决策 Y 2002 2002 C题 车灯线光源的计算 Y 2002 D题 赛程安排 Y 2003 A题 SARS的传播 微分方程、差分方程 Y 2003 B题 露天矿生产的车辆安排 整数规划、运输问题 Y 2003 2003 C题 SARS的传播 缺 2003 D题 抢渡长江 Y 2004 A题 奥运会临时超市网点设计 数据 统计分析、数据处理、优化 缺 2004 B题 电力市场的输电阻塞管理 数据拟合、优化 缺 2004 2004 C题 饮酒驾车 缺 2004 D题 公务员招聘 缺 2005 A题 长江水质的评价和预测 数据 聚类、模糊评判、主成分分析、多目标决策 缺 2005 B题 DVD在线租赁 数据 多目标规划 缺 2005 2005 C题 雨量预报方法的评价 数据 缺 2005 D题 DVD在线租赁 数据 缺 2006 A题 出版社的资源配置 数据 线性规划、多目标规划 Y 2006 B题 艾滋病疗法的评价及疗效的预测 回归、线性规划 数据 Y 2006 2006 C题 易拉罐形状和尺寸的最优设计 缺 2006 D题 煤矿瓦斯和煤尘的监测与控制 数据 缺 2007 A题 中国人口增长预测 数据 微分、差分方程 Y 2007 B题 乘公交，看奥运 数据 图论、0-1 规划、动态规划 Y 2007 2007 C题 手机“套餐”优惠几何 数据 Y

国赛历届数学建模赛题题目与解题方法

国赛历届数学建模赛题题目与解题方法

历届数学建模题目浏览：1992--20091992年 (A) 施肥效果分析问题(北京理工大学：叶其孝）(B) 实验数据分解问题（华东理工大学:俞文此; 复旦大学：谭永基）1993年 (A) 非线性交调的频率设计问题（北京大学：谢衷洁）(B) 足球排名次问题（清华大学：蔡大用）1994年 (A) 逢山开路问题（西安电子科技大学：何大可）(B) 锁具装箱问题（复旦大学:谭永基，华东理工大学:俞文此）1995年 (A) 飞行管理问题（复旦大学:谭永基，华东理工大学:俞文此）(B) 天车与冶炼炉的作业调度问题（浙江大学：刘祥官,李吉鸾）1996年 (A) 最优捕鱼策略问题（北京师范大学：刘来福）(B) 节水洗衣机问题（重庆大学：付鹂）1997年 (A) 零件参数设计问题（清华大学：姜启源）(B) 截断切割问题（复旦大学:谭永基，华东理工大学:俞文此）1998年 (A) 投资的收益和风险问题（浙江大学：陈淑平）(B) 灾情巡视路线问题（上海海运学院：丁颂康）1999年 (A) 自动化车床管理问题（北京大学：孙山泽）(B) 钻井布局问题（郑州大学：林诒勋）1999年(C) 煤矸石堆积问题（太原理工大学：贾晓峰）(D) 钻井布局问题（郑州大学：林诒勋）2000年 (A) DNA序列分类问题（北京工业大学：孟大志）(B) 钢管订购和运输问题（武汉大学：费甫生）(C) 飞越北极问题（复旦大学：谭永基）(D) 空洞探测问题（东北电力学院：关信）2001年 (A) 血管的三维重建问题（浙江大学：汪国昭）(B) 公交车调度问题（清华大学：谭泽光）(C) 基金使用计划问题（东南大学：陈恩水）(D) 公交车调度问题（清华大学：谭泽光）2002年 (A) 车灯线光源的优化设计问题（复旦大学:谭永基，华东理工大学:俞文此）(B) 彩票中的数学问题（解放军信息工程大学：韩中庚）(C) 车灯线光源的优化设计问题（复旦大学:谭永基，华东理工大学:俞文此）(D) 赛程安排问题（清华大学：姜启源）2003年 (A) SARS的传播问题（组委会）(B) 露天矿生产的车辆安排问题（吉林大学：方沛辰）(C) SARS的传播问题（组委会）(D) 抢渡长江问题（华中农业大学：殷建肃）2004年 (A) 奥运会临时超市网点设计问题(北京工业大学：孟大志)(B) 电力市场的输电阻塞管理问题(浙江大学:刘康生)(C) 酒后开车问题（清华大学：姜启源）(D) 招聘公务员问题（解放军信息工程大学：韩中庚）2005年 (A) 长江水质的评价和预测问题（解放军信息工程大学：韩中庚）(B) DVD在线租赁问题(清华大学:谢金星等)(C) 雨量预报方法的评价问题(复旦大学:谭永基)(D) DVD在线租赁问题(清华大学:谢金星等)2006年 (A) 出版社的资源配置问题(北京工业大学：孟大志)(B) 艾滋病疗法的评价及疗效的预测问题（天津大学：边馥萍）(C) 易拉罐的优化设计问题（北京理工大学：叶其孝）(D) 煤矿瓦斯和煤尘的监测与控制问题（解放军信息工程大学：韩中庚）2007年 (A) 中国人口增长预测(B) 乘公交，看奥运(C) 手机“套餐”优惠几何(D) 体能测试时间安排2008年（A）数码相机定位，（B）高等教育学费标准探讨，（C）地面搜索，（D）NBA赛程的分析与评价2009年（A）制动器试验台的控制方法分析（B）眼科病床的合理安排（C）卫星和飞船的跟踪测控（D）会议筹备历年全国数学建模试题及解法归纳赛题解法93A非线性交调的频率设计拟合、规划93B足球队排名图论、层次分析、整数规划94A逢山开路图论、插值、动态规划94B锁具装箱问题图论、组合数学95A飞行管理问题非线性规划、线性规划95B天车与冶炼炉的作业调度动态规划、排队论、图论96A最优捕鱼策略微分方程、优化96B节水洗衣机非线性规划97A零件的参数设计非线性规划97B截断切割的最优排列随机模拟、图论98A一类投资组合问题多目标优化、非线性规划98B灾情巡视的最佳路线图论、组合优化99A自动化车床管理随机优化、计算机模拟99B钻井布局 0-1规划、图论00A DNA序列分类模式识别、Fisher判别、人工神经网络00B钢管订购和运输组合优化、运输问题01A血管三维重建曲线拟合、曲面重建赛题解法01B 公交车调度问题多目标规划02A车灯线光源的优化非线性规划02B彩票问题单目标决策03A SARS的传播微分方程、差分方程03B 露天矿生产的车辆安排整数规划、运输问题04A奥运会临时超市网点设计统计分析、数据处理、优化04B电力市场的输电阻塞管理数据拟合、优化05A长江水质的评价和预测预测评价、数据处理05B DVD在线租赁随机规划、整数规划06A出版社书号问题整数规划、数据处理、优化06B Hiv病毒问题线性规划、回归分析07A 人口问题微分方程、数据处理、优化07B 公交车问题多目标规划、动态规划、图论、0-1规划08A 照相机问题非线性方程组、优化08B 大学学费问题数据收集和处理、统计分析、回归分析赛题发展的特点：1. 对选手的计算机能力提出了更高的要求：赛题的解决依赖计算机，题目的数据较多，手工计算不能完成，如03B，某些问题需要使用计算机软件，01A。

1998年世界大学生数学竞赛初试试题及详细答案

1998年世界大学生数学竞赛初试试题及详细答案
1 2 1 2
k
1 2
2 − 2(x − 1 2 ) . If (1) holds for
k 1 2 2
1 2
− 22 −1 −2(x k+1 − 22 −1 (x −
− 22
1 2 k 2 2 −1 2) 1 (x − 2 ) −
which is (2) for n = k + 1. Using (1) we can compute the integral,
2
1 Because h(0) = h(1) = − 2 , there exists a real number 0 < η < 1 for which h (η ) = 0. But g = f 2 · h , and we are done. b) If f has at least one zero, let z1 be the first one and z2 be the last one. (The set of the zeros is closed.) By the conditions, 0 < z1 ≤ z2 < 1. The function f is positive on the intervals [0, z1 ) and (z2 , 1]; this implies that f (z1 ) ≤ 0 and f (z2 ) ≥ 0. Then g (z1 ) = f (z1 ) ≤ 0 and g (z2 ) = f (z2 ) ≥ 0, and there exists a real number η ∈ [z1 , z2 ] for which g (η ) = 0. 2 the conditions hold and f · f + f is constantly 0. Remark. For the function f (x) = x+1

历年全国大学生数学建模竞赛-题目(1994-2009)

历年全国大学生数学建模竞赛-题目(1994-2009)
B 题 节水洗衣机
我国淡水资源有限，节约用水人人有责。洗衣机在家庭用水中占有相当大的 份额，目前洗衣机已非常普及，节约洗衣机用水十分重要。假设在放入衣物和洗 涤剂后洗衣机的运行过程为：加水-漂水-脱水-加水-漂水-脱水-…-加水-漂水脱水（称“加水-漂水-脱水”为运行一轮）。请为洗衣机设计一种程序（包括运 行多少轮、每轮加多少水等），使得在满足一定洗涤效果的条件下，总用水量最 少。选用合理的数据进行计算。对照目前常用的洗衣机的运行情况，对你的模型 和结果作出评价。
１）建立数学模型分析如何可持续捕获（即每年开始捕捞时渔场中各年龄组 鱼群不变），并且在此前提下得到最高的年收获量（捕捞总重量）。
２）某渔业公司承包这种鱼的捕捞业务５年，合同要求鱼群的生产能力不能 受到太大的破坏。已知承包时各年龄组鱼群的数量分别为： 122,29.7,10.1,3.29(×109 条），如果仍用固定努力量的捕捞方式，该公司采取 怎样的策略才能使总收获量最高。
1996 年全国大学生数学建模竞赛
A 题:最优捕鱼策略
为了保护人类赖以生存的自然环境，可再生资源（如渔业、林业资源）的开 发必须适度。一种合理、简化的策略是，在实现可持续收获的前提下，追求最大 产量或最佳效益。
考虑对某种鱼（鲳鱼）的最优捕捞策略：
假设这种鱼分４个年龄组：称１龄鱼，……，４龄鱼。各年龄组每条鱼的平 均重量分别为 5.07,11.55,17.86,22.99（克）；各年龄组鱼的自然死亡率均为 0.8（１/年）；这种鱼为季节性集中产卵繁殖，平均每条４龄鱼的产卵量为 1.109 ×105(个）；３龄鱼的产卵量为这个数的一半，２龄鱼和１龄鱼不产卵，产卵和 孵化期为每年的最后４个月；卵孵化并成活为１龄鱼，成活率（１龄鱼条数与产 卵总是 n 之比）为 1.22×1011/(1.22×1011+n).

1998-2015数学建模真题分析

1998-2015数学建模真题分析
养老金制度怎么达到最合理分配
预测优化
社会学人口学
MATLAB二次拟合灰色预测(GM1,1)模型Logistic模型
均值法
D
天然肠衣搭配问题
最合理使用肠衣使尽量不浪费
优化
食品学细菌学
整数线性规划优化搭配
MATLAB lingo
2012
A
葡萄酒的评价
对葡萄酒质量的判别
评价
酒文化酿造学质量评价
双重多因素分析0-1数据分析排序检验法关联性分析Alpha模型
优化
金融、投资
线性规划
线性规划
D
公交车调度
设计便于操作的全天的公交车调度方案
优化
交通运输
多目标非线性规划
线性规划
2002
A
车灯线光源的优化设计
在某一设计规范标准下确定线光源的长度
优化
光学、物理学、能源
数值模拟，微元法，连续模型，Jacobi行列式，非线性规划
数值模拟，微元法，
' \( q+ v9 G0 F; f"`0 J" N非线性规划
优化
光学、物理学、能源
连续模型；模拟散斑；微元法
反射原理
D
赛程安排
如何安排赛程使对各队来说都尽量公平
优化
统计、运筹
排除一假设法，最大号固定右上角的逆时针轮转法；同余理论；最小号固定的双向轮转法
排除一假设法；逆时针轮转法；双向轮转法
2003
A
SARS的传播
针对附件评价其合理性和实用性；搜集SARS对经济某个方面影响的数据，建立相应的数学模型并进行预测
轨道模型，图论
D
会议筹备
制定宾馆、会议室、租车的合理方案

1998年全国大学生数学建模竞赛题

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,求出完成巡视的最短时间为小时,并用较为合理的分组的准则,分成22个组对问题4，研究了在不影响分组的均衡条件下, T,t,V的允许变化范围,并得出了这三个变量的关系式,并由此对分三个组的情况进行了具体讨论。

关键词：最佳推销员回路问题哈米尔顿回路赋权图近似算法均衡度一、问题重述1998年夏天某县遭受水灾。

全国大学生数学建模竞赛历年赛题

全国大学生数学建模竞赛历年赛题Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】1992A 施肥效果分析1992B 实验数据分解1993A 非线性交调的频率设计1993B 足球队排名次1994A 逢山开路1994B 锁具装箱1995A 一个飞行管理问题1995B 天车与冶炼炉的作业调度1996A 最优捕鱼策略1996B 节水洗衣机1997A 零件参数1997B 截断切割1998A 投资的收益和风险1998B 灾情巡视路线1999A 自动化车床管理1999B 钻井布局1999C 煤矸石堆积1999D 钻井布局2000A DNA序列分类2000B 钢管购运2000C 飞越北极2000D 空洞探测2001A 血管三维重建2001B 公交车调度2001C 基金使用2001D 公交车调度2002A 车灯线光源2002B 彩票中数学2002C 车灯线光源2002D 赛程安排2003A SARS的传播2003B 露天矿生产2003C SARS的传播2003D 抢渡长江2004A 奥运会临时超市网点设计2004A 赛题使用数据2004B 电力市场的输电阻塞管理2004C 饮酒驾车2004D 公务员招聘2005A 长江水质的评价和预测2005B DVD在线租赁2005C 雨量预报方法的评价2005D DVD在线租赁2005D 数据2006A 出版社的资源配置2006A 数据2006B 艾滋病疗法的评价及疗效的预测2006B 数据2006C 易拉罐形状和尺寸的最优设计2006D 煤矿瓦斯和煤尘的监测与控制2006D 数据2007A 中国人口增长预测2007A 数据2007B 乘公交，看奥运2007B 数据2007C 手机“套餐”优惠几何2007C 数据2007D 体能测试时间安排2008A 数码相机定位2008B 高等教育学费标准探讨2008C 地面搜索2008D NBA赛程的分析与评价2008D 数据2009A 制动器试验台的控制方法分析2009A 数据2009B 眼科病床的合理安排2009C 卫星和飞船的跟踪测控2009D 会议筹备2010A 储油罐的变位识别与罐容表标定2010B 2010年上海世博会影响力的定量评估2010C 输油管的布置2010D 对学生宿舍设计方案的评价。

数学建模---非线性规划模型

M（元）：公司现有投资总额 Si（i=0~n）：欲购买的第i种资产种类（其中i=0 表 示存入银行）； xi（i=0~n）：公司购买Si金额； ri（i=0~n）：公司购买Si的平均收益率； qi（i=0~n）：公司购买Si的平均损失率； p（i=0~n）：公司购买Si超过ui时所付交易费率。
6.4.3 问题的分析
i i i i i i i
当购买Si的金额为xi（i=0~n），投资组合 x=（x0，x1，…，xn）的净收益总额
R( x) Ri ( xi )
n i 0
（6 ）
整体风险：
Q( x) max Qi ( xi )
资金约束：
1i n
n
（7）
（8 ）
F ( x) f i ( xi ) M

二、多目标规划模型 多目标规划模型的一般形式为
min f1 x , f 2 x , , f p x gi x 0, i 1, 2,....., m s.t. h j x 0, j 1, 2,....., l
T
5.7
2.7 4.5 7.6
320
267 328 131
模型的假设
1. 2.
3.
4.
在一个时期内所给出的ri，qi，pi保持不变。 在一个时间内所购买的各种资产（如股票、 证券等）不进行买卖交易，即在买入后不再 卖出。 每种投资是否收益是相互独立的。 在投资过程中，无论盈利与否必须先付交易 费。
符号的说明
表1
售价（元） 2.00 2.50 3.00 3.50 4.00 4.50 5.00 5.50 6.00 41000 38000 34000 32000 29000 28000 25000 22000 20000

历年高教杯全国大学生数学建模题目

1.6 近几年全国大学生数学建模竞赛题
A 1992 B A 1993 B A 1994 B 锁具装箱 锁具装箱 足球比赛的排名问题 逢山开路 实验数据分解 交调频率设计 农作物施肥效果分析
A 1995 B A 1996 B A 1997 B
一个飞行管理问题 天车与冶炼炉的作业调度 节水洗衣机问题 最优捕鱼问题 零件的参数设计 最优截断切割问题
长江水质的评价和预测 DVD 在线租赁 在线租赁
2006
2007
出版社的资源配置 艾滋病疗法的评价及疗效 B 的预测 A 中国人口增长预测 A B A 乘公交， 乘公交，看奥运 数码相机定位
2008 B 2009
高等教育学费标准探讨 制动器试验台的控制方法 A 分析 B 眼科病床的合理安排
A 1998 B A 1999 B A 2000 B A 2001 B
投资的收益和风险 灾情巡视路线 自动化车床管理 钻井布局 DNA 序列分类 钢管订购和运输
血管的三维重建 公交车调度
A 2002 B A 2003 B A 2004 B A 2005 B
车灯线光源的优化设计 彩票中的数学 SARS 的传播 露天矿生产的车辆安排 奥运会临时超市网点设计 电力市场的输电阻塞管理

1998年世界大学生数学竞赛复试试题及详细答案

5th INTERNATIONAL MATHEMATICS COMPETITION FOR UNIVERSITY STUDENTS July 29 - August 3, 1998, Blagoevgrad, Bulgaria Second day PROBLEMS AND SOLUTION
Problem 1. (20 points) Let V be a real vector space, and let f, f1 , f2 , . . . , fk be linear maps from V to I R. Suppose that f (x) = 0 whenever f1 (x) = f2 (x) = . . . = fk (x) = 0. Prove that f is a linear combination of f1 , f2 , ..., fk . Solution. We use induction on k . By passing to a subset, we may assume that f1 , . . . , fk are linearly independent. Since fk is independent of f1 , . . . , fk−1 , by induction there exists a vector ak ∈ V such that f1 (ak ) = . . . = fk−1 (ak ) = 0 and fk (ak ) = 0. After normalising, we may assume that fk (ak ) = 1. The vectors a1 , . . . , ak−1 are defined similarly to get fi (aj ) = 1 if i = j 0 if i = j.
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

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的允许变化范围,并得出了这三个变量的关系式,并由此对分三个组的情况进行了具体讨论。

关键词：最佳推销员回路问题哈米尔顿回路赋权图近似算法均衡度一、问题重述1998年夏天某县遭受水灾。

为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各17个乡（镇）、35个村巡视。

巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。

(1) 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。

(2) 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。

要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。

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

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

二、问题分析本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O ，使得总权（路程或时间）最小.本题是旅行售货员问题的延伸－多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是m 条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题. 众所周知，旅行售货员问题属于NP 完全问题，即求解没有多项式时间算法.显然本问题更应属于NP 完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.三、模型假设1．汽车在路上的速度总是一定，不会出现抛锚等现象；忽略天气、故障等因素的影响。

2．巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；3．每个小组的汽车行驶速度完全一样；4．分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外。

四、符号说明(,)w i j ……………………………………..任意两点i ，j 间的间距。

i e ……………………………………..各点的停留时间，即点权。

V ………………………………………汽车行驶速度。

ij d ………………………………从任意点i 至点j 的时间，则(,)/ij d w i j V =。

五、模型建立与求解公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点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 的划分12,,.......n V V V ，将G 分成n 个生成子图[][][]n V G V G V G ,......,21，使得（1）顶点i O V ∈ i=1，2，3……n（2）()1n i i V V G ==（3）()()(),i ji j i i w Max C w C Max w C α-≤，其中i C 为i V 的导出子图[]i V G 中的最佳推销员回路，()i C ω为i C 的权，i ，j=1，2，3……n（4）()1ni i w C Min ==∑定义 称()()(),0i j i j i i Max w C w C Max w C α-=为该分组的实际均衡度。

α为最大容许均衡度。

显然100≤≤α，0α越小，说明分组的均衡性越好.取定一个α后，0α与α满足条件（3）的分组是一个均衡分组.条件（4）表示总巡视路线最短。

此问题包含两方面：第一、对顶点分组；第二、在每组中求最佳推销员回路，即为单个推销员的最佳推销员问题。

由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故多个推销员的问题也不存在多项式时间内的精确算法.而图中节点数较多，为53个，我们只能去寻求一种较合理的划分准则，对图１1－9进行粗步划分后，求出各部分的近似最佳推销员回路的权，再进一步进行调整，使得各部分满足均衡性条件（3）。

从O 点出发去其它点，要使路程较小应尽量走O 点到该点的最短路.故用图论软件包求出O 点到其余顶点的最短路，这些最短路构成一棵O 为树根的树，将从O 点出发的树枝称为干枝，见图１１－１0，从图中可以看出，从O 点出发到图11-10 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% 所以这种分法的均衡性较好。

问题二由于T=2小时，t=1小时，V=35公里/小时，需访问的乡镇共有17个，村共有35个.计算出在乡（镇）及村的总停留时间为17⨯2+35=69小时，要在24小时内完成巡回，若不考虑行走时间，有: 2469<i(i 为分的组数).得i 最小为4，故至少要分4组。

由于该网络的乡（镇）、村分布较为均匀，故有可能找出停留时间尽量均衡的分组，当分4组时各组停留时间大约为25.17469=小时，则每组分配在路途上的时间大约为24-17.25=6.75小时.而前面讨论过，分三组时有个总路程599.8公里的巡视路线，分4组时的总路程不会比599.8公里大太多，不妨以599.8公里来计算.路上时间约为17358.599=小时，若平均分配给4个组，每个组约需417=4.25小时〈6.75小时，故分成4组是可能办到的。

现在尝试将顶点分为4组.分组的原则：除遵从前面准则一、二、三外，还应遵从以下准则：准则四：尽量使各组的停留时间相等。

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

这4组的近似最优解见表3：加框的表示此点只经过不停留。

该分组实际均衡度0α==-74.2269.2174.22 4.62%可以看出，表3分组的均衡度很好，且完全满足24小时完成巡视的要求。

问题三我们发现从O 点巡视H 点的最短时间是所有最短时间中最长的，其距离为77.5公里。