《校园最佳游览路线问题的数学模型分析.(定稿).doc》由会员分享，可在线阅读，更多相关《校园最佳游览路线问题的数学模型分析.(定稿).doc（8页珍藏版）》请在三一文库上搜索。
1、校园最佳游览路线问题的数学模型分析廖川荣( 南昌大学数学系 , 江西南昌 330031) 摘要 将某高校的校园示意图转化为赋权连通图 , 求得该连通图的邻接矩阵 , 利用 Floyd 算法及图论软件包构造一个最短路径矩阵 , 得到一个赋权完全图 , 将求校园最佳游览路线问题归结为图论中的最佳推销员回路问题 , 建立混合整数线性规划模型 , 并利用优化软件求得最优解 . 从而解决了校园开放日游览计划中提出的关于校园最佳游览路线和校园游览车最优配置问题 . 关键词 赋权完全图；最佳游览路线；最优配置 . 中图分类号 O157.6 文献标识码 A 文章编号 911361 引言现在国内许多高校每年都会
2、定期举办校园开放日 , 开放日旨在全面展示该校的办学特色及优美的校园环境 , 反映大学生丰富多彩的校园生活 . 通过举办开放日 , 为考生填报高考志愿提供全面真实和具体的信息 , 让考生和家长了解学校的历史和现状 , 熟悉招生政策 , 在大学和考生之间建立一个友好顺畅的交流沟通平台 .某高校开放日 , 将会有许多考生及家长要求参观该校的新校园 , 以下为校园简化示意图 :( 其中 vi 为参观者需参观的主楼、景点和场地 , 连线为两参观点间道路 , 连线上数字为两参观点间距离，单位 : 公里)图 1: 校园简化示意图说明: V1医学院教学大楼 , V2 本科生公寓 A 区, V3学生食堂 A,
3、 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,
4、V31外经楼 ,V32 学工楼 , V33 艺术楼 , V34 商业街, V35校医院 , V36本科生公寓 C 区, V37学生食堂 C, V38 体育馆 , V39 体育场 , V40 游泳馆 , V411运动场B.校方拟在本校高年级学生中招募一批临时导游 ,负责接待并陪同考生及家长乘坐校园游览车（限载50 人,时速 20 公里 / 小时）参观游览新校园 , 路线是从新校园正大门出发, 最后返回到出发地 .为了向所有参观者展示该校的风貌和亮点 , 同时满足参观者了解校园的不同要求 , 校方要求应聘者提供一份详细的校园游览计划 ,计划中应包括以下内容 :1）根据考生的理、文、工、医四种报考专
5、业为参观者选择下车参观的主楼、景点和场地 .2）根据校园简化示意图及问题 1 确定的下车参观的主楼、景点和场地 , 建立数学模型 , 按报考专业分别设计4 条不同的最佳游览路线, 使每条游览路线的总路程最短 .3）假设有 3000 本省考生及 1000 外省考生想在开放日这天参观游览该校的新校园；且根据历年统计，开放日上午参观人数约为全天参观人数的 60%.问该校开放日至少要预备多少辆校园游览车 ?2 模型假设1) 不同报考专业的参观者总是更有兴趣参观与本专业有关的主楼、 景点或场地 ,导游通过指示牌来引导报考不同专业的考生及家长乘坐不同路线的游览车 .2) 道路通畅, 游览车只在选定参观点仃
6、车, 每个参观点只参观一次 .3)对相同性质的楼群只参观一栋有代表性的主楼 .4) 不考虑天气等环境因素的影响 .5) 校园游览车限载50 人,时速 20 公里 / 小时.6) 参观者参观选定的主楼、景点与场地的时间均为5 分钟.7) 在开放日这天有 3000 本省考生及 1000 外省考生想参观游览该校的新校园 .8) 不考虑参观者上下车时间.9) 开放日工作时间为上午 8:00-12:00, 下午 1:00-17:00.10) 根据历年统计, 校园开放日上午参观人数约为全天参观人数的 60%.11）将各主楼、景点或场地看作平面上的质点 , 不考虑自身形状的大小 , 均称之为图论中的结点。3
7、 符号说明vi: 参观者需参观的主楼、景点和场地 . i 1, 2, , 41d v ,v ：两参观点 vi 与 vj 之间的路程 . i , j 1, 2, , 41i jd , min d v , v : 两参观点 vi 与 vj 之间的最短路程 . i, j 1, 2, , 41i j i jDk：第 k 条游览路线的最短路径矩阵( Floyd 矩阵).D d ，其中 nk 表示第 k 条游览路径( )k i , j n nk k中的参观点数 . (n1 =15, n2 =17, n3 =19, n4 =12)x(vi, vj): 代表游览路径中两参观点间的特征变量 . 当 vi 与 v
8、j为最佳游览路线上两个相邻的需下车参观的景点时x(vi, vj)=1, 反之 , x(vi, vj)=0. ( i, j= 1,2, ,41)Pi: 参观者乘游览车游览第 i 条路线的概率 . (i=1,2,3,4)Ri: 第 i 条游览路线上参观游览的人数 . (i =1,2,3,4)2Si : 第 i 条游览路线起点发车速率 . (i =1,2,3,4)Ti : 游览车在第 i 条路线行驶一圈所需时间 . (i=1,2,3,4)Ni : 第 i 条游览路线需要预备的最低校园游览车数 . (i=1,2,3,4)N: 校方需要预备的最低校园游览车数 . (N= N1 + N2 + N3 + N
9、4 )M: 在开放日这天想参观游览该校新校园的本省及外省考生的总人数 .(M =4000)4 模型建立与求解4.1 选择参观者下车参观的主楼、景点和场地校园开放日活动是社会各界认识了解高校的一个重要窗口 , 是加强学校与社会联系的一个重要途径 ,是提升高校社会影响力 , 发挥高校在科学技术领域中引领作用的重要措施 , 高校应在开放日向参观者充分展现该校的风貌和亮点 . 如: 基础教学设施 , 医疗卫生设施 , 体育运动设施 , 亮点建筑和人文景观 , 同时还应考虑到参观者了解校园的不同要求 . 为此 , 根据考生的理、文、工、医四种报考专业为参观者选择下列需下车参观的主楼、景点和场地 .1)
10、理科路线参观点 : v10正门 , v16 办公楼 , v17 中心广场 , v18 图书馆 , v14 基础实验大楼 , v19 计算机实验中心, v21 理科生命大楼 , v30 学生食堂 B, v29 综合教学楼 , v32 学工楼 , v34 商业街 , v36 本科生公寓 C 区, v35 校医院, v41 运动场 B, v24 正气广场 . (n1=15)2） 文科路线参观点 : v10 正门 , v16 办公楼 , v17 中心广场 , v18 图书馆 , v19 计算机实验中心 , v25 人文楼 , v27法学楼 , v31 外经楼 , v29 综合教学楼 , v30 学生食
11、堂 B, v32 学工楼 , v34 商业街 , v33 艺术楼 , v35 校医院 , v36 本科生公寓 C 区, v41 运动场 B, v24 正气广场 . (n2=17)3） 工科路线参观点 : v10 正门, v16 办公楼 , v17 中心广场 , v18 图书馆 , v11 工程实验楼 , v14 基础实验大楼 ,v19 计算机实验中心 , v22 材料楼 , v23 环境楼 , v26 信工楼 , v28 机电楼与建工楼 , v30 学生食堂 B, v29 综合教学楼 ,v32 学工楼 , v34 商业街 , v35 校医院 , v36 本科生公寓 C 区, v41 运动场 B
12、, v24 正气广场 . (n3=19)4） 医科路线参观点 : v10 正门 , v16 办公楼 , v17 中心广场 , v18 图书馆 , v6 医学实验大楼 , v5 白求恩广场 , v9运动场 A, v3 学生食堂 A, v2 本科生公寓 A 区, v1 医学院教学大楼 , v4 国际学术交流中心 , v24 正气广场 .(n4=12)4.2 设计 4 条不同的最佳游览路线1） 最短路径矩阵将校园示意图转化为赋权连通图 G(V , E):v , v E, v ,v d v ,v .i j i j i j求得该连通图的邻接矩阵 , 并利用 Floyd 算法及图论软件包构造一个最短路径矩
13、阵 (Floyd 矩阵), 得到一个赋权完全图' , 'G V E ,1其中 E中每条边的权等于结点 vi 与 vj 在图 G(V , E)中的最短路径的权 :' 'v ,v E , v ,v d min d v , v .i j i j i, j i j根据问题 1 确定的理、文、工、医 4 个报考专业 , 分别得到 4 个赋权完全子图的最短路径矩阵。3例如医科路线的 Floyd 矩阵为 :D d =4 ( i , j )12 120.00 0.40 0.65 0.90 0.80 0.60 1.35 1.25 1.00 0.60 0.40 0.900.40 0
14、.00 0.25 0.50 1.20 1.00 1.75 1.65 1.40 1.00 0.80 0.500.65 0.25 0.00 0.25 1.40 1.25 1.60 1.85 1.60 1.25 1.05 0.750.90 0.50 0.25 0.00 1.15 1.35 1.35 1.60 1.35 1.50 1.30 1.000.80 1.20 1.40 1.15 0.00 0.20 0.55 0.45 0.20 0.40 0.40 1.700.60 1.00 1.25 1.35 0.20 0.00 0.75 0.65 0.40 0.20 0.20 1.501.35 1.75 1
15、.60 1.35 0.55 0.75 0.00 0.30 0.60 0.95 0.95 2.251.25 1.65 1.85 1.60 0.45 0.65 0.30 0.00 0.30 0.70 0.85 2.151.00 1.40 1.60 1.35 0.20 0.40 0.60 0.30 0.00 0.40 0.60 1.900.60 1.00 1.25 1.50 0.40 0.20 0.95 0.70 0.40 0.00 0.20 1.500.40 0.80 1.05 1.30 0.40 0.20 0.95 0.85 0.60 0.20 0.00 1.300.90 0.50 0.75 1
16、.00 1.70 1.50 2.25 2.15 1.90 1.50 1.30 0.00;2） 最佳游览路线求解2求考生理、 文、工、医四种报考专业的最佳游览路线问题可归结为图论中的最佳推销员回路问题 ,3即在 4 个赋权完全子图中分别求一个近似最优的 Hamilton 圈, 该最优 H 圈问题可用以下两种方法求解：4方法一：二边逐次修正法 .（1）输入图' , 'G V E 的一个初始圈 ;（2）用对角线完全算法产生一个初始 H圈;（3）随机搜索出 G中若干个 H圈, 例如2000个 ;（4）对第 1、2、3步所得的每个 H圈, 用二边逐次修正法进行优化 , 得到近似最佳 H圈
17、;（5）在第 4步求出的所有 H圈中, 找出权最小的一个 , 此即要找的最佳 H圈的近似解 .5 方法二：混合整数线性规划模型 .nminZ d xij iji , j 1nst . x 1, j 1, 2,. niji 1nx 1, i 1, 2,. nijj 1u u nx n 1, 2 i j ni j ijx 0,1 i , j 1, 2,. niju 0 i 2, 3,. ni说明: 约束条件n nx j n x i n 只是该线性规划模型中的两个必要约束条件 ,1, 1,2,. , 1, 1,2,. .i .j i.ji 1 j 14而 约 束 条 件 1, ( 2 ) u u n
18、 x n i j 是n 为 避 免 产 生 子 巡 回 而 附 加 的 充 分 约 束 条 件 , 其 中 i j i ju i 2 , 3, n 可看作 n-1 个额外的变量 . 可以证明 : 任何含子巡回的路线都不满足该约束条件 , 全部巡回路线i都满足该约束条件 .求解结果如下 ( 不加括号为下车参观点）：（1）理科最佳游览路线 : v10(v16)v24(v31)v29v35(v36)v41v36v34v32v30(v28)(v26)(v22)v21(v19)v14v19v18v17v16v10, 共有 n1=15 个下车参观点 ; 最短游览路程： 5.900000（公里） .（2）文
19、科最佳游览路线 : v10v16v24v25v27v29v31v33(v39)v35(v36)v41v36v34v32v30(v28)(v26)(v22)(v21)v19v18v17(v16)v10，共有 n2=17 个下车参观点；最短游览路程：6.300000 （公里） .（3）工科最佳游览路线 : v10(v16)v24(v31)v29v35(v36)v41v36v34v32v30v28v26v22v23(v22)(v21)(v19)v14v11(v14)v19v18v17v16v10, 共有 n3=19 个下车参观点；最短游览路程： 6.800000 （公里） .（4）医科最佳游览路线
20、: v10v4v1v5v6v2v3(v7)v9(v8)(v11)(v14)(v19)v18v17v16v24(v16)v10, 共有 n4 =12 个下车参观点；最短游览路程： 5.050000 （公里） .3) 计算校方开放日需要预备的最低校园游览车数由问题假设 , 开放日将有 3000 本省考生及 1000 外省考生及其家长参观游览该校的新校园 , 参观者总数为 M= 4000;开放时间为上午 8:00-12:00 下午 13:00-17:00. 参观者按问题 2 确定的 4 条最佳游览路线分别参观游览新校园。根据历年校园开放日的人数统计 , 开放日上午参观人数约为全天参观人数的 60%.
21、因此，开放日上午将有 0.6 × M 人参观游览新校园 , 下午有 0.4 × M 人参观游览新校园 ; 校方开放日上午需要预备的最低校园游览车数可根据开放日上午参观游览的人数计算 .具体计算过程如下：n（1） 参观者游览第 i 条路线的概率 : iPi 4.nii=1（2）第 i 条路线上参观游览的人数 : Ri =0.6 × M× Pi （人） .（3）第 i 条路线起点发车速率 : 1 /RiS 辆 hi游览车限载人数 上午参观游览时间.游览路线的最短路程（4）第 i 条路线游览一圈所需时间 : ,T n h参观点的参观时间 i i游览车行驶速度（
22、5）第 i 条路线上最低游览车数 : Ni=Si× Ti（辆） .（6）开放日上午校方需要预备的最低校园游览车数： N= N1 + N2 + N3 + N4 .55 结果根据以上公式可算出 : 该高校开放日上午往返循环行使的校园游览车辆数为： 理科游览路线 4 辆, 文科游览路线 6 辆, 工科游览路线 7 辆, 医科游览路线 3 辆，开放日上午需要预备的最低游览车数为 20 辆.同理可算出开放日下午往返循环行使的校园游览车辆数为： 理科游览路线 3 辆, 文科游览路线 4 辆,工科游览路线 5 辆, 医科游览路线 2 辆, 开放日下午需要预备的最低游览车数总共为 14 辆.由于开放
23、日上午参观的人数多于下午的人数 , 校方开放日上午需要预备的最低游览车数也为全天所需要最低车辆数 . 因此, 校方校园开放日需要预备的最低游览车数为 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
24、韩中庚 . 数学建模方法及其应用 M. 北京: 高等教育出版社 ,2005,6: 185-188Mathematical model Analysis about the best route of tourist in campusLiao 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
25、matrix is gotten. Theshortest path matrix is constructed and a completed graph with weight is gotten by Floyed arithmetic and the software package ofgraph. The best tourist route of campus problem is regarded as TSP problem, i.e., find the best similar Hamilton circle in thecompleted graph with weig
26、ht. 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.6