Grafos

Problema de Asignación

Grafos forma parte de un proyecto de investigación y desarrollo de aplicaciones informáticas de diseño modular orientadas hacia la docencia, investigación y labores profesionales de Ingeniería de Organización. Grafos contiene entre otras una librería bajo licencia LGPL, para solucionar problemas de Programación Lineal Entera Mixta (lpsolve.dll 5.x - Copyright © 1991, 2005 Free Software Foundation, Inc.).

En este apartado se comentará la aplicación de la teoría de grafos para la resolución y optimización de los Problemas de Asignación.

El problema de asignación (Assignment Problem), es un problema de complejidad NP-completo. Esto es así, porque el número de posibles soluciones crece O(n3).

El problema de asignación debe su nombre a la aplicación de asignar hombres a trabajos (trabajos a máquinas, o fardos en un contenedor en su variante del problema de la mochila). Esta asignación se hará con la condición de que cada hombre puede ser asignado sólo a un trabajo y que cada trabajo sólo tendrá asignada una persona. Los problemas de asignación presentan una estructura y un proceso de resolución muy similar a los de transporte, pero con dos diferencias: asocian igual número de nodos origen con igual número de nodos de demanda; el valor de oferta en cada nodo origen es de valor uno, como lo es la demanda en cada nodo destino.

La condición necesaria y suficiente para que este tipo de problemas tenga solución, es que se encuentre balanceado, es decir, que los recursos totales sean iguales a las demandas totales. Si hay más máquinas que trabajos se formula con desigualdades, y se resuelve con trabajos ficticios.

Su aplicación es visible y de gran importancia para la resolución de problemas reales en la Dirección de Operaciones y Logística. Por ejemplo: vehículos a rutas, trabajadores, oficinas al personal, máquinas y tareas, productos a fabricar, agentes comerciales a regiones, etc.

 

Problema de asignación (mínimo coste total)

Este problema es de especial interés ya que una de las preocupaciones de los gerentes de las empresas es la utilización más eficiente de sus recursos escasos. En este caso el problema tratará de asignar un conjunto de recursos limitados a un conjunto de actividades competitivas de la mejor manera posible (óptima).

El modelo de asignación es un caso especial del modelo de transporte, en el que los recursos se asignan a las actividades en términos de uno a uno, haciendo notar que la matriz correspondiente debe ser cuadrada. Así entonces cada recurso debe asignarse, de modo único a una actividad particular o asignación.

Este problema es fácil de enunciar. Se trata por ejemplo de un conjunto de n tareas que se deben asignar de la manera más eficiente posible a otro conjunto de m máquinas. Sea xij una variable binaria que indica si la tarea i se realizará con la máquina j. Mientras que cij representa el coste de dicha asignación, o lo que es lo mismo el de realizar la tarea i con la máquina j. Cada tarea debe asignarse a una y sólo a una máquina. Cada máquina realizará una y sólo una tarea. El problema es por tanto, decidir el modo en el que deben realizarse todas las asignaciones para minimizar los costos totales.

A continuación se muestra el modelo completo del problema:

El problema es lineal porque la función coste a optimizar así como las restricciones pueden ser expresadas como ecuaciones lineales. En el caso de Grafos, este problema se aborda a través del modelo anteriormente expuesto y su resolución mediante Programación Lineal Entera Mixta. El Algoritmo Húngaro de Kuhn (1955) es uno de los más utilizados para resolver este tipo de problemas.

Otra estrategia para solucionar este problema además de la PLEM en la literatura existen multitud de estrategias de resolución para este problema: técnicas de aproximación, heurísticas, relajaciones, post-optimizaciones, óptimos locales, enumeración completa, meta-heurísticas y técnicas evolutivas, y otras.

Fuente: A. Rodríguez

más información

- Kuhn, H. W. (1955). The hungarian method for the assignment problem. Naval Res. Logistic Quart. 3, 253-258.
 

Creative Commons License Alejandro Rodríguez Villalobos