ID:
000884
Tipo Insegnamento:
Opzionale
Durata (ore):
64
CFU:
8
SSD:
RICERCA OPERATIVA
Url:
INGEGNERIA ELETTRONICA PER L'ICT/Percorso Comune Anno: 1
Anno:
2024
Dati Generali
Periodo di attività
Primo Semestre (19/09/2024 - 17/12/2024)
Syllabus
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.
Lo studente verrà introdotto all'uso di un solver commerciale ad alte prestazioni, Xpress (Fico.com)
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.
Lo studente verrà introdotto all'uso di un solver commerciale ad alte prestazioni, Xpress (Fico.com)
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.
Metodi didattici
Il corso consiste in lezioni teoriche frontali ed esercitazioni in laboratorio per l'uso del software di ottimizzazione (Xpress) 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”.
Verifica 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.
Dall'AA 21/22, al posto del progetto è possibile presentare una tesina compilativa svolta individualmente su un argomento concordato col docente. In tal caso la votazione massima complessiva è 27.
Su richiesta l'esame può essere sostenuto in lingua inglese.
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.
Dall'AA 21/22, al posto del progetto è possibile presentare una tesina compilativa svolta individualmente su un argomento concordato col docente. In tal caso la votazione massima complessiva è 27.
Su richiesta l'esame può essere sostenuto in lingua inglese.
Testi
Il docente mette a disposizione le proprie slides usate a lezione su classroom, 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. Fischetti, 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.fico.com,
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. Fischetti, 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.fico.com,
Contenuti
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. La teoria della Programmazione Lineare non viene chiesta all’orale per chi segue il corso da 6 CFU.
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).
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. La teoria della Programmazione Lineare non viene chiesta all’orale per chi segue il corso da 6 CFU.
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).
Lingua Insegnamento
Italiano, ma l'esame può essere sostenuto anche in inglese
Corsi
Corsi
INGEGNERIA ELETTRONICA PER L'ICT
Laurea Magistrale
2 anni
No Results Found
Persone
Persone (2)
Assegnisti
No Results Found