new第十四 监控摄像头的最优安装1.doc

PAGE PAGE 1 监控摄像头的最优安装 摘要： 安装摄像头能对小区实行有效的监控，保障小区居民的安全。但如何安装才能使安装摄像头数目最少、效果最优。 针对小区安装监控摄像头问题，根据每条街道都必须被观测到这个要求，将街道是否被观测到分别设为0、1，运用0 - 1规划,依据摄像头最少的原则建立数学模型，可将安装摄像头能覆盖需要监控的区域范围且所需数目最少的要求转化为以每条街道都必须被观测到为约束条件，摄像头数目最少为目标函数，建立0-1分布模型。 0-1规划模型可以通过利用矩阵反复迭代最终求得最优解最后用求解，说明所选用的算法切实可行，再利用lingo软件实现求解。得到所需安装摄像头数目为21.具体安装位置如图三（第6页）所示。 本模型假设合理，推导严谨，准确性高，能很好地解决实际问题。且具备较佳的推广性，适用于小区、校园及其他公共场所摄像头的安装。经过改进后的模型更可推广至探照灯的安装、交警人员的设置等问题。最后，我们进一步结合实际情况如街道的坡度、雨雾天气、安装成本等对模型进行了改进，使得模型更符合实际，可切实解决实际生活中的问题。 关键词：0-1分布规划 摄像头安装 lingo软件 一、问题重述 某小区在过去几个月里发生了多次夜间行窃案件。鉴于小区保安人数少，巡逻力度不够等原因，负责此小区的安全部门决定安装监控摄像头，以协助保安工作。通过使用可360度旋转的监控摄像头，在几条街道的交汇处安装一个摄像头就可以同时对这些街道进行监控。图1是此小区的地图，其中给出了需要用闭路电视进行监控的区域范围，并用数字标出了49个可以安装摄像头的位置。问题：应该选择在哪些位置安装摄像头才能使需要使用的摄像头数目最少？ 二、问题分析 根据问题提出的要求,不仅要观测到所有街道,而且尽可能少的使用摄像头。街区能否被完全观察到是主要的约束,即街道至少被一个摄像头观测到。一个交汇点设置摄像头无非就两种结果:装、不装。采用0-1分布规划，装标记为1,不装标记为0。假如一条街道能被观测到,那么也就意味着该街道至少有一个摄像头能观测到街道,这样就可以以交汇点设为主变量，建立模型。 在满足监控要求的前提下，令同一条街道j的所有交汇点处之和大于等于1为约束条件，表示在这几个交汇点处至少应该安装的摄像头数目，由所有需要监控的街道得出约束条件。 通过约束条件建立模型，利用lingo软件求解，从而得出闭路电视进行监控的区域范围所需安装摄像头的位置和最少数目。下面将对上述分析给出具体的解决步骤。 三、模型假设 1、已知摄像头可360度全方位旋转，假设摄像头旋转监控在各个角度不存在监控空白。 2、摄像头对短、长距离监控具有较高灵敏度。 3、在监控期间所有摄像头都正常工作。 4、街道上无阻挡摄像头视野的障碍物。 5、忽略街道的轻度弯曲，视其为直线，摄像头可实现有效监控。 6、位于同一直线的街道视为同一街道。 四、符号说明 m：街道交汇点总数。 n：街道总数 i：交汇点编号。 j: 街道编号。 Z: 安装摄像头总数。 :若交汇点i属于街道j时=1；若不在，=0。 :是否街道交汇点i处设置监控摄像头；若设置为1，反之，为0。 五、模型的建立与求解 1、对街道进行分析 在模型建立过程中，先对街道进行分析。通过观察分析街道情况，可知街道的分布大多为直线交汇状况，且同一条街道最多可被2台或2台以上摄像头监控。其中存在如下两种特殊情况： （1）、街道仅能被一台摄像头监控的情况(如下图中的红色街道)： 图一 存在此情况的交汇点有46，39，12，4。在此种情况下，这条街道的交汇点处必须安装摄像头。 （2）、摄像头监控出现如下图虚线部分监控盲区的情况。在此种情况下不考虑摄像头监控。 图二 2、模型的建立： 基于上述对街道情况的分析与处理建立模型。目标函数为安装的摄像头数目最少。 如问题分析所述，在满足监控要求的前提下，约束条件为：街道j的所有交汇点之和大于等于1，表示在这几个交汇点处至少应该安装的摄像头数目，由所有需要监控的街道得出约束条件。约束条件为:所有的街道都有至少有一个摄像头能监控到。 综上所述，建立的模型如下： 目标函数： 约束条件： 3、模型求解 根据约束条件和目标函数，利用lingo软件，求出结果如下： i i xi 1 1,4,6,9,11,12,14,16,19,22,25,28,31,34,36, 38,39,41,44,46,47 0 2,3,5,7,8,10,13,15,17,18,20,21,23,24,26,27, 29,30,32,33,35,37,40,42,43,45,48,49 表一 拟装摄像头对街道的监控情况如下表： 拟装摄像头交汇点编号 监控到的街道编号 拟装摄像头交汇点编号 监控到的街道编号 1 1，3 28 20，21