Software ii

Algoritmo Húngaro
De Wikipedia, la enciclopedia libre
Saltar a navegación, búsqueda

EL algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo O(n^3\,). La primera versión conocida del método Húngaro, fue inventado y publicado por Harold Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmoHúngaro, el algoritmo de la asignación de Munkres, o el algoritmo de Kuhn-Munkres.

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

El algoritmo construye una solución delproblema primal partiendo de una solución no admisible (que corresponde a una solución admisible del dual) haciéndola poco a poco más admisible.
Contenido
[ocultar]

* 1 Modelado
* 2 Algoritmo
o 2.1 Ejemplo
o 2.2 Ejemplo 2 Problema de minimización
* 3 Bibliografía
* 4 Enlaces externos
o 4.1 Implementaciones

[editar] Modelado

Elalgoritmo modela un problema de asignación como una matriz de costes n×m, donde cada elemento representa el coste de asignar el enésimo trabajador al emésimo trabajo. Por defecto, el algoritmo realiza la minimización de los elementos de la matriz; de ahí que en caso de ser un problema de minimización de costes, es suficiente con comenzar la eliminación de Gauss-Jordan para hacer ceros (al menos un ceropor línea y por columna). Sin embargo, en caso de un problema de maximización del beneficio, el coste de la matriz necesita ser modificado para que la minimización de sus elementos lleve a una maximización de los valores de coste originales. En un problema de costes infinito, el coste inicial de la matriz puede ser remodelado restando a cada elemento de cada línea el valor máximo del elemento deesa línea (o análogamente columna ). En un problema de coste infinito, todos los elementos son restados por el valor máximo de la matriz entera.
[editar] Algoritmo

(1) \, Dada la matriz de costes C \,, se construye C^\prime\, encontrando el valor mínimo de cada fila y restando ese valor a cada elemento de la fila.

\Rightarrow \; \mathit{C'}_{i,j}=\mathit{C}_{i,j}-\min\mathit{C}_{i,j}

( 2 ) \, Se encuentra el valor mínimo de cada columna y se resta a cada elemento de la columna.

\Rightarrow \; \mathit{C'}_{i,j}=\mathit{C'}_{i,j}-\min \mathit{C}_{i,j}

(3) \, A partir de \mathit{C'}\, se considera "grafo de las igualdades" a G=(N1,N2,A) \, tal que A \, está constituido por todas las copias ({i,j})\, tales que \mathit{C'}_{i,j}=0 \,. En otraspalabras, verificamos si para todas las filas existe una columna con costo 0 que no ha sido asignada a otra fila.

Determinar sobre G\, un matching M\, de cardinalidad máxima.

si |\mathit{M}| = |N_1| = |N_2| \Rightarrow \; STOP
Si todas las filas tienen a lo menos una intersección con costo cero que no ha sido ocupada por otra fila, estamos en el óptimo. Termina elalgoritmo.

(a) \, Considero C^\prime\, y se etiquetan las filas que no han sido acopladas o asignadas por el algoritmo de matching máximo.

(b) \, Se etiquetan en C^\prime\, las columnas que tienen los ceros en correspondencia o asignadas a las filas etiquetadas (con *).

(c) \, Etiquetar las filas que no han sido ya etiquetadas y acopladas o asignadas por elalgoritmo de matching máximo con las columnas ya etiquetadas (con *).

(d) \, Repetir los pasos (b) \, y (c) \, hasta que no halla más filas o columnas que etiquetar.

(e) \, Borrar las filas etiquetadas y las columnas NO etiquetadas. Para esto puede trazar una línea recta en las columnas y filas borradas.

(f) \, Sea \delta\, el elemento de C^\prime\, de valor mínimo...