Glossario · approach
Problema di Assegnazione
Matching uno-a-uno di un insieme di risorse (persone, veicoli, macchine) a un insieme di compiti al minimo costo o massimo beneficio.
Assignment ProblemAlgoritmo UnghereseHungarian Algorithm
Il problema di assegnazione (assignment problem) è il problema di accoppiare uno-a-uno n risorse (per esempio lavoratori, tecnici, veicoli) a n compiti minimizzando il costo totale o massimizzando il beneficio totale. La sua forma classica è stata risolta in tempo polinomiale da Kuhn nel 1955 con l'algoritmo ungherese — una delle soluzioni più antiche ed eleganti della ricerca operativa. Il problema generalizzato (GAP) consente più compiti per risorsa ed è NP-difficile. La spina matematica di molti problemi poggia sul problema di assegnazione: dispatch di tecnici sul campo, pianificazione turni, orari scolastici, allocazione di gare, robot-compito.
Örnek
Accoppiare 5 tecnici a 5 clienti, dove ogni tempo di viaggio è diverso. L'algoritmo ungherese trova il matching che minimizza il tempo totale in pochi secondi.