Metodo hungaro

Solo disponible en BuenasTareas
  • Páginas : 3 (670 palabras )
  • Descarga(s) : 0
  • Publicado : 29 de agosto de 2012
Leer documento completo
Vista previa del texto
Ejemplo de Asignación utilizando el Algoritmo Húngaro:
 

Existen cuatro operarios que se pueden asignar al trabajo con tres máquinas.  Un estudio de tiempos y movimientos ha arrojado lossiguientes tiempos por operario para las tres máquinas. Indicar que operario debe trabajar en que máquina y cuál de ellos no será asignado a ninguna.

 Si la matriz no está balanceada, balancearlaincluyendo las filas o columnas ficticias necesarias.

 De cada elemento de la matriz restar el mínimo valor de cada fila. De cada fila el menor valor es el 0 por lo tanto al restarle 0 queda la mismamatriz.

 De cada elemento de la matriz restar el mínimo valor de cada columna

 
 
 Realizar la Asignación de la siguiente manera:

Cada cero que se encuentre en la matriz significa que se puedeasignar esa fila a esa columna, pero una vez hecha esta asignación, ya no se tendrá en cuenta todos los demás ceros de esa misma fila y esa misma columna, debido a que sólo se  puede asignar una fila auna columna.

 Buscar de arriba a abajo la fila que tenga menos ceros, pero que mínimo tenga uno. (Pues si no tiene ninguno significa que esa fila no se puede asignar a ninguna columna) y asignaresa fila a la columna donde esta el cero (puede ser el primer cero que encuentre de izquierda a derecha). Tachar esa fila y esa columna para indicar que ya fueron asignados, para que los demás ceros deesa fila y esa columna no se tengan en cuenta. Repetir este paso hasta que haga todas las asignaciones que más pueda. Si todas las filas quedaron asignadas a todas las columnas el problema hafinalizado y esa es la solución óptima, sino será necesario utilizar el método de Flood (también se llama condición de Köning) que se explica a continuación.

 El tercer operario sólo tiene una posibleasignación. Realizarla. Queda asignado el Operario 3 a la máquina ficticia.

Ahora el Operario 4 sólo puede asignarse a la máquina 3.

El Operario 2 puede ser asignado a la máquina 1 o a la máquina...
tracking img