METODA WĘGIERSKA: NA CZYM ONA POLEGA, PRZYKŁAD - DUDAS - 2025

Metoda węgierska to algorytm używany w przypadku problemów z alokacją, gdy chcesz zminimalizować koszty. Oznacza to, że służy do znalezienia minimalnego kosztu poprzez przypisanie wielu osób do różnych działań na podstawie najmniejszego kosztu. Każde działanie musi być przypisane do innej osoby.

Problem alokacji to szczególny rodzaj problemu programowania liniowego, którego celem jest zminimalizowanie kosztów lub czasu wykonywania wielu zadań przez wiele osób.

Źródło: pixabay.com

Jedną z ważnych cech problemu alokacji jest to, że tylko jedno stanowisko (lub pracownik) jest przypisane do maszyny (lub projektu).

Metodę tę opracował węgierski matematyk D. Konig. Z tego powodu jest znana jako węgierska metoda rozwiązywania problemów z przypisaniem. Jest również znany jako algorytm alokacji Kuhn-Munkres.

Każdy problem z alokacją można łatwo rozwiązać, stosując tę ​​metodę, która składa się z dwóch faz:

- W pierwszej fazie następuje redukcja rzędów i kolumn.

- W drugiej fazie rozwiązanie jest optymalizowane iteracyjnie.

Jaka jest metoda węgierska?

Metoda węgierska składa się z czterech kroków. Pierwsze dwa kroki są wykonywane tylko raz, podczas gdy kroki 3 i 4 są powtarzane, aż do znalezienia optymalnego przydziału.

Macierz kwadratowa rzędu n na n jest uważana za dane wejściowe, które muszą zawierać tylko elementy nieujemne.

Dla danego problemu, jeśli liczba wierszy w macierzy nie jest równa liczbie kolumn, w zależności od przypadku należy dodać wiersz fikcyjny lub kolumnę fikcyjną. Koszty alokacji dla tych fikcyjnych komórek są zawsze alokowane jako zero.

Krok 1: odejmij minima każdego wiersza

Dla każdego wiersza w tablicy element o najniższej wartości jest wybierany i odejmowany od każdego elementu w tym wierszu.

Krok 2: odejmij wartości minimalne z każdej kolumny

Podobnie element o najniższej wartości jest wybierany dla każdej kolumny i odejmowany od każdego elementu w tej kolumnie.

Krok 3: zakryj wszystkie zera minimalną liczbą wierszy

Wszystkie zera w macierzy wynikającej z kroku 2 muszą być zakryte za pomocą minimalnej liczby poziomych i pionowych linii w wierszach lub kolumnach.

Jeśli w sumie potrzeba n wierszy, aby pokryć wszystkie zera, gdzie n jest równe rozmiarowi n razy n macierzy, zostanie uzyskana optymalna alokacja między zerami i dlatego algorytm się zatrzyma.

W przeciwnym razie, jeśli mniej niż n wierszy jest wymaganych do pokrycia wszystkich zer w tablicy, przejdź do kroku 4.

Krok 4: utwórz dodatkowe zera

Zaznaczany jest najmniejszy element macierzy (zwany k), który nie jest objęty żadną z linii wykonanych w kroku 3.

Wartość k jest odejmowana od wszystkich elementów, które nie są objęte liniami. Następnie wartość ka jest dodawana do wszystkich elementów, które są objęte przecięciem dwóch linii.

Elementy, które są objęte jedną linią, pozostają bez zmian. Po wykonaniu tego kroku wrócisz do kroku 3.

Optymalna alokacja

Po zatrzymaniu algorytmu w kroku 3, zestaw zer jest wybierany w taki sposób, że każdy wiersz i każda kolumna mają zaznaczone tylko jedno zero.

Jeśli w tym procesie selekcji nie ma pojedynczego zera w wierszu lub kolumnie, zostanie wybrane jedno z tych zer. Pozostałe zera w tej kolumnie lub wierszu są usuwane, powtarzając to samo dla innych przypisań.

Jeśli nie ma przypisania pojedynczego zera, istnieje wiele rozwiązań. Jednak koszt pozostanie taki sam dla różnych zestawów przydziałów.

Wszelkie dodane wiersze lub kolumny są usuwane. Zera wybrane w tej ostatecznej macierzy odpowiadają zatem idealnemu przyporządkowaniu wymaganemu w oryginalnej macierzy.

Przykład

Rozważmy firmę, w której istnieją cztery czynności (A1, A2, A3, A4), które muszą być wykonywane przez czterech pracowników (T1, T2, T3, T4). Należy przypisać jedno działanie na pracownika.

Poniższa macierz przedstawia koszt przypisania określonego pracownika do określonej czynności. Celem jest zminimalizowanie całkowitego kosztu zadania składającego się z tych czterech czynności.

Krok 1: odejmij minima każdego wiersza

Zaczynasz od odjęcia elementu o minimalnej wartości w każdym wierszu od innych elementów w tym wierszu. Na przykład najmniejszy element w pierwszym rzędzie to 69. Dlatego 69 jest odejmowane od każdego elementu w pierwszym rzędzie. Otrzymana macierz to:

Krok 2: odejmij wartości minimalne z każdej kolumny

W ten sam sposób element o minimalnej wartości każdej kolumny jest odejmowany od pozostałych elementów tej kolumny, uzyskując następującą macierz:

Krok 3: zakryj wszystkie zera minimalną liczbą wierszy

Teraz określimy minimalną liczbę linii (poziomych lub pionowych), które są wymagane do pokrycia wszystkich zer w macierzy. Wszystkie zera można pokryć za pomocą 3 linii:

Ponieważ wymagana liczba wierszy wynosi trzy i jest mniejsza niż rozmiar macierzy (n = 4), przechodzimy do kroku 4.

Krok 4: utwórz dodatkowe zera

Wybierany jest najmniejszy element nieobjęty liniami, którego wartość wynosi 6. Wartość ta jest odejmowana od wszystkich elementów nieobjętych i ta sama wartość jest dodawana do wszystkich elementów objętych przecięciem dwóch linii. Daje to następującą macierz:

Jak wskazano w metodzie węgierskiej, krok trzeci należy wykonać ponownie.

Krok 3 (powtórz)

Ponownie określana jest minimalna liczba wierszy wymaganych do pokrycia wszystkich zer w macierzy. Tym razem wymagane są cztery wiersze:

Ponieważ liczba wymaganych wierszy wynosi 4, co odpowiada rozmiarowi macierzy (n = 4), mamy optymalny podział między zerami w macierzy. Dlatego algorytm zatrzymuje się.

Optymalna alokacja

Jak wskazuje metoda, wybór dokonany z następujących zer odpowiada optymalnemu przyporządkowaniu:

Ten wybór zer odpowiada następującej optymalnej alokacji w pierwotnej macierzy kosztów:

Dlatego pracownik 1 musi wykonać czynność 3, pracownik 2, czynność 2, pracownik 3, czynność 1, a pracownik 4 musi wykonać czynność 4. Całkowity koszt tego optymalnego przydziału wynosi 69 + 37 + 11 + 23 = 140.

Bibliografia

1. Algorytm węgierski (2019). Algorytm węgierski. Zaczerpnięte z: hungarianalgorithm.com.
2. Badanie (2019). Używanie węgierskiego algorytmu do rozwiązywania problemów z przydziałami. Zaczerpnięte z: study.com.
3. Wisdom Jobs (2018). Węgierska metoda rozwiązywania problemu przydziału - ilościowe techniki zarządzania. Zaczerpnięte z: wisdomjobs.com.
4. Geeks for Geeks (2019). Węgierski algorytm dla problemu przydziału. Zaczerpnięte z: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Węgierski algorytm maksymalnego dopasowania. Znakomity. Zaczerpnięte z: brilliant.org.