Metoda węgierska jest algorytmem pozwalającym na minimalizację kosztów w zadaniu optymalizacyjnym opartym na programowaniu liniowym.
Celem metody węgierskiej jest znalezienie minimalnego kosztu zestawu zadań, które muszą być wykonane przez najbardziej odpowiednich ludzi.
Wykorzystuje programowanie liniowe (PL) do wykonania szeregu kroków, które można zautomatyzować. Tak więc narzędzia takie jak oprogramowanie statystyczne R (między innymi) mają kilka bardzo przydatnych pakietów dla tych problemów optymalizacyjnych.
Pochodzenie metody węgierskiej
Jego twórcą był węgierski matematyk (stąd jego nazwa) Harold W. Kuhn w 1955. Inny matematyk, James Munkres, zrewidował go w 1957. Wraz z tą ewolucją otrzymał inne nazwy, takie jak algorytm alokacji Munkres lub Kuhn-Munkres.
Z drugiej strony metoda ta ma precedens u dwóch autorów, Dénes König i Jenő Egerváry, zarówno Żydów, jak i Węgrów. Pierwszy opracował teorię grafów, na której opiera się ten algorytm. Drugi uogólnił twierdzenie Königa i pozwolił Kuhnowi rozwinąć metodę.
Kroki metody węgierskiej
Kolejne kroki pozwalają w prosty sposób przeprowadzić metodę węgierską za pomocą arkusza kalkulacyjnego. Ponadto ten schemat, który pokazujemy, pozwoli nam zobaczyć w sposób globalny proces, który szczegółowo opracujemy w końcowym przykładzie.
- Jako wstępne kroki musisz przypisać osoby (wiersze) do serii projektów (kolumn). Ponadto konieczne jest obliczenie różnych kosztów każdego projektu w zależności od tego, kto go realizuje i zbudowanie matrycy (C) z tymi informacjami.
- W macierzy (C) szukamy minimalnej wartości każdego wiersza. Odejmujemy to od wszystkich elementów w rzędzie i wykonujemy tę samą operację na kolumnach. Pojawi się nowa macierz (C`) z wynikami poprzednich operacji.
- Następnie tworzymy «wykres równości», który pozwala nam wybrać zadania i projekty o najniższym koszcie. Optimum byłyby te elementy, których wynik był zerowy. Jeśli prawdą jest, że nie ma elementu o wartości zero przypisanej do więcej niż jednego wiersza, algorytm się kończy.
- W przeciwnym razie należy dokonać nowego przypisania. Powstaje nowa matryca, do której stosuje się szereg modyfikacji, jak zobaczymy na przykładzie. Odtwarzamy wykres i kontynuujemy, aż otrzymamy macierz, która ma co najmniej jedno zero w każdym wierszu i na nie powtarzających się pozycjach.
- Dzięki tym informacjom mamy już przypisane osoby i projekty (zera), które optymalizują problem. Jeśli zadanie zostało już przypisane w poprzednim wierszu, jest odrzucane w następnym. Aby obliczyć koszt minimalny, dodajemy koszty macierzy początkowej, które pojawiają się w pozycji tych zer.
Przykład metody węgierskiej
Spójrzmy na prosty przykład węgierskiej metody. Wyobraźmy sobie, że mamy trzech pracowników i trzeba ich przydzielić do trzech projektów. Tworzymy macierz początkową (C) oraz wartości kosztów w każdej komórce. W tym celu musisz skorzystać z informacji dostępnych w firmie. Kiedy już mamy to wszystko, zaczynamy proces. Pomocny może być arkusz kalkulacyjny.
Obliczamy minima każdego wiersza i odejmujemy je od elementów tego wiersza i robimy to samo z kolumnami (kroki 1 i 2). W powstałej macierzy (C`) rysujemy linie w taki sposób, aby pokrywały wszystkie zera i kolejno się przecinały (krok 3). Widzimy, że są dwa wiersze, ale największą wartością liczby wierszy lub kolumn są trzy. Musimy iść dalej.
Teraz wybieramy najmniejszą z odsłoniętych liczb, w tym przykładzie są to dwie (ciemnoniebieskie). Odejmujemy go od poprzednich i dodajemy do tych, które znajdują się w miejscu przecięcia linii. W naszym przypadku to kolejne dwa (E3, T1). Pozostaje nam nowa macierz (krok 4). Przerysowujemy linie i liczymy. Są trzy wiersze, tyle samo co liczba wierszy lub kolumn. Algorytm jest zakończony.
Zaczynamy od wiersza lub kolumny z najmniejszą liczbą zer (E1, T1). Jeśli zadanie jest już przydzielone, nie można go ponownie przydzielić, na przykład z E2 nie można użyć pierwszego zera T1, ponieważ to zadanie zostało przypisane do E1. Całkowity koszt w metodzie węgierskiej będzie sumą kosztów macierzy oryginalnej (krok 1) znajdującej się na tej samej pozycji co wybrane zera (krok 5).
