УГОРСЬКИЙ МЕТОД: З ЧОГО СКЛАДАЄТЬСЯ, НАПРИКЛАД - ДУДИ - 2025

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

Проблема розподілу - це особливий тип проблеми лінійного програмування, де метою є мінімізація витрат або часу на виконання ряду завдань декількома людьми.

Джерело: pixabay.com

Однією з важливих характеристик проблеми розподілу є те, що лише одна робота (або робітник) призначена машині (або проекту).

Цей метод був розроблений угорським математиком Д. Конігом. З цієї причини він відомий як угорський метод вирішення задач. Він також відомий як алгоритм розподілу Куна-Манкреса.

Будь-яку проблему розподілу можна легко вирішити, застосувавши цей метод, який складається з двох фаз:

- З першим фазовим рядом проводяться скорочення та зменшення стовпців.

- На другій фазі рішення оптимізується на ітераційній основі.

Що таке угорський метод?

Угорський метод складається з чотирьох етапів. Перші два етапи виконуються лише один раз, тоді як кроки 3 та 4 повторюються до тих пір, поки не буде знайдено оптимального розподілу.

Квадратна матриця порядку n на n вважається вхідними даними, які повинні містити лише негативні елементи.

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

Крок 1: віднімайте мінімуми кожного ряду

Для кожного рядка в масиві вибирається елемент з найнижчим значенням і віднімається від кожного елемента в цьому рядку.

Крок 2: віднімайте мінімум з кожного стовпця

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

Крок 3: покрийте всі нулі мінімальною кількістю рядків

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

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

В іншому випадку, якщо для покриття всіх нулів у масиві потрібно менше n рядків, перейдіть до кроку 4.

Крок 4: створіть додаткові нулі

Вибирається найменший елемент матриці (називається k), який не охоплюється однією з ліній, зроблених на кроці 3.

Значення k віднімається від усіх елементів, які не охоплені рядками. Згодом значення ka додається до всіх елементів, які охоплені перетином двох прямих.

Елементи, які охоплені одним рядком, залишаються як є. Виконавши цей крок, ви переходите до кроку 3.

Оптимальний розподіл

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

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

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

Будь-які додані макетні рядки або стовпці видаляються. Таким чином, нулі, вибрані в цій кінцевій матриці, відповідають ідеальному призначенню, необхідному в вихідній матриці.

Приклад

Розглянемо компанію, де є чотири види діяльності (A1, A2, A3, A4), які повинні здійснювати чотири працівники (T1, T2, T3, T4). Один вид діяльності повинен бути призначений на одного працівника.

Наступна матриця показує вартість віднесення певного працівника до певної діяльності. Метою є мінімізація загальної вартості завдання, що складається з цих чотирьох видів діяльності.

Крок 1: віднімайте мінімуми кожного ряду

Ви починаєте з віднімання елемента з мінімальним значенням у кожному рядку від інших елементів у цьому рядку. Наприклад, найменший елемент у першому рядку - 69. Отже, від кожного елемента в першому рядку віднімається 69. Отримана матриця:

Крок 2: віднімайте мінімум з кожного стовпця

Таким же чином елемент з мінімальним значенням кожного стовпця віднімається від інших елементів цього стовпця, отримуючи таку матрицю:

Крок 3: покрийте всі нулі мінімальною кількістю рядків

Тепер ми визначимо мінімальну кількість рядків (горизонтальних чи вертикальних), які необхідні для покриття всіх нулів у матриці. Усі нулі можна покрити за допомогою 3 рядків:

Оскільки кількість потрібних рядків становить три і менше розміру матриці (n = 4), продовжуємо з кроку 4.

Крок 4: створіть додаткові нулі

Вибирається найменший елемент, не охоплений лініями, значення якого 6. Це значення віднімається від усіх не охоплених елементів і це те саме значення додається до всіх елементів, охоплених перетином двох ліній. Це призводить до отримання наступної матриці:

Як зазначено в угорському методі, крок третій повинен бути виконаний ще раз.

Крок 3 (повторити)

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

Оскільки кількість потрібних рядків дорівнює 4, що дорівнює розміру матриці (n = 4), ми маємо оптимальне розподіл між нулями в матриці. Тому алгоритм зупиняється.

Оптимальний розподіл

Як вказує метод, вибір, зроблений із наступних нулів, відповідає оптимальному призначенню:

Цей вибір нулів відповідає наступному оптимальному розподілу в початковій матриці витрат:

Тому працівник 1 повинен виконувати діяльність 3, працівник 2, діяльність 2, робітник 3, діяльність 1, а робітник 4 повинен виконувати діяльність 4. Загальна вартість цього оптимального завдання становить 69 + 37 + 11 + 23 = 140.

Список літератури

1. Угорський алгоритм (2019). Угорський алгоритм. Взято з: Hungarianalgorithm.com.
2. Навчання (2019). Використання угорського алгоритму для вирішення завдань призначення. Взято з: study.com.
3. Wisdom Jobs (2018). Угорський метод вирішення завдання призначення - Кількісні методи управління. Взято з: wisdomjobs.com.
4. Geeks для Geeks (2019). Угорський алгоритм задачі завдання. Взято з: geeksforgeeks.org.
5. Карлі Мур, Натан Лендман (2019). Угорський алгоритм максимального узгодження. Блискуча. Взято з: bril.org.