Asignación

 

 

El Problema de la Asignación es un problema clásico de la Investigación de Operaciones y es un caso particular del Problema del Transporte.


Este problema se trata de asignar una serie de Recursos a una serie de tareas.  Tiene una limitante y es que a cada tarea se le puede asignar sólo un recurso, pueden sobrar recursos o podrían sobrar tareas pero no se le puede asignar dos recursos a una misma tarea, o tres... por ejemplo si se tienen tres operarios con diferentes tiempos de operación en cuatro máquinas el modelo nos diría como asignar los tres operarios a tres máquinas (nos sobraría una) de manera que se minimice el tiempo total, pero no nos diría como asignar dos operarios a dos máquinas y el otro operario a las otras dos máquinas... si el Problema en la Vida Real se puede simplificar de esa manera, o de hecho es requerido que sea así (un recurso para una tarea), pues como se dice aquí: "santo y bueno", pero sino será necesario modelarlo como un Programa Lineal y resolverlo con el Simplex.


Ejemplos de Asignaciones: Operarios a Tareas, Máquinas a Operarios, Nadadores a Estilos, Novias a días de la semana, etc, etc, etc.


El Problema de la Asignación se basa en una información comparativa para tomar la decisión de que asignar a que, por ejemplo una matriz de costos, una matriz de tiempos, de ingresos, etc. Cuando la matriz no está balanceada, es decir, cuando no es cuadrada, cuando sobran filas o columnas, se debe balancear para que tenga solución mediante la inclusión de filas o columnas ficticias, con valores de cero en dicha matriz.

 



Formulación de Programación Lineal:


Ejemplo:


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.

 

 
Como la matriz no esta balanceada, es necesario incluir una máquina ficticia:
(esto es fundamental para asegurar que haya una respuesta. Si la matriz no está balanceada, el problema no será factible de resolver)



 

 

 

Xij = Se debe asignar el operario i a la máquina j? Sí o no?
En matemáticas existen dos números cuyas propiedades hacen que puedan representar estas respuestas son el 1 y el 0, debido a que todo número multiplicado por 1 da el mismo número entonces el 1 se puede reemplazar por la respuesta Sí y como todo número multiplicado por cero da cero entonces se puede reemplazar por la respuesta No.
Así por ejemplo:


10X11 + 7X12 + 9X13 + 0X14


representa el tiempo sumado  que emplearía el operario1 en operar las máquinas, pero solo una variable de las tres anteriores puede tomar el valor de Sí, o sea de 1 las demás tendrán que tomar el valor de 0, y eso es debido a que el operario 1 sólo puede ser asignado a una máquina, lo que significaría que el tiempo que utilice el operario 1 puede ser ya sea de "10" de "7" o de "9". Con base en esto podemos formular la función objetivo:


Min Z =
            10X11 + 7X12  +  9X13
            7X21 + 5X22  +  8X23
            9X31 + 8X32 + 10X33
            8X41 + 9X42 +    7X43

 

Restricciones:

 

Como cada operario sólo puede estar asignado a una máquina....

 

X11 + X12 + X13 + X14 = 1
X21 + X22 + X23 + X24 = 1
X31 + X32 + X33 + X34 = 1
X41 + X42 + X43 + X44 = 1

 

Y como cada máquina solo puede tener un operario asignado...


X11 + X21  + X31 + X41 = 1
X12 + X22  + X32 + X42 = 1
X13 + X23  + X33 + X43 = 1
X14 + X24  + X34 + X44 = 1


Xij = 1 o 0 para toda i,j.


Al resolver utilizando Software, por ejemplo el Solver del Excel, la respuesta que se obtiene es la siguiente:

 

Esto significa que el Operario 1 queda asignado a la Máquina Ficticia (es decir, es el que sobra), el operario 2 se asigna a la máquina 2, el operario 3 se asigna a la máquina 1 y el operario 4 se asigna a la máquina 3.

Algoritmo Húngaro:

 


El Algoritmo Húngaro sirve para reemplazar los métodos tradicionales de la Programación Binaria, que implican muchos cálculos, aprovechando la forma especial que tienen los problemas de Asignación.


Los siguientes pasos que se presentan a continuación son para minimizar, pero con algunas modificaciones se puede emplear también para maximizar.


 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 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.


 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.


 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 la Asignación... si no es óptima hacer flood, iterar hasta que se pueda hacer la asignación.

 


 

Social