A magyar módszer olyan algoritmus, amely lehetővé teszi a költségek minimalizálását egy lineáris programozáson alapuló optimalizálási problémában.
A magyar módszer célja megtalálni a legkevesebb költséget egy olyan feladatsornak, amelyet a legmegfelelőbb embereknek kell elvégezniük.
Lineáris programozást (PL) használ az automatizálható lépések sorozatának végrehajtására. Így az olyan eszközök, mint például az R statisztikai szoftver (többek között) számos nagyon hasznos csomaggal rendelkeznek ezekhez az optimalizálási problémákhoz.
A magyar módszer eredete
Alkotója a magyar matematikus (innen kapta a nevét) Harold W. Kuhn 1955-ben. Egy másik matematikus, James Munkres, 1957-ben módosította. Ezzel az evolúcióval más neveket is kapott, például a Munkres vagy a Kuhn-Munkres allokációs algoritmust.
Másrészt ennek a módszernek két szerző, König Dénes és Egerváry Jenő, mind zsidók, mind magyarok előzményei vannak. Az első kidolgozta azt a gráfelméletet, amelyen ez az algoritmus alapul. A második általánosította König tételét, és lehetővé tette Kuhn számára a módszer kidolgozását.
A magyar módszer lépései
A követendő lépések lehetővé teszik a magyar módszer egyszerű végrehajtását egy táblázat segítségével. Ezenkívül ez a bemutatott séma lehetővé teszi számunkra, hogy globális módon lássuk azt a folyamatot, amelyet az utolsó példában részletesen kidolgozunk.
- Előzetes lépésként embereket (sorokat) kell rendelnie projektek (oszlopok) sorozatához. Ezenkívül ki kell számolni az egyes projektek különböző költségeit attól függően, hogy ki hajtja végre, és felépíteni egy mátrixot (C) ezen információkkal.
- A (C) mátrixban megkeressük az egyes sorok minimális értékét. Ezt kivonjuk a sor összes eleméből, és ugyanazt a műveletet hajtjuk végre az oszlopokkal. Új mátrix (C`) jelenik meg az előző műveletek eredményeivel.
- Ezután elkészítjük az «egyenlőségek grafikonját», amely lehetővé teszi a legalacsonyabb költségű feladatok és projektek kiválasztását. Azok az elemek lennének az optimálisak, amelyek eredménye nulla. Ha igaz, hogy nincs egynél több sorhoz nulla értékű elem, akkor az algoritmus véget ér.
- Ellenkező esetben új hozzárendelést kell végrehajtani. Új mátrix készül, amelyre egy sor módosítást alkalmaznak, amint azt a példában láthatjuk. Újra elkészítjük a grafikont, és addig folytatjuk, amíg nem lesz olyan mátrixunk, amelynek minden sorban legalább egy nulla van és nem ismétlődő pozíciókban.
- Ezen információk birtokában már hozzárendeltük azokat az embereket és projekteket (nullákat), amelyek optimalizálják a problémát. Ha egy feladatot már hozzárendelt egy előző sorhoz, akkor a következőben elveti. A minimális költség kiszámításához hozzáadjuk a kezdeti mátrix költségeit, amelyek ezen nullák helyzetében jelennek meg.
Magyar módszer példa
Nézzünk meg egy egyszerű példát a magyar módszerre. Képzeljük el, hogy három dolgozónk van, és három projektbe kell őket beosztani. Minden cellában létrehozzuk a kezdő mátrixot (C) és a költségértékeket. Ehhez fel kell használni a vállalatnál elérhető információkat. Miután mindez megvan, megkezdjük a folyamatot. Segíthet egy táblázat.
Kiszámoljuk az egyes sorok minimumát, kivonjuk őket a sor elemeiből, és ugyanezt tesszük az oszlopokkal is (1. és 2. lépés). A kapott mátrixban (C`) olyan vonalakat rajzolunk, amelyek lefedik az összes nullát, és egymást keresztezik (3. lépés). Látjuk, hogy két sor van, de a sorok vagy oszlopok számának legnagyobb értéke három. Folytatnunk kell.
Most a nem fedett számok közül a legkisebbet választjuk, ebben a példában kettő (sötétkék). Kivonjuk az előzőekből, és hozzáadjuk azokat, amelyek a vonalak kereszteződésében találhatók. Esetünkben ez még kettő (E3, T1). Új mátrix marad (4. lépés). Átrajzoljuk a vonalakat és számolunk. Három sor van, megegyezik a sorok vagy oszlopok számával. Az algoritmus elkészült.
A legkevesebb nullával rendelkező sorral vagy oszloppal kezdjük (E1, T1). Ha egy feladat már van hozzárendelve, akkor azt nem lehet újra hozzárendelni, például az E2-vel nem használhatja a T1 első nulla értékét, mivel ezt a feladatot az E1-hez rendelték. A teljes módszer a magyar módszer szerint az eredeti mátrix (1. lépés) költségeinek összege lesz, amely ugyanabban a helyzetben helyezkedik el, mint a választott nullák (5. lépés).
