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

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

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

Задача про призначення є однією з основних задач комбінаторної оптимізації в галузі оптимізації або дослідження операцій в математиці. Вона полягає в знаходженні максимальної ваги для зваженого в дводольному графіку. У найзагальнішому вигляді проблема виглядає таким чином: Є цілий ряд агентів, а також ряд завдань. Будь-який агент може бути призначений для виконання будь-якого завдання, несучи певні витрати, які можуть змінюватись в залежності від агента, який виконує призначене завдання. Це необхідно для виконання всіх завдань, призначивши лише одного агента для кожної задачі таким чином, що загальна вартість завдань будуть зведені до мінімуму. Якщо число агентів і задачі дорівнюють, а загальна вартість призначення для всіх задач дорівнює сумі витрат для кожного агента (або сума витрат на кожну задачу, яка є одне і те ж в даному випадку) , то задача називається лінійною задачею про призначення. Зазвичай, говорячи про задачу про призначення без додаткових вимог, мають на увазі лінійну задачу про призначення. Алгоритми і узагальнення Угорський алгоритм є одним із багатьох алгоритмів, який був розроблений для вирішення задачі лінійного призначення протягом часу обмеженим багаточленом вираженим числом агентів. Задача про призначення є окремим випадком транспортної задачі, яка є окремим випадком задачі мінімального руху вартості, що, в свою чергу, є окремим випадком задачі лінійного програмування. Хоча можна вирішити будь-яку з цих задач за допомогою простого алгоритму, кожна спеціалізація має більш ефективні алгоритми розроблені для використання переваг своєї особливої структури. Якщо вартість включає в себе функцію квадратичної нерівності, тоді вона називається квадратичною задачею про призначення. Приклад Припустимо, що фірма таксі має три доступні таксі (агенти) і три клієнтами (завдання), які бажають бути забрані якомога швидше. Фірма пишається тим, що якнайшвидше забирає своїх клієнтів, тому для кожного таксі "вартість" забирання конкретного клієнта буде залежати від часу, необхідного для таксі, щоб досягти точки, де знаходиться клієнт. Рішення задачі про призначення – це комбінація таксі і клієнтів, загальна вартість якої буде найменша. Тим не менш, завдання про призначення може бути гнучкішим, ніж здається на перший погляд. У наведеному вище прикладі, припустимо, що існує чотири таксі, доступні, але все одно є тільки три клієнти. Тоді четверте завдання може бути придумане, яке можна назвати "сидячи на місці, нічого не роблячи», з вартістю 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 у протилежному випадку. Це формулювання дозволяє також використовувати дробові значення змінних, але завжди є оптимальне рішення, де змінні приймають цілі значення. Це тому, що матриці обмежень абсолютно унімодулярні. Перше обмеження вимагає, щоб кожен агент відносився до якої-небудь однієї задачі, а друге обмеження вимагає, щоб кожне завдання призначалось лише одному агенту.

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