Asignacion De Recursos En La IO

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

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.

Supongamos el siguiente 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.

Máquina 1 Máquina 2 Máquina 3

Operario 1 10 7 9

Operario 2 7 5 8

Operario 3 9 8 10

Operario 4 8 9 7

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)

Máquina 1 Máquina 2 Máquina 3 Máquina Ficticia

Operario 1 10 7 9 0

Operario 2 7 5 8 0

Operario 3 9 8 10 0

Operario 4 8 9 7 0

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:

Máquina 1 Máquina 2 Máquina 3 Máquina Fic.

Operario 1 0 0 0 1

Operario 2 0 1 0 0

Operario 3 1 0 0 0

Operario 4 0 0 1 0

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.

Teorema fundamental de la asignación:

Si a todos los elementos de una fila o de una columna de una matriz de rendimientos se le suma o se le resta una cantidad constante la asignación optima no varia.

Algoritmo Húngaro:

El algoritmo Húngaro esta destinado para minimizar 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 de toda 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

...