Угорський метод - це алгоритм, що дозволяє мінімізувати витрати в задачі оптимізації, заснованій на лінійному програмуванні.
Метою угорського методу є пошук мінімальних витрат на комплекс завдань, які повинні виконувати найбільш підходящі люди.
Він використовує лінійне програмування (PL) для виконання ряду кроків, які можна автоматизувати. Таким чином, такі інструменти, як статистичне програмне забезпечення R (серед іншого), мають кілька дуже корисних пакетів для цих задач оптимізації.
Походження угорського методу
Її творцем був угорський математик (звідси і назва) Гарольд В. Кун у 1955 р. Інший математик, Джеймс Мюнкрес, переглянув його в 1957 р. З цією еволюцією він отримав інші назви, такі як алгоритм розподілу Мункреса або Кун-Мункреса.
З іншого боку, цей метод має прецедент у двох авторів, Денеса Кеніга та Єне Егерварі, як євреїв, так і угорців. Перший розробив теорію графів, на якій базується цей алгоритм. Другий узагальнив теорему Кеніга і дозволив Куну розробити метод.
Етапи угорського методу
Подальші кроки дозволяють здійснити угорський метод простим способом, використовуючи електронну таблицю. Крім того, ця схема, яку ми демонструємо, дозволить нам бачити у глобальному плані процес, який ми детально розробимо на кінцевому прикладі.
- В якості попередніх кроків вам потрібно призначити людей (рядки) для ряду проектів (стовпців). Крім того, необхідно розрахувати різні витрати кожного проекту залежно від того, хто його виконує, та побудувати матрицю (C) з цією інформацією.
- У матриці (C) шукаємо мінімальне значення кожного рядка. Ми віднімаємо це з усіх елементів у рядку і виконуємо ту ж операцію зі стовпцями. З'явиться нова матриця (C`) з результатами попередніх операцій.
- Далі ми створюємо «графік рівності», який дозволяє нам вибирати завдання та проекти з найменшими витратами. Оптимальними будуть ті елементи, результат яких був нульовим. Якщо правда, що не існує елемента з нульовим значенням, призначеним для більш ніж одного рядка, алгоритм закінчується.
- В іншому випадку потрібно зробити нове призначення. Створено нову матрицю, до якої застосовано ряд модифікацій, як ми побачимо на прикладі. Ми відтворюємо графік і продовжуємо, поки не отримаємо матрицю, яка має принаймні один нуль у кожному рядку та в неповторюваних позиціях.
- З цією інформацією ми вже маємо призначених людей та проекти (нулі), які оптимізують проблему. Якщо завдання вже призначене в попередньому рядку, воно відкидається в наступному. Для обчислення мінімальних витрат додаємо витрати початкової матриці, які відображаються в положенні цих нулів.
Приклад угорського методу
Давайте розглянемо простий приклад угорського методу. Уявімо, у нас є троє робітників, і вони повинні бути призначені на три проекти. Ми створюємо початкову матрицю (C) і значення вартості в кожній комірці. Для цього вам потрібно використовувати інформацію, доступну в компанії. Отримавши все це, ми починаємо процес. Таблиця може допомогти.
Ми обчислюємо мінімуми кожного рядка і віднімаємо їх з елементів цього рядка і робимо те ж саме зі стовпцями (кроки 1 і 2). В отриманій матриці (C`) ми проводимо лінії таким чином, що вони охоплюють всі нулі і, в свою чергу, перетинають одна одну (крок 3). Ми бачимо, що є два рядки, але найбільше значення кількості рядків або стовпців - три. Ми мусимо йти далі.
Тепер ми вибираємо найменше з непокритих чисел, у цьому прикладі це два (темно-синій). Ми віднімаємо його від попередніх і додаємо до тих, які розташовані там, де прямі перетинаються. У нашому випадку це ще два (E3, T1). Нам залишається нова матриця (крок 4). Перерисовуємо лінії і підраховуємо. Є три рядки, однакові з кількістю рядків або стовпців. Алгоритм закінчений.
Починаємо з рядка або стовпця з найменшою кількістю нулів (E1, T1). Якщо завдання вже призначене, його неможливо перепризначити, наприклад, за допомогою E2 ви не можете використовувати перший нуль T1, оскільки це завдання було призначено E1. Загальна вартість, за угорським методом, буде сумою витрат вихідної матриці (Крок 1), розташованої в тому самому положенні, що і вибрані нулі (Крок 5).