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

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

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

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

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

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

Определение

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

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

maximize ∑ i = 1 m ∑ j = 1 n p i j x i j . {displaystyle sum _{i=1}^{m}sum _{j=1}^{n}p_{ij}x_{ij}.} subject to ∑ j = 1 n w i j x i j ≤ w i i = 1 , … , m {displaystyle sum _{j=1}^{n}w_{ij}x_{ij}leq w_{i}qquad i=1,ldots ,m} ; ∑ i = 1 m x i j ≤ 1 j = 1 , … , n {displaystyle sum _{i=1}^{m}x_{ij}leq 1qquad j=1,ldots ,n} ; x i j ∈ { 0 , 1 } i = 1 , … , m , j = 1 , … , n {displaystyle x_{ij}in {0,1}qquad i=1,ldots ,m,quad j=1,ldots ,n} ;

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

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

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

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

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

Формально:

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

T [ i ] = j {displaystyle T[i]=j} означает, что на работу x i {displaystyle x_{i}} предполагается назначить исполнителя b j {displaystyle b_{j}} , T [ i ] = − 1 {displaystyle T[i]=-1} означает, что на работу x i {displaystyle x_{i}} никто не назначен.

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

P j [ i ] = p i j {displaystyle P_{j}[i]=p_{ij}} , если работа x i {displaystyle x_{i}} не выбрана (т.е. T [ i ] = − 1 {displaystyle T[i]=-1} ) P j [ i ] = p i j − p i k {displaystyle P_{j}[i]=p_{ij}-p_{ik}} , если работу x i {displaystyle x_{i}} предполагается отдать исполнителю b k {displaystyle b_{k}} (т. е. T [ i ] = k {displaystyle T[i]=k} ).

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

Присваиваются начальные значения T [ i ] = − 1 {displaystyle T[i]=-1} для всех i = 1 … n {displaystyle i=1ldots n} Для всех j = 1... m {displaystyle j=1...m} выполнить: Используется алгоритм аппроксимации для получения распределения работ для исполнителя b j {displaystyle b_{j}} , используя функцию остатка дохода P j {displaystyle P_{j}} . Обозначаются выбранные работы S j {displaystyle S_{j}} . Подправляется T {displaystyle T} , используя S j {displaystyle S_{j}} , т. е. T [ i ] = j {displaystyle T[i]=j} для всех i ∈ S j {displaystyle iin S_{j}} . конец цикла