Лекция: Задачи о покрытии и упаковке

Многие задачи размещения и задачи календарного планирования могут быть сформулированы в виде задач о покрытии множества, об упаковке множеств или о разбиении множества. Ниже сформулированы три различных вида задач о покрытии и упаковке. Для данных

a) конечного множества элементов ,

b) семейства подмножеств с прибылью (или расходами), связанными с каждым членом ,

найти набор членов, максимизирующий прибыль (или минимизирующий расходы), при этом каждый элемент находится в

(P1) самое большее в одном члене (задача об упаковке);

(P2) по крайней мере в одном члене (задача о покрытии);

(P3) точно в один член (задача о разбиении множества).

Три задачи (P1), (P2) и (P3) формулируются в виде задач целочисленного линейного программирования.

Пусть ‑ матрица :

Введем решающие переменные :

Тогда задача (P2) о покрытии имеет вид:

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

Задача (P1) об упаковке имеет вид:

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

Задача (P3) о разбиении множества имеет вид:

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

Очевидно, что решение задачи о разбиении является так же решением задачи о покрытии, но обратное, вообще говоря, неверно. Задача о разбиении может не иметь решения при разрешимой задаче о покрытии.

Пример. Пусть

,,, ,

,,,,,, .

Здесь Составим матрицу :

В каждой строке матрицы А содержится хотя бы одна единица, поэтому задача имеет решение.

Оптимальное покрытие образуют наборы множеств и другие; число подмножеств в оптимальном покрытии равно трем. Среди приведенных наборов нет ни одного такого, чтобы в нем были лишь попарно непересекающиеся подмножества.

В рассмотренном примере задача о разбиении неразрешима. Если положить, то задача разбиения имеет несколько решений; приведем некоторые из них: .

Вместе с множеством решение образует любая пара непересекающихся множеств и таких, что .

Это такие пары: Других оптимальных (и допустимых) решений нет. Все допустимые решения оптимальны.

Задача о разбиении часто встречается при решении различных задач дискретной оптимизации. Так, она используется при решении симметричной задачи коммивояжера с большим числом городов.