El problema de asignación es un problema fundamental de optimización combinatoria . En su forma más general, el problema es el siguiente:
Si el número de agentes y tareas es igual, el problema se denomina asignación equilibrada . En caso contrario, se denomina asignación desequilibrada . [1] Si el costo total de la asignación de todas las tareas es igual a la suma de los costos de cada agente (o la suma de los costos de cada tarea, que es lo mismo en este caso), entonces el problema se llama asignación lineal . Comúnmente, cuando se habla del problema de asignación sin ninguna calificación adicional, se entiende el problema de asignación lineal balanceada .
Supongamos que una empresa de taxis tiene tres taxis (los agentes) disponibles y tres clientes (las tareas) que desean ser recogidos lo antes posible. La empresa se enorgullece de las rápidas recolecciones, por lo que, para cada taxi, el "costo" de recoger a un cliente en particular dependerá del tiempo que tarde el taxi en llegar al punto de recogida. Este es un problema de asignación balanceada . Su solución es cualquier combinación de taxis y clientes que resulte en el menor costo total.
Ahora, suponga que hay cuatro taxis disponibles, pero todavía solo tres clientes. Este es un problema de asignación desequilibrada . Una forma de resolverlo es inventar una cuarta tarea ficticia, quizás llamada "sentarse quieto sin hacer nada", con un costo de 0 para el taxi asignado. Esto reduce el problema a un problema de asignación equilibrada, que luego se puede resolver de la manera habitual y aún así dar la mejor solución al problema.
Se pueden hacer ajustes similares para permitir más tareas que agentes, tareas a las que se deben asignar múltiples agentes (por ejemplo, un grupo de más clientes de los que caben en un taxi) o maximizar las ganancias en lugar de minimizar los costos.
Por lo general, la función de peso se ve como una matriz cuadrada de valor real C , por lo que la función de costo se escribe como: