Ricerca Operativa

a.a. 2010/2011

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

  1. Introduzione (2 ore)

  2. Grafi e Reti di flusso (18 ore)

  3. Programmazione Lineare (18 ore)

  4. Modelli per problemi di ottimizzazione più generali (10 ore)

(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)