内容发布更新时间 : 2024/12/22 11:03:28星期一 下面是文章的全部内容请认真阅读。

。

练习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

-可编辑修改-