- Problema de la asignación
-
Problema de la asignación
El problema del asignamiento es encontrar un matching de peso máximo en un grafo bipartido ponderado. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación operativa en matemática.
En su forma más general, el problema es como sigue:
- Hay un número de agentes y un número de tareas. Cualquier agente puede ser asignado para desarrollar cualquier tarea, contrayendo algún coste que puede variar dependiendo del agente y la tarea asignados. Es necesario para desarrollar todas las tareas asignar un solo agente a cada tarea para que el coste total del asignamiento sea minimizado.
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 linear. Normalmente, cuando hablamos de problema de asignación sin ninguna matización adicional, nos referimos al problema de asignamiento linear.
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. Es posible resolver cualquiera de estos problemas mediante el algoritmo simplex, cada especialización tiene algoritmos más eficientes tomando ventaja de su estructura especial.
Definición matemática formal
La definición formal del problema del asignamiento (o problema linear del asignamiento) es
- Dados dos conjuntos, A y T. de igual tamaño, juntos con una función peso C : A × T → R. Encuentra una biyección f : A → T como la función de coste:
-
- está minimizada.
Normalmente la función peso es vista como una matriz cuadrada de valores reales C, con lo que el coste de la función queda así:
El problema es "linear" porque la función coste a optimizar así como todas las restricciones contienen solo términos lineales.
Tutoriales
- Arquimedex.com Tutorial del Método de Asignación
- IO en Excel el Método de Asignación en Excel
Categorías: Teoría de grafos | Optimización | Investigación Operativa
Wikimedia foundation. 2010.
