校园最佳游览路线问题的数学模型分析
廖川荣
(南昌大学数学系, 江西南昌330031)
[摘要] 将某高校的校园示意图转化为赋权连通图,求得该连通图的邻接矩阵,利用Floyd算法及图论软件包构造一个最短路径矩阵,得到一个赋权完全图,将求校园最佳游览路线问题归结为图论中的最佳推销员回路问题,建立混合整数线性规划模型,并利用优化软件求得最优解.从而解决了校园开放日游览计划中提出的关于校园最佳游览路线和校园游览车最优配置问题.
[关键词] 赋权完全图；最佳游览路线；最优配置.
[中图分类号] O157.6 [文献标识码] A [文章编号] 91136
1 引言
现在国内许多高校每年都会定期举办校园开放日,开放日旨在全面展示该校的办学特色及优美的校园环境,反映大学生丰富多彩的校园生活.通过举办开放日,为考生填报高考志愿提供全面真实和具体的信息,让考生和家长了解学校的历史和现状,熟悉招生政策,在大学和考生之间建立一个友好顺畅的交流沟通平台.
某高校开放日,将会有许多考生及家长要求参观该校的新校园,以下为校园简化示意图:(其中v i为参观者需参观的主楼、景点和场地,连线为两参观点间道路,连线上数字为两参观点间距离，单位:公里)
图1:校园简化示意图
说明:V1医学院教学大楼, V2本科生公寓A区, V3学生食堂A, V4国际学术交流中心, V5白求恩广场, V6医学实验大楼, V7青年教师宿舍区, V8研究生院, V9运动场A, V10正门, V11工程实验楼, V12天健园, V13研究生公寓区, V14基础实验大楼, V15本科生公寓B区, V16办公楼, V17中心广场, V18图书馆, V19计算机实验中心, V20保安楼, V21理科生命大楼, V22材料楼, V23环境楼, V24正气广场, V25人文楼, V26信工楼, V27法学楼, V28机电楼与建工楼, V29综合教学楼, V30学生食堂B, V31外经楼, V32学工楼, V33艺术楼, V34商业街, V35校医院, V36本科生公寓C区, V37学生食堂C, V38体育馆, V39体育场, V40游泳馆, V41
运动场B.
校方拟在本校高年级学生中招募一批临时导游,负责接待并陪同考生及家长乘坐校园游览车（限载 50人,时速20公里/小时）参观游览新校园,路线是从新校园正大门出发,最后返回到出发地.为了向所有参观者展示该校的风貌和亮点,同时满足参观者了解校园的不同要求,校方要求应聘者提供一份详细的校园游览计划,计划中应包括以下内容:
1）根据考生的理、文、工、医四种报考专业为参观者选择下车参观的主楼、景点和场地.
2）根据校园简化示意图及问题1确定的下车参观的主楼、景点和场地,建立数学模型,按报考专业分别设计4条不同的最佳游览路线,使每条游览路线的总路程最短.
3）假设有3000本省考生及1000外省考生想在开放日这天参观游览该校的新校园；且根据历年统计，开放日上午参观人数约为全天参观人数的60%.问该校开放日至少要预备多少辆校园游览车? 2 模型假设
1) 不同报考专业的参观者总是更有兴趣参观与本专业有关的主楼、景点或场地,导游通过指示牌来引导报考不同专业的考生及家长乘坐不同路线的游览车.
2) 道路通畅,游览车只在选定参观点仃车,每个参观点只参观一次.
3) 对相同性质的楼群只参观一栋有代表性的主楼.
4) 不考虑天气等环境因素的影响.
5) 校园游览车限载50人,时速20公里/小时.
6) 参观者参观选定的主楼、景点与场地的时间均为5分钟.
7) 在开放日这天有3000本省考生及1000外省考生想参观游览该校的新校园.
8) 不考虑参观者上下车时间.
9) 开放日工作时间为上午8:00-12:00, 下午1:00-17:00.
10) 根据历年统计, 校园开放日上午参观人数约为全天参观人数的60%.
11）将各主楼、景点或场地看作平面上的质点,不考虑自身形状的大小,均称之为图论中的结点。 3 符号说明
v i : 参观者需参观的主楼、景点和场地. ()1,2,,41i =
(),i j d v v ：两参观点v i 与v j 之间的路程.(),1,2,,41i j =
(),min ,i j i j d d v v =: 两参观点v i 与v j 之间的最短路程.(),1,2,,41i j =
D k ：第k 条游览路线的最短路径矩阵(Floyd 矩阵).,()k k k i j n
n D d ?=，其中n k 表示第k 条游览路径
中的参观点数. (n 1 =15, n 2 =17, n 3 =19, n 4 =12)
x (v i , v j ): 代表游览路径中两参观点间的特征变量. 当v i 与v j 为最佳游览路线上两个相邻的需下车参观的景点时x (v i , v j )=1, 反之, x (v i , v j )=0. (i, j=1,2, (41)
P i : 参观者乘游览车游览第i 条路线的概率. (i =1,2,3,4)
R i : 第i 条游览路线上参观游览的人数. (i =1,2,3,4)
S i : 第i 条游览路线起点发车速率. (i =1,2,3,4)
T i : 游览车在第i 条路线行驶一圈所需时间. (i =1,2,3,4)
N i : 第i 条游览路线需要预备的最低校园游览车数. (i =1,2,3,4)
N : 校方需要预备的最低校园游览车数. (N = N 1 + N 2 + N 3 + N 4 )
M : 在开放日这天想参观游览该校新校园的本省及外省考生的总人数.(M =4000)
4 模型建立与求解
4.1 选择参观者下车参观的主楼、景点和场地
校园开放日活动是社会各界认识了解高校的一个重要窗口,是加强学校与社会联系的一个重要途径,是提升高校社会影响力,发挥高校在科学技术领域中引领作用的重要措施,高校应在开放日向参观者充分展现该校的风貌和亮点.如:基础教学设施,医疗卫生设施,体育运动设施,亮点建筑和人文景观,同时还应考虑到参观者了解校园的不同要求.为此,根据考生的理、文、工、医四种报考专业为参观者选择下列需下车参观的主楼、景点和场地.
1) 理科路线参观点: v 10正门, v 16办公楼, v 17中心广场, v 18图书馆, v 14基础实验大楼, v 19计算机实验中心, v 21理科生命大楼, v 30学生食堂B, v 29综合教学楼, v 32学工楼, v 34商业街, v 36本科生公寓C 区, v 35校医院, v 41运动场B, v 24正气广场. (n 1=15)
2） 文科路线参观点: v 10正门, v 16办公楼, v 17中心广场, v 18图书馆, v 19计算机实验中心, v 25人文楼, v 27法学楼, v 31外经楼, v 29综合教学楼, v 30学生食堂B, v 32学工楼, v 34商业街, v 33艺术楼, v 35校医院, v 36本科生公寓C 区, v 41运动场B, v 24正气广场. (n 2 =17)
3） 工科路线参观点: v 10正门, v 16办公楼, v 17中心广场, v 18图书馆, v 11工程实验楼, v 14基础实验大楼, v 19计算机实验中心, v 22材料楼, v 23环境楼, v 26信工楼, v 28机电楼与建工楼, v 30学生食堂B, v 29综合教学楼, v 32学工楼, v 34商业街, v 35校医院, v 36本科生公寓C 区, v 41运动场B, v 24正气广场. (n 3=19)
4） 医科路线参观点: v 10正门, v 16办公楼, v 17中心广场, v 18图书馆, v 6医学实验大楼, v 5白求恩广场, v 9运动场A, v 3学生食堂A, v 2本科生公寓A 区, v 1医学院教学大楼, v 4国际学术交流中心, v 24正气广场. (n 4=12)
4.2 设计4条不同的最佳游览路线
1）最短路径矩阵
将校园示意图转化为赋权连通图G(V , E):
()()(),,,,i j i j i j v v E v v d v v ω?∈=.
求得该连通图的邻接矩阵,并利用Floyd 算法及图论软件包构造一个最短路径矩阵(Floyd 矩阵),得到一个赋权完全图()'',G V E ,［1］其中E′中每条边的权等于结点v i 与v j 在图G(V , E)中的最短路径的权:
()()()'',,,,min ,i j i j i j i j v v E v v d d v v ω?∈==.
根据问题1确定的理、文、工、医4个报考专业,分别得到4个赋权完全子图的最短路径矩阵。
例如医科路线的Floyd 矩阵为:
4,1212()i j D d ?==
[0.00 0.40 0.65 0.90 0.80 0.60 1.35 1.25 1.00 0.60 0.40 0.90
0.40 0.00 0.25 0.50 1.20 1.00 1.75 1.65 1.40 1.00 0.80 0.50
0.65 0.25 0.00 0.25 1.40 1.25 1.60 1.85 1.60 1.25 1.05 0.75
0.90 0.50 0.25 0.00 1.15 1.35 1.35 1.60 1.35 1.50 1.30 1.00
0.80 1.20 1.40 1.15 0.00 0.20 0.55 0.45 0.20 0.40 0.40 1.70
0.60 1.00 1.25 1.35 0.20 0.00 0.75 0.65 0.40 0.20 0.20 1.50
1.35 1.75 1.60 1.35 0.55 0.75 0.00 0.30 0.60 0.95 0.95
2.25
1.25 1.65 1.85 1.60 0.45 0.65 0.30 0.00 0.30 0.70 0.85
2.15
1.00 1.40 1.60 1.35 0.20 0.40 0.60 0.30 0.00 0.40 0.60 1.90
0.60 1.00 1.25 1.50 0.40 0.20 0.95 0.70 0.40 0.00 0.20 1.50
0.40 0.80 1.05 1.30 0.40 0.20 0.95 0.85 0.60 0.20 0.00 1.30
0.90 0.50 0.75 1.00 1.70 1.50 2.25 2.15 1.90 1.50 1.30 0.00];
2）最佳游览路线求解
求考生理、文、工、医四种报考专业的最佳游览路线问题可归结为图论中的最佳推销员回路问题,
［2］即在4个赋权完全子图中分别求一个近似最优的Hamilton 圈,［3］该最优H 圈问题可用以下两种方法求解：
方法一：二边逐次修正法.［4］
（1）输入图()'',G V E 的一个初始圈;
（2）用对角线完全算法产生一个初始H 圈;
（3）随机搜索出G′中若干个H 圈,例如2000个;
（4）对第1、2、3步所得的每个H 圈,用二边逐次修正法进行优化,得到近似最佳H 圈;
（5）在第4步求出的所有H 圈中,找出权最小的一个,此即要找的最佳H 圈的近似解.
方法二：混合整数线性规划模型.［5］
,111min .1,
1,2,....1,1,2,....1,20,1,1,2,.....02,3,....n ij ij i j n ij i n ij j i j ij ij i Z d x st x j n x i n u u nx n i j n x i j n u i n ===?=???==????==??-+≤-≤≠≤??==??≥=?∑∑∑
说明: 约束条件()()..111,1,2,....,1,1,2,.....n n
i j i j i j x
j n x i n ======∑∑只是该线性规划模型中的两个必要约束条件,
而约束条件1,(2)i j i j u u n x n i j n -+≤-
≤≠≤是为避免产生子巡回而附加的充分约束条件,其中()2,3,i u i n = 可看作n-1个额外的变量.可以证明:任何含子巡回的路线都不满足该约束条件,全部巡回路线都满足该约束条件.
求解结果如下(不加括号为下车参观点）：
（1）理科最佳游览路线: v 10→(v 16)→v 24→(v 31)→v 29→v 35→(v 36)→v 41→v 36→v 34→v 32→v 30→(v 28)→(v 26) →(v 22)→v 21→(v 19)→v 14→v 19→v 18→v 17→v 16→v 10, 共有n 1=15个下车参观点;最短游览路程：5.900000（公里）.
（2）文科最佳游览路线: v 10→v 16→v 24→v 25→v 27→v 29→v 31→v 33→(v 39)→v 35→(v 36)→v 41→v 36→v 34→ v 32→v 30→(v 28)→(v 26)→(v 22)→(v 21)→v 19→v 18→v 17→(v 16)→v 10，共有n 2=17个下车参观点；最短游览路程：
6.300000（公里）.
（3）工科最佳游览路线: v 10→(v 16)→v 24→(v 31)→v 29→v 35→(v 36)→v 41→v 36→v 34→v 32→v 30→v 28→v 26→ v 22→v 23→(v 22)→(v 21)→(v 19)→v 14→v 11→(v 14)→v 19→v 18→v 17→v 16→v 10, 共有n 3=19个下车参观点；最短游览路程：6.800000（公里）.
（4）医科最佳游览路线: v 10→v 4→v 1→v 5→v 6→v 2→v 3→(v 7)→v 9→(v 8)→(v 11)→(v 14)→(v 19)→v 18→v 17 →v 16→v 24→(v 16)→v 10, 共有n 4 =12个下车参观点；最短游览路程：5.050000（公里）.
3) 计算校方开放日需要预备的最低校园游览车数
由问题假设,开放日将有3000本省考生及1000外省考生及其家长参观游览该校的新校园,参观者总数为M=4000;开放时间为上午8:00-12:00下午13:00-17:00.参观者按问题2确定的4条最佳游览路线分别参观游览新校园。
根据历年校园开放日的人数统计,开放日上午参观人数约为全天参观人数的60%.因此，开放日上午将有0.6×M 人参观游览新校园,下午有0.4×M 人参观游览新校园;校方开放日上午需要预备的最低校园游览车数可根据开放日上午参观游览的人数计算.
具体计算过程如下：
（1） 参观者游览第i 条路线的概率: i i i i n P n
=∑4
=1.
（2）第i 条路线上参观游览的人数: R i =0.6×M ×P i （人）.
（3）第i 条路线起点发车速率: ()1/i i R S h =?辆游览车限载人数上午参观游览时间
. （4）第i 条路线游览一圈所需时间: (),i i T n h =+?游览路线的最短路程参观点的参观时间游览车行驶速度
（5）第i 条路线上最低游览车数: N i =S i ×T i （辆）.
（6）开放日上午校方需要预备的最低校园游览车数：N = N 1 + N 2 + N 3 + N 4 .
5 结果
根据以上公式可算出:该高校开放日上午往返循环行使的校园游览车辆数为：理科游览路线4辆,文科游览路线6辆,工科游览路线7辆,医科游览路线3辆，开放日上午需要预备的最低游览车数为20辆.
同理可算出开放日下午往返循环行使的校园游览车辆数为：理科游览路线3辆,文科游览路线4辆, 工科游览路线5辆,医科游览路线2辆,开放日下午需要预备的最低游览车数总共为14辆.
由于开放日上午参观的人数多于下午的人数,校方开放日上午需要预备的最低游览车数也为全天所需要最低车辆数.因此,校方校园开放日需要预备的最低游览车数为20辆.
[参考文献]
[1] 张蕾.矩阵方法求赋权图中最短路的算法[J].西北大学学报(自然科学版),2004,10: 527-530.
[2] 马良.旅行推销员问题的算法综述[J].数学的实践与认识,2000,4: 156-165.
[3] 谭永基.经济管理数学模型案例教程[M].北京:高等教育出版社,2001,8: 374-377.
[4] 杨庭栋等.最佳灾情巡视路线的数学模型[J]. 数学的实践与认识,1999,1: 50-59.
[5] 韩中庚.数学建模方法及其应用[M].北京:高等教育出版社,2005,6: 185-188
Mathematical model Analysis about the best route of tourist in campus
Liao chuanrong
(Department of Mathematics, Nanchang University, Nanchang 330031, China) Abstract: A campus’s sketch map is transfered into connected graph with weight and its adjacency matrix is gotten. The shortest path matrix is constructed and a completed graph with weight is gotten by Floyed arithmetic and the software package of graph. The best tourist route of campus problem is regarded as TSP problem, i.e., find the best similar Hamilton circle in the completed graph with weight. It is solved three problems in the opening day of campus:
1. For visitors to choose the main buildings, spots or sites.
2. According to the sketch map, design the shortest four tourist paths.
3. Get the minimal number of sightseeing bus in the opening day of campus.
Keywords:Completed graph with weight; The shortest tourist path; The best configuration.
一、判断题 1.比例尺、地图投影、各种坐标系统就构成了地图的数学法则。Y 2.地图容纳和储存了数量巨大的信息，而作为信息的载体，只能是传统概念上的纸质地图。 3.地图的数学要素主要包括地图投影、坐标系统、比例尺、控制点、图例等。 4.实测成图法一直是测制大比例尺地图最基本的方法。Y 5. 磁坐偏角指磁子午线与坐标纵线之间的夹角。以坐标纵线为准，磁子午线东偏为负，西偏为正。） 6. 一般情况下真方位角（A）、磁偏角（δ）、磁方位角（Am）三者之间的关系是A=Am+δ。 8. 城市规划、居民地布局、地籍管理等需要以小比例尺的平面地图作为基础图件。 10.方位角是由标准方向线北端或者南端开始顺时针方向到某一直线的夹角。 11.地球体的数学表面，也是对地球形体的二级逼近，用于测量计算的基准面。Y 12.在地图学中，以大地经纬度定义地理坐标。Y 13.在地理学研究及地图学的小比例尺制图中，通常将椭球体当成正球体看，采用地心经纬度。Y 14.1987年国家测绘局公布：启用《1985国家高程基准》取代《黄海平均海水面》，其比《黄海平均海水面》下降29毫米。 15.球面是个不可展的曲面，要把球面直接展成平面，必然要发生断裂或褶皱。Y 16.长度比是一个常量，它既不随着点的位置不同而变化，也不随着方向的变化而变化。 17.长度变形没有正负之分，长度变形恒为正。 18. 面积变形有正有负，面积变形为零，表示投影后面积无变形，面积变形为正，表示投影后面积增加；面积变形为负，表示投影后面积缩小。Y 19.制1：100万地图，首先将地球缩小100万倍，而后将其投影到平面上，那么1：100万就是地图的主比例尺。Y 20.在等积圆锥投影上中央经线上纬线间隔自投影中心向外逐渐增大。 21. 无论是正轴方位投影还是横轴方位投影或是斜轴方位投影，他们的误差分布规律是一致的。Y 22. 等角正轴切圆柱投影是荷兰地图学家墨卡托于1569年所创，所以又称墨卡托投影。Y 23. 等积投影的面积变形接近零。Y 25. 按基本等高距的二分之一高程绘出的等高线称为助曲线。 26. 经线在任何球心投影中的表象都是直线。Y 27. 一般情况下，等角航线是与所有经线相交成相同方位角的大圆弧线，它在圆柱投影上的表象是直线。 28. 不同地点的磁偏角是不相同的，同一地点的磁偏角是相同的。 29. 水准面有无数个，而大地水准面只有一个。Y 31. 等角航线是地球面上两点间的最短航线。 34.目前我国各地高程控制点的绝对高程起算面是1956黄海平均海水面。 35. 磁偏角只随地点的不同而不同。 36. 地图比例尺是决定地图概括数量特征的主要因素。Y 37. 地图的内容受符号的形状、尺寸、颜色和结构的直接影响，并制约着概括程度和方法。Y 38. 面状符号表达空间上具连续两维分布的现象的符号。具定位特征，为依比例符号。Y 39. 众数是最佳的数字统计量，以一个群体中出现频率最大的类别定名。Y 40. 面状符号的结构中，颜色变量起很大作用，在一定意义上说颜色变量是形状变量的组合。 41. 光的三原色又称加色原色：黄、品红、青 42. 暖色来自于蓝、青和绿等色。感觉显得稳定和清爽。它们看起来还有远离观众的效果。 43. 色彩与人的情感或情绪有着广泛的联系，不同民族的文化特点又赋予色彩以各自含义和象征。Y
选路的优化模型 摘要: 本题是一个有深刻背景的NPC问题，文章分析了分组回路的拓扑结构，并构造了多个模型，从多个侧面对具体问题进行求解。最短树结构模型给出了局部寻优的准则算法模型体现了由简到繁，确保较优的思想而三个层次分明的表述模型证明了这一类问题共有的性质。在此基础上我们的结果也是比较令人满意的。如对第一题给出了总长为599.9，单项长为216的分组，第二题给出了至少分四组的证明。最后，我们还谈到了模型的优缺点及推广思想。 一、问题描述 “水大无情，人命关天”为考察灾情，县领导决定派人及早将各乡（镇），村巡视一遍。巡视路线为从县政府所在地出发，走遍各乡（镇），村又回到县政府所在地的路线。 1.若分三组巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2.假定巡视人员在各乡（镇）停留时间为T=2小时，在各村停留时间为t =1 小时， 汽车行驶速度为V=35公里/时，要在24小时内巡视完，至少分成几组；给出这 种分组下你认为最佳的巡视路线。 3.上述关于T，t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多 少？给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 4.巡视组数已定（如三组）要求尽快完成巡视，讨论T，t和V改变时最佳路线的 影响（图见附录）。 二、问题假设 1、乡（镇）村只考察一次，多次经过时只计算一次停留时间。 2、非本县村不限制通过。 3、汽车的行驶速度始终一致。 三、符号说明 第i 人走的回路Ti=vv i(i) v2(i)v n(i) Ti=00表示第i人在0点没移动 四、模型建立
在这一节里，我们将提出若干个模型及其特点分析，不涉及对题目的求解。 最简树结构模型 在这个模型中我们依靠利用最短树的特殊结构所给出的准则，进行局部寻优，在一个不大的图里，我们较易得到较优解。 (a)分片 准则1利用最短树的长度可大致的估算出路程长，在具体操作中，各片中 的最短路程长度不宜相差太大。 准则 2 尽可能将最短树连成一个回路，这可保证局部上路程是较短的。 (b)片内调整 a2 a3 a4 a5 a6假设a3 a4有路相连 细准1对于右图的最短树结构，最好的走法是a 若a3 a4 进去重复走的话，它与上述的走法路程差w(a3, a2)+w(a2 ,a5)+w(a4, a5)—w(a3, a4)。由两点间最小原则上式是大于0的优劣可见 细准2若有如图所示结构，一般思想是：将中间树枝上的点串到两旁树枝，以便连成回路。 五、模型求解 问题一该问题完全可以用均衡模型表述 用算法模型 1 经过局部优化手工多次比较我们能够给出的最佳结果为第一组路径为 0—P—28—27—26—N—24—23—22-17—16—1—15—1—18—K—21—20—25— M--0 长191.1 经5 镇6 村 第二组路径为 0—2—5—6—L—19—J—11--G—13—14—H—12—F—10—F—9—E—8—E—7—6—5—2—0 长216.5 经6 镇11 村第三组路径为O—2—3—D—4—D—3—C—B—1—A—34—35—33—31—32—30—Q—29 —R 长192.3 经6 镇11 村总长S=599.9 公里 由算法2 给出的为 1组0—P—29—R—31—33—A—34—35—32—30—Q—28—27—26—N—24—33—22—23—N—2 6—P—0 5 乡13 村长215.2 公里 2组0—M—25—21—K—17—16—I—15—I—18—K—21—25—20—L—19—J—11—G—13—14 —O 5 乡11 村长256.2 公里 3组 O—2—5—6—7—E—9--F—12--H--—12—F—10—F—9—E-8—4—0—7—6—M—5-2—3—L —13—1—0 8 乡11 村长256.3 公里 总长727.7 公里
快递员配送路线优化模型 摘要 如今，随着网上购物的流行，快递物流行业在面临机遇的同时也需要不断迎接新的挑战。如何能够提高物流公司的配送效率并降低配送过程中的成本，已成为急需我们解决的一个问题。下面，本文将针对某公司的一名配送员在配送货物过程中遇到的三个问题进行讨论及解答。 对于问题一，由于快递员的平均速度及在各配送点停留的时间已知，故可将最短时间转换为最短路程。在此首先通过Floyd求最短路的算法，利用Matlab 程序将仓库点和所有配送点间两两的最短距离求解出来，将出发点与配送点结合起来构造完备加权图，由完备加权图确定初始H圈，列出该初始H圈加点序的距离矩阵，然后使用二边逐次修正法对矩阵进行翻转，可以求得近似最优解的距离矩阵，从而确定近似的最佳哈密尔顿圈，即最佳配送方案。 对于问题二，依旧可以将时间问题转化为距离问题。利用问题一中所建立的模型，加入一个新的时间限制条件，即可求解出满足条件的最佳路线。 对于问题三，送货员因为快件载重和体积的限制，至少需要三次才能将快件送达。所以需要对100件快件分区，即将50个配送点分成三组。利用距离矩阵寻找两两之间的最短距离是50个配送点中最大的三组最短距离的三个点，以此三点为基点按照准则划分配送点。 关键字：Floyd算法距离矩阵哈密尔顿圈二边逐次修正法矩阵翻转
问题重述 某公司现有一配送员，，从配送仓库出发，要将100件快件送到其负责的50个配送点。现在各配送点及仓库坐标已知，货物信息、配送员所承载重物的最大体积和重量、配送员行驶的平均速度已知。 问题一：配送员将前30号快件送到并返回，设计最佳的配送方案，使得路程最短。 问题二：该派送员从上午8：00开始配送，要求前30号快件在指定时间前送到，设计最佳的配送方案。 问题三：不考虑所有快件送达的时间限制，现将100件快件全部送到并返回。设计最佳的配送方案。配送员受快件重量和体积的限制，需中途返回取快件，不考虑休息时间。 符号说明 D：n个矩阵 n V：各个顶点的集合 E：各边的集合 e：每一条边 ij w:边的权 ()e G：加权无向图 , v v：定点 i j C：哈密尔顿圈 () f V：最佳哈密尔顿圈 i
第1章 优化设计 Chapter 1 Optimization Design 1-1 优化设计 1-1-1 最优化 (optimize, optimization ) 所谓最优化，通俗地说就是在一定条件下，在所有可能的计划、设计、安排中找出最好的一个来。换句话说，也就是在一定的条件下，人们如何以最好的方式来做一件事情。(Optimization deals with how to do things in the best possible manner) 结论的唯一性是最优化的特点，即公认最好。(It is the best of all possibilities) 最优化的思想体现在自然科学、工程技术及社会活动的各个领域，最优化的方法在这些领域也得到了广泛地应用。(P1) 1-1-2 最优化方法 (Arithmetic ) 要从所有可能的方案中找出最优的一个，用“试”（try ）的办法是不可行的，需要采用一定的数学手段。二十世纪五十年代以前，用于解决最优化问题的数学方法仅限于古典的微分和变分(differential and variation)。数学规划法在五十年代末被首次用于解决最优化问题，并成为现代优化方法的理论基础。线性规划和非线性规划是数学规划的主要内容，它还包括整数规划、动态规划、二次规划等等。(Linear programming or Nonlinear programming, Integer, Dynamic, Quadratic ) 数学规划法与电子计算机的密切结合,改变了最优化方法多有理论研究价值,而少有实际应用的局面,使得解决工程中的优化问题成为可能。因此,我们现在所说的最优化方法，实际上包括了最优化理论和计算机程序二方面的内容。(Optimization theory plus computer program) 1-1-3 优化设计 下面以一个简单的问题为例来说明传统设计与优化设计这二个不同的设计过程。 例1-1 设计一个体积为5cm 3的薄板包装箱，其中一边的长度不小于4m 。要求使薄板耗 材最少，试确定包装箱的尺寸参数，即长a ，宽b 和高h 。 分析 包装箱的表面积s 与它的长a ，宽b 和高h 尺寸有关。因此，耗板最少的问题可以转化为表面积最小问题，故取表面积s 为设计目标。 传统设计方法: 首先固定包装箱一边的长度如)(4m a =。要满足包装箱体积为3 5m 的设计要求，则有以下多种设计方案: 如果包装箱的长度a 再取)(4m a >的其他值，则包装箱的宽度和高度还会有很多其他结果… 。 最后，从上面众多的可行方案中选择出包装箱表面积最小的方案来，这就是相对最好的设计方案。但由于不可能列出所有可能的设计方案，最终方案就不一定是最优的。 机械产品的传统设计通常需要经过：提出课题、调查分析、技术设计、结构设计、绘图
一、问题重述 1、利用优化设计相关理论计算法，对某设计问题做优化设计。要求如下： ①列出优化数学模型; ②选择所用优化算法； ③画出程序框图； ④程序编写； ⑤程序调试运算结果。 现根据以上条件，结合生活实际，准备以铁板为材料设计一鱼缸，为了能使鱼儿有更大的生存空间，要求鱼缸容积最大。 现有边长为5米长的方形铁板，预备在四个角减去四个相等的方形面积，用以制成方形鱼缸，如何减能使鱼缸的容积最大。 二、问题分析 2.1、对于此问题，我采用的数学模型包括三部分，即设计变量、目标函数和约束条件。 模型如下： 其中，设裁去铁块的边长为：x(0 四、程序编写及函数图像 4.1求极值所用程序如下： function q=line_s(a,b) N=10000;r=0.01; a=0;b=1.5; for k=1:N; v=a+0.382*(b-a); u=a+0.618*(b-a); fv=-25*v+20*v^2-4*v^3; fu=-25*u+20*u^2-4*u^3; if fv>fu if b-v<=r u fu break; else a=v;v=u; u=a+0.618*(b-a); end else if u-a<=r v -fv break; else b=u;u=v; v=a+0.382*(b-a); end k=k+1 end end 4.2 函数曲线图程序如下: 如下曲线所得y值为负，前面（1*）已作解释。 x=0:0.1:2.5; y=-25*x+20*x.^2-4*x.^3; plot(x,y); 五、程序调试运行结果 5.1 如图所示： 当k执行5或7或10或12次时，均有x=0.8329时，有最大y=9.2593（函数中已做处理，变负为正，可以对照曲线图）。 1、高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳 万元，可使用的金属板有500t，劳动力有300人/月，机器有100台/月，此外，不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号为100万元，中号为150万元，大号为200万元，现在要制定一个生产计划，使获得的利润为最大， max=4*x1+5*x2+6*x3-100*y1-150*y2-200*y3; 2*x1+4*x2+8*x3<=500; 2*x1+3*x2+4*x3<=300; 1*x1+2*x2+3*x3<=100; @bin(y1); @bin(y2); @bin(y3); y1+y2+y3>=1; Global optimal solution found. Objective value: 300.0000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X1 100.0000 0.000000 X2 0.000000 3.000000 X3 0.000000 6.000000 Y1 1.000000 100.0000 Y2 0.000000 150.0000 Y3 0.000000 200.0000 Row Slack or Surplus Dual Price 1 300.0000 1.000000 2 300.0000 0.000000 3 100.0000 0.000000 4 0.000000 4.000000 5 0.000000 0.000000 铺路问题的最优化模型 摘要 本文采用了两种方法，一种是非线性规划从而得出最优解，另一种是将连续问题离散化利用计算机穷举取最优的方法。 根据A地与B地之间的不同地质有不同造价的特点，建立了非线性规划模型和穷举取最优解的模型，解决了管线铺设路线花费最小的难题。 问题一：在本问题中，我们首先利用非线性规划模型求解，我们用迭代法求出极小值（用Matlab实现），计算结果为总费用最小为748.6244万元，管线在各土层中在东西方向上的投影长度分别为15.6786km，3.1827 km，2.1839 km，5.8887km，13.0661km。然后，我们又用穷举法另外建立了一个模型，采用C语言实现，所得最优解为最小花费为748.625602万元，管线在各土层中在东西方向上的投影长度分别为15.70km,3.20km,2.20km,5.90km,13.00km。 问题二：本问题加进了一个非线性的约束条件来使转弯处的角度至少为160度，模型二也是如此。非线性规划模型所得计算结果为最小花费为750.6084万元，管线在各土层中在东西方向上的投影长度分别为14.4566km,4.3591km,2.5984km,6.5387km,12.0472km。遍历模型所得最优解为最小花费为750.821154万元，管线在各土层中在东西方向上的投影长度分别为14.10km,4.30km, 2.70km,6.70km,12.20km。 问题三：因为管线一定要经过一确定点P，我们将整个区域依据P点位置分成两部分，即以A点正东30km处为界，将沙土层分成两部分。非线性规划模型最小花费为752.6432万元，管线在各土层中在东西方向上的投影长度分别为21.2613km,3.3459km,2.2639km,3.1288km,2.4102km,7.5898km。遍历模型最小花费为752.649007万元，管线在各土层中在东西方向上的投影长度分别为21.30km,3.30km,2.30km,3.10km,2.40km,7.60km。 关键词：非线性规划逐点遍历穷举法 地图模型试题 ————————————————————————————————作者：————————————————————————————————日期： 2012年地图数据处理模型的原理与方法 1. 在空间数据库中，把大比例尺图形数据缩编成小比例尺，图形数据是按要素分 层的，各要素应采用什么模型确定选取指标? 2. 在空间数据库中，把大比例尺图形数据缩成编小比例尺，图形数据是按要素分 层的，各要素应采用什么模型进行具体的选取? 3. 确定河流选取程度的数学模型为21210b b x x b y ，式中，y 为河流选取程度， 1x 为资料图上单位面积河流条数，2x 为资料图上单位面积河流长度（河网密度），b 0、b 1、b 2为待定参数。试分析b 0、b 1、b 2意义和取值范围。 4. 以数据的分布特征进行分级的方法有哪几种模型？各适应什么情况？ 5. 试分析空间分布趋势模型与动态分析预测模型的异同点。 6. 论述采用模糊多层次评判数学模型建立空间数据质量评判模型的原理与方法。 u 1——指标的科学性和正确性 c 11——指标处理的合理性 c 12——指标与地图用途及使用对象的适应性 c 13——资料利用的合理性、充分性 u 2——表示方法的正确性 c 21——表示方法选择的正确性 c 22——图例设计的正确性 w 221——符号设计的正确性 A 2211——图形设计的正确性 A 2212——尺寸设计的正确性 A 2213——注记设计的正确性 w 221——色彩设计的正确性 w 223——图例设计的正确性与完备性 c 23——附图及统计图表设计的正确性 c 24——表示方法配合的合理性 c 25——表示方法的统一协调性 c 26——各种注记字体、字大配置的合理性、易读 性和统一协调性 u 3——地图精度 c 31——图幅选择设计的投影、比例尺的适应性 c 32——地图内容的位置精度 c 33——统计分级及符号的图解精度 u 4——地图现势性及反映动态情况 c 41——图上内容的现势性及保持现势性的可能性 c 42——历年变化情况的反映 c 43——预报预测的可能性 数学建模GPS 定位问题 摘要 本次建模中要解决根据GPS 卫星位置来确定GPS 信号接收机位置的问题，在本次建立的模型中主要用到的是点定位的数学模型，用码伪距进行点定位。再用Matlab 编程解得地点位置，最后转换成其经度和纬度。 对于问题一，我们采用GPS 定位中单点定位的方法(单点定位利用一点采集的观测数据和广播星历确定点的坐标)。题目中假定了卫星所在的空间位置是准确值因此不考虑广播星历。往往伪距方程解算的基本思路是将非线性观测方程进行Taylor 级数展开至一阶,忽略二阶及以上的高阶项,得到线性观测方程。我们将上 面的每两个非线性观测方程相减消去二阶及以上的高阶项可得到4 2C 个四元一次方程。在此基础上派生出64C 个线性方程组并用2222R i z i y i x =++ 进行验证选择最符合的坐标，得到四个地点在地心空间直角坐标系的坐标是(-2179,4373,4081) ； (-2174，3,4381，4090);(-2169，4410.1，4123);(-2159，4382.4，4142.3);再转换成经度和纬度就是(40:08:38.58167N ，116:10:14.01669E); (40:05:39.12131N ，116:23:48.72859E); (40:10:46.58408N ，116:11:20.90291E); (40:29:04.29791N ，116:13:23.03773E)然后再在地图上标出各个点的位置 对于问题二，由于添加了一个点，多出了一个数据，可以同样的继续采用上述方 法，只是每两个非线性观测方程相减消去二阶及以上的高阶项可得到5 2C 个四元 数学建模路线优化问题 选路的优化模型 摘要: 本题是一个有深刻背景的NPC问题，文章分析了分组回路的拓扑结构，并构造了多个模型，从多个侧面对具体问题进行求解。最短树结构模型给出了局部寻优的准则算法模型体现了由简到繁，确保较优的思想而三个层次分明的表述模型证明了这一类问题共有的性质。在此基础上我们的结果也是比较令人满意的。如对第一题给出了总长为599.9，单项长为216的分组，第二题给出了至少分四组的证明。最后，我们还谈到了模型的优缺点及推广思想。 一、问题描述 “水大无情，人命关天”为考察灾情，县领导决定派人及早将各乡（镇），村巡视一遍。巡视路线为从县政府所在地出发，走遍各乡（镇），村又回到县政府所在地的路线。 1.若分三组巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2.假定巡视人员在各乡（镇）停留时间为T=2小时，在各村停留时间为t =1 小 时，汽车行驶速度为V=35公里/时，要在24小时内巡视完，至少分成几组； 给出这种分组下你认为最佳的巡视路线。 3.上述关于T，t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多 少？给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 4.巡视组数已定（如三组）要求尽快完成巡视，讨论T，t和V改变时最佳路线 的影响（图见附录）。 二、问题假设 1、乡（镇）村只考察一次，多次经过时只计算一次停留时间。 2、非本县村不限制通过。 3、汽车的行驶速度始终一致。 三、符号说明 符号表示意义 Ti 第i 人走的回路Ti=vv i(i) v2(i)v n(i) Ti=00表示第i人在0点没移动 Vi Ti的点集Si Ti的长度 Hi(v) 在V上定义的特殊函数仅当V被第i 人走过且停留时 Hi(v)=1,否则为0 一. 管理科学的定义 管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策制定的一门学科. (1) 定量因素(2) 科学的方法(3) 辅助决策制定 二.用管理科学的方法解决问题的基本步骤. （1） 提出问题，并根据需要收录有关数据信息。管理科学工作者向管理者咨询、鉴别所 要考虑的问题以确定合理的目标，然后根据要求收集一些关键数据，并对数据作相应的分析。 （2） 建立模型，引入决策变量，确定目标函数（约束条件）。建模过程是一项创造性的 工作，在处理实际问题时，一般没有一个唯一正确的模型，而是有多种不同的方案。建模是一个演进过程，从一个初始模型往往需要不断的完善渐渐演化成一个完整的数学模型。 （3） 从模型中形成一个对问题求解的算法。要在计算机上运行数学程序对模型进行求 解，一般情况下能找到对模型求解的标准软件。例如，对线性规划问题已有Excel 、Cplex 、Lingo 等标准软件求解。有时要自己编写程序。 （4） 测试模型并在必要时修正。在模型求解后，需要对模型进行检验，以保证该模型能 准确反映实际问题，需要检验模型提供的解是否合理，所有主要相关因素是否已考虑，当有些条件变化时，解如何变化等。 （5） 应用模型分析问题以及提出管理建议。对模型求解并分析后，将相应的最优方案提 交给管理者，由管理者做出决策。管理科学工作者并不作管理决策，其研究只是对涉及的问题进行分析并向管理者提出建议。管理者还要考虑管理科学以外的众多因素才能做出决策。 （6） 帮助实施管理决策。建议被管理者采纳以后，一旦做出管理决策一般要求帮助监督 决策方案的实施。 新问题, 新模型, 新算法, 新应用. 三.优化问题的数学模型 1212max(min)(,, ,) (,,)0..1,2,n j n Z f x x x g x x x s t j m =≤?? =? 由于,j f g 是非线性函数时，此问题是非线性优化问题, 求解较复杂。我们主要讨论线性优化问题，常见的形式：混合整数规划 （1） max 0 0 Z CX hY AX GY b X Y =++≤≥≥取整数 其中111,,,,m n m p m n p A G b C h ?????，不失一般性，我们假定,,,,C h A G b 都是整数矩阵。 当0p =时，（1）为纯整数规划，当0n =时，（1）为线性规划。 工业中截断切割的优化设计 一摘要 本文讨论了加工业中截断切割的优化排序策略我们对于不同的切割 方式总数用穷举法得到720 种所可行解及其费用并对于原问题建立了决策 并对所给出的算法进行了分析和检验 1.当e=0时我归纳出解决问题的最优法则, 从而提出了将面间距统一成判断权重来作为排 序准则的算法,同时证明 了e = 0 的情况下根据这种最优准则能够实现题目所要求的优化目标 2.对于e 1 0 时我们提出了实用准则 最后我结合实际问题将本问题进行了拓展讨论了当最终产品(成品) 在毛坯(待加工长方体)中位置不预定时应如何实施加工方案以达到节省费用 和节约资源的目的,使我们的方案适用于更为广阔的领域 二问题的重述、 在工业生产中，常需要采取将物理一分为二的截断切割方式从一块长方体材料中切出一个小长方体，其加工费用取决于水平切割和垂直切割的截面面积，以及调整刀具时的额外费用。对本题所给出的问题我们首先面临的对加工次序的排序策略然后我们考虑当毛坯和产品位置不预定的时候如何采取策略以达到我们的优化目的 问题： 1> 需考虑的不同切割方式的总数。 2> 给出上述问题的数学模型和求解方法。 3> 试对某部门用的如下准则做出评价，每次选择一个加工费用最少的切割面进行切割。 4> 对于e=0 的情况有无简明的优化准则。 5> 用以下实例验证你的方法： 待加工长方体和成品长方体的长，宽，高分别为10，14.5,19 和3,2,4,两者左侧面，正面，底面之间的距离分别为6,7,5(单位为厘米，垂直切割费用为每平方厘米1 元，r 和e 的数据有 4 组： 1) r=1,e=0; 2) r=1.5,e=0; 3) r=8,e=0; 4) r=1.5, 2 ￡ e ￡15 ; 三模型的假设和符号说明 1 切割刀具为两个一个水平放置一个为垂直放置 2 目标长方体所在位置不与毛坯任一表面重合 3 水平方向只需平行移动水平刀具垂直方向只平行移动或调整后再平行 移动刀具因此调整费用e 是否付出仅取决于先后两次垂直切割是否平行而 不记是否穿插着水平切割 4毛坯与工作台接触的底面是事先指定的 §3.6 优化问题与规划模型 与最大、最小、最长、最短等等有关的问题都是优化问题。 解决优化问题形成管理科学的数学方法：运筹学。运筹学主要分支：（非）线性规划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论。 6.1 线性规划 1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》 1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论. 1. 问题 例1 作物种植安排 一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为 110元, 75元, 60元. 如何规划经营使经济效益最大. 分析：以取得最高的产值的方式达到收益最大的目标. 1. 求什么？分别安排多少亩地种蔬菜、棉花、水稻？ x 1亩、 x 2 亩、 x 3 亩 2. 优化什么？产值最大 max f=10x 1+75x 2 +60x 3 3. 限制条件？田地总量 x 1+x 2 +x 3 ≤ 50 劳力总数 1/2x 1 +1/3x 2 +1/4x 3 ≤ 20 模型 I : 设决策变量：种植蔬菜 x 1亩, 棉花 x 2 亩, 水稻 x 3 亩， 求目标函数 f=110x 1+75x 2 +60x 3 在约束条件x 1+x 2 +x 3 ≤ 50 1/2x 1 +1/3x 2 +1/4x 3 ≤20 下的最大值 规划问题：求目标函数在约束条件下的最值, 规划问题包含3个组成要素: 决策变量、目标函数、约束条件。 当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题, 否则称为非线性规划问题。 2. 线性规划问题求解方法 称满足约束条件的向量为可行解,称可行解的集合为可行域, 称使目标函数达最值的可行解为最优解. 命题 1 线性规划问题的可行解集是凸集. 因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸多边形。 命题2 线性规划问题的最优解一定在可行解集的某个极点上达到. 图解法：解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各极点处的值，经比较后，取最值点为最优解。 命题3 当两个变量的线性规划问题的目标函数取不同的目标值时，构成一族平行直线,目标值的大小描述了直线离原点的远近。 于是穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点即为取的极值的极点—最优解。 单纯形法 : 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解 案例16 停车场的优化设计 随着城市车辆的增加，停车位的需求量也越来越大，停车困难已逐渐成为市民们头疼的问题。要解决停车难问题，除了尽可能的增加停车场以外，对停车场进行优化设计也能在一定程度上缓解这一供需矛盾。停车场的优化设计就是在停车场大小确定的情况下，对停车区域进行优化设计，以便容纳更多的车辆。本文的目的就是希望分析一下这一情况，找出缓解停车困难的有效办法。 假设某公共场所附近有一块空地，如果不考虑建设地下或多层结构，我们该如何有效的设计停车位置呢？一般来说，想尽可能的把车塞进停车场，最好的办法就是以垂直停靠的方式将车一辆挤一辆地排成行，但是这样停放的后果就是车辆不能自由出入，只有后进入的车辆全部先出去了，先进入的车才可以离开停车场，显然不符合实际的需求。因而，为了使汽车能够自由地出入停车场，必须设立一定数量具有足够宽度的通道，并且每个通道都应该有足够大的“转弯半径”， 而通道越宽越多，就会使得容纳的车辆数越少。所以我们的问题就是要确定在满足车辆能够自由进出的实际需求下，如何进行停车位置和车行通道的设计，才能够停放更多的车辆，从而做到既方便停车又能获得最大的经济效益。 我们先来看看生活中非货运车辆大小的种类。根据实际调查和经验数据，这类车辆一般可分为小轿车，中型客车和大型客车三类。其中小轿车约占九成，大型客车约占一成，而中型客车一般不多于1%。根据这样的情况，我们可以免去对中型客车的车位设计，即便有中型客车停车的需要，可以使用大型车的车位，这也符合现实生活中绝大多数停车场的车位设计情况。我们设小轿车所占的比例为0.9α=,大型客车所占的比例为10.1α-=，当然现实中也有不少全为小轿车设计的停车场，例如小区的地下车库。 再来看看车位的大小。根据实际的调查，城市内比较普通的小轿车长度一般不超过4.7米，宽度一般不超过1.7米，而一般大型客车长度不超过12米，宽度不超过2.2米。另外，经实际考察可知，停车场中标志线的宽度大约为0.1米，所以我们可以假设停车场中停放轿车需要的车位长5L C =米，宽 2.5W C =米，这其中包括了0.1米的标志线宽度和至少0.3米的汽车间的横向间距。设停放大客车需要长12.5L B =米，宽3W B =米，其中包括0.1米的标志线宽度和必要的汽 一、判断题 1. 比例尺、地图投影、各种坐标系统就构成了地图的数学法则。Y 2. 地图容纳和储存了数量巨大的信息，而作为信息的载体，只能是传统概念上的纸质地图。 3. 地图的数学要素主要包括地图投影、坐标系统、比例尺、控制点、图例等。 4. 实测成图法一直是测制大比例尺地图最基本的方法。Y 5. 磁坐偏角指磁子午线与坐标纵线之间的夹角。以坐标纵线为准，磁子午线东偏为负，西偏为正。） 6. 一般情况下真方位角（A）、磁偏角（δ）、磁方位角（Am）三者之间的关系是A=Am+δ。 8. 城市规划、居民地布局、地籍管理等需要以小比例尺的平面地图作为基础图件。 10.方位角是由标准方向线北端或者南端开始顺时针方向到某一直线的夹角。 11.地球体的数学表面，也是对地球形体的二级逼近，用于测量计算的基准面。Y 12.在地图学中，以大地经纬度定义地理坐标。Y 13.在地理学研究及地图学的小比例尺制图中，通常将椭球体当成正球体看，采用地心经纬度。Y 14. 1987年国家测绘局公布：启用《1985国家高程基准》取代《黄海平均海水面》，其比《黄海平均海水面》下降29毫米。 15. 球面是个不可展的曲面，要把球面直接展成平面，必然要发生断裂或褶皱。Y 16.长度比是一个常量，它既不随着点的位置不同而变化，也不随着方向的变化而变化。 17.长度变形没有正负之分，长度变形恒为正。 18. 面积变形有正有负，面积变形为零，表示投影后面积无变形，面积变形为正，表示投影后面积增加；面积变形为负，表示投影后面积缩小。Y 19. 制1：100万地图，首先将地球缩小100万倍，而后将其投影到平面上，那么1：100万就是地图的主比例尺。Y 20.在等积圆锥投影上中央经线上纬线间隔自投影中心向外逐渐增大。 21. 无论是正轴方位投影还是横轴方位投影或是斜轴方位投影，他们的误差分布规律是一致的。Y 22. 等角正轴切圆柱投影是荷兰地图学家墨卡托于1569年所创，所以又称墨卡托投影。Y 23. 等积投影的面积变形接近零。Y 25. 按基本等高距的二分之一高程绘出的等高线称为助曲线。 26. 经线在任何球心投影中的表象都是直线。Y 27. 一般情况下，等角航线是与所有经线相交成相同方位角的大圆弧线，它在圆柱投影上的表象是直线。 28. 不同地点的磁偏角是不相同的，同一地点的磁偏角是相同的。 29. 水准面有无数个，而大地水准面只有一个。Y 31. 等角航线是地球面上两点间的最短航线。 34.目前我国各地高程控制点的绝对高程起算面是1956黄海平均海水面。 35. 磁偏角只随地点的不同而不同。 36. 地图比例尺是决定地图概括数量特征的主要因素。Y 37. 地图的内容受符号的形状、尺寸、颜色和结构的直接影响，并制约着概括程度和方 楚雄师范学院 2011年数学建模培训第二次测试论文 题目玩转云南之旅游路线优化模型 姓名李雯刘正权叶万颂 系（院）数学系 专业信息与计算科学 2011年5月15日 一、摘要 云南风光旖旎，四季如春，是旅游的天堂。本论文就是以到云南旅游的交通方式以及路线选择为背景，通过构建模型。实现以经济的方式玩转云南的各大旅游景点。 旅游的交通方式一般有自驾游览和乘坐公共交通工具两种方式。本论文通过比较用公共交通出行方式下所有旅游路线的费用，得出最佳的旅游路线。 为了方便进行进行比较，文中引入了带权图和最小生成树的模型，为比较提供了可以参考的标准，模型中既要考虑路线最短，又要在规定的时间范围完成旅程,且通过预订旅游近点数最多，费用较少。 该模型以云南各大旅游景点为带权图的点，以采用交通方式来进行旅游过程中在具体的两个旅游景点的途中花去的费用为权值，这样，在该种旅游方式下的花费就是各对应的权值之和。当然，选择了公共交通的旅游方式，可能走的旅游路线也不尽相同。这样就产生了同一个旅游方式下的多条路线费用的比较，通过比较大小，就得到了较为经济的相应旅游方式下的最佳路线了。 本文作者充分调查了云南省目前的各种交通方式的收费情况，并查找了相关的旅游路线，有利地确保了论文的真实性和可靠性。 关键字：最小生成树、最佳路线、时间、路程。 二、问题 某旅客携带着家人想到云南旅游观光，并且想玩遍云南的各大旅游景点。请为这一行旅客设计旅游路线，并为他们提供一个合理的旅游交通方式的建议。 三、符号说明 把各景点用数据代替如下： 昆明市⑴楚雄市⑵大理市⑶丽江市⑷香格里拉⑸怒江⑹保山⑺德宏⑻临沧⑼ 普洱市⑽西双版纳⑾玉溪市⑿红河⒀文山市⒁石林⒂曲靖⒃昭通⒄ 权值表示景点之间的车票价 1.地图的定义 地理环境诸要素（内容）按照一定的数学法则、运用符号系统、并经过制图综合（特征）的一种缩小表像（形式）以表达各种自然和社会现象的数质量特征及空间分布和发展变化（目的、结果）。 2.地图的基本特征 地图必须遵循一定的数学法则（可测量性、可比性）；地图必须经过科学制图综合（清晰性、一览性）；地图具有完整的符号系统（直观性、易读性）；地图是地理信息的载体（传递性、持久性）。 3.地图的基本内容 数学要素（骨架）：地图坐标、投影、比例尺、控制点等 地理要素（主体）：表达地理信息的各种图形，文字标记 辅助要素（润滑剂）：说明地图的编制情况，为应用提供相关内容，在主要图形的外侧，如图名、图号、图例、比例尺等；对主要图件在内容和形式上的补充，如统计图表、剖面图、测图时间、出版单位等 4.地图的分类 按比例尺分：-大比例尺地图（≥1:10万）-中比例尺地图（1:10万~1:100万）-小比例尺地图（≤1:100万）-微缩地图 按地图的图形内容分类：-普通地图（是指以相对平衡的程度表示地表最基本的自然和人文现象的地图。）-专题地图（是根据专业的需要，突出反映一种或几种主题要素的地图，其中，作为主题的要素表示得很详细，其他的要素则围绕表达主题的需要，作为地理基础概略表示。） 5.图幅编号 a=[φ/4°]+1 φ纬度；b=[λ/6°]+31 λ经度1:1万(G) 1：5000(H) c=4°/△φ-[(φ/ 4°)/△φ] △φ图幅纬差2′30″1′15″ d=[(λ/6°)/ △λ]+1 △图幅经差3′45″1′52.5″ X1X2X3 X4 X5X6X7 X8X9X10 λ0=(X2X3-31)*6°φ0=(X1-1)*4° λ=λ0+(X8X9X10-1)* △λφ=φ0+(4°/△φ-X5X6X7)* △φ 6.现代地图学体系 地图学的定义是以地图信息传递为中心的，探讨地图的理论实质、制作技术和使用方法的综合性科学 ┏理论地图学（地图学理论基础）~地图信息、传输、模式、认知理论；地 图可视化原理、数学制图原理、地图语言学（地图符号学）、地图感受理 论、地图概括（制图综合）理论、综合制图理论、地学信息图谱理论 现代地图学╋地图制图学（地图编制方法与技术）~普通地图制图学、专题**、遥感制图学、计算机制图学、地图印制学与计算机出版系统、多媒体电子地图与 网络地图设计和制作 ┗应用地图学（地图应用原理与方法）~地图功能、评价、分析与研究方法、 使用方法、信息自动分析和处理系统、应用、数字地图应用 7. 大地水准面：一个与静止的平均海水面相重合，并假想其穿过大陆、岛屿形成一个闭合曲面。（水准面的特点：面上任意一点的铅垂线都垂直于该点的曲面） 地球椭球面：人们假想，可以将大地体绕短轴（地轴）飞速旋转，就能形成一个表面光滑的球体，即踢球椭球体。其表面可用数学模型定义和表达称为地球椭球面。 在手机普遍流行的今天，建设基站的问题分析对于运营商来说很有必要。本文针对现有的条件和题目的要求进行讨论。在建设此模型中，核心运用到了0-1整数规划模型，且运用lingo 软件求解。 对于问题一： 我们引入0-1变量，建立目标函数：覆盖人口最大数=所有被覆盖的社区人口之和，即max=15 1j j j p y =∑，根据题目要求建立约束条件，并用数学软件LINGO 对其模型求解，得到最优解。 对于问题二： 同样运用0-1整数规划模型，建立目标函数时，此处假设每个用户的正常资费相同，所以68%可以用减少人口来求最优值，故问题二的目标函数为：max=∑=15 1j j j k p 上述模型得到最优解结果如下： 关键字：基站; 0-1整数规划；lingo 软件 1 问题的重述．．．．．．．．．．．．．．．．．．．．．．．．．3 2 问题的分析．．．．．．．．．．．．．．．．．．．．．．．．．4 3 模型的假设与符号的说明．．．．．．．．．．．．．．．．．．．5 3.1模型的假设．．．．．．．．．．．．．．．．．．．．．． 5 3.2符号的说明．．．．．．．．．．．．．．．．．．．．．． 5 4 模型的建立及求解．．．．．．．．．．．．．．．．．．．．．. 5 4.1模型的建立．．．．．．．．．．．．．．．．．．．．．． 5 4.2 模型的求解．．．．．．．．．．．．．．．．．．．．．． 6 5 模型结果的分析．．．．．．．．．．．．．．．．．．．．．．．7 6 优化方向．．．．．．．．．．．．．．．．．．．．．．．．．．7 7 参考文献．．．．．．．．．．．．．．．．．．．．．．．．．．8 8、附录．．．．．．．．．．．．．．．．．．．．．．．．．．． 9数学建模优化问题经典练习
数学建模铺路问题的最优化模型
地图模型试题
GPS定位问题数学建模
数学建模路线
优化问题的数学模型
数学建模截断切割的优化设计
优化问题与规划模型
数学建模案例_停车场的优化设计(1)
习题 答案《地图学原理与方法》地图制图学
旅游路线的优化模型
《地图学原理》知识点整理
数学建模课程设计——优化问题
相关主题
文本预览