Ricerca Operativa
a.a. 2003/2004
G. Bigi (corso A), S. Pallottino (corso B), M. G.
Scutellà (corso C)
Il corso si propone di fornire allo/a studente/essa conoscenze di base di
modellistica, problemi di flusso su reti e Programmazione Lineare.
Il corso presenterà aspetti relativi alla modellizzazione di problemi di
ottimizzazione, con enfasi sulle possibili applicazioni, e descriverà
classi di algoritmi per la loro risoluzione, introducendo la relativa teoria.
PROGRAMMA DEL CORSO
-
Introduzione (2 ore)
- Problemi decisionali, problemi di ottimizzazione ed esistenza;
- Classi di problemi; alcuni esempi.
-
Modelli e loro formulazione (5 ore)
- Tipi di variabili: logiche, continue, discrete;
- Formulazione di vincoli;
- Formulazione della funzione obiettivo.
-
Grafi e Reti di flusso (8 ore)
- Modello generale dei problemi di flusso;
- Alberi, cammini e tagli, visite di grafi e alberi;
- Il problema dei cammini minimi;
- Il problema dell'albero di copertura di costo minimo;
- Il problema del flusso massimo.
Programmazione Lineare (11 ore)
- Modelli di Programmazione Lineare, coppie di problemi duali e
teorema debole della dualità
- Vincoli attivi e non attivi, direzioni ammissibili e/o di
crescita, Lemma di Farkas;
- Teorema forte della dualità, scarti complementari e
interpretazione economica della dualità
- Basi complementari, considerazioni geometriche; algoritmi del
Simplesso Primale e del Simplesso Duale;
- Analisi post-ottimale.
(Le ore indicate non includono le esercitazioni)
Parti degli appunti (versione 03/04) non sviluppate durante il corso
1.2.2.3
1.2.3.1
1.2.4.3
1.2.10
1.2.12
2.1.1
2.2.2
2.3.4
2.3.5
2.3.7
2.4.2
2.4.3
2.5.3
2.5.4
2.6
2.7
- - -
3.3.2
3.3.3
|
Il problema del commesso viaggiatore
Soddisfattibilità
Assegnamento di frequenze
Come rappresentare il valore assoluto
Vincoli disgiuntivi
Alcuni modelli di flusso
Usi della procedura di visita
Algoritmi a coda di priorità: Heap binario (pp. 77-78)
Algoritmi a selezione su lista: Liste a doppio ingresso (pp. 79-81)
Cammini minimi con radici multiple
Algoritmo di Prim
Albero di copertura bottleneck
Algoritmo basato su preflussi
Flusso massimo con più sorgenti/pozzi
Il problema di flusso di costo minimo
Problemi di accoppiamento
Interpretazione economica degli scarti complementari (pp. 152-154)
L'algoritmo del Simplesso Duale: Individuaz. di una base duale amm. (pp. 178-179)
Analisi post-ottimale
|
|---|
Testi di riferimento
G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G.
Scutellà, Appunti di Ricerca Operativa,
a.a. 2003/2004, SEU - Servizio Editoriale Universitario di Pisa (2004)
F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa",
Franco Angeli, Milano (1999)
A. Sassano, "Modelli e algoritmi della ricerca operativa", Franco
Angeli, Milano (1999)
C. Vercellis, "Modelli e decisioni", Progetto Leonardo, Bologna (1997)