Ricerca Operativa - corso B
a.a. 2009/2010
Il corso presenta gli strumenti necessari alla definizione e alla
risoluzione di modelli analitici di ottimizzazione per problemi
reali, tipicamente di gestione, di allocazione delle risorse e di
logistica. Verranno introdotte proprietà teoriche ed alcune
delle principali tecniche algoritmiche per la risoluzione di due grandi
famiglie di problemi di ottimizzazione: i problemi di flusso su rete ed i
problemi di programmazione lineare.
PROGRAMMA DEL CORSO
-
Introduzione (2 ore)
- Problemi decisionali, problemi di ottimizzazione ed esistenza
- Classi di problemi: alcuni esempi.
-
Grafi e Reti di flusso (18 ore)
- Un modello generale per i problemi di flusso su rete
- 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
- Il problema di accoppiamento di massima cardinalittà.
Programmazione Lineare (18 ore)
- Modelli di Programmazione Lineare e coppie di problemi duali
- Teoria della dualità: teorema debole della dualità, direzioni ammissibili e/o di
crescita, Lemma di Farkas; teorema forte della dualità
- Algoritmo del Simplesso Primale e sua interpretazione geometrica;
- Teorema degli scarti complementari
- Algoritmo del Simplesso Duale e sua interpretazione geometrica.
-
Modelli per problemi di ottimizzazione più generali (10 ore)
- Tipi di variabili: logiche, continue, discrete
- Formulazioni di vincoli
- Formulazioni della funzione obiettivo
- Esempi di problemi reali.
(Le ore indicate includono le esercitazioni)
Parti degli appunti non sviluppate durante il corso (elenco
aggiornato durante lo svolgimento del corso)
1.2.2.3
1.2.3.1
1.2.4.3
1.2.10.1
1.2.12
2.1.1
2.1.2
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.2
- - -
- - -
- - -
- - -
3.3.3
|
Il problema del commesso viaggiatore
Soddisfattibilità
Assegnamento di frequenze
Minima distanza
Vincoli disgiuntivi
Alcuni modelli di flusso
Trasformazioni equivalenti
Usi della procedura di visita
Algoritmi a coda di priorità: Heap binario (pp. 79-80)
Algoritmi a selezione su lista: Liste a doppio ingresso (pp. 81-83)
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
Assegnamento di costo minimo
Interpretazione economica degli scarti complementari (pp. 160-163)
Individuazione di una base primale ammissibile (pp. 179-181)
La regola anticiclo di Bland (la dimostrazione - pp. 182-183)
Individuazione di una base duale ammissibile (pp. 188-189)
Analisi post-ottimale
|
|---|
Testi di riferimento
G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G.
Scutellà, Appunti di Ricerca Operativa,
a.a. 2006/2007, SEU - Servizio Editoriale Universitario di Pisa
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)