Задачи о покрытии и упаковке
Многие задачи размещения и задачи календарного планирования могут быть сформулированы в виде задач о покрытии множества, об упаковке множеств или о разбиении множества. Ниже сформулированы три различных вида задач о покрытии и упаковке. Для данных
a) конечного множества элементов ,
b) семейства подмножеств с прибылью (или расходами) , связанными с каждым членом ,
найти набор членов , максимизирующий прибыль (или минимизирующий расходы), при этом каждый элемент находится в
(P1) самое большее в одном члене (задача об упаковке);
(P2) по крайней мере в одном члене (задача о покрытии);
(P3) точно в один член (задача о разбиении множества).
Три задачи (P1), (P2) и (P3) формулируются в виде задач целочисленного линейного программирования.
Пусть ‑ матрица :
Введем решающие переменные :
Тогда задача (P2) о покрытии имеет вид:
при ограничениях
Задача (P1) об упаковке имеет вид:
при ограничениях
Задача (P3) о разбиении множества имеет вид:
при ограничениях
Очевидно, что решение задачи о разбиении является так же решением задачи о покрытии, но обратное, вообще говоря, неверно. Задача о разбиении может не иметь решения при разрешимой задаче о покрытии.
Пример. Пусть
, , , ,
, , , , , , .
Здесь Составим матрицу :
В каждой строке матрицы А содержится хотя бы одна единица, поэтому задача имеет решение.
Оптимальное покрытие образуют наборы множеств и другие; число подмножеств в оптимальном покрытии равно трем. Среди приведенных наборов нет ни одного такого, чтобы в нем были лишь попарно непересекающиеся подмножества.
В рассмотренном примере задача о разбиении неразрешима. Если положить , то задача разбиения имеет несколько решений; приведем некоторые из них: .
Вместе с множеством решение образует любая пара непересекающихся множеств и таких, что .
Это такие пары: Других оптимальных (и допустимых) решений нет. Все допустимые решения оптимальны.
Задача о разбиении часто встречается при решении различных задач дискретной оптимизации. Так, она используется при решении симметричной задачи коммивояжера с большим числом городов.
Дата добавления: 2016-06-05; просмотров: 1900;