Русская Википедия:Обобщённая задача о назначениях

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

Определение

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

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

maximize <math>\sum_{i=1}^m\sum_{j=1}^n p_{ij} x_{ij}.</math>

subject to <math>\sum_{j=1}^n w_{ij} x_{ij} \le w_i \qquad i=1, \ldots, m</math>;

<math> \sum_{i=1}^m x_{ij} \leq 1 \qquad j=1, \ldots, n</math>;

<math> x_{ij} \in \{0,1\} \qquad i=1, \ldots, m, \quad j=1, \ldots, n</math>;

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

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

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

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

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

Формально:

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

<math>T[i]=j</math> означает, что на работу <math>x_i</math> предполагается назначить исполнителя <math>b_j</math>,

<math>T[i]=-1</math> означает, что на работу <math>x_i</math> никто не назначен.

Остаток дохода на итерации <math>j</math> обозначается через <math>P_j</math>, где

<math>P_j[i]=p_{ij}</math>, если работа <math>x_i</math> не выбрана (т.е. <math>T[i]=-1</math>)

<math>P_j[i]=p_{ij}-p_{ik}</math>, если работу <math>x_i</math> предполагается отдать исполнителю <math>b_k</math> (т. е. <math>T[i]=k</math>).

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

Присваиваются начальные значения <math>T[i]=-1</math> для всех <math>i = 1\ldots n</math>

Для всех <math>j=1...m</math> выполнить:

Используется алгоритм аппроксимации для получения распределения работ для исполнителя <math>b_j</math>, используя функцию остатка дохода <math>P_j</math>. Обозначаются выбранные работы <math>S_j</math>.

Подправляется <math>T</math>, используя <math>S_j</math>, т. е. <math>T[i]=j</math> для всех <math>i \in S_j</math>.

конец цикла

См. также

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

Ссылки

• 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