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  

(Tutto software genuino realizzato ad hoc!)

Commenti

Post più popolari