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

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

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

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

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

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

при ${\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 )}$.

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

кінець циклу

Див. також

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

Примітки

1. L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko. Tight approximation algorithms for maximum general assignment problems. In SODA'06: Proc

Посилання

• 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