Maďarská metóda je algoritmus, ktorý umožňuje minimalizovať náklady na optimalizačný problém založený na lineárnom programovaní.
Cieľom maďarskej metódy je nájsť minimálne náklady na súbor úloh, ktoré musia vykonať tí najvhodnejší ľudia.
Využíva lineárne programovanie (PL) na vykonávanie série krokov, ktoré je možné automatizovať. Nástroje ako štatistický softvér R (okrem iného) teda majú niekoľko veľmi užitočných balíkov na tieto optimalizačné problémy.
Pôvod maďarskej metódy
Jeho tvorcom bol maďarský matematik (odtiaľ pochádza aj jeho názov) Harold W. Kuhn v roku 1955. Ďalší matematik James Munkres ho zrevidoval v roku 1957. Vďaka tomuto vývoju získal ďalšie názvy, napríklad algoritmus alokácie Munkres alebo Kuhn-Munkres.
Na druhej strane má táto metóda precedens u dvoch autorov, Dénesa Königa a Jenő Egerváryovej, Židov aj Maďarov. Prvý z nich vyvinul teóriu grafov, na ktorej je založený tento algoritmus. Druhá zovšeobecnila Königovu vetu a umožnila Kuhnovi vyvinúť metódu.
Kroky maďarskej metódy
Nasledujúce kroky umožňujú vykonať maďarskú metódu jednoduchým spôsobom pomocou tabuľky. Táto schéma, ktorú ukážeme, nám navyše umožní vidieť globálnym spôsobom proces, ktorý podrobne rozvinieme v poslednom príklade.
- Ako predbežné kroky musíte ľudí (riadky) priradiť k sérii projektov (stĺpce). Ďalej je potrebné vypočítať rôzne náklady na každý projekt v závislosti od toho, kto ho realizuje, a zostaviť maticu (C) s týmito informáciami.
- V matici (C) hľadáme minimálnu hodnotu každého riadku. Odčítame to od všetkých prvkov v riadku a vykonáme rovnakú operáciu so stĺpcami. S výsledkami predchádzajúcich operácií sa objaví nová matica (C`).
- Ďalej vytvoríme «graf rovností», ktorý nám umožní zvoliť úlohy a projekty s najnižšími nákladmi. Optimálne by boli tie prvky, ktorých výsledok bol nulový. Ak je pravda, že viac ako jednému riadku nie je priradený žiadny prvok s nulovou hodnotou, algoritmus končí.
- V opačnom prípade je potrebné vykonať nové priradenie. Vyrába sa nová matica, na ktorú sa vzťahuje rad úprav, ako to uvidíme v príklade. Znova vytvoríme graf a pokračujeme, kým nebudeme mať maticu, ktorá má v každom riadku a v neopakujúcich sa pozíciách aspoň jednu nulu.
- Vďaka týmto informáciám už máme priradených ľudí a projekty (nuly), ktoré optimalizujú problém. Ak je úloha už priradená v predchádzajúcom riadku, v nasledujúcom sa zahodí. Na výpočet minimálnych nákladov pripočítame náklady na počiatočnú maticu, ktoré sa objavia na pozícii týchto núl.
Príklad maďarskej metódy
Pozrime sa na jednoduchý príklad maďarskej metódy. Predstavme si, že máme troch pracovníkov a tí musia byť pridelení k trom projektom. V každej bunke vytvoríme počiatočnú maticu (C) a hodnoty nákladov. K tomu musíte použiť informácie dostupné v spoločnosti. Len čo toto všetko máme, začneme proces. Tabuľka môže pomôcť.
Vypočítame minimá každého riadku a odčítame ich od prvkov daného riadku a to isté urobíme so stĺpcami (kroky 1 a 2). Vo výslednej matici (C`) nakreslíme čiary tak, aby pokrývali všetky nuly a zase sa navzájom pretínali (krok 3). Vidíme, že existujú dva riadky, ale najväčšia hodnota počtu riadkov alebo stĺpcov sú tri. Musíme pokračovať.
Teraz vyberieme najmenšie z nekrytých čísel, v tomto príklade sú to dve (tmavo modrá). Odčítame to od tých predchádzajúcich a pripočítame k tým, ktoré sa nachádzajú tam, kde sa čiary pretínajú. V našom prípade sú to ďalšie dva (E3, T1). Ostáva nám nová matica (krok 4). Prekreslíme čiary a počítame. Existujú tri riadky, rovnaké ako počet riadkov alebo stĺpcov. Algoritmus je dokončený.
Začíname riadkom alebo stĺpcom s najmenším počtom núl (E1, T1). Ak je úloha už priradená, nemožno ju znova priradiť, napríklad s E2 nemôžete použiť prvú nulu T1, pretože táto úloha bola priradená k E1. Celkové náklady, v maďarskej metóde, budú súčtom nákladov na pôvodnú maticu (krok 1) umiestnenú na rovnakej pozícii ako vybrané nuly (krok 5).
