MAĎARSKÁ METÓDA: Z ČOHO POZOSTÁVA, NAPR - DUDAS - 2025

Maďarský metóda je algoritmus, ktorý sa používa pri problémoch prideľovaní, ak chcete, aby sa minimalizovalo náklady. To znamená, že sa používa na nájdenie minimálnych nákladov priradením viacerých ľudí k rôznym činnostiam založeným na najmenších nákladoch. Každá činnosť musí byť priradená inej osobe.

Problém s pridelením je špeciálny typ problému s lineárnym programovaním, ktorého cieľom je minimalizovať náklady alebo čas na vykonanie viacerých úloh viacerými ľuďmi.

Zdroj: pixabay.com

Jednou z dôležitých charakteristík problému priradenia je to, že k stroju (alebo projektu) je priradená iba jedna úloha (alebo pracovník).

Túto metódu vyvinul maďarský matematik D. Konig. Z tohto dôvodu je známa ako maďarská metóda problémov priraďovania. Je tiež známy ako algoritmus prideľovania Kuhn-Munkres.

Akýkoľvek problém s pridelením sa dá ľahko vyriešiť použitím tejto metódy, ktorá pozostáva z dvoch fáz:

- Pri prvej fáze sa vykonajú redukcie v riadkoch a stĺpcoch.

- V druhej fáze je riešenie optimalizované na základe iterácie.

Čo je maďarská metóda?

Maďarská metóda pozostáva zo štyroch krokov. Prvé dva kroky sa vykonávajú iba raz, zatiaľ čo kroky 3 a 4 sa opakujú, až kým sa nenájde optimálne rozdelenie.

Štvorcová matica rádu n podľa n sa považuje za vstupné údaje, ktoré musia obsahovať iba nezáporné prvky.

Ak sa pre daný problém počet riadkov v matici nerovná počtu stĺpcov, musí sa podľa prípadu pridať slepý riadok alebo slepý stĺpec. Alokačné náklady pre tieto figuríny sú vždy pridelené ako nula.

Krok 1: odpočítajte minimá každého riadku

Pre každý riadok v poli sa vyberie prvok s najnižšou hodnotou a odpočíta sa od každého prvku v danom riadku.

Krok 2: odpočítajte minimá z každého stĺpca

Podobne sa položka s najnižšou hodnotou vyberie pre každý stĺpec a odpočíta sa od každej položky v tomto stĺpci.

Krok 3: zakryte všetky nuly minimálnym počtom riadkov

Všetky nuly v matici, ktoré sú výsledkom kroku 2, musia byť zakryté minimálnym počtom vodorovných a zvislých čiar, buď riadkami alebo stĺpcami.

Ak je potrebných celkom n riadkov na pokrytie všetkých núl, kde n sa rovná veľkosti n krát n matice, bude medzi nulami optimálne rozdelenie, a preto sa algoritmus zastaví.

Ak sú na pokrytie všetkých núl v poli potrebné menej ako n riadkov, pokračujte krokom 4.

Krok 4: vytvorte ďalšie nuly

Vyberie sa najmenší prvok matice (nazývaný k), ktorý nie je pokrytý jednou z čiar vytvorených v kroku 3.

Hodnota k sa odpočíta od všetkých prvkov, ktoré nie sú pokryté čiarami. Následne sa hodnota ka pridá do všetkých prvkov, ktoré sú pokryté priesečníkom dvoch čiar.

Položky, ktoré sú pokryté jedným riadkom, zostanú nezmenené. Po vykonaní tohto kroku sa vrátite na krok 3.

Optimálne rozdelenie

Po zastavení algoritmu v kroku 3 sa vyberie sada núl tak, že pre každý riadok a každý stĺpec je vybraná iba jedna nula.

Ak v tomto výberovom procese nie je v riadku alebo stĺpci žiadna nula, vyberie sa jedna z týchto núl. Zvyšné nuly v tomto stĺpci alebo riadku sa odstránia a rovnaké sa opakujú aj pre ostatné priradenia.

Ak neexistuje žiadne priradenie nuly, existuje viacero riešení. Náklady však zostanú rovnaké pre rôzne súbory úloh.

Všetky fiktívne riadky alebo stĺpce, ktoré boli pridané, sa odstránia. Nuly vybrané v tejto konečnej matici teda zodpovedajú ideálnemu priradeniu požadovanému v pôvodnej matici.

príklad

Zoberme si spoločnosť, v ktorej existujú štyri činnosti (A1, A2, A3, A4), ktoré musia vykonávať štyria pracovníci (T1, T2, T3, T4). Každému pracovníkovi musí byť priradená jedna činnosť.

Nasledujúca matica ukazuje náklady na priradenie určitého pracovníka k určitej činnosti. Cieľom je minimalizovať celkové náklady na úlohu, ktorú tvoria tieto štyri činnosti.

Krok 1: odpočítajte minimá každého riadku

Začnete odpočítaním prvku s minimálnou hodnotou v každom riadku od ostatných prvkov v tomto riadku. Napríklad najmenší prvok v prvom riadku je 69. Preto sa od každého prvku v prvom riadku odpočíta 69. Výsledná matica je:

Krok 2: odpočítajte minimá z každého stĺpca

Rovnakým spôsobom sa prvok s minimálnou hodnotou každého stĺpca odpočíta od ostatných prvkov tohto stĺpca a získa sa nasledujúca matica:

Krok 3: zakryte všetky nuly minimálnym počtom riadkov

Teraz určíme minimálny počet čiar (vodorovných alebo zvislých), ktoré sú potrebné na pokrytie všetkých núl v matici. Všetky nuly môžu byť zakryté pomocou 3 riadkov:

Pretože požadovaný počet riadkov je tri a je menší ako veľkosť matice (n = 4), pokračujeme krokom 4.

Krok 4: vytvorte ďalšie nuly

Vyberie sa najmenší prvok, ktorý nie je pokrytý čiarami, ktorého hodnota je 6. Táto hodnota sa odpočíta od všetkých prvkov, ktoré nie sú pokryté, a táto rovnaká hodnota sa pripočíta ku všetkým prvkom, ktoré sú priesečníkom dvoch čiar. Výsledkom je nasledujúca matica:

Ako je uvedené v maďarskej metóde, krok 3 sa musí vykonať znova.

Krok 3 (opakovanie)

Opäť sa stanoví minimálny počet riadkov požadovaných na pokrytie všetkých núl v matici. Tentoraz sú potrebné štyri riadky:

Pretože požadovaný počet riadkov je 4, ktorý sa rovná veľkosti matice (n = 4), máme optimálne rozdelenie medzi nulami v matici. Algoritmus sa preto zastaví.

Optimálne rozdelenie

Ako metóda naznačuje, výber z nasledujúcich núl zodpovedá optimálnemu priradeniu:

Tento výber núl zodpovedá nasledujúcemu optimálnemu rozdeleniu v pôvodnej matici nákladov:

Preto musí pracovník 1 vykonávať činnosť 3, pracovník 2, činnosť 2, pracovník 3, činnosť 1 a pracovník 4 musí vykonávať činnosť 4. Celkové náklady na toto optimálne priradenie sú 69 + 37 + 11 + 23 = 140.

Referencie

1. Maďarský algoritmus (2019). Maďarský algoritmus. Prevzaté z: hungarianalgorithm.com.
2. Štúdia (2019). Využitie maďarského algoritmu na riešenie problémov priraďovania. Prevzaté z: study.com.
3. Wisdom Jobs (2018). Maďarská metóda riešenia problému priradenia - kvantitatívne techniky riadenia. Prevzaté z: wisdomjobs.com.
4. Geeks for Geeks (2019). Maďarský algoritmus pre problém priradenia. Prevzaté z: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Algoritmus maximálnej zhody v Maďarsku. Brilantná. Prevzaté z: brilliant.org.