Data una matrice di costo n×n, il problema di accoppiare uno-a-uno n lavoratori/risorse a n compiti per minimizzare costo o tempo totale; uno dei problemi combinatori più fondamentali della ricerca operativa (in letteratura: Assignment Problem; risolto dal metodo ungherese di Kuhn-Munkres in tempo polinomiale O(n³)).
In breve
Ti suona familiare?
- Siamo uno studio di ingegneria con 5-30 ingegneri + 10-50 incarichi di progetto; la decisione settimanale su chi prende cosa è intuitiva, confermata dal pianificatore + foglio di calcolo.
- Siamo uno studio legale che smista 20-80 nuovi fascicoli a settimana; il costo per avvocato e tipo di fascicolo (specializzazione + tariffa oraria + relazione esistente con il cliente) è diverso, e la distribuzione segue anzianità o 'chi è disponibile'.
- Siamo una società di facility-management con 10-50 veicoli + tecnici urbani; assegniamo 10-50 chiamate giornaliere ai tecnici, con trasferte + competenze + durate diverse.
- Siamo pianificatori in un ospedale con 5-30 chirurghi + 10-50 casi; durata e punteggio qualitativo per chirurgo e tipo di caso sono diversi, e l'assegnazione segue l'intuito 'il chirurgo più esperto al caso più complesso'.
- Siamo un istituto educativo; 20-80 docenti + 20-80 classi/corsi da abbinare, con preferenze + specializzazione + livello diversi, e l'assegnazione è semi-manuale.
- La nostra matrice di assegnazione è 'rettangolare' (7 tecnici + 12 compiti, o 15 tecnici + 9 compiti) — non essendo quadrata non è chiaro come risolvere col metodo ungherese e se applicare estensione dummy.
- Sappiamo che l'attuale assegnazione non è ottima ma non riusciamo a misurare la distanza dall'ottimo — non abbiamo numero di riferimento.
- Siamo legati a un software WFM mono-fornitore; sostiene di avere un 'modulo di ottimizzazione di assegnazione', ma quale algoritmo (ungherese, LAP, euristica) usi non è trasparente.
Perché è importante
Come si risolve
Profondità tecnica
Come si risolve
Profondità tecnicaIn una frase: Data una matrice di costo C[i,j] per coppie persona-compito (tariffa oraria × durata attesa + penalità di disallineamento competenze + trasferta), il metodo ungherese trova il matching ottimo uno-a-uno in O(n³) — ogni persona a un solo compito, ogni compito a una sola persona, costo totale minimo.
Nella letteratura di Ricerca Operativa (disciplina che usa matematica e informatica per risolvere decisioni di business) e ottimizzazione combinatoria il problema si studia come Assignment Problem (problema di assegnazione). La soluzione classica è il metodo ungherese (1955); nel 1957 fu trasformato in una procedura polinomiale O(n³) pienamente formale, perciò in letteratura moderna si parla anche di algoritmo di Kuhn-Munkres. Il nome viene dai teoremi sul matching bipartito di cui posero le basi matematici ungheresi. Tre fasi:
1. Modellazione — matrice di costo n×n + assegnazione uno-a-uno. Input: (a) n risorse (per es. personale, veicoli, macchine) — ciascuno con profilo competenze, costo orario, posizione/disponibilità, (b) n compiti — ciascuno con tipo, durata attesa, posizione, scadenza, requisito qualitativo, (c) matrice n×n C[i,j] — costo (o tempo, o beneficio negativo) di assegnare la i-esima risorsa al j-esimo compito; componenti: penalità per disallineamento competenze + tariffa oraria × durata attesa + costo trasferta + penalità preferenze/fit. Variabili di decisione: x[i,j] ∈ {0,1}. Vincoli: ogni risorsa a esattamente un compito (∑_j x[i,j] = 1, ∀i), ogni compito a esattamente una risorsa (∑i x[i,j] = 1, ∀j). Obiettivo: minimizzare ∑{i,j} C[i,j] × x[i,j]. Il modello deve essere quadrato e bilanciato; per il caso rettangolare (m≠n) si usa l’estensione con dummy: con m=7 persone + n=12 compiti, aggiungi 5 persone dummy; costo dummy sul compito è 0 (se è ammissibile lasciare il compito non assegnato) o M molto grande (se ogni compito va assegnato). Per m>n, aggiungi compiti dummy. Per la variante di massimizzazione (massimizzare il beneficio totale), sostituisci costo con -beneficio; lo stesso algoritmo funziona.
2. Soluzione — metodo ungherese e alternative moderne. Il nucleo del metodo ungherese è riduzione di righe/colonne + copertura sul grafo degli zeri + augmentazione nelle celle non coperte: (a) sottrai il minimo di ogni riga, (b) sottrai il minimo di ogni colonna, (c) trova un matching massimo sugli zeri, (d) se non perfetto, copri le righe/colonne non assegnate con il numero minimo di linee, sottrai il minimo delle celle non coperte dalle righe non coperte e aggiungilo alle intersezioni di copertura, aggiorna gli zeri, (e) ripeti fino a matching perfetto. Complessità O(n³), tempo polinomiale, ottimo garantito. Alternative moderne: LAP risolto da algoritmi del cammino aumentante più corto, 5-20× più veloce in pratica; auction algorithm — parallelizzabile. LP-base: la rilassazione LP è totalmente unimodulare e dà direttamente ottimo intero. Bottleneck Assignment: minimizza il massimo costo assegnato (equità max-min). Quadratic Assignment (QAP): costi accoppiati — NP-difficile, problema distinto.
3. Integrazione sul campo. Output a tre livelli: (a) lista di assegnazione — coppie risorsa-compito, inizio-fine atteso, contributo al costo, (b) confronto di alternative — accanto all’ottimo, 2-3 alternative quasi-ottime (priorità trasferta, competenza, continuità con cliente), (c) retroazione sulla matrice — dopo l’esecuzione si misura la durata/qualità reale e si aggiornano le stime. Integrazione: HR, CRM/progetto, GIS. Comitato mensile: analisi reale-vs-ottimo, calibrazione, equilibrio del carico, continuità cliente.
Alternative
Manuale + foglio di calcolo
GratuitoZero licenza
Per chi: Pool piccolo (risorse <10, compiti <10)
- + Costo software zero
- + Conoscenza del pianificatore in primo piano
- + Per matrici 5×5 o 7×7 si trova quasi-ottimo manualmente
- − Oltre 10×10 ottimo manuale impossibile — intuito devia 15-30%
- − Drift della stima della matrice non misurato
- − Caso rettangolare gestito a intuito; nessuna estensione dummy
- − Motivazione non a registro — reclami di trasparenza senza risposta
Modulo ungherese/LAP open source + integrazione custom
Open SourceLicenza gratuita; sviluppo 8-16 settimane o 300K-1M TRY consulenza
Per chi: Azienda di servizi media con team tecnico, integrata con HR/CRM
- + Metodo ungherese + LAP maturi nelle librerie open source
- + Tempo polinomiale O(n³) — 100×100 in secondi
- + Ottimo garantito; nessun drift euristico
- + Varianti rettangolare + max + bottleneck disponibili
- + Codice aperto — trasparenza auditabile
- − Richiede competenza OR + team software interno
- − Stima della matrice richiede modello dati a parte
- − Assegnazione dinamica multi-periodo necessita modellazione aggiuntiva
- − Manutenzione resta in casa
Software di workforce management (WFM) con modulo di assegnazione
Aziendale200K-1.2M TRY licenza + 80K-400K TRY/anno manutenzione
Per chi: Azienda medio-grande (risorse 30-200), CRM/HR/operazioni integrati
- + Modulo integrato (libreria ungherese o LAP all'interno)
- + HR + CRM + planning integrati
- + Assegnazione multi-periodo supportata
- + Supporto operativo + formazione
- − Variante d'algoritmo non sempre trasparente
- − Licenza alta + rollout lungo (9-15 mesi)
- − Modello di stima 'scatola nera' — da negoziare
- − Rischio lock-in
Piattaforma enterprise OR + modello di assegnazione custom
AziendaleAnnuali 600K-3M TRY (piattaforme OR grandi)
Per chi: Azienda grande, multi-area + multi-periodo + stocastica
- + Ungherese + LAP + auction + varianti stocastiche integrate
- + GAP come modulo aggiuntivo
- + Multi-obiettivo (costo + equità + continuità)
- + Metodologia trasparente — i risultati sono verificabili da uno specialista indipendente
- − Licenza alta + rollout lungo (12-24 mesi)
- − Scope ampio — eccessivo per piccola-media scala
- − Team OR + integrazione necessari
- − Personalizzazione locale prolunga il progetto
Raccomandazione
Chiedi nell'incontro
- Cosa gira sotto al modulo di assegnazione — un algoritmo di matching sistematico (metodo ungherese / cammino aumentante più corto / tipo asta), un solver di programmazione lineare o una regola euristica? La variante scelta e se garantisce l'ottimo sono documentate nella specifica?
- Come gestisce il caso rettangolare (m≠n) — aggiunta automatica di righe/colonne dummy o manuale? Come sceglie il costo dummy (0 o M grande)?
- Supporta la variante di massimizzazione — conversione costo/beneficio automatica?
- Supporta bottleneck assignment (equità max-min)? In quali scenari consigliato?
- Come si stima la matrice C[i,j] — input manuale, derivata dallo storico, o ibrido? Esiste un report di deviazione?
- Supporta multi-obiettivo (costo + equità + continuità) o solo singolo obiettivo? Somma pesata + frontiera di Pareto?
- Dopo un pilot con dati reali (6-10 settimane), che report di risparmio è prodotto rispetto all'assegnazione manuale — costo totale, tempo, equilibrio del carico?
- Se finisce il contratto, in quale formato standard possiamo esportare storico matrice, archivio assegnazioni, registro continuità e parametri dell'algoritmo?
Dettagli tecnici
Nota editoriale
Nel linguaggio comune il problema si chiama “distribuzione del lavoro”, “assegnazione del personale” o “allocazione delle risorse”. In letteratura accademica è l’Assignment Problem; la soluzione classica è il metodo ungherese, anche noto come algoritmo di Kuhn-Munkres, un algoritmo combinatorio polinomiale O(n³). Il nome deriva dai teoremi sul matching bipartito sviluppati ai primi del Novecento dai matematici ungheresi Dénes König e Jenő Egerváry; Harold Kuhn costruì l’algoritmo su quella base nel 1955, e James Munkres lo trasformò in procedura polinomiale formale nel 1957. Non confondere con #072 (Stable Matching): lo stable matching lavora con liste di preferenza su due lati — il candidato A preferisce l’istituzione X e l’istituzione X preferisce A, e il matching evita coppie bloccanti. Nell’assegnazione c’è solo una matrice di costo unilaterale — la persona ha un costo sul compito, non c’è ordine di preferenza; niente pagamento ma costo, e l’obiettivo è la somma dei costi (ottimo sociale). Non confondere con #094 (Transportation Problem): nel trasporto m fonti e n destinazioni possono differire (m≠n) e ogni fonte può inviare quantità divisibile a più destinazioni. Nell’assegnazione ogni risorsa va a esattamente una destinazione e ogni destinazione riceve da esattamente una fonte — assegnazione quadrata 0/1.
Punto più trascurato sul campo: estensione con dummy per il caso rettangolare (m≠n). Il metodo ungherese originale richiede matrice quadrata n×n; in pratica arriva 7 persone + 12 compiti, o 15 persone + 9 compiti. La soluzione è semplice ma il professionista non la conosce: estendi a quadrata con righe/colonne dummy. (a) m<n: aggiungi (n-m) persone dummy con costo M (molto grande) — se ‘ogni compito deve essere assegnato’; altrimenti costo 0 e i compiti non assegnati ‘vanno’ al dummy (in realtà restano non assegnati). (b) m>n: aggiungi compiti dummy. Il professionista non conosce la procedura — perdita di ottimo 10-25%. Secondo punto trascurato: conversione massimizzazione ↔ minimizzazione. Alcuni problemi sono in ‘massimizzare beneficio totale’; il metodo ungherese è di minimizzazione, ma sostituendo costo con -beneficio o applicando (max_beneficio - beneficio) si trasforma in minimizzazione; stesso algoritmo. Terzo punto trascurato: drift di stima della matrice. Perché l’algoritmo dia l’ottimo, C[i,j] deve essere stimato bene; stime cattive danno assegnazioni cattive. Come si stima la matrice (storico, formula di competenza, tariffa di trasferta) è un problema di modellazione che precede l’algoritmo — i professionisti lo fanno per intuito, e la qualità di output è limitata dalla qualità della stima. Quarto punto trascurato: confusione con QAP (assegnazione quadratica). Nell’assegnazione lineare le celle sono indipendenti; in QAP due assegnazioni interagiscono — NP-difficile, classe a parte (Koopmans-Beckmann 1957). Confondere genera la sorpresa ‘perché ci mette così tanto’.
Percorso passo-passo per PMI
Fase 1 — Misura la matrice di costo e rendila esplicita. Almeno 6-12 mesi di storico: per ogni coppia persona-compito durata reale, punteggio qualità, distanza, fit cliente/progetto. Formula scritta: C[i,j] = α × durata_stimata[i,j] × tariffa_oraria[i] + β × distanza[i,j] + γ × disallineamento_competenza[i,j] + δ × penalità_continuità[i,j]. I pesi (α, β, γ, δ) sono decisione manageriale; inizialmente α=1, β=0.5, γ=2 (alto), δ=0.3. Dopo ogni assegnazione si registra la deviazione reale-vs-stima.
Fase 2 — Costruisci il capitale di conoscenza. Mappa competenze del personale, tassonomia dei compiti, tariffa di trasferta (regione×regione), regole di continuità con cliente. Questo dataset alimenta il modello di stima della matrice.
Fase 3 — Pilot. 6-10 settimane. Su un sotto-insieme (per es. una regione o un tipo di lavoro) calcola l’ottimo col metodo ungherese e affiancalo all’assegnazione manuale. Il pianificatore decide; l’algoritmo raccomanda. Testa la procedura dummy per il caso rettangolare. Criteri di successo definiti prima: costo -10% min, tempo pianificatore -50% min, sbilanciamento carico -20% min.
Fase 4 — Roll-out. In 9-15 mesi estensione a tutto il perimetro + multi-obiettivo. Comitato mensile: analisi reale-vs-ottimo, calibrazione trimestrale, equilibrio del carico, continuità cliente.
Rischi — cosa può andare storto
Drift di stima della matrice. Se C[i,j] è mal stimato, l’algoritmo trova l’ottimo sbagliato. Soluzione: calibrazione trimestrale, celle con deviazione >25% innescano analisi.
Competenza multi-dimensionale — un singolo scalare non basta. Soluzione: formulazione multi-obiettivo o componenti riportate separatamente.
Preferenze in conflitto (dimensione sociale). Soluzione: penalità di preferenza nella matrice o alternative sulla frontiera di Pareto.
Lock-in con WFM mono-fornitore. Senza clausola di esportazione annuale in formato standard, perdere il fornitore significa perdere la memoria operativa.
Vista tecnica della soluzione
| Approccio | Scala tipica | Tempo | Ottimo garantito? |
|---|---|---|---|
| Assegnazione intuitiva | Piccolo (n<10) | immediato | No, 70-85% |
| Manuale + foglio (semi-sistematico) | Piccolo (n<10) | minuti | No, quasi-ottimo |
| Metodo ungherese (Kuhn 1955 / Munkres 1957) | Medio (n<200) | secondi | Sì, O(n³) |
| LAP shortest augmenting path (Jonker-Volgenant 1987) | Medio-grande (n<2000) | secondi | Sì, 5-20× più veloce |
| Auction (Bertsekas 1988) | Grande + parallelo | secondi-minuti | Sì (ε-convergenza) |
| LP generico (totalmente unimodulare) | Tutte le scale | minuti | Sì (intero per rilassazione) |
| Bottleneck (max-min) | Equità | secondi | Sì (ricerca binaria) |
| QAP (quadratico) | Interazioni | ore | No, NP-difficile |
| GAP (generalizzato) | Più compiti per risorsa | ore | NP-difficile |
Funzione obiettivo:
- Obiettivo 1 — Costo totale minimo: assegnazione lineare classica.
- Obiettivo 2 — Tempo totale minimo: tempo-centrica.
- Obiettivo 3 — Bottleneck (max-min): equità.
- Obiettivo 4 — Multi-obiettivo: Pareto o somma pesata.
Varianti — secondo il campo:
- Assegnazione lineare classica (quadrata + bilanciata).
- Rettangolare (m≠n) con dummy.
- Massimizzazione (costo := -beneficio).
- Bottleneck (max-min).
- GAP (capacità).
- QAP (interazioni).
- Dinamica multi-periodo.
- Stocastica.
Fonti accademiche
Elencate nel frontmatter sotto sources.
Fonti
- Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2), 83-97. Fonte fondazionale della soluzione polinomiale; nome in onore dei matematici ungheresi König ed Egerváry.
- Munkres, J. (1957). Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1), 32-38. Procedura polinomiale O(n³) formale.
- Burkard, R., Dell’Amico, M. e Martello, S. (2009). Assignment Problems. SIAM. Riferimento canonico (lineare, bottleneck, quadratico, generalizzato).
- Jonker, R. e Volgenant, A. (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38(4), 325-340. Algoritmo LAP — 5-20× più veloce in pratica.
- Pentico, D. W. (2007). Assignment problems: A golden anniversary survey. European Journal of Operational Research, 176(2), 774-793. Rassegna di 50 anni.
- Bertsekas, D. P. (1988). The auction algorithm: A distributed relaxation method for the assignment problem. Annals of Operations Research, 14(1), 105-123. Auction parallelo.
- YÖK Thesis Centre — parola chiave ‘atama problemi’, ‘Macar algoritması’ o ‘Hungarian’ — 25+ tesi dall’accademia TR. tez.yok.gov.tr
Glossario
- 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.
- Algoritmo Ungherese
- Algoritmo combinatorio che risolve il problema di assegnazione (matrice di costo n×n, matching uno-a-uno di costo minimo) in tempo polinomiale O(n³); Kuhn (1955) e Munkres (1957).
- Matching Bipartito Pesato
- Problema di ricerca operativa di trovare, in un grafo bipartito con archi pesati, un matching di peso totale massimo (o minimo) tra due insiemi disgiunti di vertici.
Problemi correlati
Come Costruisco Pattern Settimanali — Domanda Coperta, Riposo, Ore e Equità Tenuti Insieme?
Il responsabile HR o operations di un servizio 7-giorni 24-ore (call center di una catena retail, reception alberghiera, sicurezza, pulizia ospedaliera) non assegna singoli turni ma **pattern settimanali** per 100-500 dipendenti: chi lavora quali giorni, in quale turno (mattina/pomeriggio/notte), con quale distribuzione di riposi — domanda coperta nei picchi, carico del fine settimana e notturno ripartito equamente. Il piano intuitivo sanguina da uno dei due estremi: personale insufficiente nei picchi (coda in cassa, vendite perse, chiamate abbandonate) o in eccesso nelle ore vuote (80-200 TRY/ora di manodopera, circa 30-60K TRY al mese sprecati in un'operazione da 100 persone). In più, gli sforamenti contrattuali (tetto settimanale di 45 ore, 5 giorni consecutivi, 7-10 notti al mese) generano sanzioni in busta paga e rischi giuslavoristici; senza un criterio di equità scritto, il turnover sale al 40-80 % e ogni nuova assunzione costa 8-30K TRY di formazione. In un'operazione da 200 persone, il monte salari annuo è di 30-80M TRY; un miglioramento del 10 % vale 3-8M TRY all'anno.
Quale Tecnico a Quale Cliente, a Che Ora?
Un servizio di climatizzazione, una società di manutenzione ascensori, un'assistenza elettrodomestici, un fornitore di tecnici ISP o un servizio per macchinari agricoli con 5–50 tecnici sul campo affronta ogni mattina una lista di richieste: 30–150 clienti per manutenzione programmata, riparazione guasti o installazione. La decisione: quale tecnico, quale cliente, in che ordine, a che ora. Vincoli da rispettare simultaneamente: finestra oraria del cliente (mattina / pomeriggio / orario specifico), competenza del tecnico (climatizzazione marca A vs B, tipo di ascensore, infrastruttura internet), tempo di viaggio (20–90 min in città), ricambi nel furgone del tecnico, priorità del guasto urgente. L'assegnazione manuale regge fino a 10–15 tecnici; oltre, il team di dispatch spende 2–4 ore al giorno al telefono — appuntamenti slittati, clienti insoddisfatti e tecnici fermi diventano la routine.