Обобщённая задача о назначениях

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

В прикладной математике под обобщённой задачей о назначениях понимается задача комбинаторной оптимизации, являющаяся обобщением задачи о назначениях, в которой множество исполнителей имеет размер, не обязательно равный размеру множества работ. При этом исполнитель может быть назначен для выполнения любых работ (не обязательно одной работы, как в задаче о назначениях). При назначении исполнителя для выполнения работы задается две величины — затраты и доход. Каждый исполнитель имеет определённый бюджет, так что сумма всех затрат не должна превышать этот бюджет. Требуется найти такое назначение исполнителей для выполнения работ, чтобы максимизировать доход.

Специальные случаи

[править | править код]

В случае, когда бюджеты исполнителей и все стоимости работ равны 1, задача превращается в задачу о максимальном паросочетании.

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

Если имеется всего один агент, задача сводится к задаче о ранце.

Определение

[править | править код]

Имеется n работ и m исполнителей . Каждый исполнитель имеет бюджет . Для каждой пары исполнитель и работа задан доход и вес . Решением является подмножество работ U и распределение работ из U по исполнителям. Решение допустимо, если сумма затрат на назначенные работы исполнителя не превосходит бюджета . Доходом от решения является сумма всех доходов всех распределений работа-исполнитель.

Математически обобщённую задачу о назначениях можно сформулировать следующим образом:

maximize
subject to ;
;
;

Обобщённая задача о назначениях является NP-трудной и даже APX-трудной.

Фляйшер, Гоманс, Мирокни и Свириденко предложили комбинаторный алгоритм локального поиска с аппроксимацией и алгоритм на основе линейного программирования с аппроксимацией [1].

Аппроксимация является лучшей известной аппроксимацией обобщенной задачи о назначениях.

Жадный аппроксимирующий алгоритм

[править | править код]

Используя алгоритм -аппроксимации задачи о назначениях, можно создать ()-аппроксимацию для обобщенной задачи о назначениях на манер жадного алгоритма используя концепцию остатка дохода. Алгоритм итерационно создает предварительную последовательность, в которой на итерации предполагается закрепить работы за исполнителем . Выбор для исполнителя может быть изменён в дальнейшем при закрепление работ за другими исполнителям. Остаток дохода работы для исполнителя равен , если не отдана другому исполнителю, и , если работа отдана исполнителю .

Формально:

Используем вектор для предварительного выбора и в этом векторе

означает, что на работу предполагается назначить исполнителя ,
означает, что на работу никто не назначен.

Остаток дохода на итерации обозначается через , где

, если работа не выбрана (т.е. )
, если работу предполагается отдать исполнителю (т. е. ).

Таким образом, алгоритм выглядит следующим образом:

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

Примечания

[править | править код]
  1. L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko. Tight approximation algorithms for maximum general assignment problems. In SODA'06: Proc