In questa lezione si introducono le definizioni fondamentali di teoria dei grafi necessarie per formulare e risolvere i problemi di ottimizzazione su rete che saranno descritti nelle lezioni successive.
Nell’ambito dei grafi orientati si forniscono le definizioni di percorso e circuito e si introducono particolari tipi di grafi orientati. Vengono esposte inoltre le principali forme di rappresentazione di un grafo, corrispondenti a diverse strutture dati, di tipo matriciale o vettoriale.
Si descrive poi la procedura di visita di un grafo e si introducono infine i parametri numerici fondamentali necessari per la definizione dei problemi di ottimizzazione su rete.
cij ≤ cik + ckj
∀ij ∈A, ∀ k ∈V, k ≠ i, j
Cp,od = ∑ij ∈p cij
∀ p ∈Pod
R = (V, A, W ) in cui V ed A assumono i significati noti e W è l’insieme dei pesi sui vertici.
R = (V, A, C ) in cui C è l’insieme dei costi di spostamento sugli archi.
R = (V, A, W, C )
2. Ottimizzazione non lineare monodimensionale
3. Ottimizzazione non lineare multidimensionale non vincolata
4. Ottimizzazione non lineare multidimensionale vincolata
5. Ottimizzazione lineare: formulazione di modelli
6. Ottimizzazione lineare: Algoritmo del Simplesso
7. Ottimizzazione lineare: Algoritmo del Simplesso - II parte
8. Ottimizzazione lineare: Algoritmo del Simplesso - III parte
9. Ottimizzazione lineare: il metodo del Big M
10. Ottimizzazione lineare: il metodo delle due fasi
11. Ottimizzazione lineare: Algoritmo del Simplesso revisionato
12. Ottimizzazione lineare: Analisi post-ottimale
13. Ottimizzazione lineare: il modello duale
15. Ottimizzazione intera: il metodo del piano di taglio
16. Ottimizzazione intera: il metodo Branch and Bound
17. Ottimizzazione su rete: Introduzione alla Teoria dei Grafi
18. Ottimizzazione su rete: Problemi di percorso
19. Ottimizzazione su rete: Problemi di flusso
20. Ottimizzazione su rete: Problemi di progetto, circuito e locali...