El método húngaro es un algoritmo de optimización combinatoria que resuelve el problema de asignación en tiempo polinomial y que anticipó métodos primarios-duales posteriores . Fue desarrollado y publicado en 1955 por Harold Kuhn , quien le dio el nombre de "método húngaro" porque el algoritmo se basó en gran medida en los trabajos anteriores de dos matemáticos húngaros : Dénes Kőnig y Jenő Egerváry . [1] [2]
James Munkres revisó el algoritmo en 1957 y observó que es (fuertemente) polinomial . [3] Desde entonces, el algoritmo se conoce también como algoritmo de Kuhn-Munkres o algoritmo de asignación de Munkres . La complejidad temporal del algoritmo original fue, sin embargo Edmonds y Karp , e independientemente Tomizawa notaron que se puede modificar para lograr untiempo de ejecución. [4] [5] [ ¿cómo? ] Uno de los [ cita requerida ] más populares variantes es el algoritmo de Jonker-Volgenant. [6] Ford y Fulkerson ampliaron el método a problemas generales de flujo máximo en forma del algoritmo Ford-Fulkerson . En 2006, se descubrió que Carl Gustav Jacobi había resuelto el problema de asignación en el siglo XIX y la solución se había publicado póstumamente en 1890 en latín. [7]
El problema
Ejemplo
En este sencillo ejemplo hay tres trabajadores: Paul, Dave y Chris. Uno de ellos tiene que limpiar el baño, otro barrer los pisos y el tercero lavar las ventanas, pero cada uno exige un pago diferente por las distintas tareas. El problema es encontrar la forma más económica de asignar los trabajos. El problema se puede representar en una matriz de los costos de los trabajadores que realizan el trabajo. Por ejemplo:
Baño limpio | Barrer pisos | Lavar ventanas | |
---|---|---|---|
Paul | $ 2 | $ 3 | $ 3 |
Dave | $ 3 | $ 2 | $ 3 |
Chris | $ 3 | $ 3 | $ 2 |
El método húngaro, cuando se aplica a la tabla anterior, daría el costo mínimo: esto es $ 6, logrado al hacer que Paul limpie el baño, Dave barre los pisos y Chris lave las ventanas.
Formulación de matriz
En la formulación de la matriz, se nos da una matriz n × n no negativa , donde el elemento en la i -ésima fila y la j -ésima columna representa el costo de asignar el j -ésimo trabajo al i -ésimo trabajador. Tenemos que encontrar una asignación de los trabajos a los trabajadores, de modo que cada trabajo se asigne a un trabajador y a cada trabajador se le asigne un trabajo, de manera que el costo total de la asignación sea mínimo.
Esto se puede expresar como permutando las filas y columnas de una matriz de costos C para minimizar el rastro de una matriz:
donde L y R son matrices de permutación .
Si el objetivo es encontrar la asignación que se obtiene el máximo de costos, el problema puede ser resuelto mediante la negación de la matriz de costos C .
Formulación de gráfico bipartito
El algoritmo es más fácil de describir si formulamos el problema usando un gráfico bipartito. Tenemos un gráfico bipartito completo con vértices de los trabajadores) y vértices de trabajo), y cada borde tiene un costo no negativo . Queremos encontrar una combinación perfecta con un costo total mínimo.
El algoritmo en términos de gráficos bipartitos
Llamemos a una función un potencial si para cada . El valor del potencial es la suma del potencial sobre todos los vértices: .
El costo de cada emparejamiento perfecto es al menos el valor de cada potencial: el costo total del emparejamiento es la suma de los costos de todas las aristas; el costo de cada borde es al menos la suma de los potenciales de sus puntos finales; dado que la coincidencia es perfecta, cada vértice es un punto final de exactamente un borde; por lo tanto, el costo total es al menos el potencial total.
El método húngaro encuentra un emparejamiento perfecto y un potencial tal que el costo de emparejamiento es igual al valor potencial. Esto demuestra que ambos son óptimos. De hecho, el método húngaro encuentra una combinación perfecta de bordes estrechos : un borde se llama apretado para un potencial Si . Denotemos el subgrafo de bordes estrechos por. El costo de una combinación perfecta en (si hay uno) es igual al valor de .
Durante el algoritmo mantenemos un potencial y una orientación de (denotado por ) que tiene la propiedad de que los bordes orientados desde a formar una coincidencia . Inicialmente, es 0 en todas partes, y todos los bordes están orientados desde a (entonces esta vacio). En cada paso, modificamospara que su valor aumente, o modifique la orientación para obtener una coincidencia con más aristas. Mantenemos el invariante de que todos los bordes deestán apretados. Hemos terminado si es una combinación perfecta.
En un paso general, dejemos y ser los vértices no cubiertos por (entonces consta de los vértices en sin borde entrante y consta de los vértices en sin borde de salida). Dejar ser el conjunto de vértices alcanzables en de por un camino dirigido sólo siguiendo los bordes que son estrechos. Esto se puede calcular mediante una búsqueda en amplitud .
Si no está vacío, luego invierta la orientación de una ruta dirigida en de a . Por lo tanto, el tamaño de la correspondencia correspondiente aumenta en 1.
Si está vacío, entonces deja
está bien definido porque al menos uno de esos bordes debe existir siempre que la coincidencia aún no sea del tamaño máximo posible (consulte la sección siguiente); es positivo porque no hay bordes estrechos entre y . Incrementar por en los vértices de y disminuir por en los vértices de . La resultante sigue siendo un potencial, y aunque el gráfico cambios, todavía contiene (ver las siguientes subsecciones). Orientamos los nuevos bordes desde a . Por la definición de el conjunto de vértices alcanzables desde aumenta (tenga en cuenta que el número de bordes estrechos no aumenta necesariamente).
Repetimos estos pasos hasta es una combinación perfecta, en cuyo caso da una asignación de costo mínimo. El tiempo de ejecución de esta versión del método es: está aumentado tiempos, y en una fase donde no ha cambiado, hay como máximo cambios potenciales (desde aumenta cada vez). El tiempo suficiente para un cambio potencial es.
Prueba de que el algoritmo avanza
Debemos mostrar que siempre que la coincidencia no sea del tamaño máximo posible, el algoritmo siempre puede progresar, es decir, para aumentar el número de bordes emparejados o ajustar al menos un borde. Es suficiente mostrar que al menos uno de los siguientes se mantiene en cada paso:
- es del tamaño máximo posible.
- contiene una ruta de aumento.
- contiene un camino de cola suelta : un camino desde algún vértice en a un vértice en que consta de cualquier número (posiblemente cero) de bordes estrechos seguidos de un solo borde suelto. El borde suelto de salida de un camino de cola suelta es, por lo tanto, de, garantizando que está bien definido.
Si es del tamaño máximo posible, por supuesto, hemos terminado. De lo contrario, según el lema de Berge , debe existir un camino de aumento con respecto a en el gráfico subyacente . Sin embargo, esta ruta puede no existir en: Aunque cada borde par en es ajustado por la definición de , los bordes impares pueden estar sueltos y, por lo tanto, ausentes de . Un punto final de es en , el otro en ; wlog, supongamos que comienza en. Si cada borde en es estrecho, entonces sigue siendo un camino creciente en y hemos terminado. De lo contrario, deja ser el primer borde suelto en . Siluego hemos encontrado un camino de cola suelta y hemos terminado. De lo contrario, es accesible desde algún otro camino de aristas estrechas desde un vértice en . Dejar ser el subtrayecto de comenzando en y continuar hasta el final, y dejar ser el camino formado al viajar a lo largo de hasta un vértice en se alcanza, y luego continúa hasta el final de . Observa eso es un camino creciente en con al menos un borde suelto menos que . puede ser reemplazado con y este proceso de razonamiento se repitió (formalmente, usando inducción en el número de bordes sueltos) hasta que un camino de aumento en o un camino de cola suelta en es encontrado.
La prueba de que el ajuste del potencial Y hojas M sin cambios
Para mostrar que cada borde en permanece después de ajustar , basta con mostrar que para una ventaja arbitraria en , sus dos puntos finales, o ninguno de ellos, están en . Con este fin deja ser una ventaja en de a . Es fácil ver que si es en luego debe ser también, ya que cada borde en Es ajustado. Supongamos ahora, hacia la contradicción, que pero . en sí mismo no puede estar en porque es el punto final de un borde coincidente, por lo que debe haber alguna ruta dirigida de bordes estrechos desde un vértice en a . Este camino debe evitar, ya que eso es por suposición no en , por lo que el vértice inmediatamente anterior en este camino hay algún otro vértice . es un borde estrecho de a y está así en . Pero entonces contiene dos aristas que comparten el vértice , contradiciendo el hecho de que es una coincidencia. Por lo tanto, cada borde en tiene ambos puntos finales o ninguno en .
Prueba de que sigue siendo un potencial
Para mostrar que sigue siendo un potencial después de ser ajustado, es suficiente para mostrar que ninguna ventaja ha aumentado su potencial total más allá de su costo. Esto ya está establecido para los bordes en por el párrafo anterior, así que considere una ventaja arbitraria de a . Si se incrementa en , entonces tambien , en ese caso se reduce en , dejando el potencial total del borde sin cambios, o , en cuyo caso la definición de garantiza que . Por lo tanto sigue siendo un potencial.
Interpretación de matrices
Dado trabajadores y tareas, y un × matriz que contiene el costo de asignar a cada trabajador a una tarea, encuentre la asignación de minimización de costos.
Primero, el problema se escribe en forma de matriz como se indica a continuación
a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 d1 d2 d3 d4
donde a, b, cyd son los trabajadores que deben realizar las tareas 1, 2, 3 y 4. a1, a2, a3, a4 denotan las sanciones incurridas cuando el trabajador "a" realiza las tareas 1, 2, 3, 4 respectivamente . Lo mismo se aplica también a los demás símbolos. La matriz es cuadrada, por lo que cada trabajador puede realizar solo una tarea.
Paso 1
Luego realizamos operaciones de fila en la matriz. Para ello, el más bajo de todos una i (i perteneciente a 1-4) se toma y se resta de cada elemento en la fila. Esto conducirá a al menos un cero en esa fila (obtenemos múltiples ceros cuando hay dos elementos iguales que también resultan ser los más bajos en esa fila). Este procedimiento se repite para todas las filas . Ahora tenemos una matriz con al menos un cero por fila.
Como los hay trabajadores y tareas, agregar o restar un número fijo a cada elemento en una fila o columna solo cambiará el costo de la asignación en esa cantidad; pero la asignación de costo mínimo con las ponderaciones anteriores seguirá siendo una asignación de costo mínimo con las nuevas ponderaciones.
Ahora intentamos asignar tareas a los agentes de manera que cada agente esté haciendo una sola tarea y la penalización incurrida en cada caso sea cero. Como todos los pesos son no negativos, la asignación tendrá un costo mínimo. Esto se ilustra a continuación.
0 a2 ' a3 ' a4 ' b1 ' b2 ' b3 ' 0 c1 ' 0 c3 ' c4 ' d1 ' d2 ' 0 d4 '
Los ceros que se indican como 0 son las tareas asignadas.
Paso 2
A veces puede resultar que la matriz en esta etapa no se puede utilizar para asignar, como es el caso de la matriz a continuación.
0 a2 ' a3 ' a4 ' b1 ' b2 ' b3 ' 0 0 c2 ' c3 ' c4 ' d1 ' 0 d3 ' d4 '
En el caso anterior, no se puede realizar ninguna cesión. Tenga en cuenta que la tarea 1 la realizan de manera eficiente tanto el agente ay c. No se puede asignar la misma tarea a ambos. También tenga en cuenta que nadie hace la tarea 3 de manera eficiente. Para superar esto, repetimos el procedimiento anterior para todas las columnas (es decir, el elemento mínimo en cada columna se resta de todos los elementos en esa columna ) y luego verificamos si una asignación es posible.
En la mayoría de las situaciones, esto dará el resultado, pero si aún no es posible, debemos continuar.
Paso 3
Todos los ceros de la matriz deben cubrirse marcando el menor número posible de filas y / o columnas. El siguiente procedimiento es una forma de lograr esto:
Primero, asigne tantas tareas como sea posible.
- La fila 1 tiene un cero, por lo que está asignado. El 0 en la fila 3 está tachado porque está en la misma columna.
- La fila 2 tiene un cero, por lo que está asignado.
- El único cero de la fila 3 se ha tachado, por lo que no se asigna nada.
- La fila 4 tiene dos ceros sin cruzar. Se puede asignar uno y el otro cero se tacha.
Alternativamente, se puede asignar el 0 en la fila 3, haciendo que en su lugar se cruce el 0 en la fila 1.
0 ' a2 ' a3 ' a4 ' b1 ' b2 ' b3 ' 0 ' 0 c2 ' c3 ' c4 ' d1 ' 0 ' 0 d4 '
Ahora a la parte del dibujo.
- Marque todas las filas que no tengan asignaciones (fila 3).
- Marque todas las columnas que tengan ceros en las filas recién marcadas (columna 1).
- Marque todas las filas que tengan asignaciones en las columnas recién marcadas (fila 1).
- Repita los pasos descritos en las 2 viñetas anteriores hasta que no se marquen filas o columnas nuevas.
× 0 ' a2 ' a3 ' a4 ' × b1 ' b2 ' b3 ' 0 ' 0 c2 ' c3 ' c4 ' × d1 ' 0 ' 0 d4 '
Ahora dibuje líneas a través de todas las columnas marcadas y filas sin marcar .
× 0 ' a2 ' a3 ' a4 ' × b1 ' b2 ' b3 ' 0 ' 0 c2 ' c3 ' c4 ' × d1 ' 0 ' 0 d4 '
La descripción detallada antes mencionada es solo una forma de dibujar el número mínimo de líneas para cubrir todos los ceros. Otros métodos también funcionan.
Paso 4
De los elementos que quedan, encuentre el valor más bajo. Reste esto de cada elemento sin marcar y agréguelo a cada elemento cubierto por dos líneas.
Esto equivale a restar un número de todas las filas que no están cruzadas y sumar el mismo número a todas las columnas que están cruzadas. Estas operaciones no cambian las asignaciones óptimas.
Repita los pasos 3 a 4 hasta que sea posible realizar una asignación; esto es cuando el número mínimo de líneas utilizadas para cubrir todos los ceros es igual al máximo (número de personas, número de asignaciones), asumiendo que las variables ficticias (generalmente el costo máximo) se usan para completar cuando el número de personas es mayor que el número de asignaciones.
Según el teorema de Kőnig, [8] el número mínimo de líneas (cobertura mínima del vértice [9] ) será(el tamaño de la coincidencia máxima [10] ). Por lo tanto, cuando se requieren líneas, la asignación de costo mínimo se puede encontrar mirando solo ceros en la matriz.
Bibliografía
- RE Burkard, M. Dell'Amico, S. Martello: Problemas de asignación (reimpresión revisada). SIAM, Filadelfia (PA.) 2012. ISBN 978-1-61197-222-1
- M. Fischetti, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Italia, 1995.
- R. Ahuja , T. Magnanti , J. Orlin , "Network Flows", Prentice Hall, 1993.
- S. Martello, "Jeno Egerváry: desde los orígenes del algoritmo húngaro hasta la comunicación por satélite". Revista Centroeuropea de Investigación Operativa 18, 47–58, 2010
Referencias
- ^ Harold W. Kuhn, "El método húngaro para el problema de asignación", Naval Research Logistics Quarterly , 2 : 83–97, 1955. Publicación original de Kuhn.
- ^ Harold W. Kuhn, "Variantes del método húngaro para problemas de asignación", Naval Research Logistics Quarterly , 3 : 253-258, 1956.
- ^ J. Munkres, "Algoritmos para los problemas de asignación y transporte", Revista de la Sociedad de Matemáticas Industriales y Aplicadas , 5 (1): 32-38, marzo de 1957.
- ^ Edmonds, Jack; Karp, Richard M. (1 de abril de 1972). "Mejoras teóricas en eficiencia algorítmica para problemas de flujo de red". Revista de la ACM . 19 (2): 248–264. doi : 10.1145 / 321694.321699 .
- ^ Tomizawa, N. (1971). "Sobre algunas técnicas útiles para la solución de problemas de la red de transporte". Redes . 1 (2): 173-194. doi : 10.1002 / net.3230010206 . ISSN 1097-0037 .
- ^ Jonker, R .; Volgenant, A. (diciembre de 1987). "Un algoritmo de ruta de aumento más corto para problemas de asignación lineal densos y dispersos". Computación . 38 (4): 325–340. doi : 10.1007 / BF02278710 .
- ^ https://web.archive.org/web/20151016182619/http://www.lix.polytechnique.fr/~ollivier/JACOBI/presentationlEngl.htm
- ^ Teorema de Kőnig (teoría de grafos) Teorema de Konig
- ^ Cubierta de vértice cubierta de vértice mínima
- ^ Coincidencia (teoría de grafos) coincidencia
enlaces externos
- Bruff, Derek, El problema de la asignación y el método húngaro (formalismo matricial).
- Mordecai J. Golin, Emparejamiento bipartito y el método húngaro (formalismo bigraph), Notas del curso, Universidad de Ciencia y Tecnología de Hong Kong .
- Algoritmo de coincidencia máxima húngaro (ambos formalismos), en el sitio web de Brilliant.
- RA Pilgrim , algoritmo de asignación de Munkres. Modificado para matrices rectangulares , notas del curso, Murray State University .
- Mike Dawes , The Optimal Assignment Problem , Notas del curso, Universidad de Western Ontario .
- Sobre el método húngaro de Kuhn - Un tributo desde Hungría , András Frank , Grupo de Investigación Egervary, Pazmany P. setany 1 / C, H1117, Budapest, Hungría.
- Conferencia: Fundamentos de la investigación operativa - Problema de asignación - Algoritmo húngaro , Prof. G. Srinivasan, Departamento de Estudios de Gestión, IIT Madras.
- Extensión: análisis de sensibilidad de la asignación (con complejidad de tiempo O (n ^ 4)) , Liu, Shell.
- Resuelva cualquier problema de asignación en línea , proporciona una explicación paso a paso del algoritmo húngaro.
Implementaciones
Tenga en cuenta que no todos estos satisfacen las complejidad del tiempo, incluso si así lo afirman. Algunos pueden contener errores, implemente el más lentoalgoritmo, o tiene otras ineficiencias. En el peor de los casos, un ejemplo de código vinculado desde Wikipedia podría modificarse posteriormente para incluir código de explotación. La verificación y la evaluación comparativa son necesarias cuando se utilizan ejemplos de código de autores desconocidos.
- Reclamación de implementación de C O ( norte 3 ) {\ Displaystyle O (n ^ {3})} complejidad del tiempo
- Reclamación de implementación de Java O ( norte 3 ) {\ Displaystyle O (n ^ {3})} complejidad del tiempo
- Reclamación de implementación de Matlab O ( norte 3 ) {\ Displaystyle O (n ^ {3})} complejidad del tiempo (dominio público)
- Implementación de Python
- Implementación de Ruby con pruebas unitarias
- Reclamación de implementación de C # O ( norte 3 ) {\ Displaystyle O (n ^ {3})} complejidad del tiempo
- Implementación de D con pruebas unitarias (puerto de una versión de Java que reclama O ( norte 3 ) {\ Displaystyle O (n ^ {3})} )
- Implementación interactiva en línea
- Implementaciones en serie y en paralelo.
- Matlab y C
- Implementación de Perl
- Implementación de C ++
- Reclamación de implementación de C ++ O ( norte 3 ) {\ Displaystyle O (n ^ {3})} complejidad del tiempo (licencia de código abierto estilo BSD)
- Implementación de MATLAB
- Implementación de C
- Implementación de JavaScript con pruebas unitarias (puerto de una versión de Java que reclama O ( norte 3 ) {\ Displaystyle O (n ^ {3})} complejidad del tiempo)
- El paquete Clue R propone una implementación, solve_LSAP
- Implementación de Node.js en GitHub
- Implementación de Python en el paquete scipy