数学建模第二轮缴费站设置问题.docVIP

缴费站设置问题 摘 要 本文解决的是,再运用相关图论知识分别对每个问题进行分析建立了相应的求解模型. 对于问题一:Lingo软件求出11.71181百米. 对于问题二:一个线性规划的模型二求解过程对于问题: 我们定义衡量分组是否均衡的均衡度,以巡视的总路程最短作为目标函数建立最佳巡视路线模型,结合矩阵翻转法求出这种分组的最佳H圈进而得到这个问题的近似最优解.此后,我们再将结果进行修正得到均衡度更小的最优解,详见下表: 表: 问题的求解结果W─C─T─V─Q─R─Q─D─S─A─X─W 117 340 Ⅱ W─B─I─P─I─G─W 113 Ⅲ W─F─L─Y─H─K─M─N─J─U─E─F─W 110 关键词:1. 问题重述 .1问题背景: 某城市共有24个社区,各社区的人口数及道路之间连接各不相同,为了便于社区居民缴纳煤气费,煤气公司拟建三个煤气缴费站;为了方便市公安局的治安管理,拟建若干派出所,并为其分配不同的管辖区;社区W是市政府所在地,市领导需要从此出发分三组巡视所有社区. 1.2题目所给信息: 题中给出了24个社区相应的人口数(参见表2)及各社区的的道路连接图(参见图1) 表: 各社区的人口数(单位: 千人) 编号 A B C D E F G H I J K L 人口 10 12 18 6 10 15 4 8 7 11 13 11 编号 M N P Q R S T U V W X Y 人口 11 8 9 22 14 8 7 10 15 28 18 13 图1: 各社区的的道路连接图 (注: 横线上的数据表示相邻社区之间的距离,单位: 百米) 1.3本文需解决的问题有: 问题一: 问题二:问题: 市领导从W区出发分三组巡视社区,如何安排巡视路线可以最快完成巡视？ 2. 模型的假设与符号说明 2.1模型的假设 假设: 煤气缴费站建在某个社区时,该社区所有地方到该缴费站的距离为0; 假设: 路况良好,警车车速保持稳定,不会出现抛锚等现象; 假设4: 不考虑巡视时在各社区的停留时间; 假设5: 每个小组的汽车行驶速度完全一样. 2.2符号说明 符号 符号说明 社区依字母顺序的编号 第个个社区间的公路长(与的定义相同) 第个个社区的最短路径长 第个个社区缴费,0-1变量 第 第个社区的总人数 居民到最近缴费站的平均距离 所需派出所的个数 派出所是否建在第 第个个社区所在的派出管辖,0-1变量 第个社区所在的派出所所需的警力 该城区所需的总警力 第三个问题中第种分组的均衡度 问题中的原加权图 原图中的顶点集 顶点集的划分 分成的第个生成子图 的导出子图中的最佳巡视回路 最佳巡视回路的权 3. 问题分析 在,每个社区看作图中的一个节点,各社区间的公路看作图中对应的边,公路的长度看作对应边上的权,这就是题目给出的社区间的加权网络图.在解决社区的煤气缴费站和派出所选址问题及最佳巡视路线问题时,可以转化为图中总权(时间或距离)最小问题来求解.所以,社区之间的公路连接图并没有直接作用,所以我们根据题目中的道路连接图用Floyd算法求出每两个社区的最短路径,以供解决下面的问题使用. 针对问题一:等于社区居民到最近缴费站的距离乘以该社区居民总数之和除以城市总人数,这即为问题的目标函数.又考虑到每个社区只到一个缴费站缴费,我们用0-1变量来表示某社区是否到某缴费站缴费.同样,为了确定三个缴费站建在哪三个社区,我们用0-1变量来表示缴费站是否建在该社区.通过分析,可以得出这两个0-1变量的约束条件.建立一个线性规划的模型.再和题目给出的人口数等数据代入该线性规划模型利用Lingo软件求出. 针对问题二:.这同样也是最优选址问题,相对问题一,它只是所需选址的个数未知,然后有距离的具体约束,其他条件与要求与问题一基本一致.因此,作为最终选址的标准,所以可以直接将模型一的目标函数改为派出所的个数的最小值,约束条件做相应变化,同样是有两个0-1变量和,这样即可建立另一个线性规划的模型二.其求解过程. 针对问题: 此问题是多个推销员的最佳推销员回路问题,要分三组最快完成巡视可以看做是要设计总路程最短且各组尽可能均衡的巡视路线.首先,我们将原图视为关于社区的加权图.那么,该问题就是在加权图中求顶点集的划分,将分成个生成子图,使其满足相应的约束条件.定义: 该分组的均衡度=(子回路的最大权值-子回路的最小权值)÷子回路的最大权值,限制每种分组求解结果的均衡度均比前一次的小,最后以巡视的总路程最短作为目标函数.这样建立的模型为非线性规划模型,我们采用此方法得到的是问题的近似最优解,此后,我们再将结果进行修正得到问题的最优解. 4. 数据分析 图2: 各社区的人