Ricerca Operativa - Corso A
a.a. 2009/2010
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 (8 ore)
- Tipi di variabili: logiche, continue, discrete;
- Formulazione di vincoli;
- Formulazione della funzione obiettivo.
-
Grafi e Reti di flusso (20 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;
- Il problema del flusso di costo minimo.
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 non sviluppate durante il corso
Sezione aggiornata periodicamente durante lo svolgimento del corso (ultimo aggiornamento: 20/4/2010)
- - -
1.2.2.3
1.2.3
1.2.4.3
1.2.10.1
1.2.11
1.2.12
2.1.1
2.1.2
2.2.2
2.3.4
2.3.5
2.3.6
2.4.2
2.4.3
2.5.3
2.5.4
2.6.3
2.6.4
2.7
- - -
- - -
- - -
3.3.3
|
Algoritmi approssimati e rilassamenti (pp. 6-7)
Il problema del commesso viaggiatore
Relazioni logiche
Assegnamento di frequenze
Minima distanza
Funzioni lineari a tratti
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 su grafi aclicici
Algoritmo di Prim
Albero di copertura bottleneck
Algoritmo basato su preflussi
Flusso massimo con più sorgenti/pozzi
Algoritmo basato su cancellazione di cicli
Basi di cicli
Problemi di accoppiamento
Interpretazione economica degli scarti complementari (pp. 160-163)
La regola anticiclo di Bland (la dimostrazione - pp. 182-183)
Individuazione di una base duale ammissibile (pp. 188-189)
Analisi post-ottimale
|
|---|
Testo 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
Altri testi di consultazione
R.K. Ahuja, T.L. Magnanti, J. Orlin, Network flows. Theory, algorithms and applications, Prentice Hall, 1993.
C. Vercellis, Modelli e decisioni, Progetto Leonardo, 1999.
P. Serafini, Ottimizzazione, Zanichelli, 2000.
C. Vercellis, Ottimizzazione. Teoria, metodi, applicazioni, McGraw Hill, 2008.