C'è da spostare una macchina

Un'azienda di autonoleggi si trova con un'autovettura di troppo nelle sedi di Bari, Pescara, Firenze, Bologna, Torino e Genova. Nello stesso tempo, gli manca un'autovettura nelle sedi di Roma, Napoli, Perugia, Milano, Venezia e Potenza. Vorrebbe organizzare il trasferimento delle 6 autovetture, minimizzando il chilometraggio complessivo.

	Roma	Napoli	Perugia	Milano	Venezia	Potenza
Bari	431	262	564	880	819	130
Pescara	210	245	273	589	528	309
Firenze	284	474	150	317	274	609
Bologna	398	588	243	219	156	723
Torino	682	871	547	142	405	1006
Genova	523	713	389	141	398	848

Si tratta di un tipico problema di assegnazione. A volerlo risolvere di forza bruta purtroppo c'è da perderci la testa, perché se la matrice quadrata che descrive i dati del problema è di dimensione n, le coppie diverse che si possono formare sono n!. Già nel nostro caso 6! = 720, che è un numeraccio.

Lo risolviamo perciò con il metodo ungherese, che è un algoritmo di ottimizzazione combinatoria che risolve il problema dell'assegnazione in un tempo polinomiale. Fu sviluppato e pubblicato da Harold Kuhn nel 1955. Fu chiamato metodo ungherese perché l'algoritmo era ampiamente fondato sui lavori precedenti dei due matematici ungheresi Dénes Kőnig e Jenő Egerváry, entrambi morti suicidi, il primo a causa delle persecuzioni naziste contro gli Ebrei, il secondo a causa dell'accanimento su di lui della burocrazia comunista. Nel 2006, si è scoperto che Carl Gustav Jacobi aveva già risolto il problema dell'assegnazione nel 19° secolo, come descritto in una sua pubblicazione postuma del 1890 in latino.

Il metodo è spiegato abbastanza bene, per noi a cui l'inglese non fa paura, in queste slides.

Per la spiegazione del procedimento e per ottenere la soluzione del problema fate click qui

La soluzione ottimale finale è quindi:

1	Bari	-->	Potenza	:	130
2	Pescara	-->	Napoli	:	245
3	Firenze	-->	Roma	:	284
4	Bologna	-->	Venezia	:	156
5	Torino	-->	Milano	:	142
6	Genova	-->	Perugia	:	389

Il costo totale ottimale è 1346 km

L'algoritmo ha scartato una soluzione alternativa con lo stesso costo totale,
che sarebbe stata:

1	Bari	-->	Potenza	:	130
2	Pescara	-->	Napoli	:	245
3	Firenze	-->	Perugia	:	150
4	Bologna	-->	Venezia	:	156
5	Torino	-->	Milano	:	142
6	Genova	-->	Roma	:	523

Per ripetere il procedimento con matrici riempite con dati casuali:

Dimensione matrice  2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 

(Tutto software genuino realizzato ad hoc!)