Algoritmo húngaro, o cómo las matemáticas ayudan a asignar tareas

Hola amigos En este artículo me gustaría hablar sobre un algoritmo interesante de la disciplina "Investigación operativa", a saber, sobre el método húngaro y cómo resolver problemas de asignación con su ayuda. Me referiré a la teoría sobre en qué casos y para qué tareas es aplicable este algoritmo, lo analizaré paso a paso en mi ejemplo inventado y compartiré mi modesta descripción del código para su implementación en el lenguaje R. ¡Comencemos!

Algunas palabras sobre el método

Para no pintar mucha teoría con términos y definiciones matemáticas, propongo considerar un par de opciones para construir el problema de asignación, y creo que comprenderá de inmediato en qué casos aplicaremos el método húngaro:

• La tarea de nombrar empleados para puestos. Es necesario distribuir a los trabajadores a los puestos para que se logre la máxima eficiencia, o hay un costo mínimo de trabajo.
• Asignación de máquinas a secciones de producción. La distribución de máquinas para que durante su operación la producción sea lo más rentable posible, o el costo de mantenerlas sea mínimo.
• Se estima la selección de candidatos para varias vacantes. Analizaremos este ejemplo a continuación.

Como puede ver, hay muchas opciones para las cuales es aplicable el método húngaro, y surgen tareas similares en muchas áreas de actividad.

Como resultado, la tarea debe resolverse de modo que un artista intérprete o ejecutante (persona, máquina, herramienta, ...) pueda realizar solo un trabajo, y cada trabajo lo realice un solo artista intérprete o ejecutante.

Una condición necesaria y suficiente para resolver un problema es su tipo cerrado. Es decir cuando el número de artistas intérpretes o ejecutantes = el número de obras (N = M). Si no se cumple esta condición, puede agregar artistas ficticios, o trabajos ficticios, para los cuales los valores en la matriz serán cero. Esto no afectará la solución del problema, solo le dará el tipo cerrado necesario.

Algoritmo paso a paso por ejemplo

Planteamiento del problema: deje que se planifique una conferencia científica importante. Para llevarlo a cabo, debe configurar el sonido, la luz, las imágenes, registrar a los invitados y prepararse para los descansos entre presentaciones. Hay 5 organizadores para esta tarea. Cada uno de ellos tiene ciertas estimaciones del desempeño de un trabajo en particular (supongamos que estas estimaciones se establecen como el promedio aritmético de las revisiones de sus empleados). Es necesario distribuir a los organizadores para que su puntaje total sea máximo. La tarea tiene la siguiente forma:


Si el problema se resuelve al máximo (como en nuestro caso), entonces en cada fila de la matriz es necesario encontrar el elemento máximo, restarlo de cada elemento de la fila correspondiente y multiplicar toda la matriz por -1. Si el problema se resuelve al mínimo, se debe omitir este paso.


En cada fila y en cada columna solo debe haber un cero seleccionado. (es decir, cuando se eligió cero, los ceros restantes en esta fila o en esta columna ya no se tienen en cuenta). En este caso, esto no se puede hacer:


( Si el problema se resuelve al mínimo, entonces debe comenzar con este paso ). Continuamos la solución aún más. Reducción matricial por filas (busque el elemento mínimo en cada fila y reste de cada elemento, respectivamente):


Porque Como todos los elementos mínimos son cero, la matriz no ha cambiado. Realizamos la reducción en columnas:


Nuevamente, buscamos que en cada columna y en cada fila solo haya un cero seleccionado. Como se puede ver a continuación, en este caso es imposible de hacer. Presenté dos opciones sobre cómo elegir ceros, pero ninguna de ellas dio el resultado deseado:


Continuamos la decisión aún más. Tache las filas y columnas que contienen cero elementos ( ¡IMPORTANTE! El número de cruces debe ser mínimo ). Entre los elementos restantes, buscamos el mínimo, lo restamos de los elementos restantes (que no están tachados) y lo sumamos a los elementos que se encuentran en la intersección de las filas y columnas tachadas (lo que está marcado en verde se resta allí; lo que está marcado en dorado se resume allí; luego, lo que no está pintado, no tocar):


Como puede ver ahora, en cada columna y fila solo hay un cero seleccionado. ¡Completamos la solución del problema!


Sustituya en la tabla inicial la ubicación de los ceros seleccionados. Por lo tanto, obtenemos el plan óptimo, u óptimo, en el que los organizadores se distribuyen entre el trabajo y la suma de las estimaciones resultó ser máxima:


Si resuelve el problema y todavía es imposible elegir ceros para que solo haya uno en cada columna y fila, entonces repetimos el algoritmo desde el lugar donde se realizó la reducción por filas (el elemento mínimo en cada fila).

Implementación del lenguaje de programación R

El algoritmo húngaro se implementa utilizando recursiones. Espero que mi código no cause dificultades. Primero necesita compilar tres funciones, y luego comenzar los cálculos.

Los datos para resolver el problema se toman del archivo example.csv que tiene la forma:



El resultado del programa:

En conclusión

Muchas gracias por tomarse el tiempo de leer mi artículo. Proporcionaré todos los enlaces utilizados a continuación. Espero que hayas aprendido algo nuevo por ti mismo o que hayas actualizado tus viejos conocimientos. Todo éxito, buena y buena suerte!

Recursos utilizados

1. Wikipedia irrumpida
2. Y otros buenos sitios
3. Destaqué para mí mismo alguna información de este artículo.