Problemas De Asignación

PROBLEMAS DE ASIGNACIÓN

El problema de asignación tuvo su origen en la revolución industrial, ya que el surgimiento de las máquinas hizo que fuera necesario asignar una tarea a un trabajador. El Problema de 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.

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.

Los problemas de asignación presentan una estructura similar a los de transporte, 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.

La restricción importante para cada agente es que será designado a una y solo una tarea.

Algoritmos y generalizaciones

El algoritmo Húngaro es uno de los muchos algoritmos que han sido diseñados para resolver el problema del asignamiento lineal con un tiempo acotado por una expresión polinómica del número de agentes.

El problema del asignamiento es un caso especial del problema del transportador, que es un caso especial del problema del flujo de coste mínimo. El problema de asignación también puede ser resuelto por medio del algoritmo simplex (creado en 1947 por el matemático George Dantzig).El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables, es un método iterativo que permite ir mejorando la solución en cada paso. Cada especialización tiene algoritmos más eficientes tomando ventaja de su estructura espacial.

Si Xij=1 Si se asigna el trabajador i a la tarea j. Si Xij=0 No se asigna el trabajador i a la tarea j. Cij: Costo de asignar al trabajador i la tarea j.

Parámetro M: M es un número muy grande en los problemas de asignación se utiliza para representar que al trabajador i no se le puede asignar la tarea j.

Características:

• El Problema de Asignación debe estar equilibrado, es decir, que las ofertas y las demandas sean igual a 1. Un elemento importante para el problema de asignación es la matriz de costos, si el número de renglones o columnas no son iguales el problema esta desbalanceado y se puede obtener una solución incorrecta, para obtener una solución correcta la matriz debe ser cuadrada.

• Si el número de agentes y tareas son iguales y el coste total de la asignación para todas las tareas es igual a la suma de los costes de cada agente (o la suma de los costes de cada tarea, que es lo mismo en este caso), entonces el problema es llamado problema de asignamiento lineal. Normalmente, cuando hablamos de problema de asignación sin ninguna matización adicional, nos referimos al problema de asignamiento lineal.

Elementos

Tabla de transporte: Otra forma de plantear el problema de transporte ( recordemos que el problema de asignación es un caso especial del de transporte) es mediante una tabla llamada tabla de transporte, la cual tiene forma de matriz donde los renglones representan las fuentes y las columnas los destinos o trabajos.

• En las casillas que se encuentran en la esquina se colocan los coeficientes de costo.

• Una vez realizado esto, utilizamos alguno de los métodos (vogel, esquina noroeste, costos mínimos) para obtener una solución inicial

• Donde no exista un coeficiente de costo se le anota una M. 4

Matriz de costos: Es una matriz cuadrada de n*n, donde cada elemento representa el costo de asignar el enésimo trabajador al enésimo trabajo; renglones = trabajadores. Es la tabla en donde, se identifica, se evalúa y se cuantifica los beneficios económicos, costos y riesgos de los productos/servicios, después de definir la necesidad el alcance y el alineamiento estratégico de los productos/servicios, en donde se evalúa el beneficio total de la propiedad (características), una vez creada la matriz se demuestra el valor económico para la realización del producto o servicio correspondiente. 4

Matriz de Costos Reducida Es la matriz que se obtiene después de haber restado el elemento más pequeño a cada renglón (reducción de renglones) y restarle a esa nueva matriz el elemento más pequeño a cada columna (reducción de columnas).

Distribución óptima: Sean un conjunto de fragmentos F = {F1 , F2,..., Fn} y una red formada por el conjunto de sitios S = {S1, S2,..., Sm} en la cual un conjunto de aplicaciones Q = {q1, q2,..., qq} se ejecutan. El problema de la asignación implica encontrar la distribución óptima de F sobre S. (multi)

Método simplex: Método de solución de los problemas de programación lineal donde se obtiene una solución factible y óptima (en donde se pueden obtener resultados como solución múltiple, solución no acotada, o que el problema no tenga solución).

Solución Óptima: El conjunto de los vértices del recinto se denomina conjunto de soluciones factibles básicas y el vértice donde se presenta la solución óptima se llama solución máxima (o mínima según el caso).

Ejemplo

Existen cuatro

...