legislacion informatica
Páginas: 3 (649 palabras)
Publicado: 21 de enero de 2014
Algoritmo Húngaro
EL algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo . La primera versión conocida del método Húngaro, fue inventado y publicadopor Harold Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo Húngaro, el algoritmo de la asignación de Munkres, o el algoritmo deKuhn-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 esque es fuertemente polinómico (ver Complejidad computacional para más detalles).
El algoritmo construye una solución del problema primal partiendo de una solución no admisible (que corresponde a unasolución admisible del dual) haciéndola poco a poco más admisible.
Modelado
El algoritmo modela un problema de asignación como una matriz de costes n×m, donde cada elemento representa el coste deasignar 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, essuficiente con comenzar la eliminación de Gauss-Jordan para hacer ceros (al menos un cero por línea y por columna). Sin embargo, en caso de un problema de maximización del beneficio, el coste de lamatriz 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 puedeser remodelado restando a cada elemento de cada línea el valor máximo del elemento de esa línea (o análogamente columna ). En un problema de coste infinito, todos los elementos son restados por elvalor máximo de la matriz entera.
Algoritmo
Dada la matriz de costes , se construye encontrando el valor mínimo de cada fila y restando ese valor a cada elemento de la fila.
Se encuentra el...
EL algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo . La primera versión conocida del método Húngaro, fue inventado y publicadopor Harold Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo Húngaro, el algoritmo de la asignación de Munkres, o el algoritmo deKuhn-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 esque es fuertemente polinómico (ver Complejidad computacional para más detalles).
El algoritmo construye una solución del problema primal partiendo de una solución no admisible (que corresponde a unasolución admisible del dual) haciéndola poco a poco más admisible.
Modelado
El algoritmo modela un problema de asignación como una matriz de costes n×m, donde cada elemento representa el coste deasignar 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, essuficiente con comenzar la eliminación de Gauss-Jordan para hacer ceros (al menos un cero por línea y por columna). Sin embargo, en caso de un problema de maximización del beneficio, el coste de lamatriz 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 puedeser remodelado restando a cada elemento de cada línea el valor máximo del elemento de esa línea (o análogamente columna ). En un problema de coste infinito, todos los elementos son restados por elvalor máximo de la matriz entera.
Algoritmo
Dada la matriz de costes , se construye encontrando el valor mínimo de cada fila y restando ese valor a cada elemento de la fila.
Se encuentra el...
Leer documento completo
Regístrate para leer el documento completo.