Registrati | Profilo Personale | Norme Generali | Clubartespressione | Privacy

Problema del commesso viaggiatore

      

   

Tecnologia

 Registrazione Tribunale di Rieti n. 5 del 07/11/2002

 

 

Articolo di:

Dott P. CARTILLONE


Soluzioni di Hamilton

 

Stampa agevole

Invia questa pagina ad un amico

Nessun download

Torna all'indice

 

 

2002-2019 Tutti i diritti riservati

Ricerca operativa


Ricerca Operativa

Problema del commesso viaggiatore

Soluzioni di Hamilton

(Torino, May 10 2002 12:00AM) DEFINIZIONE DEL PROBLEMA

Si supponga di dover rifornire di viveri 6 postazioni A B C D E F. Il percorso che porta da una postazione ad un’altra è contraddistinto con un numero che indica la distanza “ponderata”, ponderata perché legata non solo alla distanza fisica vera e propria, ma anche alle difficoltà che il percorso tra i due punti può riservare. Alla fine occorre tornare sulla postazione di partenza.

Facciamo un esempio, con una tabella (MATRICE) e con un grafico (GRAFO) che può aiutarci a chiarire meglio il problema:

Ovviamente, per andare da A a A occorre una distanza pari a 0 che indichiamo con -.

Supponiamo, per semplicità, che il percorso alla rovescia abbia la stessa distanza, non consideriamo ostacoli, sensi unici che possano ostacolare tale supposizione.

A B C D E F

A - 7 11 3 4 10

B 7 - 5 6 24 11

C 11 5 - 6 12 2

D 3 6 6 - 7 4

E 4 24 12 7 - 12

F 10 11 2 4 12 -



Cioè: Per andare da A a B occorre una distanza pari a 7

Per andare da A a C occorre una distanza pari a 11

Per andare da A a D occorre una distanza pari a 3

Per andare da A a E occorre una distanza pari a 4

Per andare da A a F occorre una distanza pari a 10

.... e via via per gli altri percorsi.



Il problema consiste nel rifornire di viveri tutte le sei postazioni col minimo percorso “COSTO MINIMO”.

Questo è un classico problema di Ricerca Operativa, materia sviluppata dai matematici e dagli informatici, e trova applicazione anche in altri campi, ovvero in tutti quei casi dove si ricerca il PERCORSO MINIMO. Alla fine, il percorso trovato costituisce un CIRCUITO.

Una possibile soluzione, consiste nel fare il percorso seguendo il circuito A-B-C-D-E-F-A, che utilizzando i dati della matrice ci porta ad un costo totale pari a 47.

AB + BC +CD +DE +EF +FA = 7+5+6+7+12+10 = 47. (Circuito 1)

Probabilmente, questo è il percorso più facile, ma forse non è il più economico.

Di possibili soluzioni ce ne sono almeno 60. Tale numero è dato da (N-1) ! /2.

Questo è un problema di difficile risoluzione per la Ricerca Operativa, perché aumenta considerevolmente all’aumentare delle postazioni (NODI).

Risolvendo lo stesso problema con un algoritmo di ricerca operativa, legato ai circuiti di HAMILTON (che non passano mai 2 volte per lo stesso nodo) si ottiene che il circuito più economico è quello che porta a A-E-D-F-C-B-A, per un costo totale di 29.

AE + ED + DF + FC + CB + BA = 4+7+4+2+5+7 = 29. (Circuito 2).

Circuito 2

OSSERVAZIONE:

Non sempre fare il giro delle postazioni senza ripassare dallo stesso nodo è la soluzione più conveniente.

E’ possibile dimostrare che ci sono percorsi, che ci fanno passare più di una volta dallo stesso nodo e che hanno lo stesso costo se non addirittura più economici. In particolare, per questo caso il circuito A-E-A-D-F-C-B-A ha lo stesso costo di 29.

AE + EA + AD + DF + FC + CB + BA = 4+4+3+4+2+5+7 = 29. (Circuito 3)

Circuito 3

CONSIDERAZIONI:

Ipotizziamo di avere un’altra MATRICE dei percorsi: A B C D E F

A - 7 30 3 4 30

B 7 - 5 30 30 30

C 30 5 - 30 30 2

D 3 30 30 - 30 4

E 4 30 30 30 - 30

F 30 30 2 4 30 -



In questo caso, un circuito generico di HAMILTON, che non passa mai 2 volte per lo stesso punto non è il più conveniente. Facilmente si calcola che il circuito 2 ha un costo pari a 52.

AE + ED + DF + FC + CB + BA = 4+30+4+2+5+7 = 52

ed ogni altro circuito di HAMILTON ha un costo pari se non superiore. Mentre un circuito NON di HAMILTON come il circuito 3 ha un costo pari a 29.

AE + EA + AD + DF + FC + CB + BA = 4+4+3+4+2+5+7 = 29

che senza alcun dubbio è il più conveniente.

Non sempre i circuiti di HAMILTON sono i più convenienti per risolvere questo tipo di problemi legati al COMMESSO VIAGGIATORE ed ai percorsi minimi.

Sarà forse perché in questa matrice non vale la proprietà di DISUGUAGLIANZA TRIANGOLARE”?
 

 

Inizio

INVIA UN'OPERA

PROFILO PERSONALE

SUPPLEMENTI

 

Pubblicazione

Tesi di Ricerca, Laurea, Master, Dottorato di ricerca.

 

Inserimento opere letterarie, articoli, foto, dipinti,...

Servizio riservato agli utenti registrati

 

Accesso all'area personale

Il servizio consente di modificare le proprie impostazioni personali

  Registrati | Profilo Personale | Norme Generali | Clubartespressione | Privacy

2002-2019 Graffiti-on-line.com

Tutti i diritti di proprietą artistica e letteraria sono riservati.

Registrazione al tribunale di Rieti n. 5 del 07/11/2002.

Consultare le norme generali e la politica sulla privacy.

Proprietario e Direttore responsabile Carmelo SARCIA'

La pubblicazione di articoli, saggi, opere letterarie, tesi di ricerca, ecc. verrą sottoposta alla preventiva approvazione di una commissione tecnica composta di esperti nel ramo nominati dalla Direzione.

Chi siamo | Mappa del Sito | Contattaci | WebMail | Statistiche