Método húngaro

El método húngaro es un algoritmo que permite minimizar los costos en un problema de optimización basado en la programación lineal.

El objetivo del método húngaro es encontrar el coste mínimo de un conjunto de tareas que deben ser realizadas por las personas más adecuadas.

Utiliza la programación lineal (PL) para realizar una serie de pasos que se pueden automatizar. Así, herramientas como el software estadístico R (entre otros) tiene varios paquetes de mucha utilidad para estos problemas de optimización.

Origen del método húngaro

Su creador fue el mátemático húngaro (de ahí su nombre) Harold W. Kuhn en el año 1955. Otro matemático, James Munkres, lo revisó en 1957. Con esta evolución ha recibido otras denominaciones como algoritmo de asignación de Munkres o de Kuhn-Munkres.

Por otro lado, este método tiene un antecedente en dos autores, Dénes König y Jenő Egerváry, ambos judios y húngaros. El primero desarrolló la teoría de grafos en la cual se basa este algoritmo. El segundo generalizó el teorema de König y permitió a Kuhn desarrollar el método.

Pasos del método húngaro

Los pasos a seguir permiten realizar el método húngaro de una manera sencilla utilizando una hoja de cálculo. Además, este esquema que mostramos permitirá ver de forma global el proceso que desarrollaremos en detalle en el ejemplo final.

• Como pasos previos, hay que asignar a las personas (filas) a una serie de proyectos (columnas). Además, hay que calcular los diferentes costes de cada proyecto en función de quién lo realice y construir con esta información una matriz (C).
• En la matriz (C) buscamos el valor mínimo de cada fila. Restamos este a todos los elementos de la fila y realizamos la misma operación con las columnas. Aparecerá una nueva matriz (C`) con los resultados de las operaciones anteriores.
• A continuación creamos el «grafo de igualdades», que nos permite escoger las tareas y proyectos con menor costo. El óptimo serían aquellos elementos cuyo resultado fue cero. Si se cumple que no hay ningún elemento con valor cero asignado a más de una fila el algoritmo termina.
• En caso contrario, hay que realizar una nueva asignación. Se realiza una nueva a matriz a la que se aplican una serie de modificaciones, como veremos en el ejemplo. Volvemos a crear el grafo y avanzamos hasta que nos quede una matriz que tenga al menos un cero en cada fila y en posiciones no repetidas.
• Con esta información ya tenemos a las personas y los proyectos asignados (los ceros) que optimizan el problema. Si una tarea ya está asignada en una fila anterior, en la siguiente se descarta. Para calcular el coste mínimo sumamos los costes de la matriz inicial que aparecen en la posición de dichos ceros.

Ejemplo del método húngaro

Veamos un sencillo ejemplo del método húngaro de. Imaginemos que tenemos tres trabajadores y hay que asignarlos a tres proyectos. Creamos la matriz inicial (C) y los valores de los coste en cada celda. Para esto hay que utilizar la información disponible en la empresa. Una vez tenemos todo esto comenzamos el proceso. Una hoja de cálculo puede ayudar.

Calculamos los mínimos de cada fila y los restamos a los elementos de esa fila y hacemos lo mismo con las columnas (pasos 1 y 2). En la matriz resultante (C`) dibujamos líneas de tal manera que tapen todos los ceros y a su vez se crucen entre ellas (paso 3). Vemos que hay dos líneas, pero el mayor valor del número de filas o columnas es tres. Hay que seguir.

Ahora elegimos el menor de los números no tapados, en este ejemplo es el dos (azul oscuro). Lo restamos a los anteriores y lo sumamos a los que se sitúan donde se cruzan las líneas. En nuestro caso es otro dos (E3,T1). Nos queda una nueva matriz (paso 4). Volvemos a dibujar las líneas y contamos. Hay tres líneas, igual que el número de filas o columnas. Se acaba el algoritmo.

Comenzamos por la fila o columna con menos ceros (E1,T1). Si una tarea está ya asignada no se puede volver a asignar, por ejemplo, con el E2 no se puede utilizar el primer cero de la T1, ya que esta tarea estaba asignada al E1. El coste total, en el método húngaro, será la suma de los costes de la matriz original (Paso 1) situados en la misma posición que los ceros elegidos (paso 5).