Ricerca Operativa
a.a. 2005/2006
Il corso presenta gli strumenti necessari alla costruzione e alla
risoluzione di modelli analitici di ottimizzazione per problemi
reali, tipicamente di gestione, di allocazione delle risorse e di
logistica. Verranno illustrate le proprietà teoriche ed alcune
delle principali tecniche algoritmiche per la soluzione di due grandi
classi di problemi di ottimizzazione: problemi di flusso su reti e
problemi di programmazione lineare.
PROGRAMMA DEL CORSO
-
Introduzione (2 ore)
- Problemi decisionali, problemi di ottimizzazione ed esistenza;
- Classi di problemi; alcuni esempi.
-
Modelli e loro formulazione (12 ore)
- Tipi di variabili: logiche, continue, discrete;
- Formulazione di vincoli;
- Formulazione della funzione obiettivo.
-
Grafi e Reti di flusso (16 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 (18 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;
(Le ore indicate 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)