problema de asignación
a coste mínimo
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 <tex>O(n^3)</tex>.
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 <tex>n</tex> tareas que se deben asignar de la manera más eficiente posible a otro conjunto de m máquinas. Sea <tex>x_{ij}</tex> una variable binaria que indica si la tarea <tex>i</tex> se realizará con la máquina <tex>j</tex>. Mientras que <tex>c_{ij}</tex> representa el coste de dicha asignación, o lo que es lo mismo el de realizar la tarea <tex>i</tex> con la máquina <tex>j</tex>. 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. La función objetivo queda expresada como:
<tex> \displaystyle{\min \sum_{i=1}^m\sum_{j=1}^n {c_{ij} x_{ij}}}</tex>
y está sujeto a las restricciones:
<tex> \displaystyle{\sum_{i=1}^m {x_{ij}} =1 \quad \forall {j=1 \ldots n}} </tex>
<tex> \displaystyle{\sum_{j=1}^n {x_{ij}} =1 \quad \forall {i=1 \ldots m}} </tex>
<tex> \displaystyle{x_{ij} \in (0,1)}</tex>
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 (PLEM o MILP en inglés). El Algoritmo Húngaro de Kuhn (1955) es uno de los más utilizados para resolver este tipo de problemas.
En la literatura existen multitud de estrategias de resolución para este problema además de la PLEM: técnicas de aproximación, heurísticas, relajaciones, post-optimizaciones, óptimos locales, enumeración completa, meta-heurísticas y técnicas evolutivas, y otras.
Más información en:
- Kuhn, H. W. (1955). The hungarian method for the assignment problem. Naval Res. Logistic Quart. 3, 253-258.