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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Задача про призначення є окремим випадком транспортної задачі, яка є окремим випадком задачі мінімального руху вартості[en], що, в свою чергу, є окремим випадком задачі лінійного програмування.

Узагальнений опис проблеми[ред.ред. код]

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

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

Алгоритми і узагальнення[ред.ред. код]

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

Приклад[ред.ред. код]

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

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

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

Математичне визначення[ред.ред. код]

Математичне визначення задачі про призначення виглядає наступним чином: Дано дві множини, A і T , рівного розміру, разом з ваговою функцією C : A × T. Знайти Бієкцію f : AT таку, що функція витрат:

\sum_{a\in A}C(a,f(a))
мінімізується.

Зазвичай вагова функція розглядається як квадратні речові (з дійсними числами) матриці C, тому функція вартості записується наступним чином:

\sum_{a\in A}C_{a,f(a)}

Задача є "лінійною", оскільки функція вартості повинна бути оптимізована так як і всі обмеження, які містять тільки лінійні умови.

\sum_{i\in A}\sum_{j\in T}C(i,j)x_{ij}

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

\sum_{j\in T}x_{ij}=1\text{ for }i\in A, \,
\sum_{i\in A}x_{ij}=1\text{ for }j\in T, \,
x_{ij}\ge 0\text{ for }i,j\in A,T. \,

Змінна Xij - завдання призначене агенту, приймає значення 1, якщо завдання виконується, і 0 у протилежному випадку. Це формулювання дозволяє також використовувати дробові значення змінних, але завжди є оптимальне рішення, де змінні приймають цілі значення. Це тому, що матриці обмежень абсолютно унімодулярні. Перше обмеження вимагає, щоб кожен агент відносився до якої-небудь однієї задачі, а друге обмеження вимагає, щоб кожне завдання призначалось лише одному агенту.

Джерела[ред.ред. код]