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