ься до місця очікування, визначеного замовником. Рішенням задачі про призначення буде розподіл машин за замовниками, таке, що сумарна ціна (сумарний час очікування) мінімально.
Задачу про призначення можна зробити більш гнучкою. У наведеному вище прикладі можуть виявитися не три, а чотири вільних таксі, але замовника, як і раніше, три. Можна призначити четверту задачу, яку можна назвати «сиди тихо, нічого не роби», з ціною 0 для машини, якою вона призначається. Завдання може бути вирішена звичайним методом і знову дасть найкраще рішення.
Аналогічний прийом можна використовувати у випадку, коли число замовлень може перевищувати число доступних машин, і машина може бути призначена на виконання декількох робіт, а також коли робота може бути призначена декільком виконавцям (наприклад, якщо замовник - група , не поміщається в одне таксі). Можна також поставити завдання збільшення доходу, а не мінімізацію ціни.
6. Угорська алгоритм
Угорська алгоритм - алгоритм оптимізації, вирішальний завдання про призначення за поліноміальний час. Він був розроблений і опублікований Харолда Куном ( англ. ) в 1955 році. Автор дав йому ім'я «угорський метод» у зв'язку з тим, що алгоритм в значній мірі заснований на більш ранніх роботах двох угорських математиків (Кеніга і Егерварі ( англ. )).
Джеймс Манкрес ( англ. ) в 1957 році помітив, що алгоритм є (строго) поліноміальним. З цього часу алгоритм відомий також як алгоритм Куна - Манкреса або алгоритм Манкреса рішення задачі про призначення . Тимчасова складність оригінального алгоритму була O (n 4 ) , проте Едмондс ( англ. ) і Карпо (а також Томідзава незалежно від них) показали, що його можна модифікувати так, щоб досягти часу виконання O (n 3 ) . Форд і Фалкерсоном ( англ. ) поширили метод на загальні транспортні завдання. У 2006 році було виявлено, що Якобі знайшов рішення задачі про призначення в XIX столітті і опублікував його в 1890 році на латині.
Постановка завдання.
Дана неотрицательная матриця розміру n Ч n , де елемент в i -й рядку і j -му стовпці відповідає вартості виконання j -ого виду робіт i -м працівником. Потрібно знайти таку відповідність робіт працівникам, щоб витрати на оплату праці були найменшими. Якщо мета полягає в знаходженні призначення з найбільшою вартістю, то рішення зводиться до вирішення щойно сформульованої задачі шляхом заміни кожної вартості C на різницю між максимальною вартістю і C .
Матрична інтерпретація алгоритму
Для n працівників і робіт, дана матриця n Ч n (матриця вартості), що задає вартість виконання кожної роботи кожним працівником. Знайти мінімальну вартість виконання робіт, таку що кожен працівник виконує рі...
