MÈTODE HONGARÈS: EN QUÈ CONSISTEIX, EXEMPLE - DUDAS - 2025

El mètode hongarès és un algoritme que s'utilitza en problemes d'assignació quan es vol minimitzar el cost. És a dir, s'usa per trobar el cost mínim a l'assignar diverses persones a diverses activitats basades en el menor cost. S'ha de assignar cada activitat a una persona diferent.

Un problema d'assignació és un tipus especial de problema de programació lineal, on l'objectiu és minimitzar el cost o el temps de completar una quantitat de treballs per part de diverses persones.

Font: pixabay.com

Una de les característiques importants de el problema d'assignació és que només s'assigna un treball (o treballador) a una màquina (o projecte).

Aquest mètode va ser desenvolupat pel matemàtic hongarès D. Konig. Per aquesta raó, se li coneix com el mètode hongarès per problemes d'assignació. També és conegut com algorisme d'assignació de Kuhn-Munkres.

Qualsevol problema d'assignació es pot resoldre fàcilment aplicant aquest mètode que consta de dues fases:

- Amb la primera fase es realitzen reduccions de files i reduccions de columnes.

- En la segona fase s'optimitza la solució sobre una base iterativa.

En què consisteix el mètode hongarès?

El mètode hongarès consta de quatre passos. Els primers dos passos s'executen una sola vegada, mentre que els passos 3 i 4 es repeteixen fins a trobar una assignació òptima.

Es considera com a dada d'entrada a una matriu quadrada de l'ordre n per n, la qual ha de contenir només elements no negatius.

Per a un problema donat, si el nombre de files de la matriu no és igual a el nombre de columnes s'ha d'agregar una fila fictícia o columna fictícia, depenent de el cas. Els costos d'assignació per a aquestes cel·les fictícies sempre s'assignen com a zero.

Pas 1: restar els mínims de cada fila

Per a cada fila de la matriu es selecciona l'element amb el valor més baix i s'ho queda de cada element en aquesta fila.

Pas 2: restar els mínims de cada columna

De manera similar, es selecciona per cada columna l'element amb el valor més baix i s'ho queda de cada element en aquesta columna.

Pas 3: cobrir tots els zeros amb un mínim nombre de línies

S'han de cobrir tots els zeros en la matriu resultant de el pas 2 usant un nombre mínim de línies horitzontals i verticals, ja sigui per files o columnes.

Si es requereix un total de n línies per cobrir tots els zeros, en què n igual a la mida n per n de la matriu, es tindrà una assignació òptima entre els zeros i per tant l'algorisme s'atura.

En cas contrari, si es requereixen menys de n línies per cobrir tots els zeros en la matriu, es continua amb el pas 4.

Pas 4: crear zeros addicionals

Se selecciona el menor element de la matriu (anomenat k) que no estigui cobert per una de les línies realitzades en el pas 3.

Es resta el valor de k de tots els elements que no estan coberts per línies. Posteriorment se suma el valor de ca tots els elements que estan coberts per la intersecció de dues línies.

Els elements que estan coberts per una sola línia es deixen tal com estan. Després de realitzar aquest pas, es torna a al pas 3.

assignació òptima

Una vegada que s'aturi l'algoritme en el pas 3, es tria un conjunt de zeros de manera que cada fila i cada columna tingui només un zero seleccionat.

Si en aquest procés de selecció no hi ha un únic zero en una fila o columna, es triarà llavors un d'aquests zeros. S'eliminen els zeros restants en aquesta columna o fila, repetint el mateix per a les altres assignacions també.

Si no hi ha una única assignació de zeros vol dir que hi ha múltiples solucions. No obstant això, el cost seguirà sent el mateix per als diferents conjunts de assignacions.

S'elimina qualsevol fila o columna fictícia que s'hagi agregat. Els zeros elegits en aquesta matriu final corresponen així a l'assignació ideal requerida en la matriu original.

exemple

Considerem una empresa on hi ha quatre activitats (A1, A2, A3, A4) que han de ser executades per quatre treballadors (T1, T2, T3, T4). S'ha de assignar una activitat per treballador.

La següent matriu mostra el cost d'assignar un determinat treballador a una determinada activitat. L'objectiu que es persegueix és minimitzar el cost total de la tasca composta per aquestes quatre activitats.

Pas 1: restar els mínims de cada fila

Es comença per restar l'element amb el valor mínim de cada fila dels altres elements d'aquesta fila. Per exemple, l'element més petit a la primera fila és 69. Per tant, es resta 69 de cada element a la primera fila. La matriu resultant és:

Pas 2: restar els mínims de cada columna

De la mateixa manera, es resta l'element amb el valor mínim de cada columna dels altres elements d'aquesta columna, obtenint la següent matriu:

Pas 3: cobrir tots els zeros amb un mínim nombre de línies

Ara es determinarà el mínim nombre de línies (horitzontals o verticals) que es requereixen per cobrir tots els zeros a la matriu. Tots els zeros es poden cobrir usant 3 línies:

A causa que el nombre de línies requerides és tres i és menor que la mida de la matriu (n = 4), es continua amb el pas 4.

Pas 4: crear zeros addicionals

Se selecciona el menor element no cobert per les línies, el valor és 6. Es resta aquest valor de tots els elements no coberts i aquest mateix valor se suma a tots els elements coberts per la intersecció de dues línies. Això dóna com a resultat la següent matriu:

Tal com està indicat en el mètode hongarès, s'ha de realitzar de nou el pas número tres.

Pas 3 (repetició)

Novament es determina el mínim nombre de línies requerides per cobrir tots els zeros a la matriu. En aquesta ocasió es requereixen quatre línies:

A causa que el nombre de línies requerides és 4, igual a la mida de la matriu (n = 4), es té una assignació òptima entre els zeros a la matriu. Per tant, l'algorisme s'atura.

assignació òptima

Tal com indica el mètode, la selecció realitzada dels següents zeros correspon a una assignació òptima:

Aquesta selecció de zeros correspon a la següent assignació òptima en la matriu de costos original:

Per tant, el treballador 1 ha realitzar l'activitat 3, el treballador 2, l'activitat 2, el treballador 3, l'activitat 1 i el treballador abril de realitzar l'activitat 4. El cost total d'aquesta assignació òptima és de 69 + 37 + 11 + 23 = 140.

referències

1. Hungarian Algorithm (2019). The Hungarian algorithm. Pres de: hungarianalgorithm.com.
2. Study (2019). Using the Hungarian Algorithm to Solve Assignment Problems. Pres de: study.com.
3. Wisdom Jobs (2018). Hungarian Method for Solving Assignment Problem - Quantitative Techniques for Management. Pres de: wisdomjobs.com.
4. Geeks for Geeks (2019). Hungarian Algorithm for Assignment Problem. Pres de: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Hungarian Maximum Matching Algorithm. Brilliant. Pres de: brilliant.org.