闭路电视监控系统的优化设计(数学建模课程设计).doc
《闭路电视监控系统的优化设计(数学建模课程设计).doc》由会员分享,可在线阅读,更多相关《闭路电视监控系统的优化设计(数学建模课程设计).doc(7页珍藏版)》请在沃文网上搜索。
1、 闭路电视监控系统的优化设计摘要:本题主要解决的问题是选择安装摄像头的位置,并且在保证所有区域被监控的条件下安装摄像头数目最少。我们首先将这一问题转化为01整数规划问题,并用LINDO软件求解。由于每条街道的两端基本(也有极少数街道只有一端可以安装摄像头)都是可以安装摄像头的位置,我们可以把街道看做线段,安装摄像头的位置看作点,这样工业区的布局图就转化为一个图论模型,本题就转化为求图的最小点覆盖的问题了。利用图的关联矩阵求出最小覆盖的点,这些点就是安装摄像头的位置!关键字:01整数规划 关联矩阵 最小点覆盖Abstract :The aim of this term is to choose
2、the places of fixing web-cameras,and make sure the whole aeras are under the control .Under this condition ,we should make sure that the number of fixed web-cameras is minimal. Firstly ,we convert this problem to the case of zero one integer programming ,and LINDO can solve this changing case .Secon
3、dly,we can change our idea to think about this problem .Because the two points of each street are available places for fixing web-cameras (only a very few streets have one available point to fix web-cameras ),we can respond the streets to line segments ,at the same time ,the place of fixing web-came
4、ras responding to vertices ,then the layout of this industrial park becames a model of graph theory .Hence the original term transforms to solve the minimal vertex covering problems of graph .We can use the correlative matrix to find out the minimal vertex covering concourse, the solving points are
5、the final places for fixing Keywords: zeroone integral layout correlative matrix minimal vertex covering1. 问题重述某市的工业区发生多起夜间入室行窃案件,此工业区有保安巡逻,但保安人数太少,因此负责此区域安全的相关市政部门决定安装监控摄像头,以协助保安工作。下图给出了该工业区的地图,其中给出了需要用闭路电视进行监控的区域范围,并标记44个可以安装摄像头的位置,要求设计一种安装方案使安装的摄像头数目最少但保证需监控的区域全在监控范围。图一2. 名词和符号说明(1) xn 二值变量,取0或1(
6、2) 表示位置n和m在同一条街道上(3) 关联矩阵R= (n为定点数,m为边数),其中= 即仅当以i为顶点的邻边是时,=1 (4) 覆盖 : 若图G的每条边都至少有一个端点在顶点集V的一个子集K之中,则称K为G的覆盖。(5)一个图可以有很多覆盖,含顶点个数最少的覆盖称为最小覆盖。3模型假设(1)所安装的监控摄像头都可以360度旋转,因此在几条街道的交汇处安装一个摄像头就可以同时对这些街道进行监控(2)可以安装摄像头的地方都是一条街道的末端,即一般可以安装摄像头的相邻的地点之间是一条街道(3)转化为图论问题时假定所有的路口都是可以安装摄像头的位置3. 问题分析与模型建立题目给我们提供了可以安装摄
7、像头进行监控的地方,我们只需要考虑在某地方是否安装摄像头。安与不安是两个方面,我们考虑用01规划来解决此问题。定义二值变量xn(n=1,2,43,44),当且仅当在位置n处设置了摄像头此时的变量踩取1,否则为0.要使安装的摄像头数量最少,即的值最小!为了保证监控到位,必须限定每条街道都应至少处于一个摄像头监控之下。因此,如果位置n和m之间存在一条街道,则需要在位置n上()或位置m上()安装一个摄像头,或者在这两个位置上都安装摄像头。可以同时用两个摄像头监控一条街道,并且有些时候这样做能够带来一些好处:在图一中,在位置4和位置8上同时安装摄像头似乎对这条街道显得有些多余,但这两个摄像头同时能够对
8、位置5,6和7方向的死胡同进行监控。经过上述分析我们可以建立一个非常简单的01整数规划模型:Minimize : xm+xn=1 n=1,2,3,.,43,444. 模型求解要求解上述01整数规划模型,我们首先要把约束条件满足的等式全部找出来,即每条街道上安装摄像头的位置的xn值之和大于等于1.这个过程比较繁琐,但使用计算机求解就必须先完成这个步骤。通过人工查找共有52条街道,即可写出52个约束不等式,因为这些不等式没有规律,故只能一个一个的写出。我们知道解50个以下的变量的01规划问题LINDO比较方便,本题只有44个变量故用LINDO软件求解将根据题目列出的不等式带入上面建立的01规划模型
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
20 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 闭路电视 监控 系统 优化 设计 数学 建模 课程设计
