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

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

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

Специальные случаи[править | править вики-текст]

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

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

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

Определение[править | править вики-текст]

У нас есть n видов предметов, x_1,\dots ,x_n и m видов ёмкостей b_1,\dots ,b_m. Каждая ёмкость b_i связана с бюджетом w_i. Для каждой пары ёмкость b_i и предмет x_j задан доход p_{i,j} и вес w_{i,j}. Решением является подмножество предметов U и распределение предметов из U по ёмкостям. Решение преемлемо, если вес предметов в ёмкости b_i не превосходит бюджета w_i. Доходом от решения является сумма всех доходов всех распределений предмет-ёмкость.

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

maximize \sum_{i=1}^m\sum_{j=1}^n p_{ij} x_{ij}.
subject to \sum_{j=1}^n w_{ij} x_{ij} \le w_i \qquad i=1, \ldots, m;
 \sum_{i=1}^m x_{ij} \leq 1 \qquad j=1, \ldots, n;
 x_{ij} \in \{0,1\} \qquad i=1, \ldots, m, \quad j=1, \ldots, n;

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

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

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

Жадный аппроксимирующий алгоритм[править | править вики-текст]

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

Формально:

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

T[i]=j означает, что предмет x_i предполагается положить в ёмкость b_j
T[i]=-1 означает, что предмет x_i не выбран .

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

P_j[i]=p_{ij} если предмет x_i не выбран (т.е. T[i]=-1)
P_j[i]=p_{ij}-p_{ik} если предмет x_i предполагается положить в ёмкость b_k (т.е. T[i]=k).

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

Присвоим начальные значения T[i]=-1 для всех i = 1\ldots n
Для всех j=1...m выполнить:
Используем алгоритм аппроксимации для получения распределения предметов для ёмкости b_j, используя функцию остатка дохода P_j. Обозначим выбранные предметы S_j.
Подправим T, используя S_j, т.е. T[i]=j для всех 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

Внешние ссылки[править | править вики-текст]