Cos'è il problema dell'assegnazione?

Il problema dell'assegnazione è un classico problema di ottimizzazione combinatoria: dato un insieme di lavoratori e compiti, ciascuno con un costo associato, trovare l'accoppiamento uno-a-uno che minimizza il costo totale. Appare naturalmente nella pianificazione, nella logistica, nell'allocazione delle risorse e nella ricerca operativa — in qualsiasi situazione in cui è necessario abbinare due gruppi nel modo più efficiente possibile.

Il problema viene risolto con l'algoritmo ungherese (chiamato anche algoritmo di Munkres), un metodo efficiente sviluppato negli anni '50. A differenza degli approcci a forza bruta che devono valutare ogni permutazione, l'algoritmo ungherese trova la soluzione ottimale in tempo polinomiale, rendendolo pratico anche per matrici di dimensioni moderate.

Descrizione dello strumento

Inserisci una matrice di costi che rappresenta quanto costa assegnare ogni lavoratore a ogni compito, quindi fai clic su Risolvi per trovare istantaneamente l'assegnazione ottimale. Lo strumento evidenzia quali coppie lavoratore-compito minimizzano il costo totale e visualizza il risultato in una tabella chiara insieme al costo totale ottimale.

Esempi

Matrice di input (3 lavoratori × 3 compiti):

Compito 1 Compito 2 Compito 3
Lavoratore 1 400 150 400
Lavoratore 2 400 450 600
Lavoratore 3 300 225 300

Assegnazioni ottimali:

Lavoratore Compito Costo
Lavoratore 1 Compito 2 150
Lavoratore 2 Compito 1 400
Lavoratore 3 Compito 3 300

Costo totale: 850

Funzionalità

  • Matrice modificabile — fai clic su qualsiasi cella o intestazione di colonna per rinominare lavoratori, compiti e costi direttamente nella tabella
  • Dimensione configurabile — supporta matrici da 2×2 fino a 8×8
  • Risultati istantanei — l'algoritmo ungherese viene eseguito nel browser senza round-trip al server

Come funziona

Lo strumento utilizza l'algoritmo di Munkres (ungherese) per risolvere il problema dell'assegnazione in modo ottimale. Costruisce una matrice di costi dai tuoi input, applica una serie di passaggi di riduzione di righe e colonne, e trova iterativamente un accoppiamento massimale di zeri fino a quando non viene identificata un'assegnazione ottimale completa. La complessità temporale è $O(n^3)$, dove $n$ è la dimensione della matrice.

Per matrici non quadrate (più lavoratori che compiti o viceversa), l'algoritmo riempie la matrice con zeri in modo che ogni lavoratore e ogni compito sia abbinato.

Opzioni spiegate

  • Numero di lavoratori / righe — controlla quante righe appaiono nella matrice di costi (2–8)
  • Numero di compiti / colonne — controlla quante colonne appaiono nella matrice di costi (2–8)
  • Celle della matrice di costi — inserisci il costo dell'assegnazione di uno specifico lavoratore a uno specifico compito; è accettato qualsiasi valore numerico

Limitazioni

  • La dimensione della matrice è limitata a 8×8 (64 celle)
  • L'algoritmo minimizza il costo totale; per massimizzare (ad esempio, per matrici di profitto), nega i valori prima di inserirli
  • I valori di celle non numeriche vengono trattati come zero