CIRIACO D'AMBROSIO | OTTIMIZZAZIONE

cod. 0522200016

OTTIMIZZAZIONE

	0522200016
	DIPARTIMENTO DI MATEMATICA
	CORSO DI LAUREA MAGISTRALE
	MATEMATICA
	2020/2021

CURRICULUM APPLICATIVO

	OBBLIGATORIO
	ANNO CORSO 1
	ANNO ORDINAMENTO 2018
	SECONDO SEMESTRE

MODULI

	SSD	CFU	ORE	ATTIVITÀ	TIPO DI ATTIVITÁ FORMATIVA
	MAT/09	6	48	LEZIONE	CARATTERIZZANTE

DOCENTI

	FRANCESCO CARRABS T Curriculum
	CIRIACO D'AMBROSIO Curriculum

	Obiettivi
	CONOSCENZA E CAPACITÀ DI COMPRENSIONE: IL CORSO DI OTTIMIZZAZIONE SI PROPONE DI APPROFONDIRE ED AMPLIARE LE CONOSCENZE SUI PROBLEMI DI PROGRAMMAZIONE LINEARE CONTINUA ED INTERA, INTRODOTTI NEL CORSO DI RICERCA OPERATIVA, CON PARTICOLARE RIGUARDO A CLASSI DI PROBLEMI DI RILEVANTE INTERESSE APPLICATIVO. IN PARTICOLARE, VERRANNO PRESENTATI ALGORITMI ALTERNATIVI AL METODO DEL SIMPLESSO PER LA RISOLUZIONE DI PROBLEMI DI PROGRAMMAZIONE LINEARE CONTINUA AVENTI UN ELEVATISSIMO NUMERO DI VINCOLI E VARIABILI. RELATIVAMENTE AI PROBLEMI DI OTTIMIZZAZIONE LINEARE A VARIABILI INTERE E BINARIE, IL CORSO SI PROPONE DI INSEGNARE I PRINCIPALI FONDAMENTI DI MODELLAZIONE MATEMATICA DI PROBLEMI DI OTTIMIZZAZIONE COMBINATORIALE E DI INTRODURRE I PRINCIPALI ALGORITMI RISOLUTIVI, SIA DI TIPO ESATTO SIA DI TIPO APPROSSIMATO. CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE CAPACITÀ DI FORMULARE PROBLEMI DECISIONALI DI INTERESSE APPLICATIVO TRAMITE OPPORTUNI MODELLI MATEMATICI A VARIABILI CONTINUE O INTERE A SECONDA DELLE ESIGENZE. CAPACITÀ DI RICONOSCERE LA COMPLESSITÀ COMPUTAZIONALE INTRINSECA NEL PROBLEMA DECISIONALE AFFRONTATO E, IN BASE AD ESSA, ESSERE IN GRADO DI INDIVIDUARE GLI ALGORITMI PIÙ EFFICACI DA UTILIZZARE PER RISOLVERE IL PROBLEMA. CAPACITÀ DI PROGETTARE ALGORITMI EURISTICI IN GRADO DI INDIVIDUARE IN BREVE TEMPO BUONE SOLUZIONI AMMISSIBILI PER IL PROBLEMA IN ESAME.

CONOSCENZA E CAPACITÀ DI COMPRENSIONE:
IL CORSO DI OTTIMIZZAZIONE SI PROPONE DI APPROFONDIRE ED AMPLIARE LE CONOSCENZE SUI PROBLEMI DI PROGRAMMAZIONE LINEARE CONTINUA ED INTERA, INTRODOTTI NEL CORSO DI RICERCA OPERATIVA, CON PARTICOLARE RIGUARDO A CLASSI DI PROBLEMI DI RILEVANTE INTERESSE APPLICATIVO. IN PARTICOLARE, VERRANNO PRESENTATI ALGORITMI ALTERNATIVI AL METODO DEL SIMPLESSO PER LA RISOLUZIONE DI PROBLEMI DI PROGRAMMAZIONE LINEARE CONTINUA AVENTI UN ELEVATISSIMO NUMERO DI VINCOLI E VARIABILI. RELATIVAMENTE AI PROBLEMI DI OTTIMIZZAZIONE LINEARE A VARIABILI INTERE E BINARIE, IL CORSO SI PROPONE DI INSEGNARE I PRINCIPALI FONDAMENTI DI MODELLAZIONE MATEMATICA DI PROBLEMI DI OTTIMIZZAZIONE COMBINATORIALE E DI INTRODURRE I PRINCIPALI ALGORITMI RISOLUTIVI, SIA DI TIPO ESATTO SIA DI TIPO APPROSSIMATO.

CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE
CAPACITÀ DI FORMULARE PROBLEMI DECISIONALI DI INTERESSE APPLICATIVO TRAMITE OPPORTUNI MODELLI MATEMATICI A VARIABILI CONTINUE O INTERE A SECONDA DELLE ESIGENZE.
CAPACITÀ DI RICONOSCERE LA COMPLESSITÀ COMPUTAZIONALE INTRINSECA NEL PROBLEMA DECISIONALE AFFRONTATO E, IN BASE AD ESSA, ESSERE IN GRADO DI INDIVIDUARE GLI ALGORITMI PIÙ EFFICACI DA UTILIZZARE PER RISOLVERE IL PROBLEMA.
CAPACITÀ DI PROGETTARE ALGORITMI EURISTICI IN GRADO DI INDIVIDUARE IN BREVE TEMPO BUONE SOLUZIONI AMMISSIBILI PER IL PROBLEMA IN ESAME.

	Prerequisiti
	PER SOSTENERE L'ESAME DI OTTIMIZZAZIONE LO STUDENTE DEVE AVER SUPERATO L'ESAME DI RICERCA OPERATIVA.

	Contenuti
	1. LA PROGRAMMAZIONE LINEARE (PL) (ORE LEZ. 12; ORE ESERC. 4) - CASO PATOLOGICO DEL METODO DEL SIMPLESSO: CUBO DI KLEE E MINTY; ALGORITMO DELL'ELLISSOIDE; TABLEAU DEL SIMPLESSO; - METODO DEL SIMPLESSO DUALE; - ALGORITMO PRIMALE-DUALE; - ALGORITMO DEL DELAYED COLUMN GENERATION; 2. PROGRAMMAZIONE LINEARE INTERA (PLI) (ORE LEZ. 26; ORE ESERC. 6) - VARIABILI E VINCOLI LOGICI; PROBLEMI CON FUNZIONI OBIETTIVO MULTIPLE; - PRINCIPALI CLASSI DI PROBLEMI COMBINATORI; - RILASSAMENTO LAGRANGIANO; BENDERS DECOMPOSITION; DISUGUAGLIANZE VALIDE; - METODI RISOLUTIVI DI TIPO ESATTO: BRANCH AND BOUND, PIANI DI TAGLIO, BRANCH AND CUT. - METODI RISOLUTIVI DI TIPO APPROSSIMATO: ALGORITMI DI RICERCA LOCALI, ALGORITMO GREEDY, TABU SEARCH, SIMULATED ANNEALING, ALGORITMO GENETICO;

Contenuti

1. LA PROGRAMMAZIONE LINEARE (PL) (ORE LEZ. 12; ORE ESERC. 4)
- CASO PATOLOGICO DEL METODO DEL SIMPLESSO: CUBO DI KLEE E MINTY; ALGORITMO DELL'ELLISSOIDE; TABLEAU DEL SIMPLESSO;
- METODO DEL SIMPLESSO DUALE;
- ALGORITMO PRIMALE-DUALE;
- ALGORITMO DEL DELAYED COLUMN GENERATION;

2. PROGRAMMAZIONE LINEARE INTERA (PLI) (ORE LEZ. 26; ORE ESERC. 6)
- VARIABILI E VINCOLI LOGICI; PROBLEMI CON FUNZIONI OBIETTIVO MULTIPLE;
- PRINCIPALI CLASSI DI PROBLEMI COMBINATORI;
- RILASSAMENTO LAGRANGIANO; BENDERS DECOMPOSITION; DISUGUAGLIANZE VALIDE;
- METODI RISOLUTIVI DI TIPO ESATTO: BRANCH AND BOUND, PIANI DI TAGLIO, BRANCH AND CUT.
- METODI RISOLUTIVI DI TIPO APPROSSIMATO: ALGORITMI DI RICERCA LOCALI, 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 E' GUIDATO DAL DOCENTE E TENDE A SVILUPPARE E RAFFORZARE LE CAPACITÀ DELL’ALLIEVO DI IDENTIFICARE LE TECNICHE PIÙ IDONEE ALLA RISOLUZIONE DELL’ESERCIZIO STESSO.

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 E' GUIDATO DAL DOCENTE E TENDE A SVILUPPARE E RAFFORZARE LE CAPACITÀ DELL’ALLIEVO DI IDENTIFICARE LE TECNICHE PIÙ IDONEE ALLA 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 TRENTESI E TIENE CONTO DELLA CAPACITÀ 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 DIMOSTRA INCERTEZZE NEL PRESENTARE GLI ARGOMENTI AFFRONTATI DURANTE IL CORSO E UNA SCARSA CAPACITÀ ESPOSITIVA. IL LIVELLO 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.

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 TRENTESI E TIENE CONTO DELLA CAPACITÀ 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 DIMOSTRA INCERTEZZE NEL PRESENTARE GLI ARGOMENTI AFFRONTATI DURANTE IL CORSO E UNA SCARSA CAPACITÀ ESPOSITIVA.

IL LIVELLO 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.

	Testi
	- CHRISTOS H. PAPADIMITRIOU: COMBINATORIAL OPTIMIZATION: ALGORITHMS AND COMPLEXITY - GEORGE L. NEMHAUSER, LAURENCE A. WOLSEY, INTEGER AND COMBINATORIAL OPTIMIZATION, 1999 - APPUNTI DELLE LEZIONI. PER APPROFONDIMENTI: LAURENCE A. WOLSEY, INTEGER PROGRAMMING, 1998.

	Altre Informazioni
	- IL CORSO È EROGATO IN ITALIANO. - LA FREQUENZA È CALDAMENTE CONSIGLIATA. - L’ORARIO DI RICEVIMENTO È DISPONIBILE A QUESTO LINK: HTTPS://DOCENTI.UNISA.IT/001227/HOME HTTPS://DOCENTI.UNISA.IT/020511/HOME

BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2022-05-23]

CIRIACO D'AMBROSIO | OTTIMIZZAZIONE