Metoda maghiară este un algoritm care permite minimizarea costurilor într-o problemă de optimizare bazată pe programare liniară.
Scopul metodei maghiare este de a găsi costul minim al unui set de sarcini care trebuie îndeplinite de cei mai potriviți oameni.
Folosește programarea liniară (PL) pentru a efectua o serie de pași care pot fi automatizați. Astfel, instrumente precum software-ul statistic R (printre altele) au mai multe pachete foarte utile pentru aceste probleme de optimizare.
Originea metodei maghiare
Creatorul său a fost matematicianul maghiar (de unde și numele său) Harold W. Kuhn în 1955. Un alt matematician, James Munkres, l-a revizuit în 1957. Cu această evoluție a primit alte nume precum algoritmul de alocare Munkres sau Kuhn-Munkres.
Pe de altă parte, această metodă are un precedent la doi autori, Dénes König și Jenő Egerváry, ambii evrei și unguri. Primul a dezvoltat teoria graficelor pe care se bazează acest algoritm. Al doilea a generalizat teorema lui König și ia permis lui Kuhn să dezvolte metoda.
Etape ale metodei maghiare
Pașii de urmat permit realizarea metodei maghiare într-un mod simplu folosind o foaie de calcul. În plus, această schemă pe care o prezentăm ne va permite să vedem într-un mod global procesul pe care îl vom dezvolta în detaliu în exemplul final.
- Ca pași preliminari, trebuie să atribuiți persoane (rânduri) unei serii de proiecte (coloane). În plus, este necesar să se calculeze diferitele costuri ale fiecărui proiect în funcție de cine îl realizează și să se construiască o matrice (C) cu aceste informații.
- În matricea (C) căutăm valoarea minimă a fiecărui rând. Scădem acest lucru din toate elementele din rând și efectuăm aceeași operație cu coloanele. O nouă matrice (C`) va apărea cu rezultatele operațiilor anterioare.
- Apoi, creăm „graficul egalităților”, care ne permite să alegem sarcinile și proiectele cu cel mai mic cost. Optimul ar fi acele elemente al căror rezultat a fost zero. Dacă este adevărat că nu există niciun element cu o valoare zero atribuită mai multor rânduri, algoritmul se termină.
- În caz contrar, trebuie făcută o nouă misiune. Se face o nouă matrice căreia i se aplică o serie de modificări, așa cum vom vedea în exemplu. Recreăm graficul și continuăm până când avem o matrice care are cel puțin un zero în fiecare rând și în poziții care nu se repetă.
- Cu aceste informații avem deja oamenii și proiectele alocate (zerourile) care optimizează problema. Dacă o sarcină este deja alocată într-un rând anterior, aceasta este eliminată în următorul. Pentru a calcula costul minim adăugăm costurile matricei inițiale care apar în poziția acestor zerouri.
Exemplu de metodă maghiară
Să vedem un exemplu simplu al metodei maghiare de. Să ne imaginăm că avem trei lucrători și aceștia trebuie să fie repartizați la trei proiecte. Creăm matricea inițială (C) și valorile costurilor în fiecare celulă. Pentru aceasta trebuie să utilizați informațiile disponibile în companie. Odată ce avem toate acestea, începem procesul. O foaie de calcul vă poate ajuta.
Calculăm minimele fiecărui rând și le scădem din elementele acelui rând și facem același lucru cu coloanele (pașii 1 și 2). În matricea rezultată (C`) trasăm linii în așa fel încât să acopere toate zerourile și la rândul lor să se intersecteze (pasul 3). Vedem că există două linii, dar cea mai mare valoare a numărului de rânduri sau coloane este de trei. Trebuie să continuăm.
Acum alegem cel mai mic dintre numerele descoperite, în acest exemplu sunt două (albastru închis). O scădem din cele anterioare și o adăugăm la cele care sunt situate acolo unde liniile se intersectează. În cazul nostru, sunt încă două (E3, T1). Ne-a rămas o nouă matrice (pasul 4). Redesenăm liniile și numărăm. Există trei linii, la fel ca numărul de rânduri sau coloane. Algoritmul este terminat.
Începem cu rândul sau coloana cu cele mai puține zerouri (E1, T1). Dacă o sarcină este deja atribuită, aceasta nu poate fi realocată, de exemplu, cu E2 nu puteți utiliza primul zero al T1, deoarece această sarcină a fost atribuită E1. Costul total, în metoda maghiară, va fi suma costurilor matricei inițiale (Pasul 1) situat în aceeași poziție ca și zerourile alese (pasul 5).