Ciencia

Universidad de Oriente
Núcleo Bolívar
Unidad Experimental Puerto Ordaz
Cátedra: Investigación de Operaciones II
Sección: 01


CIUDAD GUAYANA, AGOSTO DE 2011
Definició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. Los problemas de asignación presentan una estructura similar a los detransporte, pero con dos diferencias: asocian igual número  de orígenes con igual número de demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino.

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 lepuede 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 elProblema 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í, 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,

El Problema de la Asignación se basa enuna 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.

Las etapas decálculo son las siguientes:

1. Determinar el elemento de menor valor de cada columna y restarlo de cada elemento del cuadro original

Al restar los estos valores de su columna correspondiente en la tabla original, se obtiene la nueva tabla:

2. Se traza el menor número de líneas sobre renglones o columnas o sobre ambos, de tal manera que se cubran todos los ceros de la matriz.

Si elnúmero de líneas trazadas es menor que el número de renglones, deberá continuarse con el cálculo. Si el número de líneas es igual al de renglones o columnas, entonces se ha alcanzado la solución óptima y será posible obtener con los ceros de la matriz una asignación de costo mínimo.

En este caso se puede observar que son suficientes cuatro lineas para tachar todos los ceros que existen en lamatriz lo cual indica que debe continuarse con el cálculo

3. Debe determinarse el menor elemento de cada renglón y restarlo e cada elemento de su renglón, con lo que se forma la nueva matriz

4. Se encierran entre paréntesis aquellos ceros que sean únicos en su columna o en su renglón, o en ambos, tachando los otros ceros que aparezcan en el mismo renglón o columna; si esto no es posible,seleccionamos el renglón o columna que tenga el menor número de ceros y encerramos entre paréntesis a cualquiera de ellos tachando los demás de la misma columna o del mismo renglón del cero seleccionado.

Revisando primero por columna los ceros que son únicos y luego por renglón.

Los ceros encerrados en paréntesis indican las asignaciones que podemos hacer; por esta razón, los vamos a llamar"Ceros de Asignación". Como se ve en el cuadro anterior solamente hay cuatro si contamos con cinco, el problema estaría resuelto; es necesario por la tanto continuar con el siguiente paso.

5. Como en el paso 2 debe trazase el menor número de líneas sobre renglones o columnas o sobre ambos, de tal manera que se cubran todos los ceros. Para esto existe un método que determina el mínimo de líneas...