Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Giuseppe Bruno » 11.Progetto ottimale di reti


Argomenti della lezione

  • Definizioni generali
  • Gli elementi del problema
  • Il modello matematico generale
  • Il problema dell’albero minimo

Gli elementi del problema

In funzione del modello di rappresentazione di un problema di localizzazione, i servizi possono essere di diversa estensione. A tal proposito si parla di:

Problemi di localizzazione puntuale
Quando i servizi sono efficacemente rappresentabili attraverso punti nello spazio di localizzazione.

Progetto di reti
Quando i servizi hanno una estensione tale da non poter essere rappresentati come punti.

Gli elementi del problema (segue)

Dal punto di vista funzionale una rete si compone di:

Nodi sorgenti o origini
Luoghi in cui si producono i beni e i servizi da distribuire attraverso la rete; dalle sorgenti ha origine l’offerta del servizio.

Nodi terminali o destinazioni
Luoghi presso i quali vanno consegnati i beni o sono consumati i servizi; nei terminali ha destinazione la domanda del servizio.

Nodi di interscambio
Nodi attraversati dal flusso proveniente dalle origini e diretto verso le destinazioni.

Collegamenti
Strutture fisiche e/o tecnologiche che connettono i vari punti della rete e sono caratterizzati da parametri fisici (es: lunghezza, capacità), tecnologici e di costo.

Gli elementi del problema (segue)


Gli elementi del problema (segue)


Gli elementi del problema (segue)


Gli elementi del problema (segue)

I problemi decisionali relativi alla gestione dei servizi su rete si possono distinguere in:

Definizione della topologia: consiste nelle decisioni circa la localizzazione dei nodi della rete, le loro caratteristiche e la disposizione dei collegamenti;

Dimensionamento: riguarda l’attribuzione delle caratteristiche fisiche e tecnologiche degli elementi (es: collegamenti)

Gestione: riguarda le politiche di instradamento dei flussi, attraverso la scelta di percorsi e regole di attraversamento.

Gli elementi del problema (segue)

In merito ai problemi di topologia e dimensionamento si possono distinguere:

  • Problemi di progetto ex-novo
  • Problemi di ampliamento di reti esistenti

Gli elementi del problema (segue)

Domanda

La domanda, reale o potenziale, è definita in termini di matrice origine-destinazione D={dst} dove dst rappresenta la domanda di avente origine in s e destinazione in t.

La domanda viene indirizzata sui percorsi tra s e t, in base ad un modello di distribuzione, dando luogo a flussi sugli archi.

In un modello di distribuzione tutto-niente la domanda viene indirizzata lungo il minimo percorso tra s e t.

Gli elementi del problema (segue)

Domanda

Il flusso sul generico arco i,j sarà dato dalla sovrapposizione di diversi flussi origine destinazione.

Ad esempio, in presenza di una domanda origine-destinazione 1-6 (d16), 2-5 (d25), 3-4 (d34), i flussi sulla rete si distribuiscono come indicato in figura, e il flusso sull’arco (i,j) è dato da fij=d16+d25+d34.


Il modello matematico generale


Il modello matematico generale (segue)


Il problema dell’albero minimo

In molte applicazioni la topologia di rete da realizzare è quella ad albero. Un albero è rappresentabile attraverso un grafo di n nodi connesso senza cicli.

Proprietà:

  • Per ogni coppia di nodi esiste una sola catena che li unisce;
  • Se si cancella uno spigolo si perde la connessione e si formano due sottoalberi;
  • È composto da n-1 spigoli ed è la topologia che assicura la connessione con il minor numero di spigoli.

Il problema dell’albero minimo (segue)

Dati n nodi, siano cij i costi di localizzazione dello spigolo (i,j), il problema dell’albero a costo minimo (Minimum Spanning Tree) consiste nell’individuare l’albero che connette tutti i nodi a costo totale minimo.

Il problema è di tipo polinomiale e può essere risolto in maniera esatta utilizzando l’algoritmo costruttivo di Prim.

Il problema dell’albero minimo (segue)

Algoritmo di Prim

1. Inizializzazione
Si individua un qualsiasi nodo t e si pone S={t}, S‘=V-{t} e z(S)=0

2. Aggiunta di un nuovo elemento alla soluzione parziale
Per ogni iS si individua il nodo k(i)∈S‘ più vicino a i (cik(i)=mink∈S’ cik). Si individuano, quindi, i nodi i* e k(i*) cui è associato il minimo dei costi cik(i) (ci*k(i*)=mini∈S cik(i)).
Si pone S=S∪{k(i*)} e S‘=S‘-{k(i*)}; si aggiunge lo spigolo (i*,k(i*)) all’albero parziale e si pone z(S)=z(S)+ci*k(i*).

3. Criterio di arresto
Se S≡V la soluzione è completa e l’algoritmo si arresta; altrimenti si torna al passo 2.

 

Il problema dell’albero minimo (segue)


Il problema dell’albero minimo (segue)


Il problema dell’albero minimo (segue)


Il problema dell’albero minimo (segue)


Il problema dell’albero minimo (segue)


Il problema dell’albero minimo (segue)


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion