Maďarská metoda - co to je, definice a koncept
Maďarská metoda je algoritmus, který umožňuje minimalizovat náklady v optimalizačním problému založeném na lineárním programování.
Cílem maďarské metody je najít minimální náklady na soubor úkolů, které musí provádět nejvhodnější lidé.
Využívá lineární programování (PL) k provádění řady kroků, které lze automatizovat. Nástroje, jako je statistický software R (mimo jiné), tedy mají několik velmi užitečných balíčků pro tyto optimalizační problémy.
Původ maďarské metody
Jeho tvůrcem byl maďarský matematik (odtud jeho název) Harold W. Kuhn v roce 1955. Další matematik, James Munkres, jej revidoval v roce 1957. S tímto vývojem získal další jména, jako je alokační algoritmus Munkres nebo Kuhn-Munkres.
Na druhou stranu má tato metoda precedens u dvou autorů, Dénes König a Jenő Egerváry, Židů i Maďarů. První vyvinul teorii grafů, na které je tento algoritmus založen. Druhý zobecnil Königovu větu a umožnil Kuhnovi vyvinout metodu.
Kroky maďarské metody
Následující kroky umožňují provést maďarskou metodu jednoduchým způsobem pomocí tabulky. Toto schéma, které ukážeme, nám navíc umožní vidět v globálním smyslu proces, který podrobně rozvineme v posledním příkladu.
- Jako předběžné kroky musíte přiřadit lidi (řádky) k řadě projektů (sloupců). Kromě toho je nutné vypočítat různé náklady každého projektu v závislosti na tom, kdo jej provádí, a sestavit matici (C) s těmito informacemi.
- V matici (C) hledáme minimální hodnotu každého řádku. Odečteme to od všech prvků v řádku a provedeme stejnou operaci se sloupci. S výsledky předchozích operací se objeví nová matice (C`).
- Dále vytvoříme «graf rovností», který nám umožní vybrat úkoly a projekty s nejnižšími náklady. Optimální by byly ty prvky, jejichž výsledek byl nulový. Pokud je pravda, že k více než jednomu řádku není přiřazen žádný prvek s nulovou hodnotou, algoritmus končí.
- Jinak musí být provedeno nové přiřazení. Je vytvořena nová matice, na kterou je aplikována řada úprav, jak uvidíme v příkladu. Znovu vytvoříme graf a pokračujeme, dokud nebudeme mít matici, která má alespoň jednu nulu v každém řádku a v neopakujících se pozicích.
- S touto informací již máme přiřazené lidi a projekty (nuly), které optimalizují problém. Pokud je úkol již přiřazen v předchozím řádku, je zahozen v dalším. Pro výpočet minimálních nákladů přidáme náklady na počáteční matici, které se objeví v poloze těchto nul.
Příklad maďarské metody
Podívejme se na jednoduchý příklad maďarské metody. Představme si, že máme tři pracovníky a musí být přiděleni ke třem projektům. V každé buňce vytvoříme počáteční matici (C) a hodnoty nákladů. K tomu musíte použít informace dostupné ve společnosti. Jakmile to všechno máme, zahájíme proces. Tabulka může pomoci.
Vypočítáme minima každého řádku a odečteme je od prvků daného řádku a uděláme totéž se sloupci (kroky 1 a 2). Ve výsledné matici (C`) nakreslíme čáry takovým způsobem, že pokrývají všechny nuly a zase se protínají (krok 3). Vidíme, že existují dva řádky, ale největší hodnota počtu řádků nebo sloupců jsou tři. Musíme pokračovat.
Nyní vybereme nejmenší z nekrytých čísel, v tomto příkladu jsou to dvě (tmavě modrá). Odečteme jej od předchozích a přidáme k těm, které se nacházejí tam, kde se čáry protínají. V našem případě jsou to další dva (E3, T1). Zůstala nám nová matice (krok 4). Překreslujeme čáry a počítáme. Existují tři řádky, stejné jako počet řádků nebo sloupců. Algoritmus je dokončen.
Začínáme s řádkem nebo sloupcem s nejmenším počtem nul (E1, T1). Pokud je úkol již přiřazen, nelze jej znovu přiřadit, například u E2 nemůžete použít první nulu T1, protože tento úkol byl přiřazen E1. Celkové náklady v maďarské metodě budou součtem nákladů na původní matici (krok 1) umístěnou na stejné pozici jako vybrané nuly (krok 5).
