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 i∈S 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)
Le lezioni del Corso
1. Introduzione al corso di Ricerca operativa II
2. Generalità e classificazione dei sistemi di produzione
3. La logistica dei sistemi di produzione
4. Introduzione all'ottimizzazione combinatoria
5. Fondamenti di teoria della complessità computazionale
6. Algoritmi euristici costruttivi e migliorativi
10. Problemi di Localizzazione
12. Introduzione alla gestione delle scorte
13. Modelli stocastici per la gestione delle scorte
14. Modelli discreti per la gestione delle scorte
15. Introduzione allo scheduling
16. Scheduling su macchina singola
17. Problemi di scheduling su macchina singola e su macchine parall...
