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

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

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

Введем решающие переменные если видеокамера установлена в проходе , иначе .

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

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

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

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

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