Glosario · approach
Problema de Asignación
Emparejamiento uno-a-uno de un conjunto de recursos (personas, vehículos, máquinas) a un conjunto de tareas al menor coste o máximo beneficio.
Assignment ProblemAlgoritmo HúngaroHungarian Algorithm
El problema de asignación (assignment problem) consiste en emparejar n recursos (por ejemplo trabajadores, técnicos, vehículos) a n tareas, minimizando el coste total o maximizando el beneficio total. Su forma clásica fue resuelta en tiempo polinómico por Kuhn en 1955 con el 'algoritmo húngaro' — una de las soluciones más antiguas y elegantes de la OR. El problema generalizado (GAP) permite varias tareas por recurso y es NP-duro. El esqueleto matemático de muchos problemas se apoya en el problema de asignación: asignación de técnicos en campo, planificación de turnos, horarios escolares, asignación de licitaciones, robot-tarea.
Örnek
Emparejar 5 técnicos con 5 clientes, donde cada tiempo de viaje es distinto. El algoritmo húngaro encuentra el emparejamiento con tiempo total mínimo en segundos.