Problema di assegnazione

I problemi di assegnazione (o problemi di assegnamento) sono quei problemi di ricerca operativa in cui bisogna assegnare diverse attività in maniera ottimale. Il problema di assegnazione è considerato un problema facile, anche se è un problema combinatorio e generalmente tali problemi sono NP-hard, cioèdifficili da risolvere. Tuttavia questo è uno dei particolari problemi che godono della proprietà di integralità e difatti altro non è che un particolare problema del flusso di costo minimo. Questo è un problema di fondamentale importanza in poiché spesso si ritrova nella struttura di problemi più complessi: ovvero spesso i problemi applicativi sono un problema di assegnamento con dei vincoli aggiuntivi. In questo modo - tramite le cosiddettetecniche di rilassamento - si possono utilizzare gli algoritmi studiati per questo problema per risolvere il problema originario.