WikiSort.ru - Не сортированное

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

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

В случае, когда бюджеты исполнителей и все стоимости работ равны 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}}$ .

конец цикла

См. также

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

Примечания

Ссылки

• 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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.