Ungari meetod on algoritm, mis võimaldab minimeerida lineaarsel programmeerimisel põhineva optimeerimisprobleemi kulusid.
Ungari meetodi eesmärk on leida ülesannete komplekti minimaalsed kulud, mida peavad täitma kõige sobivamad inimesed.
See kasutab lineaarset programmeerimist (PL) automatiseeritud sammude rea sooritamiseks. Seega on sellistel tööriistadel nagu statistikatarkvara R (muu hulgas) nende optimeerimisprobleemide jaoks mitu väga kasulikku paketti.
Ungari meetodi päritolu
Selle loojaks oli Ungari matemaatik (sellest ka nimi) Harold W. Kuhn 1955. aastal. Teine matemaatik, James Munkres, muutis seda 1957. aastal. Selle evolutsiooniga on ta saanud ka teisi nimesid, näiteks Munkresi või Kuhn-Munkresi eraldusalgoritm.
Teisalt on sellel meetodil pretsedent kahes juudis ja ungarlases Dénes Königis ja Jenő Egervárys. Esimene töötas välja graafiteooria, millel see algoritm põhineb. Teine üldistas Königi teoreemi ja võimaldas Kuhnil meetodit välja töötada.
Ungari meetodi etapid
Järgitavad sammud võimaldavad Ungari meetodit tabeli abil lihtsal viisil läbi viia. Lisaks võimaldab see skeem, mida näitame, näha globaalsel viisil protsessi, mille me viimases näites üksikasjalikult välja töötame.
- Esialgsete sammudena peate määrama inimesed (read) projektide reale (veerud). Lisaks on vaja arvutada iga projekti erinevad kulud sõltuvalt sellest, kes seda teostab, ja koostada selle teabega maatriks (C).
- Maatriksist (C) otsime iga rea minimaalse väärtuse. Me lahutame selle kõigist rea elementidest ja teeme sama toimingu veergudega. Ilmub uus maatriks (C`) koos eelmiste toimingute tulemustega.
- Järgmisena loome «võrdsuste graafiku», mis võimaldab meil valida kõige madalama kuluga ülesandeid ja projekte. Optimaalsed oleksid elemendid, mille tulemus oleks null. Kui on tõsi, et pole ühtegi elementi, mille nullväärtus oleks määratud rohkem kui ühele reale, siis algoritm lõpeb.
- Vastasel juhul tuleb teha uus ülesanne. Tehakse uus maatriks, millele rakendatakse rida modifikatsioone, nagu näeme näites. Loome graafiku uuesti ja jätkame, kuni meil on maatriks, millel on vähemalt üks null igas reas ja mittekorduvates positsioonides.
- Selle teabe abil on meil juba määratud inimesed ja projektid (nullid), mis probleemi optimeerivad. Kui ülesanne on juba eelmises reas määratud, visatakse see järgmisesse ära. Miinimumkulude arvutamiseks lisame nende nullide asukohas esinevad esialgse maatriksi kulud.
Ungari meetodi näide
Vaatame lihtsat näidet Ungari meetodist. Kujutame ette, et meil on kolm töötajat ja nad tuleb määrata kolmele projektile. Igas lahtris loome algmaatriksi (C) ja maksumuse väärtused. Selleks peate kasutama ettevõttes saadaolevat teavet. Kui see kõik on meil olemas, alustame protsessi. Abi võib olla arvutustabelist.
Arvutame iga rea miinimumid ja lahutame need selle rea elementidest ning teeme samamoodi veergudega (sammud 1 ja 2). Saadud maatriksis (C`) joonistame jooned nii, et need kataksid kõik nullid ja ristuksid omakorda üksteisega (samm 3). Näeme, et on kaks rida, kuid ridade või veergude arvu suurim väärtus on kolm. Me peame jätkama.
Nüüd valime katmata numbritest väikseima, selles näites on see kaks (tumesinine). Me lahutame selle eelmistest ja lisame neile, mis asuvad joonte ristumiskohas. Meie puhul on see veel kaks (E3, T1). Meile jääb uus maatriks (4. samm). Joonistame jooned ümber ja loeme. Seal on kolm rida, sama mis ridade või veergude arv. Algoritm on valmis.
Alustame kõige vähem nullidega reaga või veeruga (E1, T1). Kui ülesandele on juba määratud, ei saa seda uuesti määrata, näiteks E2-ga ei saa te kasutada T1 esimest nulli, kuna see ülesanne määrati E1-le. Kogumaksumus on Ungari meetodil valitud nullidega (positsioon 5) samas asendis asuva algse maatriksi (1. etapp) kulude summa.