MAGYAR MÓDSZER: MIBŐL ÁLL, PÉLDA - DUDAS - 2025

A magyar módszer egy olyan algoritmus, amelyet akkor alkalmaznak allokációs problémákra, amikor a költségeket minimalizálni akarják. Vagyis arra használják, hogy megtalálják a minimális költségeket azáltal, hogy több embert különféle tevékenységekhez rendelnek a legkevesebb költség alapján. Minden tevékenységet egy másik személyhez kell rendelni.

Az allokációs probléma a lineáris programozási probléma egy speciális típusa, ahol a cél az, hogy minimalizáljuk a több feladat elvégzésének költségeit vagy idejét.

Forrás: pixabay.com

Az allokációs probléma egyik fontos jellemzője, hogy egy géphez (vagy projekthez) csak egy munkát (vagy munkást) rendelnek hozzá.

Ezt a módszert D. Konig magyar matematikus fejlesztette ki. Ezért a hozzárendelési problémák magyar módszereként ismert. Kuhn-Munkres allokációs algoritmusként is ismert.

Bármely allokációs problémát könnyen meg lehet oldani a két fázisból álló módszer alkalmazásával:

- Az első fázisban a sorok csökkentését és az oszlopcsökkentéseket elvégezzük.

- A második szakaszban a megoldást iteratív alapon optimalizálják.

Mi a magyar módszer?

A magyar módszer négy lépésből áll. Az első két lépést csak egyszer hajtják végre, míg a 3. és 4. lépést addig ismételjük, amíg meg nem találják az optimális elosztásot.

Az n-n szerinti rendű négyzetes mátrixot bemeneti adatoknak kell tekinteni, amelyeknek csak nem negatív elemeket kell tartalmazniuk.

Egy adott probléma esetén, ha a mátrixban a sorok száma nem egyezik meg az oszlopok számával, az eset függvényében egy üres sort vagy egy üres oszlopot kell hozzáadni. Az ilyen dummy cellák kiosztási költségeit mindig nullaként osztják fel.

1. lépés: vonja le az egyes sorok minimumát

A tömb minden sorához a legalacsonyabb értékű elemet választják ki és vonják le az adott sor minden eleméből.

2. lépés: vonja le a minimumokat az egyes oszlopokból

Hasonlóképpen, minden oszlophoz kiválasztják a legalacsonyabb értékű elemet, és kivonják az oszlop minden eleméből.

3. lépés: fedje le az összes nullát minimális számú sorral

A mátrix minden, a 2. lépésből származó nulláját minimális számú vízszintes és függőleges vonallal kell lefedni, akár sorok, akár oszlopok segítségével.

Ha n

Ellenkező esetben, ha n-nél kevesebb vonalra van szükség a tömb összes nullájának lefedéséhez, folytassa a 4. lépéssel.

4. lépés: hozzon létre extra nullákat

A mátrix legkisebb elemét (k nevű) választják ki, amelyet a 3. lépésben létrehozott vonalak nem fednek le.

A k értékét minden olyan elemből levonják, amelyeket a sorok nem fednek le. Ezt követően a ka értékét hozzáadjuk minden olyan elemhez, amelyet a két vonal metszéspontja lefed.

Azok a tételek, amelyeket egyetlen sor fed le, ahogy maradnak. A lépés végrehajtása után visszatér a 3. lépéshez.

Optimális elosztás

Miután az algoritmust a 3. lépésben leállítottuk, nullákat választunk úgy, hogy minden sorban és minden oszlopban csak egy nulla legyen kiválasztva.

Ha ebben a kiválasztási folyamatban nincs egyetlen nulla egy sorban vagy oszlopban, akkor az egyik nulla kerül kiválasztásra. Az oszlopban vagy a sorban fennmaradó nullákat eltávolítják, és ugyanazt megismételik a többi hozzárendelésnél is.

Ha nincs egyetlen nulla hozzárendelés, akkor több megoldás is létezik. A költségek ugyanakkor változatlanok maradnak a különböző feladatkészleteknél.

Az összes hozzáadott sor vagy oszlop eltávolításra kerül. Az ebben a végső mátrixban kiválasztott nullák tehát megfelelnek az eredeti mátrixban megkövetelt ideális hozzárendelésnek.

Példa

Vegyük egy olyan társaságot, ahol négy tevékenység van (A1, A2, A3, A4), amelyeket négy munkavállalónak kell elvégeznie (T1, T2, T3, T4). Munkavállalónként egy tevékenységet kell kiosztani.

Az alábbi mátrix egy munkavállaló egy bizonyos tevékenységhez történő hozzárendelésének költségeit mutatja. A cél az, hogy minimalizáljuk a négy tevékenységből álló feladat összköltségét.

1. lépés: vonja le az egyes sorok minimumát

Először az elemet kivonva vonja le az egyes sorokban szereplő legkisebb értéket az adott sor többi eleméből. Például az első sorban a legkisebb elem a 69. Ezért a 69-et kivonjuk az első sor minden eleméből. A kapott mátrix:

2. lépés: vonja le a minimumokat az egyes oszlopokból

Hasonlóképpen, az egyes oszlopok legkisebb értékű elemét levonják az oszlop többi eleméből, a következő mátrixot kapva:

3. lépés: fedje le az összes nullát minimális számú sorral

Most meghatározzuk a vonalak (vízszintes vagy függőleges) minimális számát, amelyre szükség van a mátrix összes nullájának lefedéséhez. Az összes nullát 3 sor felhasználásával lehet lefedni:

Mivel a szükséges vonalak száma három és kevesebb, mint a mátrix mérete (n = 4), folytatjuk a 4. lépést.

4. lépés: hozzon létre extra nullákat

A legkisebb elemet választják ki, amelyet a vonalak nem fednek le, és amelynek értéke 6. Ezt az értéket kivonják az összes nem lefedett elemből, és ugyanazt az értéket adják hozzá az összes elemhez, amelyre két vonal keresztezi. Ez a következő mátrixot eredményezi:

A magyar módszer szerint a harmadik lépést meg kell ismételni.

3. lépés (ismétlés)

Megint meghatározzuk a mátrix összes nullájának lefedéséhez szükséges vonalak minimális számát. Ezúttal négy sor szükséges:

Mivel a szükséges vonalak száma 4, megegyezik a mátrix méretével (n = 4), ezért optimális eloszlást kapunk a mátrix nullái között. Ezért az algoritmus leáll.

Optimális elosztás

Amint a módszer jelzi, a következő nullák kiválasztása megfelel az optimális hozzárendelésnek:

Ez a nullák kiválasztása az alábbi optimális elosztásnak felel meg az eredeti költségmátrixban:

Ezért az 1. munkavállalónak végre kell hajtania a 3. tevékenységet, a 2. munkavállalót, a 2. tevékenységet, a 3. munkavállalót, az 1. tevékenységet és a 4. munkavállalót. 11 + 23 = 140.

Irodalom

1. Magyar algoritmus (2019). A magyar algoritmus. Forrás: hungarianalgorithm.com.
2. Tanulmány (2019). A magyar algoritmus felhasználása a hozzárendelési problémák megoldására. Forrás: study.com.
3. Wisdom Jobs (2018). Magyar módszer a megbízási probléma megoldására - Menedzsment kvantitatív technikák. Forrás: wisdomjobs.com.
4. Geeks Geeks számára (2019). Magyar hozzárendelési probléma algoritmus. Feltöltve: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Magyar maximális illesztési algoritmus. Ragyogó. Forrás: brilliant.org.