METODA MAGHIARĂ: DIN CE CONSTĂ, DE EXEMPLU - DUDAS - 2025

Metoda maghiară este un algoritm care este utilizat în problemele de alocare atunci când doriți să minimizați costurile. Adică este utilizat pentru a găsi costul minim, alocând mai multe persoane la diverse activități bazate pe cel mai mic cost. Fiecare activitate trebuie să fie atribuită unei persoane diferite.

O problemă de alocare este un tip special de problemă de programare liniară, în care obiectivul este de a reduce costurile sau timpul de finalizare a unui număr de locuri de muncă de către mai multe persoane.

Sursa: pixabay.com

Una dintre caracteristicile importante ale problemei de alocare este aceea că doar un singur post (sau lucrător) este atribuit unei mașini (sau unui proiect).

Această metodă a fost dezvoltată de matematicianul maghiar D. Konig. Din acest motiv, este cunoscută sub numele de metoda maghiară pentru probleme de atribuire. Este cunoscut și ca algoritmul de alocare Kuhn-Munkres.

Orice problemă de alocare poate fi rezolvată cu ușurință prin aplicarea acestei metode care constă în două faze:

- Odată cu prima fază, se realizează reduceri de rând și reduceri de coloană.

- În a doua fază, soluția este optimizată în mod iterativ.

Care este metoda maghiară?

Metoda maghiară constă din patru pași. Primii doi pași se execută o singură dată, în timp ce pașii 3 și 4 se repetă până când se găsește o alocare optimă.

O matrice pătrată de ordinul n cu n este considerată date de intrare, care trebuie să conțină numai elemente non-negative.

Pentru o problemă dată, dacă numărul de rânduri din matrice nu este egal cu numărul de coloane, trebuie să se adauge un rând manechin sau o coloană manechin, în funcție de caz. Costurile de alocare pentru acele celule manechin sunt întotdeauna alocate ca fiind zero.

Pasul 1: scade minimele fiecărui rând

Pentru fiecare rând din tablă, elementul cu cea mai mică valoare este selectat și scăzut din fiecare element din rândul respectiv.

Pasul 2: scade minimele din fiecare coloană

În mod similar, elementul cu cea mai mică valoare este selectat pentru fiecare coloană și scăzut din fiecare articol din acea coloană.

Pasul 3: acoperiți toate zerourile cu un număr minim de linii

Toate zerourile din matrice rezultate din etapa 2 trebuie acoperite folosind un număr minim de linii orizontale și verticale, fie prin rânduri, fie prin coloane.

Dacă este necesar un total de n linii pentru a acoperi toate zerourile, unde n este egal cu dimensiunea n ori n a matricei, va exista o alocare optimă între zerouri și, prin urmare, algoritmul se oprește.

În caz contrar, dacă sunt necesare mai puțin de n linii pentru a acoperi toate zerourile din tablă, treceți la pasul 4.

Pasul 4: creează zerouri suplimentare

Este selectat cel mai mic element al matricei (numit k) care nu este acoperit de una dintre liniile realizate în pasul 3.

Valoarea k este scăzută din toate elementele care nu sunt acoperite de linii. Ulterior, valoarea ka este adăugată la toate elementele care sunt acoperite de intersecția a două linii.

Elementele care sunt acoperite de o singură linie sunt lăsate așa cum este. După efectuarea acestui pas, reveniți la pasul 3.

Alocare optimă

După ce algoritmul este oprit în pasul 3, se alege un set de zerouri astfel încât fiecare rând și fiecare coloană să aibă doar un zero selectat.

Dacă în acest proces de selecție nu există un singur zero într-un rând sau coloană, atunci se va alege unul dintre acele zerouri. Celelalte resturi din acea coloană sau rând sunt eliminate, repetând același lucru și pentru celelalte atribuții.

Dacă nu există o singură atribuire zero, există mai multe soluții. Cu toate acestea, costul va rămâne același pentru diferite seturi de misiuni.

Orice rânduri sau coloane care se adaugă sunt eliminate. Cero-urile alese în această matrice finală corespund, așadar, cu sarcina ideală necesară în matricea inițială.

Exemplu

Să luăm în considerare o companie unde există patru activități (A1, A2, A3, A4) care trebuie desfășurate de patru lucrători (T1, T2, T3, T4). Trebuie să fie atribuită o activitate pentru fiecare lucrător.

Următoarea matrice arată costul alocării unui anumit lucrător unei anumite activități. Obiectivul este de a reduce costul total al sarcinii alcătuite din aceste patru activități.

Pasul 1: scade minimele fiecărui rând

Începeți scăzând elementul cu valoarea minimă din fiecare rând din celelalte elemente din acel rând. De exemplu, cel mai mic element din primul rând este 69. Prin urmare, 69 se scade din fiecare element din primul rând. Matricea rezultată este:

Pasul 2: scade minimele din fiecare coloană

În același mod, elementul cu valoarea minimă a fiecărei coloane este scăzut din celelalte elemente din acea coloană, obținând următoarea matrice:

Pasul 3: acoperiți toate zerourile cu un număr minim de linii

Acum vom determina numărul minim de linii (orizontale sau verticale) care sunt necesare pentru a acoperi toate zerourile din matrice. Toate zerourile pot fi acoperite folosind 3 linii:

Deoarece numărul de linii necesare este de trei și este mai mic decât dimensiunea matricei (n = 4), continuăm cu pasul 4.

Pasul 4: creează zerouri suplimentare

Este selectat cel mai mic element care nu este acoperit de linii, a cărui valoare este 6. Această valoare se scade din toate elementele care nu sunt acoperite și această aceeași valoare se adaugă la toate elementele acoperite de intersecția a două linii. Rezultă următoarea matrice:

După cum este indicat în metoda maghiară, pasul trei trebuie să fie efectuat din nou.

Pasul 3 (repetare)

Din nou se determină numărul minim de linii necesare pentru a acoperi toate zerourile din matrice. De data aceasta sunt necesare patru linii:

Deoarece numărul de linii necesare este 4, egal cu dimensiunea matricei (n = 4), avem o alocare optimă între zerourile din matrice. Prin urmare, algoritmul se oprește.

Alocare optimă

După cum indică metoda, selecția făcută din următoarele zerouri corespunde unei alocări optime:

Această selecție de zerouri corespunde următoarei alocări optime în matricea costurilor inițiale:

Prin urmare, lucrătorul 1 trebuie să efectueze activitatea 3, lucrătorul 2, activitatea 2, lucrătorul 3, activitatea 1, iar lucrătorul 4 trebuie să efectueze activitatea 4. Costul total al acestei sarcini optime este de 69 + 37 + 11 + 23 = 140.

Referințe

1. Algoritmul maghiar (2019). Algoritmul ungar. Luat de la: hungarianalgorithm.com.
2. Studiu (2019). Utilizarea algoritmului ungar pentru rezolvarea problemelor de atribuire. Luat de la: studiu.com.
3. Wisdom Jobs (2018). Metoda maghiară pentru soluționarea problemei de atribuire - tehnici cantitative pentru management. Luat de la: înțelepciune.com.
4. Geeks for Geeks (2019). Algoritmul maghiar pentru problema alocării. Luat de la: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Algoritmul de potrivire maximă maghiară. Sclipitor. Luat de la: fantastic.org.