MAĎARSKÁ METODA: Z ČEHO SE SKLÁDÁ, PŘÍKLAD - DUDAS - 2025

Maďarský metoda je algoritmus, který se používá při problémech přidělování, pokud chcete, aby se minimalizovalo náklady. To znamená, že se používá k nalezení minimálních nákladů přiřazením více lidí k různým činnostem na základě nejnižších nákladů. Každá činnost musí být přiřazena jiné osobě.

Problém s přidělováním je zvláštní typ problému s lineárním programováním, jehož cílem je minimalizovat náklady nebo čas na dokončení několika úloh více lidmi.

Zdroj: pixabay.com

Jednou z důležitých charakteristik problému přidělení je to, že ke stroji (nebo projektu) je přiřazena pouze jedna úloha (nebo pracovník).

Tuto metodu vyvinul maďarský matematik D. Konig. Z tohoto důvodu se nazývá maďarská metoda problémů s přiřazením. Je také známý jako alokační algoritmus Kuhn-Munkres.

Jakýkoli problém s alokací lze snadno vyřešit použitím této metody, která se skládá ze dvou fází:

- S první fází se provádí redukce v řádcích a sloupcích.

- Ve druhé fázi je řešení optimalizováno na základě iterace.

Co je maďarská metoda?

Maďarská metoda sestává ze čtyř kroků. První dva kroky jsou provedeny pouze jednou, zatímco kroky 3 a 4 jsou opakovány, dokud není nalezeno optimální přiřazení.

Čtvercová matice řádu n podle n je považována za vstupní data, která musí obsahovat pouze nezáporné prvky.

Pokud se pro daný problém počet řádků v matici nerovná počtu sloupců, musí být podle případu doplněn fiktivní řádek nebo fiktivní sloupec. Alokační náklady pro tyto figuríny jsou vždy přiděleny jako nula.

Krok 1: odečtěte minima z každého řádku

Pro každý řádek v poli je vybrán prvek s nejnižší hodnotou a odečten od každého prvku v tomto řádku.

Krok 2: odečtěte minima z každého sloupce

Podobně je položka s nejnižší hodnotou vybrána pro každý sloupec a odečtena od každé položky v daném sloupci.

Krok 3: zakryjte všechny nuly minimálním počtem řádků

Všechny nuly v matici, které jsou výsledkem kroku 2, musí být zakryty minimálním počtem vodorovných a svislých čar, buď řádků nebo sloupců.

Je-li pro pokrytí všech nul požadováno celkem n řádků, kde n je rovno velikosti n krát n matice, bude dosaženo optimálního rozdělení mezi nulami, a proto se algoritmus zastaví.

V opačném případě, pokud je vyžadováno méně než n řádků pro pokrytí všech nul v poli, pokračujte krokem 4.

Krok 4: vytvořte další nuly

Je vybrán nejmenší prvek matice (nazývaný k), který není pokryt jednou z linií vytvořených v kroku 3.

Hodnota k se odečte od všech prvků, které nejsou pokryty čarami. Následně je hodnota ka přidána ke všem prvkům, které jsou pokryty průnikem dvou čar.

Položky, které jsou pokryty jedním řádkem, zůstanou tak, jak jsou. Po provedení tohoto kroku se vrátíte ke kroku 3.

Optimální alokace

Po zastavení algoritmu v kroku 3 je vybrána sada nul tak, že každý řádek a každý sloupec má pouze jednu nulu vybranou.

Pokud v tomto výběrovém procesu není žádná jednotlivá nula v řádku nebo sloupci, bude vybrána jedna z těchto nul. Zbývající nuly ve sloupci nebo řádku jsou odstraněny a opakují se i pro ostatní přiřazení.

Pokud není přiřazeno žádné nulové číslo, existuje více řešení. Náklady však zůstanou stejné pro různé sady úkolů.

Všechny falešné řádky nebo sloupce, které byly přidány, budou odstraněny. Nuly vybrané v této konečné matici tedy odpovídají ideálnímu přiřazení požadovanému v původní matici.

Příklad

Uvažujme společnost, kde existují čtyři činnosti (A1, A2, A3, A4), které musí provádět čtyři pracovníci (T1, T2, T3, T4). Každému pracovníkovi musí být přiřazena jedna činnost.

Následující matice ukazuje náklady na přiřazení určitého pracovníka k určité činnosti. Cílem je minimalizovat celkové náklady na úkol tvořený těmito čtyřmi činnostmi.

Krok 1: odečtěte minima z každého řádku

Začněte odečtením prvku s minimální hodnotou v každém řádku od ostatních prvků v tomto řádku. Například nejmenší prvek v prvním řádku je 69. Proto je od každého prvku v prvním řádku odečteno 69. Výsledná matice je:

Krok 2: odečtěte minima z každého sloupce

Stejným způsobem se prvek s minimální hodnotou každého sloupce odečte od ostatních prvků tohoto sloupce a získá se následující matice:

Krok 3: zakryjte všechny nuly minimálním počtem řádků

Nyní určíme minimální počet čar (vodorovných nebo svislých), které jsou potřebné k pokrytí všech nul v matici. Všechny nuly lze zakrýt pomocí 3 řádků:

Protože požadovaný počet řádků je tři a je menší než velikost matice (n = 4), pokračujeme krokem 4.

Krok 4: vytvořte další nuly

Je vybrán nejmenší prvek, který není pokrytý čarami, jehož hodnota je 6. Tato hodnota se odečte od všech prvků, které nejsou pokryty, a stejná hodnota se přičte ke všem prvkům zakrytým průnikem dvou čar. Výsledkem je následující matice:

Jak je uvedeno v maďarské metodě, třetí krok musí být proveden znovu.

Krok 3 (opakování)

Znovu se stanoví minimální počet řádků potřebných k pokrytí všech nul v matici. Tentokrát jsou vyžadovány čtyři řádky:

Protože požadovaný počet řádků je 4, stejný jako velikost matice (n = 4), máme optimální matici mezi nulami v matici. Algoritmus se proto zastaví.

Optimální alokace

Jak metoda naznačuje, výběr provedený z následujících nul odpovídá optimálnímu přiřazení:

Tento výběr nul odpovídá následujícímu optimálnímu rozdělení v původní matici nákladů:

Proto musí pracovník 1 vykonávat aktivitu 3, pracovník 2, činnost 2, pracovník 3, činnost 1 a pracovník 4 musí provádět činnost 4. Celkové náklady na toto optimální přiřazení jsou 69 + 37 + 11 + 23 = 140.

Reference

1. Maďarský algoritmus (2019). Maďarský algoritmus. Převzato z: hungarianalgorithm.com.
2. Studie (2019). Využití maďarského algoritmu k vyřešení problémů s přiřazením. Převzato z: study.com.
3. Moudrost práce (2018). Maďarská metoda řešení problému přiřazení - kvantitativní techniky pro řízení. Převzato z: wisdomjobs.com.
4. Geeks for Geeks (2019). Maďarský algoritmus pro problém přiřazení. Převzato z: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Algoritmus maximální shody v Maďarsku. Brilantní. Převzato z: brilliant.org.