数学建模课程设计---闭路电视监控系统的优化设计.doc

闭路电视监控系统的优化设计摘要:本题主要解决的问题是选择安装摄像头的位置，并且在保证所有区域被监控的条件下安装摄像头数目最少。我们首先将这一问题转化为01整数规划问题，并用lindo软件求解。由于每条街道的两端基本（也有极少数街道只有一端可以安装摄像头）都是可以安装摄像头的位置，我们可以把街道看做线段，安装摄像头的位置看作点，这样工业区的布局图就转化为一个图论模型，本题就转化为求图的最小点覆盖的问题了。利用图的关联矩阵求出最小覆盖的点，这些点就是安装摄像头的位置！关键字：01整数规划 关联矩阵 最小点覆盖abstract :the aim of this term is to choose 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 .secondly,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-cameras 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 the final places for fixing keywords: zeroone integral layout correlative matrix minimal vertex covering1. 问题重述某市的工业区发生多起夜间入室行窃案件，此工业区有保安巡逻，但保安人数太少，因此负责此区域安全的相关市政部门决定安装监控摄像头，以协助保安工作。下图给出了该工业区的地图，其中给出了需要用闭路电视进行监控的区域范围，并标记44个可以安装摄像头的位置，要求设计一种安装方案使安装的摄像头数目最少但保证需监控的区域全在监控范围。图一2. 名词和符号说明(1） xn 二值变量，取0或1(2） 表示位置n和m在同一条街道上(3） 关联矩阵r= (n为定点数，m为边数)，其中= 即仅当以i为顶点的邻边是时，=1 （4） 覆盖 ： 若图g的每条边都至少有一个端点在顶点集v的一个子集k之中，则称k为g的覆盖。（5）一个图可以有很多覆盖，含顶点个数最少的覆盖称为最小覆盖。3模型假设（1）所安装的监控摄像头都可以360度旋转，因此在几条街道的交汇处安装一个摄像头就可以同时对这些街道进行监控（2）可以安装摄像头的地方都是一条街道的末端，即一般可以安装摄像头的相邻的地点之间是一条街道（3）转化为图论问题时假定所有的路口都是可以安装摄像头的位置3. 问题分析与模型建立题目给我们提供了可以安装摄像头进行监控的地方，我们只需要考虑在某地方是否安装摄像头。安与不安是两个方面，我们考虑用01规划来解决此问题。定义二值变量xn（n=1，2，43，44），当且仅当在位置n处设置了摄像头此时的变量踩取1，否则为0.要使安装的摄像头数量最少，即的值最小！为了保证监控到位，必须限定每条街道都应至少处于一个摄像头监控之下。因此，如果位置n和m之间存在一条街道，则需要在位置n上()或位置m上（）安装一个摄像头，或者在这两个位置上都安装摄像头。可以同时用两个摄像头监控一条街道，并且有些时候这样做能够带来一些好处：在图一中，在位置4和位置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规划模型，并输入lindo：min x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40+x41+x42+x43+x44subject tox43 =1x41+x43 =1x41+x42 =1x42+x44 =1x40+x39 =1 x39+x38=1x38+x37=1x43+x42=1x42+x38=1x44 =1x44+x37=1x41+x39=1x37+x35=1x34+x36=1x32+x33=1x33+x34=1x34+x35=1x35+x10=1x10+x9=1x3+x10=1x3+x1=1x3+x4=1x4+x5=1x4+x8=1x8+x7=1x8+x6=1x33+x31=1x31+x28=1x28+x29=1x29+x30=1x23+x24=1x24+x25=1x25+x26=1x26+x27=1x34+x15=1x15+x18=1x18+x19=1x19+x20=1x20+x21=1x21+x22=1x21+x25=1x18+x12=1x19+x16=1x10+x12=1x12+x16=1x11+x12=1x11+x13=1x13+x16=1x13+x14=1x14+x17=1x14+x2=1x1+x2=1endint 44最后一行表示44个决策变量全部为01变量运行程序得到的结果x1=x4=x8=x10=x12=x13=x14=x18=x19=x21=x24=x26=x28=x30=x33=x34=x37=x39=x42=x43=x44=1由此可见最佳方案需要安装21个摄像头，即在标号为1，4，8，10，12，13，14，18，19，21，24，26，28，30，33，34，37，39，42，43，44的道口安装摄像头就可保证整个工业区的道路全在监控范围！图二用椭圆标记出了这些摄像头的位置。5. 尝试转化为图论中的最小点覆盖问题5.1 问题分析与模型建立 上面我们已经用01整数规划求出了最优解，再仔细观察该工业区的布局图，不难发现基本每条街道的路口都是可以安装摄像头的位置，但有且仅有一个路口不是，我们考虑大量位置的时候可以忽略这个位置，假设它也可以安装摄像头。我们可以把该工业区的布局图转化成一个图论模型，每条街道表示边，街道两端的路口表示顶点。我们把每条边和每个顶点分别标号，可以得到下面的点边图（图三）我们必须先介绍覆盖和最小覆盖两个概念：（1）若图g的每条边都至少有一个端点在顶点集v的一个子集k之中，则称k为g的覆盖。（2）一个图可以有很多覆盖，含顶点个数最少的覆盖称为最小覆盖。换言之在本道题目中就是要求每条街道都至少有一个路口安装摄像头，并且保证安装摄像头的数目最小。我们可以清晰的看到摄像头的安置问题实际为求图的最小点覆盖。5.2 模型求解因为关联矩阵表示的是顶点和边之间的关系，所以关联矩阵与覆盖密切相关。顶点集v的子集k是图g的一个覆盖，当且仅当g的关联矩阵k中的各顶点所对应的行内，每列至少存在一个元素“1”。从关联矩阵可以找出一个最小覆盖。最小点覆盖问题没什么高效的算法，先就以一个简化的图的为例子说明最小点覆盖的求解方法。该图的关联矩阵为 r= 下面从该矩阵出发求对应图的最小点覆盖，步骤如下（1） 在矩阵中取恰有两个“1”的那一列中“1”所在的行（如3行），令3k，划去3行及3行中元素所在的， ，列，得 （2） 在上面新矩阵中再取恰有两个“1”的那一列中“1”所在的行（如5行），令5k，划去5行及5行中元素“1”所在的列，得 （3） 因为1大于2，1大于4（若对所有的j有，记j大于k），划去2，4行，1k，过程结束，最小覆盖k=（1，3，5）通过上面的例子我们可以简单的概括最小点覆盖的启发式算法：在关联矩阵中找出恰有两个“1“的那一列中”1“所在的行,选取其中任意的一行i，i点就归属最小覆盖集，划去i行及i行中元素”1“所在的列，这样便得到一个新的矩阵。对新矩阵重复上述操作直到不能继续进行此操作。用此算法可以求解出图三的最小点覆盖集，即k= x1, x4, x8, x10, x12, x13, x14, x18, x19, x21, x24, x26, x28 ,x30, x33, x34, x37, x39, x 41,x42, x45 ，要注意特殊点位置45也在其中，我们把位置45附近的点集做细微的调整，把位置41和位置45换成位置43和位置44也可以满足题目的要求。所以最终安装摄像头的位置是点1，4，8，10，12，13，14，18，19，21，24，26，28，30，33，34，37，39，42，43，44，和01规划的求解相同。6总结本题主要解决的问题是选择安装摄像头的位置，并且在保证所有区域被监控的条件下安装摄像头数目最少。我们首先将这一问题转化为01整数规划问题，并用lindo软件求解，求出的值为1的点的位置就是安装摄像头的位置。由于每条街道的两端基本（也有极少数街道只有一端可以安装摄像头）都是可以安装摄像头的位置，我们可以把街道看做线段，安装摄像头的位置看作点，这样工业区的布局图就转化为一个图论模型，本题就转化为求图的最小点覆盖的问题了。利用图的关联矩阵求出最小覆盖的点集，这些点就是安装摄像头的位置！我们发现两种方法都可以求出闭路电视系统的最优监控方案，但转化图的顶点数目比较多时用最小点覆盖问题求解过程比较麻烦，像本题45个顶点求解就很