Ricerca Operativa - Corso A
a.a. 2012/2013
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 e 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 del flusso massimo
- Il problema di flusso di costo minimo.
Programmazione Lineare (20 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 (8 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.5.3
2.6.2
2.6.4
2.7
pag. 140
pag. 145
- - -
- - -
- - -
- - -
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
Albero di copertura di costo minimo
Algoritmo basato su preflussi
Algoritmo basato su cammini minimi successivi (per il problema di flusso di
costo minimo)
Basi di cicli
Problemi di accoppiamento
Teorema 3.1 (in 3.1)
Teorema 3.4 (in 3.1)
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)