Algoritmo húngaro

EL algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo $O(n^3\,)$. La primera versión conocida del método Húngaro, fue inventado y publicado por Harold Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo Húngaro, el algoritmo de la asignación de Munkres, o el algoritmo de Kuhn-Munkres.

El algoritmo desarrollado por Kuhn está basado fundamentalmente en los primeros trabajos de otros dos matemáticos Húngaros: Dénes König y Jenő Egerváry. La gran ventaja del método de Kuhn es que es fuertemente polinómico (ver Complejidad computacional para más detalles).

El algoritmo construye una solución del problema primal partiendo de una solución no admisible (que corresponde a una solución admisible del dual) haciéndola poco a poco más admisible.

Modelado

El algoritmo modela un problema de asignación como una matriz de costes n×m, donde cada elemento representa el coste de asignar el enésimo trabajador al emésimo trabajo. Por defecto, el algoritmo realiza la minimización de los elementos de la matriz; de ahí que en caso de ser un problema de minimización de costes, es suficiente con comenzar la eliminación de Gauss-Jordan para hacer ceros (al menos un cero por línea y por columna). Sin embargo, en caso de un problema de maximización del beneficio, el coste de la matriz necesita ser modificado para que la minimización de sus elementos lleve a una maximización de los valores de coste originales. En un problema de costes infinito, el coste inicial de la matriz puede ser remodelado restando a cada elemento de cada línea el valor máximo del elemento de esa línea (o análogamente columna ). En un problema de coste infinito, todos los elementos son restados por el valor máximo de la matriz entera.

Algoritmo

$(1) \,$ Dada la matriz de costes $C \,$, se construye $C^\prime\,$ encontrando el valor mínimo de cada fila y restando ese valor a cada elemento de la fila.

$\Rightarrow \; \mathit{C'}_{i,j}=\mathit{C}_{i,j}-\min \mathit{C}_{i,j}$

$( 2 ) \,$ Se encuentra el valor mínimo de cada columna y se resta a cada elemento de la columna.

$\Rightarrow \; \mathit{C'}_{i,j}=\mathit{C'}_{i,j}-\min \mathit{C}_{i,j}$

$(3) \,$ A partir de $\mathit{C'}\,$ se considera "grafo de las igualdades" a $G=(N1,N2,A) \,$ tal que $A \,$ está constituido por todas las copias $({i,j})\,$ tales que $\mathit{C'}_{i,j}=0 \,$. En otras palabras, verificamos si para todas las filas existe una columna con costo 0 que no ha sido asignada a otra fila.

Determinar sobre $G\,$ un matching $M\,$ de cardinalidad máxima.

si $|\mathit{M}| = |N_1| = |N_2| \Rightarrow \; STOP$

Si todas las filas tienen a lo menos una intersección con costo cero que no ha sido ocupada por otra fila, estamos en el óptimo. Termina el algoritmo.

$(a) \,$ Considero $C^\prime\,$ y se etiquetan las filas que no han sido acopladas o asignadas por el algoritmo de matching máximo.

$(b) \,$ Se etiquetan en $C^\prime\,$ las columnas que tienen los ceros en correspondencia o asignadas a las filas etiquetadas (con *).

$(c) \,$ Etiquetar las filas que no han sido ya etiquetadas y acopladas o asignadas por el algoritmo de matching máximo con las columnas ya etiquetadas (con *).

$(d) \,$ Repetir los pasos $(b) \,$ y $(c) \,$ hasta que no halla más filas o columnas que etiquetar.

$(e) \,$ Borrar las filas etiquetadas y las columnas NO etiquetadas. Para esto puede trazar una línea recta en las columnas y filas borradas.

$(f) \,$ Sea $\delta\,$ el elemento de $C^\prime\,$ de valor mínimo entre aquellos costos no borrados (o tarjados) en el paso anterior.

$(g) \,$ Restar $\delta\,$ a cada elemento no borrado y sumarlo a los elementos doblemente borrados (o donde haya intersección o cruces entre las líneas marcadas en el paso $(e) \,$ )

$(h) \,$ Volver al paso $(1) \,$.

Ejemplo

En un cierto punto del algoritmo tenemos el grafo $G \,$ y la matriz $C^\prime\,$.

matching máximo del grafo de las igualdades.

$C'=\begin{pmatrix} 1 & 2 & 7 & 3 & 0 \\ 3 & 4 & 1 & 0 & 2 \\ 2 & 3 & 6 & 0 & 0 \\ 0 & 6 & 1 & 1 & 0 \\ 2 & 0 & 0 & 4 & 5 \end{pmatrix}$

En $G \,$ tengo un arco $\Longleftrightarrow \;$ tengo un $0 \,$ en$C^\prime\,$.

$M =\{ (1,5'), (2,4'), (4,1'), (5,3') \}\,$ es matching máximo pero no es perfecto, pues la fila 3 está sin asignar. $\Rightarrow \;$ volvemos al paso $(3) \,$ del algoritmo.

$(a) \,$

$\begin{pmatrix} & & & & & \\ & 1 & 2 & 7 & 3 & 0 \\ & 3 & 4 & 1 & 0 & 2 \\ \star \; & 2 & 3 & 6 & 0 & 0 \\ & 0 & 6 & 1 & 1 & 0 \\ & 2 & 0 & 0 & 4 & 5 \end{pmatrix}$$\Rightarrow \;$

$(b) \,$

$\begin{pmatrix} & & & & \star\;& \star\;\\ & 1 & 2 & 7 & 3 & 0 \\ & 3 & 4 & 1 & 0 & 2 \\ \star \; & 2 & 3 & 6 & 0 & 0 \\ & 0 & 6 & 1 & 1 & 0 \\ & 2 & 0 & 0 & 4 & 5 \end{pmatrix}$$\Rightarrow \;$

$(c) \,$ El matching de las columnas $4'\,$ y $5'\,$ esta acopladas al de las filas $1\,$ y $2 \Rightarrow \;$

$(d) \,$

$\begin{pmatrix} & & & & \star\;& \star\;\\ \star \; & 1 & 2 & 7 & 3 & 0 \\ \star \; & 3 & 4 & 1 & 0 & 2 \\ \star \; & 2 & 3 & 6 & 0 & 0 \\ & 0 & 6 & 1 & 1 & 0 \\ & 2 & 0 & 0 & 4 & 5 \end{pmatrix}$$\Rightarrow \;$

$(e) \,$

$\begin{pmatrix} & & & & \star\;& \star\;\\ \star \; & 1 & 2 & 7 & & \\ \star \; & 3 & 4 & 1 & & \\ \star \; & 2 & 3 & 6 & & \\ & & & & & \\ & & & & & \end{pmatrix}$$\Rightarrow \;$

$(f) \,$

$\delta =min \begin{pmatrix} 1 & 2 & 7 \\ 3 & 4 & 1 \\ 2 & 3 & 5 \end{pmatrix}= 1$

$(g) \,$ Resto $\delta\,$ a los elementos no borrados de $C^\prime\,$ y sumo $\delta\,$ a los elementos doblemente borrados de $C^\prime\,$.

$C'=\begin{pmatrix} 0 & 1 & 6 & 3 & 0 \\ 2 & 3 & 0 & 0 & 2 \\ 1 & 2 & 5 & 0 & 0 \\ 0 & 6 & 1 & 2 & 1 \\ 2 & 0 & 0 & 5 & 6 \end{pmatrix}$$\Rightarrow \;$

$(h) \,$ Volvemos al paso $(1) \,$, para recrear el grafo de las igualdades y calcular de nuevo el matching máximo.

Ejemplo 2 Problema de minimización

Enunciado del problema: En una empresa existen N tareas a realizar y N personas que pueden realizarlas. Tenemos una matriz N×N que contiene el coste de asignar a cada trabajador en cada tarea, en el presente caso, se supone que existen cuatro operarios (a, b, c y d) y cuatro tareas a realizar (1,2,3 y 4). El problema estriba en encontrar que tarea debemos asignar a cada trabajador para que el coste total sea mínimo. En primer lugar debemos partir de una matriz como la siguiente:

$\begin{bmatrix} a1 & a2 & a3 & a4\\ b1 & b2 & b3 & b4\\ c1 & c2 & c3 & c4\\ d1 & d2 & d3 & d4\end{bmatrix}$

Donde a, b, c y d son los trabajadores que deben ejecutar las distintas tareas 1, 2, 3 y 4. En la matriz a1 representa el coste en que se incurre si el trabajador A, desarrolla la tarea 1, a2, a3, a4 muestra el coste en que se incurre cuando el trabajador A ejecuta las tareas 1, 2, 3, 4 respectivamente. De la misma forma sucede para el resto de los trabajadores. La matriz es cuadrada de manera que cada trabajador puede ejecutar solo una tarea.

Se comienza a operar con la matriz.

• Para hacer esto, se toma el menor valor de todos los que se encuentran en la primera fila a_i (i se encuentra entre 1-4) y es restado de los otros elementos de esa fila.
• Se repite este procedimiento para todas las filas.
• Esto nos lleva a que en cada fila haya al menos un cero (Pueden existir varios ceros en una fila, cuando hay dos casillas que tienen valores iguales y son a la vez los valores mínimos de esas filas).
• Ahora disponemos de una matriz donde al menos existe un cero en cada fila.
• Tratamos de asignar a los trabajadores, de manera que cada empleado solo realice una tarea y que el coste en cada caso sea cero.

Esto se muestra en la siguiente matriz, donde los ceros son las tareas asignadas:

0	a2'	0'	a4'
b1'	b2'	b3'	0'
0'	c2'	c3'	c4'
d1'	0'	d3'	d4'

En algunos casos puede resultar que la matriz anterior no puede ser utilizada para asignar.

0	a2'	a3'	a4'
b1'	b2'	b3'	0'
0	c2'	c3'	c4'
d1'	0	d3'	d4'

Efectivamente en el caso de la matriz anterior no se puede realizar una asignación completa, la tarea 1 es realizada de manera eficiente por los empleados A y C (Existen dos ceros en la columna 1). Ambos no pueden ser asignados a la misma tarea, también debemos advertir que nadie puede realizar la tarea 3 de manera eficiente. Para superar esto, debemos repetir el procedimiento anterior de restar el menor, para todas las columnas y entonces comprobamos si es posible la asignación.

En la mayoría de los casos esto nos dará el resultado, pero si todavía no es posible la asignación, entonces se debe seguir el siguiente procedimiento:

• En primer lugar asigna tantas tareas como sean posible y después se debe hacer lo siguiente (asignar tareas en las filas 2, 3 y 4)

0	a2'	a3'	a4'
b1'	b2'	b3'	0'
0'	c2'	c3'	c4'
d1'	0'	d3'	d4'

• Marca todas las filas que no tengan asignación (fila 1).
• Marca todas las columnas que tengan ceros en esa fila (columna 1).
• Marca todas las filas que tengan asignación en la columna dada (fila 3).
• Marca todas las columnas que tengan asignaciones en la fila dada.
• Repetir este proceso hasta que se obtenga un circuito cerrado.

×
0	a2'	a3'	a4'	×
b1'	b2'	b3'	0'
0'	c2'	c3'	c4'	×
d1'	0'	d3'	d4'

Una vez realizado todo esto se trazan líneas (casillas color gris) sobre todas las columnas marcadas y todas filas sin marcar.

×
0	a2'	a3'	a4'	×
b1'	b2'	b3'	0'
0'	c2'	c3'	c4'	×
d1'	0'	d3'	d4'

De los elementos que están sin tachar (en blanco), se busca el valor más bajo, se resta éste de todos los elementos que no están señalados o tachados y se le suma a los elementos que se encuentran en la intersección de dos líneas. Los demás elementos se dejan sin cambiar. Ahora se asigna las tareas usando las reglas de arriba. Repite el procedimiento hasta que sea posible la asignación. Básicamente se encuentra el segundo coste mínimo entre dos filas. El procedimiento es repetido hasta que seas capaz de distinguir entre los trabajadores en términos de menor coste.

Bibliografía

• R.E.Burkard, M.Del'Amico, S.Martello: Assignment Problems. SIAM, Philadelphia PA.) 2009. ISBN 978-0-89871-663-4
• Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistic Quarterly, 2:83-97, 1955. Kuhn's original publication.
• Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistic Quarterly, 3: 253-258, 1956.
• J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society of Industrial and Applied Mathematics, 5(1):32-38, 1957 March.

Enlaces externos

• R. A. Pilgrim, Munkres' Assignment Algorithm. Modified for Rectangular Matrices, Course notes, Murray State University.
  • Or: Step-by-step description of algorithm
• Mike Dawes, The Optimal Assignment Problem, Course notes, University of Western Ontario.

Implementaciones

• Serial and parallel implementations.
• C# implementation
• Petr Tichavský, maxmatching, Matlab implementation.
• Perl implementation
• Lisp implementation
• Java implementation