Il problema di assegnamento abbina n agenti a n compiti, uno a uno. La variabile è:
Il modello di costo minimo è:
Il primo vincolo impone che ogni agente riceva esattamente un compito; il secondo che ogni compito sia assegnato a un solo agente. La funzione obiettivo somma i costi delle coppie scelte. Se il problema è di massimizzazione, per esempio massimizzare profitto o affinità, lo si può trasformare in minimizzazione cambiando segno ai coefficienti o sottraendoli da una costante opportuna.
È un caso speciale del problema dei trasporti con offerte e domande pari a 1. La matrice dei vincoli è totalmente unimodulare: la rilassazione lineare ha vertici interi. Questo significa che, anche sostituendo x_{ij}\in\{0,1\} con:
le soluzioni estreme del problema lineare sono già intere. È una proprietà strutturale molto utile, perché evita la complessità tipica di molti problemi interi generali.
Il metodo ungherese risolve il problema usando riduzioni di righe e colonne che non cambiano l’assegnamento ottimo, perché ogni soluzione usa esattamente una cella per riga e una per colonna.
Se il numero di agenti e compiti non coincide, si aggiungono righe o colonne fittizie con costi opportuni per ottenere una matrice quadrata. Se alcune assegnazioni sono vietate, si possono usare costi molto grandi o vincoli espliciti, facendo attenzione a non introdurre soluzioni numericamente instabili.
Le applicazioni includono assegnazione di operatori a turni, macchine a lavorazioni, veicoli a missioni, studenti a progetti, sensori a tracce, risorse cloud a job e accoppiamenti in sistemi logistici. Il modello base richiede assegnamenti uno a uno; se un agente può svolgere più compiti o un compito richiede più agenti, servono generalizzazioni come trasporto, flusso su rete o programmazione intera.
Un errore comune è inserire nel costo c_{ij} solo una distanza o un tempo medio senza considerare vincoli reali di compatibilità, capacità, priorità o sequenza. Il problema di assegnamento è potente proprio quando la matrice dei costi rappresenta correttamente il compromesso operativo da ottimizzare.
Vedi anche: Programmazione Lineare, Programmazione Intera.