练习2-展厅监控问题.docVIP

练习2 展厅监控问题 (试求出所有可能的解—用Lingo和matlab求解) 展厅保安监控问题——海湾艺术馆考虑安装一系列摄像安全系统以减少其保安费用。下图是海湾艺术馆用于展览的8间展厅的示意图。各展厅之间的通道显示为⑴ - ⒀。一家保安公司建议在一些通道安装双向摄像机。每架摄象机都可以很好地监控通道两侧的展厅。例如：在通道⑷处安装摄象机，则展厅 1 和 4 就可以完全被监控到，等等。管理层用最少数量的双向摄像机覆盖所有的8间展厅。 展厅1 展厅1 展厅2 展厅3 展厅4 展厅5 展厅6 展厅7 展厅8 （1） （3） （5） （6） （7） （8） （9） （10） （11） （13） （12） （2） （4） 模型假设? ? 通道里的一台双向摄像机能很好地监控与之相邻的展厅，不会出现故障。?? 符号说明? xi：第i个通道里安排的摄像机台数；? f：用的摄像机总台数。? ? 模型的建立与求解：? ? 第i个通道里要么安排摄像机，要么不安排摄像机，故有 1 通道安排摄像机 xi= 0 通道不安排摄像机 ? 要使用的摄像机最少，则易见目标函数为? Min f=? 要求是每个展厅都被监视到，即与每个展厅相邻的摄像机总数至少为1，即得下列约束条件：? ???????????????????????? 用lingo解此0-1规划问题，得最少需要用4台摄像机才能使所有展厅都被监视到，lingo给出的摄像机安排方案为在通道1、5、8、13出分别安放一摄像机。但是仔细研究原题会发现使摄像机总数为4台的方案不止一种，如3、6、10、11通道处安放摄像机也可满足题意。我们用计算机穷举的方法找出了所有满足要求的摄像机安放方案，共有6种， 方案 通道组合 1 1 5 8 13 2 1 7 11 12 3 2 4 8 13 4 2 6 7 13 5 3 6 9 13 6 3 6 10 11 用lingo解出了最少摄像机数，但它只给出了一种方案。lingo在计算规划问题时采用迭代法，给出了最优解及一组使目标函数取最优解的自变量值，要得出所有可能的方案必须枚举，找出所有可行的方案。 计算最优解的Lingo程序：? model:? sets:? sxt/1..13/:x;? endsets? min=@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));? End 找所有满足条件的摄像机安放方案的MATLAB程序： clear? for?i=1:10? for?j=i+1:11????????? for?k=j+1:12??????????? ? for?l=k+1:13? ???????????????? A=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,l??????????????? ??end???????????? ?end???????? end????? end? End 枚举法 tic; clc;?? clear?all;? position=[];? for?a=0:1;? for?b=0:1;????????? for?c=0:1;????????????? for?d=