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

Задача про призначення є однією з базових задач комбінаторної оптимізації в галузі оптимізації або дослідження операцій в математиці. Вона полягає в знаходженні парування мінімальної (або максимальної) ваги між елементами двох скінчених множин. Вона може бути подана як знаходження парування у зваженому двочастковому графі.

З іншого боку Задача про призначення належить до задач лінійного програмування. Вона є спеціальним випадком транспортної задачі, яка своєю чергою може бути представлена як Задача про потік мінімальної вартості^[en].

Узагальнений опис задачі

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

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

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

Алгоритми

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

Приклад

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

Розв'язання цієї задачі про призначення — це таке парування таксі й клієнтів, щоб сумарний час подачі машин клієнтам був найменшим.

Однак, завдання про призначення може бути гнучкішим, ніж здається на перший погляд. У наведеному вище прикладі, припустимо, що існує чотири доступні таксі, але, як і раніше, тільки три клієнти. Тоді четвертим завданням призначимо «нікуди не їхати» з вартістю 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). Теория графов. Алгоритмический подход. Мир.