参赛编码 (由组委会填写) 第三届重庆人字宄生数学建模大赛 题目信息采集设备的布置问题 学院 汽车工程学院 姓名 学号 电话 刘巧斌2014071321088304070 队员信息 邹桃|2014070212913290060867 犹佐龙20140702049t136483417455 竞赛题目 信息采集设备的定位问题 摘要 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
参赛编码 （由组委会填写） 第三届重庆大学研究生数学建模大赛 题 目信息采集设备的布置问题 学院 汽车工程学院 姓名 学号 电话 刘巧斌 20140713210 18883724070 邹桃 20140702129 13290060867 队员信息 犹佐龙 20140702049t 13648347455 竞赛题目： A 题 信息采集设备的定位问题 摘 要 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
信息采集是进行数据分析的基础,而信息采集设备的合理布置,对于数据采集的质量和 效率有有重要的意义。以重庆大学A区为例,对校园的主要道路和建筑物进行拓扑简化, 在此基础上,分析人群在校园内的活动特征,通过大数定理,获得校园不同建筑物人群 的活动热点图;建立不同建筑物之间的人口转移概率矩阵,并分析校园内主要道路的流 量情况;以学生一天早高峰出行路径的获取为例,建立摄像头布置的数学模型,以尽可 能多监控学生活动为目标,通过0-1规划确定10个摄像头的合理布置位置;最后,以摄 像头安装数量为变量,通过多项式数据拟合方法获得为获得人群的理论完全覆盖活动轨 迹必须使用的最小摄像头数量。本文的研究可为类似信息采集设备的布置提供依据,有 一定的理论意义和实际利用价值。 关键词:信息采集设备布置;大数定理;人口转移概率矩阵;0-1规划; 多项式拟合 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
信息采集是进行数据分析的基础，而信息采集设备的合理布置，对于数据采集的质量和 效率有有重要的意义。以重庆大学A区为例，对校园的主要道路和建筑物进行拓扑简化， 在此基础上，分析人群在校园内的活动特征，通过大数定理，获得校园不同建筑物人群 的活动热点图；建立不同建筑物之间的人口转移概率矩阵，并分析校园内主要道路的流 量情况；以学生一天早高峰出行路径的获取为例，建立摄像头布置的数学模型，以尽可 能多监控学生活动为目标，通过0-1规划确定10个摄像头的合理布置位置；最后，以摄 像头安装数量为变量，通过多项式数据拟合方法获得为获得人群的理论完全覆盖活动轨 迹必须使用的最小摄像头数量。本文的研究可为类似信息采集设备的布置提供依据，有 一定的理论意义和实际利用价值。 关键词：信息采集设备布置；大数定理；人口转移概率矩阵；0-1 规划； 多项式拟合 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
目录 问题重述 问题背景 1.2目标任务 模型假设 三、符号说明 四、模型建立与求解 2 4.1问题一模型建立与求解… 4.2问题二模型建立与求解 4.3问题三模型建立与求解. 10 五、模型的检验 六、模型的评价 参考文献 附录 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
目 录 一、问题重述 ........................................................ 1 1.1 问题背景................................................................ 1 1.2 目标任务................................................................ 1 二、模型假设 ........................................................ 1 三、符号说明 ........................................................ 1 四、模型建立与求解 .................................................. 2 4.1 问题一模型建立与求解.......................................................................................................... 2 4.2 问题二模型建立与求解.......................................................................................................... 6 4.3 问题三模型建立与求解........................................................................................................ 10 五、模型的检验 ..................................................... 15 六、模型的评价 ..................................................... 16 参考文献 ........................................................... 16 附录 ............................................................... 18 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
问题重述 1.1问题背景 信息采集设备的布置直接影响信息采集的质量和效率,不合理的布置不仅造成资源 的浪费,更影响信息的获取。因此,对信息采集设备的布置问题进行深入研究很有必要。 1.2目标任务 信息采集是进行数据分析的基础,而信息采集设备的布置关系到所收集数据的质量 和效率。比如一些传感设备的布置问题、摄像装置的布置问题等 为简单起见,以我们学校A区校园为例,研究下面的问题 (1)根据地图确定我们学校校园的主要道路和主要建筑的位置。分析人群一天的主要 活动特征结合我校基本数据,得到我校活动热点图。 (2)在上述硏究的基础上,分析主要道路的流量情况。 (3)现在有一批摄像头(10个)需要安装在适当的位置,使得通过这些摄像头得到的 视频能够确定尽可能多的人的活动轨迹。 二、模型假设 1)不考虑车辆仅考虑步行 2)根据真实校园地图,对校园主要建筑物和道路进行适当的简化: 3)假设学校是个封闭系统,不考虑校园内外人员的流动,仅考虑人群在校园内的活动 4)假设人群都是理性的,即人群在出发地点和目标地点之间的移动遵循距离最小原则; 5)不考虑教职工和留学生的活动,仅考虑学生(本科生和博硕士研究生)的活动; 6)活动特征中,仅考虑本科生到教学楼,研究生到实验室的情况。 符号说明 P个体在校园内固定两个建筑物之间的移动概率,小于1,i=1~17 2摄像头的可能布置点取值,0或1,i=1~20 c各个可能布置点摄像头的拍摄系数,1=1-20 压:各条道路人流量,i=1~43 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
1 一、问题重述 1.1 问题背景 信息采集设备的布置直接影响信息采集的质量和效率，不合理的布置不仅造成资源 的浪费，更影响信息的获取。因此，对信息采集设备的布置问题进行深入研究很有必要。 1.2 目标任务 信息采集是进行数据分析的基础，而信息采集设备的布置关系到所收集数据的质量 和效率。比如一些传感设备的布置问题、摄像装置的布置问题等。 为简单起见，以我们学校 A 区校园为例，研究下面的问题： （1）根据地图确定我们学校校园的主要道路和主要建筑的位置。分析人群一天的主要 活动特征结合我校基本数据，得到我校活动热点图。 （2）在上述研究的基础上，分析主要道路的流量情况。 （3）现在有一批摄像头（10个）需要安装在适当的位置，使得通过这些摄像头得到的 视频能够确定尽可能多的人的活动轨迹。 二、模型假设 1）不考虑车辆仅考虑步行； 2）根据真实校园地图，对校园主要建筑物和道路进行适当的简化； 3）假设学校是个封闭系统，不考虑校园内外人员的流动，仅考虑人群在校园内的活动； 4）假设人群都是理性的，即人群在出发地点和目标地点之间的移动遵循距离最小原则； 5）不考虑教职工和留学生的活动，仅考虑学生（本科生和博硕士研究生）的活动； 6）活动特征中，仅考虑本科生到教学楼，研究生到实验室的情况。 三、符号说明 个体在校园内固定两个建筑物之间的移动概率，小于 1，i=1~17； 摄像头的可能布置点取值，0 或 1, i=1~20； 各个可能布置点摄像头的拍摄系数, i=1~20; 各条道路人流量， i=1~43。 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
四、模型建立与求解 4.1问题一模型建立与求解 根据校园电子地图确定重庆大学A区的主要道路和建筑位置,并对道路和建筑物进 行编号。以大数定理为基础,建立人群活动热点图。 4.1.1模型建立 (1)人群活动特征与地图的简化 根据重庆大学A区的校园电子地图(如图4-1所示),获得主要建筑物和道路,根 据人群活动的主要特征,忽略人群活动较少的区域的建筑物与道路,只考虑人群活动相 对密集区域的建筑物和道路,对地图进行适当的简化,从而方便下一步的研究。 由重庆大学官网可知,重庆大学A区全日制学生约19000余人,其中本科生约10000 人,硕士研究生约7500人,博士生约1500人。本科生的活动特征主要为宿舍-食堂-教 学楼(图书馆),而博硕士研究生的活动特征主要为宿舍-食堂-实验室 大季A区校园平面图 图4-1重庆大学A区电子地图 (2)建筑物和道路的编号 分析校园地图可知,主要的教学科研活动产所为五教、八教、研究生院、主教 传动实验室、电影学院、图书馆、综合实验楼、动力学院、电气学院、经管学院、公管 学院等12处。主要的饮食服务场所为一食堂、三食堂和五食堂等3处。主要的宿舍有 舍、二舍、三舍、五舍、六舍、十舍、博士生公寓等六处,由于 三和四舍都 是研究生,且连成一片,故将14舍在简化地图上简化为研究生宿舍,因此根据地理位 置和活动特征的不同,将重庆大学A区学生宿舍简化为五舍、六舍、研究生宿舍、博士 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
2 四、模型建立与求解 4.1 问题一模型建立与求解 根据校园电子地图确定重庆大学 A 区的主要道路和建筑位置，并对道路和建筑物进 行编号。以大数定理为基础，建立人群活动热点图。 4.1.1 模型建立 （1）人群活动特征与地图的简化 根据重庆大学 A 区的校园电子地图（如图 4-1 所示），获得主要建筑物和道路，根 据人群活动的主要特征，忽略人群活动较少的区域的建筑物与道路，只考虑人群活动相 对密集区域的建筑物和道路，对地图进行适当的简化，从而方便下一步的研究。 由重庆大学官网可知，重庆大学 A 区全日制学生约 19000 余人，其中本科生约 10000 人，硕士研究生约 7500 人，博士生约 1500 人。本科生的活动特征主要为宿舍-食堂-教 学楼（图书馆），而博硕士研究生的活动特征主要为宿舍-食堂-实验室。 图 4-1 重庆大学 A 区电子地图 （2）建筑物和道路的编号 分析校园地图可知，主要的教学科研活动产所为五教、八教、研究生院、主教、 传动实验室、电影学院、图书馆、综合实验楼、动力学院、电气学院、经管学院、公管 学院等 12 处。主要的饮食服务场所为一食堂、三食堂和五食堂等 3 处。主要的宿舍有 一舍、二舍、三舍、五舍、六舍、十舍、博士生公寓等六处，由于一、二、三和四舍都 是研究生，且连成一片，故将 1~4 舍在简化地图上简化为研究生宿舍，因此根据地理位 置和活动特征的不同，将重庆大学 A 区学生宿舍简化为五舍、六舍、研究生宿舍、博士 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
生宿舍、本科生宿舍等5处。将校园内的主要道路分别按R-R43编号,如图4-2所示。 本科生宿 ● 五食堂○ R 令18/博士宿舍 R4研究生宿舍 动力工程学○6教 R32 ◆R19○ 思群广场 2研究生院 5数R R34 R12 11 101 10 R13 R11◆ R7◆7 综合实验楼 团结广场 R4 R5g◆ 经管 图4-2重庆大学A区简化后的主要道路和建筑物 (3)人群活动热点图 根据以上人群活动特征,将人群活动分为三个阶段,分别为休息阶段、吃饭阶段和工作 学习阶段。其中休息阶段假定人群全部分布于各宿舍;吃饭阶段人群全部分布于各食堂; 工作学习阶段人群全部发布于各教学楼、实验室和图书馆。本文的目的就是通过摄像头 的合理布置,尽可能多的获得学生在这三个阶段转换时的移动轨迹。表4-1、2、3所示 分别是各建筑物的人口分布,针对每个阶段,主要活动区域的人口总数为学校学生总人 数,即19000。图4-3为简化的人群活动路径,即通过以上的假设,本文要研究的问题 转化为通过信息采集设备,尽可能多的记录19000在宿舍、食堂和学习科研场所移动时 的活动路径,如图4-3所示 宿舍 食学 教学科 研场所 图4-3简化的人群活动路径 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
3 生宿舍、本科生宿舍等 5 处。将校园内的主要道路分别按 R1-R43 编号，如图 4-2 所示。 本科生宿 五食堂 研究生宿舍 博士宿舍 一食堂 公管 主教 经管 7教 综合实验楼 5教 8教 图书馆 研究生院 动力工程学 院 6教 4 5 6 7 10 9 8 11 12 15 14 13 19 18 17 16 R1 R3 R2 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 R14 R16 R18 R17 R15 R19 R21 R20 R22 R24 R23 R25 R26 R27 R28 R30 R29 R31 R32 R33 R34 R35 R36 R38 R39 R43 R42 R41 五舍 20 电影 2 传动 3 三食堂 1 R37 六舍 民 主 湖 团结广场 思群广场 图 4-2 重庆大学 A 区简化后的主要道路和建筑物 （3）人群活动热点图 根据以上人群活动特征，将人群活动分为三个阶段，分别为休息阶段、吃饭阶段和工作 学习阶段。其中休息阶段假定人群全部分布于各宿舍；吃饭阶段人群全部分布于各食堂； 工作学习阶段人群全部发布于各教学楼、实验室和图书馆。本文的目的就是通过摄像头 的合理布置，尽可能多的获得学生在这三个阶段转换时的移动轨迹。表 4-1、2、3 所示 分别是各建筑物的人口分布，针对每个阶段，主要活动区域的人口总数为学校学生总人 数，即 19000。图 4-3 为简化的人群活动路径，即通过以上的假设，本文要研究的问题 转化为通过信息采集设备，尽可能多的记录 19000 在宿舍、食堂和学习科研场所移动时 的活动路径，如图 4-3 所示。 图 4-3 简化的人群活动路径 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
本科生宿舍(10000人) 五舍(2500) 五食堂 O六含 士宿舍 (1500) R4 究生宿舍 动力工程学Q6教 12°研究生院 (2160 RI 8教R22 R12 图书 17R16)g6 R35 (2000) Rl1◆ 8○综合实验 公管 (240)○ 团结广场 (4160) (600) (480) 图44重庆大学A区人口分布图 表4-1简化地图中各宿舍的人口发布 宿舍人数分布 本科硕士博士总和 本科生宿舍10000 10000 研究生宿舍 5000 舍 6舍 0000 25000 2500 2500 2500 博士宿舍 0 1500 1500 人数总计100005001500119000 表4-2简化地图中各食堂的人口分布 食堂人数分布 1食堂6000 3食堂6000 5食堂700 人数总和19000 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
4 本科生宿舍（10000人） 五食堂 （7000） 研究生宿舍 （2500） 博士宿舍 （1500） 一食堂 （6000） 公管 （240） 主教 （4160） 经管 （480） 7教 （600） 综合实验 楼（900） 8教 （3000） 5教 （3000） 图书馆 （2000） 研究生院 （2160） 动力工程学 院（600） 6教 （900） 4 5 6 7 10 9 8 11 12 15 14 13 19 18 17 16 R1 R3 R2 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 R14 R16 R18 R17 R15 R19 R21 R20 R22 R24 R23 R25 R26 R27 R28 R30 R29 R31 R32 R33 R34 R35 R36 R38 R39 R43 R42 R41 五舍（2500） 20 电影 （360） 2 传动 （600） 3 三食堂 （6000） 1 R37 六舍 （2500） 民 主 湖 团结广场 思群广场 图 4-4 重庆大学 A 区人口分布图 表 4-1 简化地图中各宿舍的人口发布 宿舍人数分布 本科 硕士 博士 总和 本科生宿舍 10000 0 0 10000 研究生宿舍 0 2500 0 2500 5 舍 0 2500 0 2500 6 舍 0 2500 0 2500 博士宿舍 0 0 1500 1500 人数总计 10000 7500 1500 19000 表 4-2 简化地图中各食堂的人口分布 食堂人数分布 1 食堂 6000 3 食堂 6000 5 食堂 7000 人数总和 19000 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
表4-3简化地图中各教学科研场所的人口分布 教学科研场所人数分布 本科硕士博士总和 电影 传动 000 500100 600 公管 20040 240 200018003602160 经管 400 480 7教 100 60 综合实验楼 0750150900 6教 750150900 研究生院 018003602160 动力 0500100600 5教 3000 8教 3000 88 图书馆 20000 100007500150019000 (4)摄像头可能安装位置的确定和编号 由以上人群活动路径和地图的简化,我们可以大体确定摄像头的可能布置点,如 图4-2所示,C1-C20是20个摄像头的可能布置点,选取的可能布置点是人口集中区 主要交通干道,交叉路口等处。 (5)地点转移概率 根据上述人口密度分布,可以得出各个学生从宿舍出发去往各个活动场所的概率 分布,其具体概率值见表4-4。(备注:表中各个概率值是指各个学生去该活动场所的可 能性。) 表4-4地点转移概率表 匚概率活动场所概率 活动场所 概率 活动场所 食堂 P=02主教(本科) P 200 6 三食堂 影视学院 综合实验楼 Pg P-900 五食堂 传动实验室 216 研究生院 15 P9 25 900 P4=03 教 公管学院 P 900 P6-900 2s=0.3 8教 =216主教(研究生) 动力学院 P7=60/900 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
5 表 4-3 简化地图中各教学科研场所的人口分布 教学科研场所人数分布 本科 硕士 博士 总和 电影 0 300 60 360 传动 0 500 100 600 公管 0 200 40 240 主教 2000 1800 360 2160 经管 0 400 80 480 7 教 0 500 100 600 综合实验楼 0 750 150 900 6 教 0 750 150 900 研究生院 0 1800 360 2160 动力 0 500 100 600 5 教 3000 0 0 0 8 教 3000 0 0 0 图书馆 2000 0 0 0 总计 10000 7500 1500 19000 （4）摄像头可能安装位置的确定和编号 由以上人群活动路径和地图的简化，我们可以大体确定摄像头的可能布置点，如 图 4-2 所示，C1-C20 是 20 个摄像头的可能布置点，选取的可能布置点是人口集中区， 主要交通干道，交叉路口等处。 （5）地点转移概率 根据上述人口密度分布，可以得出各个学生从宿舍出发去往各个活动场所的概率 分布，其具体概率值见表 4-4。（备注：表中各个概率值是指各个学生去该活动场所的可 能性。） 表 4-4 地点转移概率表 概率 活动场所 概率 活动场所 概率 活动场所 一食堂 主教（本科） 7 教 三食堂 影视学院 综合实验楼 五食堂 传动实验室 研究生院 5 教 公管学院 6 教 8 教 主教（研究生） =60/900 动力学院 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
2s=0z 图书馆 经管 4.1.2问题一的综合分析与进一步研究 人群活动特征和活动热点的确定是进一步研究摄像头的合理布置位置的关键,以上 建模过程简化涉及到的数学理论依据是大数定理。综合考虑学生的人数和教学楼、实验 室的人口容纳量,根据概率确定各个建筑物的人数发布。从而得到人群的活动热点图。 将人群的活动路径简化为宿舍-食堂-教学试验楼这样三点一线的路径,可以大大简 化模型的复杂度,而对研究结果不会有很大的影响 条件允许的话,实际上可以根据手机信号确定人群活动的区域,从而确定校园内的 人群活动热点图。 4.2问题二模型建立与求解 主要道路人群流量的计算是进行下一步摄像头布置位置优化的基础。本文假定人群 在出发点和目标点之间移动的轨迹是确定的,即人群中的每个个体都具有完全理性,可 以通过理智判断出两个目标点之间的最短路径,个体每次在两个确定目标点之间的活动 路径是确定的。基于以上假设,可以统计岀所有学生在校内按照简化的人群活动路径模 型的所用活动轨迹(见附录一:人群三点一线所有可能路径统计表)。为统计出R-R43 的人群流量密度做好准备工作 4.21模型建立与求解 通过计算各个宿舍到食堂再到教学楼实验室的概率,再乘以相应的人数,就可以获 得各条道路的人流量,如表4-5所示,由表可以画出道路流量统计棒状图,如图44所 示。图4-5所示为各道路人流量的聚类分析。由聚类分析可知校园地图上右上角的道路 人流量较大,这与实际在硏究生院/五教/八教的人口密度较高有关,说明了人流量统计 的正确性 表4-5道路人流量统计表 道路编号 人流量6303.16614.3975.79960.00328.420.0060000.0056.42168.429000 14 17 19 5384.21947.37 人流量 0.004607.37699.746325.267155.79771.87415.796434.74551.681710.535974.74 道路編号 人流量6172.631368424804.210.006000070000600000.008271.589824.216052.63 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
6 图书馆 经管 4.1.2 问题一的综合分析与进一步研究 人群活动特征和活动热点的确定是进一步研究摄像头的合理布置位置的关键，以上 建模过程简化涉及到的数学理论依据是大数定理。综合考虑学生的人数和教学楼、实验 室的人口容纳量，根据概率确定各个建筑物的人数发布。从而得到人群的活动热点图。 将人群的活动路径简化为宿舍-食堂-教学试验楼这样三点一线的路径，可以大大简 化模型的复杂度，而对研究结果不会有很大的影响。 条件允许的话，实际上可以根据手机信号确定人群活动的区域，从而确定校园内的 人群活动热点图[1]。 4.2 问题二模型建立与求解 主要道路人群流量的计算是进行下一步摄像头布置位置优化的基础。本文假定人群 在出发点和目标点之间移动的轨迹是确定的，即人群中的每个个体都具有完全理性，可 以通过理智判断出两个目标点之间的最短路径，个体每次在两个确定目标点之间的活动 路径是确定的。基于以上假设，可以统计出所有学生在校内按照简化的人群活动路径模 型的所用活动轨迹（见附录一：人群三点一线所有可能路径统计表）。为统计出 R1-R43 的人群流量密度做好准备工作。 4.2.1 模型建立与求解 通过计算各个宿舍到食堂再到教学楼实验室的概率，再乘以相应的人数，就可以获 得各条道路的人流量，如表 4-5 所示，由表可以画出道路流量统计棒状图，如图 4-4 所 示。图 4-5 所示为各道路人流量的聚类分析。由聚类分析可知校园地图上右上角的道路 人流量较大，这与实际在研究生院/五教/八教的人口密度较高有关，说明了人流量统计 的正确性。 表 4-5 道路人流量统计表 道路编号 1 2 3 4 5 6 7 8 9 10 11 人流量 6303.16 614.39 75.79 960.00 328.42 0.00 600.00 0.00 568.42 1168.42 900.00 道路编号 12 13 14 15 16 17 18 19 20 21 人流量 631.58 331.58 5384.21 947.37 0.00 3000.00 2384.21 3107.37 0.00 4007.37 道路编号 22 23 24 25 26 27 28 29 30 31 32 人流量 0.00 4607.37 6994.74 6325.26 7155.79 7771.58 7415.79 6434.74 5513.68 1710.53 5974.74 道路编号 33 34 35 36 37 38 39 40 41 42 43 人流量 6172.63 1368.42 4804.21 0.00 6000.00 7000.00 6000.00 0.00 8271.58 9824.21 6052.63 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
10000 各条道路人流里统计图 8000 6000 2000 图4-5各道路人流量发布图 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
7 人 流 量 图 4-5 各道路人流量发布图 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com