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

Задача про призначення може бути описана через різні прикладні ситуації. Наприклад, є ряд агентів і ряд завдань. Будь-який агент може бути призначений для виконання будь-якого завдання. Виконання агентом завдання пов'язане з витратами, які змінюються в залежності від того, який агент виконує завдання. Необхідно виконати всі завдання, призначивши для кожного завдання лише одного агента, таким чином, щоби загальні витрати були мінімальні.

Якщо кількість агентів і завдань однакові, а загальна вартість виконання всіх завдань дорівнює сумі витрат виконання окремих завдань, то задача називається лінійною задачею про призначення. Цей варіант задачі є базовим і найпростішим. Зазвичай, говорячи про задачу про призначення без додаткових вимог, мають на увазі лінійну задачу про призначення.

В інших варіантах задачі можуть бути додаткові умови, інші способи розрахунку загальних витрат, базові умови можуть бути дещо змінені. Наприклад, може бути неоднакова кількість агентів і завдань, нелінійність у визначенні загальних витрат тощо. В таких випадках кажуть про узагальнену задачу про призначення.

Для розв'язання лінійної задачі про призначення можуть бути застосовані різні методи. Від загальних методів розв'язання задач лінійного програмування до спеціальних методів розв'язування задач на графах. Як правило, спеціальні методи, що розроблені саме для цієї задачі, є значно більш швидкими оскільки враховують і використовують особливості структури задачі. Так, наприклад, Угорський алгоритм є одним із перших алгоритмів, який був розроблений для вирішення лінійної задачі про призначення. Час розв'язання задачі пропорційний числу агентів. Іншими алгоритмами, що застосовуються для вирішення задачі є адаптовані симплекс алгоритм і алгоритм аукціону.

Припустимо, що фірма таксі має три доступні машини (агенти) і замовлення від трьох клієнтів (завдання), які бажають поїхати якомога швидше. Фірма пишається тим, що якнайшвидше обслуговує своїх клієнтів, тому для кожного таксі «вартість» забирання конкретного клієнта встановлюється як час, що необхідний, щоб таксі було подано клієнту. Рішення цієї задачі про призначення — це таке парування таксі і клієнтів, щоби сумарний час подачі машин клієнтам був найменшим.

Тим не менш, завдання про призначення може бути гнучкішим, ніж здається на перший погляд. У наведеному вище прикладі, припустимо, що існує чотири доступні таксі, але, як і раніше, тільки три клієнти. Тоді четвертим завданням призначимо «нікуди не їхати» з вартістю 0 для кожного таксі. Така задача розв'язується так само, як і попередня.

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

Математичне визначення задачі про призначення виглядає наступним чином: дано дві множини, A (agents) і T (tasks), рівного розміру, разом з ваговою функцією C (costs): A × T → R. Знайти Бієкцію (взаємно-однозначну відповідність, парування) f : A → T таку, що функція загальних витрат:

${\displaystyle \sum _{a\in A}C(a,f(a))}$ : має мінімальне значення.

Зазвичай вагова функція ${\displaystyle C(a,t)}$ задається як множина чисел ${\displaystyle C_{ij}}$ для усіх пар ${\displaystyle (i,j)}$, де ${\displaystyle i\in A,j\in T}$.

Задача записується як задача лінійного програмування

${\displaystyle \sum _{i\in A}\sum _{j\in T}C_{ij}x_{ij}}$

з обмеженнями:

${\displaystyle \sum _{j\in T}x_{ij}=1{\text{ for all }}i\in A,\,}$

${\displaystyle \sum _{i\in A}x_{ij}=1{\text{ for all }}j\in T,\,}$

${\displaystyle x_{ij}\geq 0{\text{ for all pairs }}(i,j)\in A{\text{x}}T.\,}$

Змінна ${\displaystyle x_{ij}}$ — приймає значення ${\displaystyle 1}$, якщо агент ${\displaystyle i}$ виконує завдання ${\displaystyle j}$, і ${\displaystyle 0}$ у протилежному випадку. Мінімальне значення Цільової функції може досягатися при різних не завжди цілих значеннях змінних ${\displaystyle x_{ij}}$, але при цьому завжди існує інше оптимальне рішення задачі, де змінні приймають цілі значення. Це тому, об'єднана матриця обмежень задачі є повністю Унімодулярною. Перше обмеження вимагає, щоб кожен агент виконував рівно одне завдання, друге — щоб кожне завдання виконувалось тільки одним агентом.

• Burkard, Rainer; M. Dell'Amico, S. Martello (2012). Assignment Problems (Revised reprint). SIAM. ISBN 978-1-61197-222-1.
• Пападимитриу, Христос; К. Стайглиц (1985). Комбинаторная оптимизация. Алгоритмы и сложность. Мир.
• Кристофидес, Никос (1978). Теория графов. Алгоритмический подход. Мир.