Ricerca Operativa

a.a. 2006/2007

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

  1. Introduzione (2 ore)

  2. Modelli e loro formulazione (12 ore)

  3. Grafi e Reti di flusso (16 ore)

  4. Programmazione Lineare (18 ore)

(Le ore indicate includono le esercitazioni)

Parti degli appunti non sviluppate durante il corso (ultimo aggiornamento al 5/6/2007)
1.2.2.3
1.2.3.1
1.2.4.3
1.2.10.1
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.3
Il problema del commesso viaggiatore
Soddisfattibilità
Assegnamento di frequenze
Minima distanza
Vincoli disgiuntivi
Alcuni modelli di flusso
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
Problemi di accoppiamento
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)