2. Docenti
  3. Didattica

METODI DI OTTIMIZZAZIONE

Francesco CARRABS METODI DI OTTIMIZZAZIONE

0522500054
DIPARTIMENTO DI INFORMATICA
CORSO DI LAUREA MAGISTRALE
INFORMATICA
2024/2025



ANNO ORDINAMENTO 2016
SECONDO SEMESTRE
CFUOREATTIVITÀ
648LEZIONE
RAFFAELE CERULLI T Curriculum
FRANCESCO CARRABS Curriculum
Obiettivi
IL CORSO DI METODI DI OTTIMIZZAZIONE SI PROPONE DI FORNIRE LE CONOSCENZE PER LA RISOLUZIONE DI PROBLEMI DI PROGRAMMAZIONE LINEARE CONTINUA (PL) CON UN NUMERO MOLTO ELEVATO DI VARIABILI DECISIONALI. INOLTRE, INTRODUCE LE TECNICHE PER LA FORMULAZIONE DI PROBLEMI REALI CON MODELLI DI PROGRAMMAZIONE LINEARE INTERA (PLI) E PRESENTA I PRINCIPALI ALGORITMI ESATTI ED EURISTICI PER LA RISOLUZIONE DEI PROBLEMI DI PLI. DURANTE IL CORSO VERRANNO DESCRITTE DIVERSE CLASSI DI PROBLEMI DI OTTIMIZZAZIONE, CON PARTICOLARE ATTENZIONE A QUELLE DI MAGGIORE INTERESSE APPLICATIVO.

CONOSCENZA E CAPACITÀ DI COMPRENSIONE
ALLA FINE DEL CORSO LO STUDENTE CONOSCERÀ:
- GLI ALGORITMI, ALTERNATIVI AL METODO DEL SIMPLESSO, PER LA RISOLUZIONE DI PROBLEMI DI PL DI GRANDI DIMENSIONI;
- I CONCETTI BASE DELLA TEORIA DELLA COMPLESSITÀ, NECESSARI PER INDENTIFICARE LA COMPLESSITÀ DEI PROBLEMI DI OTTIMIZZAZIONE AFFRONTATI;
- I PRINCIPALI FONDAMENTI DELLA MODELLAZIONE MATEMATICA DI PROBLEMI DI OTTIMIZZAZIONE A VARIABILI INTERE E LE TECNICHE PER VALUTARE L'EFFICACIA DEI MODELLI MATEMATICI PROPOSTI;
- I PRINCIPALI ALGORITMI RISOLUTIVI SIA DI TIPO ESATTO CHE DI TIPO EURISTICO/METAEURISTICO PER LA RISOLUZIONE DI PROBLEMI DI PLI.

CAPACITÀ DI APPLICARE CONOSCENZE E COMPRENSIONE
ALLA FINE DEL CORSO LO STUDENTE SARÀ IN GRADO DI:
- FORMULARE PROBLEMI DI OTTIMIZZAZIONE TRAMITE MODELLI MATEMATICI A VARIABILI CONTINUE, INTERE O MISTE;
- APPLICARE I CONCETTI DELLA TEORIA DELLA COMPLESSITÀ, PRESENTATI DURANTE IL CORSO, PER VALUTARE LA POSSIBILE INTRATTABILITÀ DI UN PROBLEMA DI OTTIMIZZAZIONE;
- PROGETTARE ED APPLICARE ALGORITMI PER LA RISOLUZIONE DI PROBLEMI DI PL DI GRANDI DIMENSIONI;
- PROGETTARE ED APPLICARE ALGORITMI ESATTI PER LA RISOLUZIONE DI PROBLEMI DI PLI;
- PROGETTARE ED APPLICARE ALGORITMI EURISTICI E/O METAEURISTICI PER LA RISOLUZIONE DI PROBLEMI DI PLI.
AUTONOMIA DI GIUDIZIO
ALLA FINE DEL CORSO LO STUDENTE SARÀ IN GRADO DI:
- SAPER RICONOSCERE IN MODO AUTONOMO ED EFFICACE I MODELLI E I METODI DI OTTIMIZZAZIONE PIÙ ADATTI PER LA RISOLUZIONE DEL PROBLEMA IN ESAME, ANCHE IN PRESENZA DI UN NUMERO ELEVATO DI VARIABILI DECISIONALI, E DI RIUSCIRE AD INTERPRETARNE CORRETTAMENTE I RISULTATI;
- RICONOSCERE LA COMPLESSITÀ COMPUTAZIONALE INTRINSECA NEL PROBLEMA DI OTTIMIZZAZIONE AFFRONTATO E, IN BASE AD ESSA, ESSERE IN GRADO DI INDIVIDUARE GLI ALGORITMI PIÙ EFFICACI DA UTILIZZARE PER RISOLVERE IL PROBLEMA.

ABILITÀ COMUNICATIVE
ALLA FINE DEL CORSO LO STUDENTE AVRÀ ACQUISITO ADEGUATE CAPACITÀ DI ANALISI DI UN PROBLEMA DI OTTIMIZZAZIONE E DEI POSSIBILI SCENARI RISOLUTIVI UTILIZZANDO UNA NOTAZIONE ADEGUATA ED UN LINGUAGGIO APPROPRIATO CHE METTA IN LUCE LE COMPETENZE DELLE METODOLOGIE ACQUISITE. SARÀ, INOLTRE, CAPACE DI TRASMETTERE IN MODO CHIARO E SINTETICO AGLI INTERLOCUTORI, SPECIALISTI E NON, I CONCETTI NECESSARI PER LA COMPRENSIONE DEI MODELLI E DEGLI ALGORITMI SVILUPPATI. INFINE, SARÀ IN GRADO DI CONFRONTARSI CON ALTRI INTERLOCUTORI SULLE QUESTIONI RELATIVE ALLA RISOLUZIONE DI PROBLEMI DI OTTIMIZZAZIONE.

CAPACITÀ DI APPRENDIMENTO
LO STUDENTE SARÀ IN GRADO DI:
- APPLICARE LE CONOSCENZE ACQUISITE A CONTESTI DIFFERENTI DA QUELLI PRESENTATI DURANTE IL CORSO;
- APPROFONDIRE GLI ARGOMENTI TRATTATI USANDO MATERIALI DIDATTICI O SCIENTIFICI DIVERSI DA QUELLI USATI DURANTE IL CORSO;
- APPRENDERE, ANCHE IN MODO AUTONOMO, ULTERIORI CONOSCENZE SUI PROBLEMI DI MATEMATICA APPLICATA.
Prerequisiti
PER SOSTENERE L'ESAME DI OTTIMIZZAZIONE È PROPEDEUTICO AVER SUPERATO L'ESAME DI RICERCA OPERATIVA.
Contenuti
1. LA PROGRAMMAZIONE LINEARE (PL) (6 ORE DI LEZIONE E 2 DI ESERCITAZIONE)
- RICHIAMI DEI PRINCIPALI RISULTATI DELLA PROGRAMMAZIONE LINEARE;
- CASO PATOLOGICO DEL METODO DEL SIMPLESSO: CUBO DI KLEE E MINTY;
- ALGORITMO DELL'ELLISSOIDE;
- TABLEAU DEL SIMPLESSO.
2 ALGORITMI ALTERNATIVI AL METODO DEL SIMPLESSO (4 ORE DI LEZIONE TEORICA E 4 DI ESERCITAZIONE)
- METODO DEL SIMPLESSO DUALE;
- ALGORITMO DEL DELAYED COLUMN GENERATION.
3. LA PROGRAMMAZIONE LINEARE INTERA (PLI) (14 ORE DI LEZIONE E 2 DI ESERCITAZIONE)
- TEORIA DELLA COMPLESSITÀ: CLASSIFICAZIONE DEI PROBLEMI DI OTTIMIZZAZIONE IN BASE ALLA LORO DIFFICOLTÀ;
- VARIABILI E VINCOLI LOGICI; PROBLEMI CON FUNZIONI OBIETTIVO MULTIPLE;
- PRESENTAZIONE DEI PRINCIPALI PROBLEMI COMBINATORI;
- RILASSAMENTO LAGRANGIANO;
- DISUGUAGLIANZE VALIDE.
4 APPROCCI ESATTI (6 ORE DI LEZIONE E 2 DI ESERCITAZIONE)
METODI RISOLUTIVI DI TIPO ESATTO:
- BRANCH AND BOUND;
- PIANI DI TAGLIO;
- BRANCH AND CUT.
5 APPROCCI EURISTICI (6 ORE DI LEZIONE E 2 DI ESERCITAZIONE)
METODI RISOLUTIVI DI TIPO EURISTICO:
- ALGORITMI DI RICERCA LOCALE;
- ALGORITMO GREEDY;
- TABU SEARCH;
- SIMULATED ANNEALING;
- ALGORITMO GENETICO.
Metodi Didattici
L’INSEGNAMENTO PREVEDE LEZIONI FRONTALI DELLA DURATA DI 48 ORE COMPLESSIVE (6 CFU), CHE SI SVOLGONO IN AULA CON L’AUSILIO DI PROIEZIONI; ALLA FINE DELLA PRESENTAZIONE DI UN ARGOMENTO SONO PREVISTI VARI ESEMPI APPLICATIVI ED ESERCITAZIONI IN AULA. LO SVOLGIMENTO DEGLI ESERCIZI È GUIDATO DAL DOCENTE E TENDE A SVILUPPARE E RAFFORZARE LE CAPACITÀ DELLO STUDENTE DI IDENTIFICARE LE TECNICHE PIÙ IDONEE PER LA RISOLUZIONE DELL’ESERCIZIO STESSO.
Verifica dell'apprendimento
LA PROVA DI ESAME È FINALIZZATA A VALUTARE NEL SUO COMPLESSO LE CONOSCENZE E LE CAPACITÀ DI COMPRENSIONE DEI CONCETTI PRESENTATI A LEZIONE, NONCHÉ LA CAPACITÀ DI APPLICARE TALI CONOSCENZE NELLA RISOLUZIONE DI PROBLEMI DI OTTIMIZZAZIONE.
LA PROVA DI ESAME CONSISTE IN UN COLLOQUIO ORALE SUI CONTENUTI DEL CORSO TRAMITE IL QUALE SARANNO VALUTATE LE CONOSCENZE ACQUISITE IN MERITO SIA AGLI ASPETTI TEORICI CHE A QUELLI APPLICATIVI PER LA RISOLUZIONE DI PROBLEMI OTTIMIZZAZIONE.
LA VALUTAZIONE DELL'ORALE È ESPRESSA IN TRENTESIMI E TIENE CONTO DELLA CAPACITÀ DI DESCRIZIONE DEL FUNZIONAMENTO DEGLI ALGORITMI DI OTTIMIZZAZIONE PRESENTATI A LEZIONE E DELLA CAPACITÀ DI ESPORRE IN MODO CHIARO E SINTETICO GLI ARGOMENTI STUDIATI.
IL LIVELLO DI VALUTAZIONE MINIMO (18) È ATTRIBUITO QUANDO LO STUDENTE MOSTRA UNA CONOSCENZA FRAMMENTARIA DEI CONTENUTI TEORICI E UNA LIMITATA CAPACITÀ DI FORMULARE I PROBLEMI DI OTTIMIZZAZIONE E DI APPLICARE GLI ALGORITMI RISOLUTIVI.
IL LIVELLO DI VALUTAZIONE MASSIMO (30) È ATTRIBUITO QUANDO LO STUDENTE DIMOSTRA UNA CONOSCENZA COMPLETA ED APPROFONDITA DEGLI ARGOMENTI DEL CORSO E MOSTRA UNA NOTEVOLE CAPACITÀ DI INDIVIDUARE I METODI PIÙ APPROPRIATI PER RISOLVERE I PROBLEMI DI OTTIMIZZAZIONE AFFRONTATI.
LA LODE VIENE ATTRIBUITA QUANDO IL CANDIDATO DIMOSTRA SIGNIFICATIVA PADRONANZA DEI CONTENUTI TEORICI ED OPERATIVI E MOSTRA DI SAPER PRESENTARE GLI ARGOMENTI CON NOTEVOLE PROPRIETÀ DI LINGUAGGIO E CAPACITÀ DI ELABORAZIONE AUTONOMA ANCHE IN CONTESTI DIVERSI DA QUELLI PROPOSTI DAL DOCENTE NELLE ATTIVITÀ DIDATTICHE.
Testi
- CHRISTOS H. PAPADIMITRIOU, K. STEIGLITZ: COMBINATORIAL OPTIMIZATION: ALGORITHMS AND COMPLEXITY, 1998;
- M.S. BAZARAA, J.J. JARVIS & H.D. SHERALI, LINEAR PROGRAMMING AND NETWORK FLOWS, FOURTH EDITION, JOHN WILEY, 2010;
- GEORGE L. NEMHAUSER, LAURENCE A. WOLSEY, INTEGER AND COMBINATORIAL OPTIMIZATION, 1999.
- APPUNTI DELLE LEZIONI FORNITI DAL DOCENTE DURANTE IL CORSO.
PER APPROFONDIMENTI:
LAURENCE A. WOLSEY, INTEGER PROGRAMMING, 1998.
Altre Informazioni
- EMAIL: RAFFAELE@UNISA.IT, FCARRABS@UNISA.IT
- IL CORSO È EROGATO IN ITALIANO;
- LA FREQUENZA NON È OBBLIGATORIA MA CALDAMENTE CONSIGLIATA;
- L’ORARIO DI RICEVIMENTO È DISPONIBILE SULLA PAGINA WEB DEL DOCENTE: HTTPS://DOCENTI.UNISA.IT/001227/HOME
  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2024-11-18]