Definición de Método húngaro | Diccionario Economico
El método húngaro es una técnica utilizada en la programación matemática para resolver problemas de asignación óptima de recursos, minimizando el costo total. Se basa en asignar elementos a través de la formación de una matriz de costos y la aplicación de algoritmos de optimización para encontrar la solución óptima.
El objetivo del método húngaro es encontrar el costo mínimo de un conjunto de tareas que deben ser realizadas por las personas más adecuadas.
Utiliza programación lineal (LP) para realizar una serie de pasos que se pueden automatizar. Como tal, herramientas como el software estadístico R (entre otros) tienen algunos paquetes muy útiles para tratar estos problemas de optimización.
Origen del método húngaro
Su creador fue el matemático húngaro (de ahí su nombre) Harold W. Kuhn en 1955. Otro matemático, James Mancres, lo revisó en 1957.
Por otra parte, este método tiene como precursores a dos autores, Denes König y Jeno Egerváry, judíos y húngaros. El primero desarrolló la teoría de grafos en la que se basa este algoritmo. El segundo generalizó el teorema de Koenig y permitió a Kuhn desarrollar el método.
Etapas del Método Húngaro
Los siguientes pasos te permitirán completar el método húngaro de forma sencilla utilizando una hoja de cálculo. Además, este diagrama, que mostraremos, nos permitirá ver el proceso, que desarrollaremos en detalle en el ejemplo final, a escala global.
- Al igual que en los pasos anteriores, debe asignar personas (filas) a una serie de proyectos (columnas). Además, es necesario calcular los diferentes costos de cada proyecto, dependiendo de quién lo lleve a cabo, y construir una matriz (C) con esta información.
- En la matriz (C) buscamos el valor mínimo de cada fila. Restamos esto de todos los elementos de la fila y realizamos la misma operación en las columnas. Aparecerá una nueva matriz (C`) con los resultados de las operaciones anteriores.
- A continuación, creamos un «gráfico de igualdad» que nos permite seleccionar tareas y proyectos con el costo más bajo. Los elementos óptimos son aquellos cuyo resultado es igual a cero. Si es cierto que no se asigna ningún elemento nulo a más de una fila, el algoritmo termina.
- De lo contrario, se debe realizar una nueva asignación. Se crea una nueva matriz, a la que se le aplican una serie de modificaciones, como veremos en el ejemplo. Recreamos el gráfico y continuamos hasta obtener una matriz que tenga al menos un cero en cada fila y en posiciones que no se repitan.
- Con esta información ya tenemos asignadas personas y proyectos (nulos) que optimizan el problema. Si la tarea ya está asignada en la línea anterior, se descarta en la siguiente. Para calcular el costo mínimo, sumamos los costos de la matriz original que aparecen en las posiciones de los ceros especificados.
Un ejemplo del método húngaro
Veamos un ejemplo simple del método húngaro. Imaginemos que tenemos tres trabajadores y tenemos que asignarlos a tres proyectos. Cree una matriz inicial (C) y valores de costo en cada celda. Para ello, es necesario utilizar la información disponible en la empresa. Cuando tenemos todo esto, comenzamos el proceso. Una hoja de cálculo puede ayudar.
Calculamos los mínimos de cada fila y los restamos de los elementos de esa fila y hacemos lo mismo para las columnas (pasos 1 y 2). En la matriz resultante (C`), dibujamos líneas de tal manera que se superpongan a todos los ceros y se intersequen entre sí (paso 3). Vemos que hay dos filas, pero el mayor valor del número de filas o columnas es tres. Debemos seguir adelante.
Ahora elegimos el más pequeño de los números descubiertos, en este ejemplo es dos (azul). Lo restamos de los anteriores y lo sumamos a los ubicados en la intersección de las rectas. En nuestro caso, son dos más (E3,T1). Nos queda una nueva matriz (paso 4). Vuelva a dibujar las líneas y cuente. Hay tres filas, tantas como filas o columnas. El algoritmo está terminado.
Comencemos con la fila o columna con la menor cantidad de ceros (E1,T1). Si ya se asignó una tarea, no se puede reasignar, por ejemplo, el primer cero de T1 no se puede usar con E2, ya que esta tarea se asignó a E1. El coste total en el método húngaro será la suma del coste de la matriz original (paso 1) situada en la misma posición que los ceros seleccionados (paso 5).
¿Problemas o dudas? Te ayudamos
Si quieres estar al día, suscríbete a nuestra newsletter y síguenos en Instagram. Si quieres recibir soporte para cualquier duda o problema, no dude en ponerse en contacto con nosotros en info@wikieconomia.org