RICERCA OPERATIVA
Anno accademico e docente
Non hai trovato la Scheda dell'insegnamento riferita a un anno accademico precedente?
Ecco come fare >>
- English course description
- Anno accademico
- 2022/2023
- Docente
- MADDALENA NONATO
- Crediti formativi
- 6
- Periodo didattico
- Secondo Semestre
- SSD
- MAT/09
Obiettivi formativi
- Il corso ha lo scopo di introdurre lo studente alla modellizzazione matematica dei processi decisionali e alle principali metodologie di tipo quantitativo per la loro risoluzione. Particolare enfasi viene posta sulle metodologie di tipo euristico per la soluzione di problemi di ottimizzazione combinatoria di grandi dimensioni. Tali strumenti si ritengono necessari per affrontare i problemi decisionali complessi connessi ai compiti direttivi e di coordinamento che un ingegnere è chiamato a svolgere nei vari settori operativi.
Le conoscenze acquisite riguardano:
1) I principali problemi su grafi, sia topologici che di flusso, e relativi algoritmi.
2) I paradigmi di riferimento delle principali classi di algoritmi euristici, sia costruttivi che di miglioramento.
Al termine del corso lo studente avrà acquisito due abilità fondamentali: la capacità di formulare un modello astratto di un problema di ottimizzazione combinatoria; la capacità di individuare le strutture presenti su cui articolare un approccio risolutivo di tipo euristico, oppure, avendo ricondotto il problema in esame a un problema noto nella classe P, di applicare un algoritmo ad hoc per la sua soluzione esatta. Prerequisiti
- Per seguire il corso con profitto, si consiglia di avere familiarità con i contenuti dei corsi di Fondamenti di Informatica 1 e 2, Analisi Matematica 1 e 2. Il superamento di detti esami NON e' vincolante.
Contenuti del corso
- Formulazione di un problema di ottimizzazione: variabili decisionali, funzioni-obiettivo, vincoli.
Problemi, algoritmi, e complessità.
Ottimizzazione su grafi, problemi, algoritmi risolutivi e applicazioni: (cammini ottimi, gestione di progetti, problemi di scheduling con risorse condivise, alberi di copertura, network design, assegnamenti, reti di flusso).
Cenni di Programmazione Lineare (proprietà, algoritmo del simplesso) e Programmazione Lineare a Variabili Intere (Branch and Bound) esemplificando attraverso l'esame di alcuni dei problemi più noti dell'ottimizzazione combinatoria, con particolare enfasi sulla costruzione del modello matematico.
Algoritmi euristici: costruttivi (greedy e algoritmi ad hoc) e ricerca locale.
Metaeuristiche neighborhood based e population based: GRASP, ricerca tabu, simulated annealing, VNS,VLNS, algoritmi genetici, scatter search e path relinking.
Tutti gli algoritmi proposti verranno illustrati attraverso l'esemplificazione sui problemi di ottimizzazione discreta piu' noti.
Utilizzo marginale di sw commerciale in laboratorio (X-Press MP). Metodi didattici
- Il corso consiste in lezioni teoriche frontali ed esercitazioni in laboratorio per l'uso del software di ottimizzazione e per l'implementazione di alcuni schemi di algoritmi. Viene incoraggiata la discussione in aula sulla modellizzazione dei problemi, secondo un approccio di tipo “problem solving”.
Modalità di verifica dell'apprendimento
- L’esame ha lo scopo di verificare se il candidato abbia acquisito le conoscenze e le abilità specificate negli obiettivi formativi dell'insegnamento.
L'esame del corso di Ricerca Operativa consiste in una prova orale.
La prova è suddivisa in due parti. Nella prima il candidato presenta e discute assieme ai colleghi (il lavoro di gruppo è incoraggiato ma i componenti del gruppo devono sostenere l'esame nella stessa data) il progetto svolto su un argomento scelto dalla lista fornita dal docente o di sua elezione ma concordato. Lo studente deve dimostrare di sapere applicare le metodologie studiate durante il corso per la soluzione del problema scelto, mettendone in luce pro e contro e giustificando le proprie scelte implementative. Il linguaggio di implementazione degli algoritmi è a libera scelta, e può prevedere l'uso di del solver Xpress a supporto di altre tecniche di soluzione (euristiche ibride). La seconda parte consiste in una prova orale sugli argomenti svolti a lezione. Il punteggio finale si compone della somma dei punteggi ottenuti nelle due parti. Al progetto sono riservati al massimo 22 punti, alla conoscenza del programma svolto i restanti 10. Per ottenere la lode occorre totalizzare almeno 31.
Su richiesta l'esame può essere sostenuto in lingua inglese. Testi di riferimento
- Il docente mette a disposizione le proprie slides usate a lezione: sono accessibili previa autenticazione sul sito del corso, ricordando che si tratta di ausili alla didattica e non sono da intendersi come dispense.
Materiale sui singoli argomenti viene fornito dal docente durante il corso e caricato sul sito.
Si consigliano per approfondimento i seguenti testi, presenti in biblioteca:
M. Fischietti, Lezioni di Ricerca Operativa; Ed. Libreria Progetto, Padova, 1993 (per la programmazione lineare e intera).
R. Ahuja, T. Magnanti, J. Orlin; Network Flows; Prentice Hall, 1993 (per i problemi di flusso)
Hillier F.S. LiebermanG.J., Introduction to Operations Research; Holden-Day, Oackland CA, 1986, (per una introduzione generale)
A Sassano, Modelli e algoritmi della Ricerca Operativa; Franco Angeli 1999.
X-Press User Guide, www.dashoptimization.com,
