Modelo de asignacion en excel

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 recursosa 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 sepuede 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 unainformació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 deProgramació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.
Página | 1

Como la matriz no esta balanceada, es necesario incluir una máquinaficticia: (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 sepuede 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 esdebido 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

Página | 2

X31 + X32 + X33 + X34 = 1 X41 + X42 + X43 + X44 = 1

Y como cada máquina solo puede tener un operario asignado...
X11 X12 X13 X14 + + + + X21 X22 X23 X24 + X31 + X41 = 1 + X32 + X42 = 1 + X33 + X43 = 1 + X34 + X44 = 1

Xij = 1 o 0 para toda i,j.

Al resolver utilizando Software, por ejemplo el Solver del Excel, la respuesta que seobtiene 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,...