ingles


Universidad Técnica De Cotopaxi

Unidad Académica De Ciencias Agropecuarias Y Recursos Naturales
Carrera:
Ing. Agroindustrial
Ciclo:
Cuarto
Paralelo:
“A”
Asignatura:
Investigación Operativa
Alumna:
Ortega Vanessa
Docente:
Ing. Javier Tapia
Fecha: 9/05/2013
Método húngaro:
Fue inventado y publicado por Harold Kuhn en 1955, una matriz de costes n×m, donde cada elementorepresenta el coste de asignar el enésimo trabajador al ené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 cero por línea y por columna).
El método Húngaro es un método de optimización de problemas deasignación, conocido como tal gracias a que los primeros aportes al método clásico definitivo fueron de Dénes König y Jenő Egerváry dos matemáticos húngaros. El algoritmo tal como se detallará a continuación está diseñado para la resolución de problemas de minimización únicamente, será entonces cuestión de agregar un paso adicional para abordar ejercicios de maximización.
ALGORITMO HÚNGARO, PASO1
Antes que nada cabe recordar que el método húngaro trabaja en una matriz de costos n*m (en este caso conocida como matriz m*m, dado que el número de filas es igual al número de columnas n = m), una vez construida esta se debe encontrar el elemento más pequeño en cada fila de la matriz.
ALGORTIMO HÚNGARO, PASO 2
Una vez se cumple el procedimiento anterior se debe construir una nueva matrizn*m, en la cual se consignarán los valores resultantes de la diferencia entre cada costo y el valor mínimo de la fila a la cual cada costo corresponde (valor mínimo hallado en el primer paso).
ALGORTIMO HÚNGARO, PASO 3
Este paso consiste en realizar el mismo procedimiento de los dos pasos anteriores referidos ahora a las columnas, es decir, se halla el valor mínimo de cada columna, con ladiferencia que este se halla de la matriz resultante en el segundo paso, luego se construirá una nueva matriz en la cual se consignarán los valores resultantes de la diferencia entre cada costo y el valor mínimo de la columna a la cual cada costo corresponde, matriz llamada "Matriz de Costos Reducidos".
ALGORITMO HÚNGARO, PASO 4
A continuación se deben de trazar líneas horizontales o verticales oambas (únicamente de esos tipos) con el objetivo de cubrir todos los ceros de la matriz de costos reducidos con el menor número de líneas posibles, si el número de líneas es igual al número de filas o columnas se ha logrado obtener la solución óptima (la mejor asignación según el contexto de optimización), si el número de líneas es inferior al número de filas o columnas se debe de proceder con elpaso 5.
ALGORITMO HÚNGARO, PASO 5
Este paso consiste en encontrar el menor elemento de aquellos valores que no se encuentran cubiertos por las líneas del paso 4, ahora se restará del restante de elementos que no se encuentran cubiertos por las líneas; a continuación este mismo valor se sumará a los valores que se encuentren en las intersecciones de las líneas horizontales y verticales, una vezfinalizado este paso se debe volver al paso 4.
Aplicación del método húngaro:
El método Húngaro es aplicado con más frecuencia en las áreas de producción de las empresas, para ver cuál de las maquinas en operación puede presentar problemas o algún fallo que afecta a la producción.
También en las la gerencias que buscan una ruta de distribución o una asignación que optimizará algún objetivo;éste puede ser la minimización del costo total, la maximización de las utilidades o la minimización del tiempo total involucrado.
Esta técnica es usada por un gran número de problemas NP-hard, tales como:
Problema de la mochila.
Programación lineal.
Programación no lineal.
Problema del viajante.
Problema de la asignación cuadrática.
Problema de máxima satisfacibilidad (Versión Inglesa)....