La Ricerca Operativa è la Scienza che si propone di realizzare modelli razionali per la rappresentazione di problemi complessi e di determinarne contestualmente i relativi algoritmi risolutivi. Obiettivo del Corso e’ quello di approfondire le competenze dello studente su tematiche di Ricerca Operativa con enfasi su complessità computazionale, ottimizzazione combinatoria ed analisi multi criteri.

Alla fine del Corso, si prevede che lo studente sia in grado di valutare la complessità computazionale di algoritmi dati, di ideare algoritmi esatti ed euristici per problemi reali di ottimizzazione combinatoria, di essere a conoscenza dei principali metodi di analisi multi criteri e di saperli applicare in relazione a specifici problemi di decisione.

Basi di Ricerca operativa con enfasi sulla programmazione lineare.

Complessità computazionale.
Elementi di Teoria dei Grafi.
Ottimizzazione combinatoria: metodi esatti, euristici, algoritmi di approssimazione.
Analisi multicriteri: introduzione all’ottimizzazione multi-obiettivi (ottimalità di Pareto ed approcci risolutivi) e ai metodi multicriteri di surclassamento, metodi ELECTRE per la cernita e la segmentazione.

Le esercitazioni in aula tratteranno applicazioni dei metodi presentati a lezione. In laboratorio alcuni strumenti informatici saranno utilizzati in relazione ai problemi considerati.

Appunti forniti dal docente.

Testi di riferimento che contengono parte degli argomenti presentati nel Corso sono i seguenti

• M.R. Garey, D.S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co.
• C.H. Papadimitriou, K. Steiglitz (1982), Combinatorial Optimization. Algorithms and Complexity, Prentice Hall.
• V. Vazirani (2001), Approximation Algorithms, Springer.
• P. Vincke (1992), Multicriteria decision-Aid, Wiley, Chichester.
• L.A. Wolsey (1999), Integer Programming and Combinatorial Optimization, Wiley.

Esame scritto.