Пример. Проектирование системы видеонаблюдения

Картинная галерея планирует использовать систему видеонаблюдения в выставочных залах. Выставочные залы показаны на рисунке. Залы пронумерованы от 1 до 8; проходы между залами -- от 1 до 13. Фирма по установке охранного оборудования предлагает установить двунаправленные камеры в проходах между залами. Каждая камера модет просматривать 2 зала, в проходе между которыми она установлена. Например, если видеокамера размещена в проходе 4, то она будет просматривать залы 1 и 4; если видеокамера размещена в проходе 11, то она будет просматривать залы 7 и 8. Галерея решила не размещать камеры на самом входе в галерею. Целью является установка системы видеонаблюдения, покрывающей все залы галереи с минимальным числом видеокамер.

Сформулировать модель 0-1 целочисленного программирования для размещения видеокамер в галерее.

Введем решающие переменные Пример. Проектирование системы видеонаблюдения - №1 - открытая онлайн библиотека если видеокамера установлена в проходе Пример. Проектирование системы видеонаблюдения - №2 - открытая онлайн библиотека , иначе Пример. Проектирование системы видеонаблюдения - №3 - открытая онлайн библиотека .

Тогда целевая функция (минимизация числа видеокамер) имеет вид:

Пример. Проектирование системы видеонаблюдения - №4 - открытая онлайн библиотека

Ограничение для зала 1 имеет вид:

Пример. Проектирование системы видеонаблюдения - №5 - открытая онлайн библиотека , т.е. зал 1 должен просматриваться хотя бы одной из камер, установленных в проходах 1, 4, 6.

Записывая ограничения для всех залов, получим следующую модель:

Пример. Проектирование системы видеонаблюдения - №6 - открытая онлайн библиотека

Пример. Проектирование системы видеонаблюдения - №7 - открытая онлайн библиотека

Рис. 1.1. Залы галереи.