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

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

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

.

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

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

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