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

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

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

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

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

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

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

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

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

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

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

Формально:

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

Остаток дохода на итерации  обозначается через , где 
, если работа  не выбрана (т.е. ) 
, если работу  предполагается отдать исполнителю  (т. е. ).

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

См. также 
Задача о назначениях

Примечания

Ссылки 
 Reuven Cohen, Liran Katzir, and Danny Raz, "An Efficient Approximation for the Generalized Assignment Problem", Information Processing Letters, Vol. 100, Issue 4, pp. 162–166, November 2006. 
 Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, and Maxim Sviridenko, "Tight Approximation Algorithms for Maximum General Assignment Problems", SODA 2006, pp. 611–620.
 Hans Kellerer, Ulrich Pferschy, David Pisinger, Knapsack Problems , 2005. Springer Verlag ISBN 3-540-40286-1

NP-полные задачи
Исследование операций