Algoritmo húngaro

La primera versión conocida del método Húngaro, fue inventado y publicado por Harold W. Kuhn en 1955.

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).

En primer lugar debemos partir de una matriz como la siguiente: 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 2, 3, 4 respectivamente.

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).

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: Una vez realizado todo esto se trazan líneas (casillas color gris) sobre todas las columnas marcadas y todas las filas sin marcar.