Metodo hungaro

Método Húngaro

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
Este algoritmo se usa para resolver problemas de minimización, ya que es más eficaz que el empleado para resolver el problema del transporte por el alto grado de degeneración que pueden presentar los problemas de asignación. Elproblema de asignación tiene que ver con la asignación de tareas a empleados, de territorios a vendedores, de contratos a postores o de trabajos a plantas. Al aplicar el método de transporte y el método de asignación la gerencia está buscando una ruta de distribución o una asignación que optimizará algún objetivo; éste puede se la minimización del costo total, la maximización de las utilidades ola minimización del tiempo total involucrado.
El problema de asignación es una variación del problema original de transporte, variación en la cual las variables de decisión X (i,j) solo pueden tomar valores binarios, es decir ser cero (0) o uno (1) en la solución óptima, lo que supone que la oferta y la demanda están perfectamente alineadas, de hecho ambas son iguales a uno (1).
Los Usos de esteproblema de asignación para resolver diversas situaciones, entre los que cabe mencionar se encuentran la asignación de personal a maquinas, herramientas o puestos de trabajos, horarios a maestros, candidatos a vacantes, huéspedes a habitaciones, comensales a mesas, vendedores a zonas territoriales etc.
Una característica particular del modelo de asignación es que para su resolución no se hacenecesario que el número de fuentes sea igual al número de destinos, lo cual es muy común en la vida real teniendo en cuenta su aplicación, pues generalmente la cantidad de aspirantes es exageradamente superior al número de vacantes (lógicamente haciendo referencia a la aplicación del modelo al contexto de oferta y demanda laboral).
Algoritmo Húngaro:
El algoritmo Húngaro esta destinado paraminimizar si tenemos que maximizar tendremos previamente que darle la vuelta a la matriz restándole el mayor elemento de toda la matriz a cada uno de los elementos de la misma de manera que el elemento que era más pequeño pasara a ser el más grande y a la inversa.
El Algoritmo Húngaro se debe a D. König y E. E Egervóry.
Cuando hay que pasar de maximizar a minimizar en lugar de operar con el mayor detoda la matriz podemos ir tomando el mayor de cada fila o columna e ir restándole todos los elementos de esa fila o columna con lo cual conseguiremos de camino obtener por lo menos un cero como mínimo en cada fila o columna. Si en alguna columna no hubiera ceros le quitamos el mayor a la columna.

Método Húngaro para la asignación:
La más conocida técnica de solución para el problema deasignación pura es el método húngaro, desarrollado a partir del teorema que demostró el matemático húngaro König en 1916. Este método utiliza la propiedad de reducción de matrices para reducir la matriz original de costo, hasta que los costos C i j asociados con la asignación óptima, sean cero y todos los otros costos sean no negativos.

En cada iteración del método húngaro, se reduce la matriz de talmanera que haya al menos un cero en cada renglón y columna, comprobando con el teorema de König si se ha alcanzado la solución óptima. Si el número mínimo de renglones y/o columnas necesarios para cubrir todos los ceros es n, entonces existe una asignación óptima (no necesariamente única).

Un problema de asignación es un problema de transporte balanceado, en el cual todas las ofertas y todas lasdemandas son iguales a uno. Se puede resolver eficientemente un problema de asignación m x m mediante el método Húngaro:

Paso 1.
Empiece por encontrar el elemento más pequeño en cada renglón de la matriz de costos. Construya una nueva matriz, al restar de cada costo, el costo mínimo de su renglón. Encuentre, para esta nueva matriz el costo mínimo en cada columna. Construya una nueva matriz...