Прикладные задачи покрытия

Рассмотрим прикладные задачи размещения средств обслуживания, которые могут быть сформулированы в виде задач покрытия множеств. Имеется множество потенциальных мест для размещения центров обслуживания и множество районов , требующих услуг обслуживания. Расходы на размещение центра в составляет . Подмножество районов, которые могут быть обслужены центром, размещенным в , обозначено . Введем бинарную переменную :

Пусть ‑ матрица инцидентности для ; тогда

.

Задача выбора множества мест для размещения центров обслуживания с минимальной суммарной стоимостью является задачей покрытия множества:

при ограничениях

(каждый район должен быть обслужен центрами обслуживания)