闭路电视监控系统的优化设计(数学建模课程设计)

《闭路电视监控系统的优化设计(数学建模课程设计)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、闭路电视监控系统的优化设计摘要:本题主要解决的问题是选择安装摄像头的位置，并且在保证所有区域被监控的条件下安装摄像头数目最少。我们首先将这一问题转化为0—1整数规划问题，并用LINDO软件求解。由于每条街道的两端基本（也有极少数街道只有一端可以安装摄像头）都是可以安装摄像头的位置，我们可以把街道看做线段，安装摄像头的位置看作点，这样工业区的布局图就转化为一个图论模型，本题就转化为求图的最小点覆盖的问题了。利用图的关联矩阵求出最小覆盖的点，这些点就是安装摄像头的位置！关键字：0—1整数规划关联矩阵最小点覆盖Abstract:Theaimofthistermist

2、ochoosetheplacesoffixingweb-cameras，andmakesurethewholeaerasareunderthecontrol.Underthiscondition,weshouldmakesurethatthenumberoffixedweb-camerasisminimal.Firstly,weconvertthisproblemtothecaseofzero–oneintegerprogramming,andLINDOcansolvethischangingcase.Secondly,wecanchangeourideato

3、thinkaboutthisproblem.Becausethetwopointsofeachstreetareavailableplacesforfixingweb-cameras(onlyaveryfewstreetshaveoneavailablepointtofixweb-cameras),wecanrespondthestreetstolinesegments,atthesametime,theplaceoffixingweb-camerasrespondingtovertices,thenthelayoutofthisindustrialparkb

4、ecamesamodelofgraphtheory.Hencetheoriginaltermtransformstosolvetheminimalvertexcoveringproblemsofgraph.Wecanusethecorrelativematrixtofindouttheminimalvertexcoveringconcourse,thesolvingpointsarethefinalplacesforfixingKeywords:zero—oneintegrallayoutcorrelativematrixminimalvertexcoveri

5、ng1.问题重述某市的工业区发生多起夜间入室行窃案件，此工业区有保安巡逻，但保安人数太少，因此负责此区域安全的相关市政部门决定安装监控摄像头，以协助保安工作。下图给出了该工业区的地图，其中给出了需要用闭路电视进行监控的区域范围，并标记44个可以安装摄像头的位置，要求设计一种安装方案使安装的摄像头数目最少但保证需监控的区域全在监控范围。图一1.名词和符号说明(1）xn二值变量，取0或1(2）表示位置n和m在同一条街道上(3）关联矩阵R=(n为定点数，m为边数)，其中=即仅当以i为顶点的邻边是时，=1（4）覆盖：若图G的每条边都至少有一个端点在顶点集V的一个子集K

6、之中，则称K为G的覆盖。（5）一个图可以有很多覆盖，含顶点个数最少的覆盖称为最小覆盖。3模型假设（1）所安装的监控摄像头都可以360度旋转，因此在几条街道的交汇处安装一个摄像头就可以同时对这些街道进行监控（2）可以安装摄像头的地方都是一条街道的末端，即一般可以安装摄像头的相邻的地点之间是一条街道（3）转化为图论问题时假定所有的路口都是可以安装摄像头的位置2.问题分析与模型建立题目给我们提供了可以安装摄像头进行监控的地方，我们只需要考虑在某地方是否安装摄像头。安与不安是两个方面，我们考虑用0—1规划来解决此问题。定义二值变量xn（n=1，2，…，43，44），当

7、且仅当在位置n处设置了摄像头此时的变量踩取1，否则为0.要使安装的摄像头数量最少，即的值最小！为了保证监控到位，必须限定每条街道都应至少处于一个摄像头监控之下。因此，如果位置n和m之间存在一条街道，则需要在位置n上()或位置m上（）安装一个摄像头，或者在这两个位置上都安装摄像头。可以同时用两个摄像头监控一条街道，并且有些时候这样做能够带来一些好处：在图一中，在位置4和位置8上同时安装摄像头似乎对这条街道显得有些多余，但这两个摄像头同时能够对位置5，6和7方向的死胡同进行监控。经过上述分析我们可以建立一个非常简单的0—1整数规划模型：Minimize:xm+xn

8、>=1n=1,2,3,….,43,44