Ejemplo de Asignación

 
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 los siguientes 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, balancearla incluyendo 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 misma matriz.


 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 puede asignar 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 a una 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 asignar esa 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 de esa 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 ha finalizado 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 posible asignació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 2, escojamos indiferentemente la
máquina 2.


El operario 1 no pudo ser asignado. Por lo tanto aún no se ha encontrado la asignación óptima. Hay que  aplicar el método del Flood.

Como se puede intuir, en una matriz como la anterior se puede realizar la asignación de diferentes maneras. Cada forma diferente de asignar significa un desarrollo diferente del ejercicio, pero al final, cualquier forma lleva siempre al óptimo.

 Método de Flood.

 Señalar todas las filas que no tienen una asignación. (Cuando digo señalar puede ser una pequeña X a la izquierda de la fila o arriba de la columna)


 Señalar todas las columnas que tengan un cero en la columna señalada.


 Señalar todas las filas que tienen una asignación en las columnas indicadas.


 Repetir estos pasos hasta que no pueda señalarse más columnas o filas.
(No  hay más filas que no tengan asignación)
 Dibujar una línea por cada fila NO señalada y por cada columna SI señalada.


 Encontrar el mínimo valor de los elementos no cubiertos y restarlo a todos los elementos no cubiertos, y sumar este valor a cada elemento que se encuentre en la intersección de una línea horizontal  con una línea  vertical.


Realizar Asignación:

Asignar primero las filas que sólo tienen una alternativa: Operario 4 con la Máquina 3. La fila 2 y la 3 tienen dos opciones y la fila 1 tiene 3 opciones. Asignemos el Operario 3 con la Máquina 1, la fila 2 con la máquina 2  y la fila 1 con la máquina ficticia.  Todas las filas han sido asignadas, así que se ha encontrado el óptimo.

Nota: Si se explora un poco todas las posibles asignaciones, se dará uno cuenta que existen más soluciones que llevan una asignación total, eso significa que hay varias soluciones óptimas, además, dependiendo de la forma en que se haga la asignación, puede que no queden todas las filas asignadas, eso significaría una iteración más...

Solución:


 

Contenido :

Social