练习2-展厅监控问题

练习 2 展厅监控问题 试求出所有可能的解 用 Lingo 和 matlab 求解 展厅保安监控问题 海湾艺术馆考虑安装一系列摄像安全系统以减少其保安费用 下图 是海湾艺术馆用于展览的 8 间展厅的示意图 各展厅之间的通道显示为 一家保安 公司建议在一些通道安装双向摄像机 每架摄象机都可以很好地监控通道两侧的展厅 例 如 在通道 处安装摄象机 则展厅 1 和 4 就可以完全被监控到 等等 管理层用最少 数量的双向摄像机覆盖所有的 8 间展厅 模型假设 通道里的一台双向摄像机能很好地监控与之相邻的展厅 不会出现故障 符号说明 xi 第 i 个通道里安排的摄像机台数 f 用的摄像机总台数 模型的建立与求解 第 i 个通道里要么安排摄像机 要么不安排摄像机 故有 1 通道安排摄像机 xi 0 通道不安排摄像机 要使用的摄像机最少 则易见目标函数为 Min f 13 1i ix 要求是每个展厅都被监视到 即与每个展厅相邻的摄像机总数至少为 1 即得下列约束条 件 展厅 1展厅 2 展厅 3展厅 4展厅 5展厅 6 展厅 7展厅 8 1 3 5 6 7 8 9 10 11 13 12 2 4 1 1 1 1 1 1 1 1 1311 11952 131210 10987 7543 321 1286 641 xx xxxx xxx xxxx xxxx xxx xxx xxx 用 lingo 解此 0 1 规划问题 得最少需要用 4 台摄像机才能使所有展厅都被监视到 lingo 给出的摄像机安排方案为在通道 1 5 8 13 出分别安放一摄像机 但是仔细研究原题会 发现使摄像机总数为 4 台的方案不止一种 如 3 6 10 11 通道处安放摄像机也可满足题 意 我们用计算机穷举的方法找出了所有满足要求的摄像机安放方案 共有 6 种 方案通道组合 115813 2171112 324813 426713 536913 6361011 用 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 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 将所有满足条件的可行解找出 并构