Узагальнена задача про призначення

У прикладній математиці під узагальненою задачею про призначення розуміють задачу комбінаторної оптимізації, що є узагальненням задачі про призначення, в якій множина виконавців має розмір, не обов'язково рівний розміру множини робіт. При цьому виконавця можна призначити для виконання будь-яких робіт (не обов'язково однієї роботи, як у задачі про призначення). При призначенні виконавця для виконання роботи задається дві величини — ціна і дохід. Кожен виконавець має певний бюджет, так що сума всіх витрат не повинна перевищувати цього бюджету. Потрібно знайти таке призначення виконавців для виконання робіт, щоб максимізувати прибуток.

Особливі випадки

У разі, коли бюджети виконавців і всі вартості робіт дорівнюють 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}$. Доходом від розв'язку є сума всіх доходів усіх розподілів робота-виконавець.

Математично узагальнену задачу про призначення можна сформулювати так:

максимізувати $\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.$

при $\sum _{j=1}^{n}w_{ij}x_{ij}\leq 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 )$.

Апроксимація $({\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}$.

кінець циклу

Див. також

• Задача про призначення

Посилання

• Reuven Cohen, Liran Katzir, Danny and 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