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