OTTIMIZZAZIONE
Anno accademico 2019/2020 - 1° annoCrediti: 6
SSD: MAT/09 - Ricerca operativa
Organizzazione didattica: 150 ore d'impegno totale, 102 di studio individuale, 24 di lezione frontale, 24 di esercitazione
Semestre: 1°
Obiettivi formativi
Il corso è finalizzato ad introdurre le basi metodologiche dell’ottimizzazione matematica. Il corso si propone dunque di fornire gli strumenti analitici per formulare un modello matematico di un problema di scelta ottima reale, codificarlo opportunamente e interpretare la soluzione trovata come strategia operativa. Particolare enfasi sarà data alle applicazioni nei settori socio-economico, informatico e ingegneristico.
Alla fine del corso lo studente sarà in grado di formulare un modello matematico di un problema di vita reale, codificarlo nel linguaggio algebrico di riferimento (AMPL) ed interpretare la soluzione trovata.
L'obiettivo del corso è fornire agli studenti gli strumenti analitici e metodologici per affrontare problemi di ottimizzazione e le tecniche di modellazione matematica dei problemi decisionali. Gli studenti inoltre acquisiranno la conoscenza di alcuni algoritmi risolutivi di problemi di programmazione lineare e non lineare.
Gli studenti acquisiranno le competenze necessarie a riconoscere i problemi di ottimizzazione e sviluppare modelli matematici di problemi decisionali. In particolare, gli studenti saranno in grado di calcolare le soluzioni di problemi di programmazione lineare e non lineare e di implementare codici in AMPL.
Gli studenti acquisiranno autonomia nelle scelte modellistiche ed algoritmiche relative a problemi decisionali complessi e saranno in grado di interpretare la soluzione.
Gli studenti saranno in grado di sostenere una conversazione e di leggere testi su argomenti riguardanti la modellazione di problemi decisionali e acquisiranno ulteriori abilità comunicative e di appropriatezza espressiva nell'impiego del linguaggio tecnico. Saranno inoltre in grado di trasmettere la propria esperienza e conoscenza ad altri.
Il corso si propone di fornire agli studenti le conoscenze e le competenze nel campo dell'ottimizzazione e dei problemi di ottimizzazione che sorgono in varie aree, quali la matematica, l'informatica e l'ingegneria gestionale. Gli studenti avranno inoltre acquisito capacità di apprendere in modo autonomo.
Modalità di svolgimento dell'insegnamento
Il corso include lezioni frontali, esercitazioni e laboratorio. Per ogni argomento, saranno svolti alla lavagna vari esercizi. Altri esercizi saranno proposti agli studenti, che potranno svolgerli singolarmente o in gruppo.
Prerequisiti richiesti
Nessuno.
Frequenza lezioni
Fortemente consigliata.
Contenuti del corso
1. PROGRAMMAZIONE LINEARE
Problemi di PL. Algoritmo del Simplesso. Teoria della Dualità.
2. PROGRAMMAZIONE LINEARE INTERA
Esempi di problemi di PLI. Metodo dei piani di taglio. Metodo del
Branch and Bound. Problema dello zaino. Problema del commesso viaggiatore.
3. PROGRAMMAZIONE NON LINEARE
Condizioni di ottimalità. Metodi risolutivi per l'ottimizzazione vincolata e non vincolata.
4. SOFTWARE PER L'OTTIMIZZAZIONE MATEMATICA.
GeoGebra, Excel, AMPL, Mathematica.
Testi di riferimento
- R. Tadei, F. Della Croce, “Elementi di Ricerca Operativa”, Società Editrice Esculapio, 2005;
- R. Tadei, F. Della Croce, A. Grosso, “Fondamenti di Ottimizzazione”, Società Editrice Esculapio, 2005;
- R. Baldacci, M. Dell’Amico, “Fondamenti di Ricerca Operativa”, Pitagora Editrice, 2002;
- M. Bruglieri, A. Colorni, “Ricerca Operativa”, Zanichelli, 2012;
- M. Caramia, S. Giordani, F. Guerriero, R. Musmanno, D. Pacciarelli, “Ricerca Operativa”, Isedi, 2014
- F. Hillier, G.J. Liebermann, “Ricerca Operativa”, McGraw-Hill, 2006
- F. Fumero, Metodi di ottimizzazione. Esercizi ed applicazioni, Società Editrice Esculapio, 2013
- L. Grippo, M. Sciandrone, Metodi di Ottimizzazione Non Vincolata, Springer, Unitext 2011.
Programmazione del corso
Argomenti | Riferimenti testi | |
---|---|---|
1 | Modelli di programmazione lineare | 1,3,4,5,6 e dispense su Studium |
2 | Geometria della programmazione lineare | 1,3,4,5,6 e dispense su Studium |
3 | Algebra della programmazione lineare | 1,3,4,5,6 e dispense su Studium |
4 | Il metodo del simplesso | 1,3,4,5,6 e dispense su Studium |
5 | Dualità | 1,3,4,5,6 e dispense su Studium |
6 | Programmazione lineare intera | 2,3,4,5,6 e dispense su Studium |
7 | Modelli di programmazione lineare intera | 2,3,4,5,6 e dispense su Studium |
8 | Metodo dei piani di taglio | 2,3,4,5,6 e dispense su Studium |
9 | Metodo del branch and bound | 2,3,4,5,6 e dispense su Studium |
10 | Il problema dello zaino | 2 e dispense su Studium |
11 | Il problema del matching e dell'assegnamento | 2 e dispense su Studium |
12 | Il problema del commesso viaggiatore | 2 e dispense su Studium |
13 | Programmazione non lineare | 2, dispense su Studium |
14 | Condizioni di ottimalità per problemi vincolati e non vincolati | 2, dispense su Studium |
15 | Metodi risolutivi per problemi vincolati e non vincolati | 2, dispense su Studium |
16 | Implementazione in AMPL | dispense su Studium |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
Le competenze e le conoscenze acquisite dagli studenti saranno verificate tramite un esame orale con risoluzione di esercizi.
Sarà proposta agli studenti una prova in itinere in forma scritta riguardante la prima metà del programma e corrispondente a 3CFU. La prova in itinere non è obbligatoria e si svolgerà nel periodo previsto da CdS per lo svolgimento delle prove in itinere. Coloro che la supereranno, potranno svolgere l'esame finale, entro la sessione di ottobre 2019, solo sulla seconda parte del programma; tutti gli altri svolgeranno l'esame finale su tutto il programma.
Esempi di domande e/o esercizi frequenti
Risoluzione di un problema di programmazione lineare con il metodo del simplesso. Risoluzione di un problema di programmazione lineare intera con il metodo del Branch and Bound. Il problema dello zaino. Metodo dei tagli. Condizioni di ottimalità ed illimitatezza in programmazione lineare. Condizioni di ottimalità per problemi di ottimizzazione non vincolata. Condizioni KKT. Metodi di penalità e barriera. Risoluzione di problemi di programmazione lineare con GeoGebra o Excel. Codice in AMPL.