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

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

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

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

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

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

Определение

Имеется n работ ${\displaystyle x_{1},\dots ,x_{n}}$ и m исполнителей ${\displaystyle b_{1},\dots ,b_{m}}$. Каждый исполнитель ${\displaystyle b_{i}}$ имеет бюджет ${\displaystyle w_{i}}$. Для каждой пары исполнитель ${\displaystyle b_{i}}$ и работа ${\displaystyle x_{j}}$ задан доход ${\displaystyle p_{i,j}}$ и вес ${\displaystyle w_{i,j}}$. Решением является подмножество работ U и распределение работ из U по исполнителям. Решение допустимо, если сумма затрат на назначенные работы исполнителя ${\displaystyle b_{i}}$ не превосходит бюджета ${\displaystyle w_{i}}$. Доходом от решения является сумма всех доходов всех распределений работа-исполнитель.

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

maximize ${\displaystyle \sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.}$

subject to ${\displaystyle \sum _{j=1}^{n}w_{ij}x_{ij}\leq w_{i}\qquad i=1,\ldots ,m}$;

${\displaystyle \sum _{i=1}^{m}x_{ij}\leq 1\qquad j=1,\ldots ,n}$;

${\displaystyle x_{ij}\in \{0,1\}\qquad i=1,\ldots ,m,\quad j=1,\ldots ,n}$;

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

Фляйшер, Гоманс, Мирокни и Свириденко предложили комбинаторный алгоритм локального поиска с аппроксимацией ${\displaystyle (2+\varepsilon )}$ и алгоритм на основе линейного программирования с аппроксимацией ${\displaystyle ({\frac {e}{e-1}}+\varepsilon )}$^[1].

Аппроксимация ${\displaystyle ({\frac {e}{e-1}}+\epsilon )}$ является лучшей известной аппроксимацией обобщенной задачи о назначениях.

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

Используя алгоритм ${\displaystyle \alpha }$-аппроксимации задачи о назначениях, можно создать (${\displaystyle \alpha +1}$)-аппроксимацию для обобщенной задачи о назначениях на манер жадного алгоритма используя концепцию остатка дохода. Алгоритм итерационно создает предварительную последовательность, в которой на итерации ${\displaystyle j}$ предполагается закрепить работы за исполнителем ${\displaystyle b_{j}}$. Выбор для исполнителя ${\displaystyle b_{j}}$ может быть изменён в дальнейшем при закрепление работ за другими исполнителям. Остаток дохода работы ${\displaystyle x_{i}}$ для исполнителя ${\displaystyle b_{j}}$ равен ${\displaystyle p_{ij}}$, если ${\displaystyle x_{i}}$ не отдана другому исполнителю, и ${\displaystyle p_{ij}}$ – ${\displaystyle p_{ik}}$, если работа отдана исполнителю ${\displaystyle b_{k}}$.

Формально:

Используем вектор ${\displaystyle T}$ для предварительного выбора и в этом векторе

${\displaystyle T[i]=j}$ означает, что на работу ${\displaystyle x_{i}}$ предполагается назначить исполнителя ${\displaystyle b_{j}}$,

${\displaystyle T[i]=-1}$ означает, что на работу ${\displaystyle x_{i}}$ никто не назначен.

Остаток дохода на итерации ${\displaystyle j}$ обозначается через ${\displaystyle P_{j}}$, где

${\displaystyle P_{j}[i]=p_{ij}}$, если работа ${\displaystyle x_{i}}$ не выбрана (т.е. ${\displaystyle T[i]=-1}$)

${\displaystyle P_{j}[i]=p_{ij}-p_{ik}}$, если работу ${\displaystyle x_{i}}$ предполагается отдать исполнителю ${\displaystyle b_{k}}$ (т. е. ${\displaystyle T[i]=k}$).

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

Присваиваются начальные значения ${\displaystyle T[i]=-1}$ для всех ${\displaystyle i=1\ldots n}$

Для всех ${\displaystyle j=1...m}$ выполнить:

Используется алгоритм аппроксимации для получения распределения работ для исполнителя ${\displaystyle b_{j}}$, используя функцию остатка дохода ${\displaystyle P_{j}}$. Обозначаются выбранные работы ${\displaystyle S_{j}}$.

Подправляется ${\displaystyle T}$, используя ${\displaystyle S_{j}}$, т. е. ${\displaystyle T[i]=j}$ для всех ${\displaystyle i\in S_{j}}$.

конец цикла

См. также

• Задача о назначениях

Примечания

1. L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko. Tight approximation algorithms for maximum general assignment problems. In SODA'06: Proc

Ссылки

• 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