练习2-展厅监控问题

练习2展厅监控问题(试求出所有可能的解—用Lingo和matlab求解)展厅保安监控问题——海湾艺术馆考虑安装一系列摄像安全系统以减少其保安费用。下图是海湾艺术馆用于展览的8间展厅的示意图。各展厅之间的通道显示为⑴-⒀。一家保安公司建议在一些通道安装双向摄像机。每架摄象机都可以很好地监控通道两侧的展厅。例如：在通道⑷处安装摄象机，则展厅1和4就可以完全被监控到，等等。管理层用最少数量的双向摄像机覆盖所有的8间展厅。模型假设通道里的一台双向摄像机能很好地监控与之相邻的展厅，不会出现故障。符号说明xi：第i个通道里安排的摄像机台数；f：用的摄像机总台数。模型的建立与求解：第i个通道里要么安排摄像机，要么不安排摄像机，故有1通道安排摄像机xi=0通道不安排摄像机要使用的摄像机最少，则易见目标函数为Minf=131iix要求是每个展厅都被监视到，即与每个展厅相邻的摄像机总数至少为1，即得下列约束条件：展厅1展厅2展厅3展厅4展厅5展厅6展厅7展厅8（1）（3）（5）（6）（7）（8）（9）（10）（11）（13）（12）（2）（4）111111111311119521312101098775433211286641xxxxxxxxxxxxxxxxxxxxxxxxxx用lingo解此0-1规划问题，得最少需要用4台摄像机才能使所有展厅都被监视到，lingo给出的摄像机安排方案为在通道1、5、8、13出分别安放一摄像机。但是仔细研究原题会发现使摄像机总数为4台的方案不止一种，如3、6、10、11通道处安放摄像机也可满足题意。我们用计算机穷举的方法找出了所有满足要求的摄像机安放方案，共有6种，方案通道组合11581321711123248134267135369136361011用lingo解出了最少摄像机数，但它只给出了一种方案。lingo在计算规划问题时采用迭代法，给出了最优解及一组使目标函数取最优解的自变量值，要得出所有可能的方案必须枚举，找出所有可行的方案。1、计算最优解的Lingo程序：model:sets:sxt/1..13/:x;endsetsmin=@sum(sxt:x);x(1)+x(4)+x(6)=1;x(1)+x(2)+x(3)=1;x(6)+x(8)+x(12)=1;x(3)+x(4)+x(5)+x(7)=1;x(7)+x(8)+x(9)+x(10)=1;x(10)+x(12)+x(13)=1;x(2)+x(5)+X(9)+x(11)=1;x(11)+x(13)=1;@for(sxt:@bin(x));End2、找所有满足条件的摄像机安放方案的MATLAB程序：clearfori=1:10forj=i+1:11fork=j+1:12forl=k+1:13A=zeros(1,13);A(i)=1;A(j)=1;A(k)=1;A(l)=1;if(A(1)+A(4)+A(6)=1)&(A(1)+A(2)+A(3)=1)&(A(6)+A(8)+A(12)=1)&(A(3)+A(4)+A(5)+A(7)=1)&(A(7)+A(8)+A(9)+A(10)=1)&(A(10)+A(12)+A(13)=1)&(A(2)+A(5)+A(9)+A(11)=1)&(A(11)+A(13)=1)i,j,k,lendendendendEnd枚举法tic;clc;clearall;position=[];fora=0:1;forb=0:1;forc=0:1;ford=0:1;fore=0:1;forf=0:1;forg=0:1forh=0:1;fori=0:1;forj=0:1;fork=0:1;forl=0:1;form=0:1;%%进行约束条件判断，将可行解先挑出来%%if(a+d+f=1)&(f+h+l=1)&(a+b+c=1)&(c+d+e+g=1)&(g+h+i+j=1)&(j+m+l=1)&(b+e+i+k=1)&(k+m=1)%%满足条件（即所有展厅均可监控到）的可行解找出来，并求出摄象头数%%plus=sum([abcdefghijklm]);%%将所有满足条件的可行解找出，并构成矩阵position，第一列为相应的摄象头数%%position=[position;plusabcdefghijklm];end