OTTIMIZZAZIONE
Anno accademico 2020/2021 - 1° annoCrediti: 6
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 a presentare le basi metodologiche dell’ottimizzazione matematica. L'obiettivo del corso è rendere gli studenti capaci di formulare problemi decisionali come problemi di programmazione lineare o non lineare e di risolverli utilizzando opportuni algoritmi numerici. Alla fine del corso lo studente sarà in grado di costruire un modello matematico di un problema decisionale reale e di interpretare la soluzione trovata come strategia operativa. Particolare enfasi sarà data alle applicazioni nei settori socio-economico, informatico e ingegneristico.
Il corso si propone di fornire le seguenti competenze:
Conoscenza e capacità di comprensione: acquisizione di conoscenze di base nell’ambito della programmazione lineare e non lineare e della modellizzazione matematica; capacità di riconoscere i problemi di ottimizzazione e sviluppare modelli matematici di problemi decisionali.
Capacità di applicare conoscenza e comprensione: capacità di applicare metodi numerici per calcolare le soluzioni di problemi decisionali complessi e di interpretare la soluzione; uso di ambienti e software per la programmazione matematica.
Autonomia di giudizio: acquisizione di consapevole autonomia di giudizio attraverso lo svolgimento autonomo delle esercitazioni in aula e in laboratorio.
Abilità comunicative: capacità di sostenere una conversazione e/o di leggere testi su argomenti riguardanti la modellazione di problemi decisionali; appropriatezza espressiva nell'impiego del linguaggio tecnico; capacità di trasmettere la propria esperienza e conoscenza ad altri.
Capacità di apprendimento: acquisizione di adeguate capacità per lo sviluppo e l'approfondimento di ulteriori competenze; conseguimento di una preparazione di base e di una autonomia di studio che consenta agli studenti di consultare libri di testo avanzati e riviste specializzate nei settori di ricerca dell'ottimizzazione matematica.
Modalità di svolgimento dell'insegnamento
Il corso comprende lezioni frontali, esercitazioni in aula e, se consentito, presso i laboratori informatici. Per ogni argomento, saranno svolti dal docente vari esercizi e saranno organizzate esercitazioni guidate.
Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte le necessarie variazioni rispetto a quanto dichiarato in precedenza, al fine di rispettare il programma previsto e riportato nel syllabus.
Prerequisiti richiesti
Nessuno.
Frequenza lezioni
Fortemente consigliata.
Contenuti del corso
1. PROGRAMMAZIONE LINEARE (circa 12 ore)
Problemi di PL. Algoritmo del Simplesso. Teoria della Dualità.
2. PROGRAMMAZIONE LINEARE INTERA (circa 5 ore)
Esempi di problemi di PLI. Metodo dei piani di taglio. Metodo del Branch and Bound. Problema dello zaino. Il commesso viaggiatore.
3. TEORIA DEI GIOCHI (circa 3 ore)
Giochi non cooperativi statici. Equilibri di Nash. Giochi a somma nulla. Soluzioni di minimax e programmazione lineare.
3. PROGRAMMAZIONE NON LINEARE (circa 4 ore)
Condizioni di ottimalità. Metodi risolutivi per l'ottimizzazione vincolata e non vincolata.
4. SOFTWARE PER L'OTTIMIZZAZIONE MATEMATICA. (circa 24 ore)
GeoGebra, Excel, AMPL, Mathematica.
Testi di riferimento
[1] R. Tadei, F. Della Croce, “Elementi di Ricerca Operativa”, Società Editrice Esculapio, 2010;
[2] R. Baldacci, M. Dell’Amico, “Fondamenti di Ricerca Operativa”, Pitagora Editrice, 2002
[3] M. Bruglieri, A. Colorni, “Ricerca Operativa”, Zanichelli, 2012;
[4] F. Fumero, Metodi di ottimizzazione. Esercizi ed applicazioni, Società Editrice Esculapio, 2013
Programmazione del corso
| Argomenti | Riferimenti testi | |
|---|---|---|
| 1 | Introduzione e Modelli di programmazione lineare | [1] Capitoli 1 e 2; [2] Capitoli 1 e 2; [3] Capitoli 1 e 2; [4] Parte I Capitolo 1 e Parte II Capitolo 1 |
| 2 | Metodo grafico per la programmazione lineare | [2] Capitolo 3; [3] Capitolo 8; [4] Parte I Capitolo 2 e Parte II Capitolo 2; dispense del docente |
| 3 | Geometria della programmazione lineare | [2] Capitolo 3; [3] Capitolo 8; |
| 4 | Algebra della programmazione lineare | [1] Capitolo 3; [2] Capitolo 3; [3] Capitolo 8; dispense del docente |
| 5 | Il metodo del simplesso | [1] Capitolo 3; [2] Capitolo 3; [3] Capitolo 8; [4] Parte I Capitolo 3 e Parte II Capitolo 3 |
| 6 | Dualità | [1] Capitolo 4; [2] Capitolo 3; [3] Capitolo 9; dispense del docente |
| 7 | Programmazione lineare intera | [2] Capitolo 4; [3] Capitolo 10; [4] Parte I Capitolo 5 e Parte II Capitolo 5; dispense del docente |
| 8 | Metodo dei piani di taglio | [2] Capitolo 4; [3] Capitolo 10; [4] Parte I Capitolo 5 e Parte II Capitolo 5; dispense del docente |
| 9 | Metodo del branch and bound | [2] Capitolo 4; [3] Capitolo 10; [4] Parte I Capitolo 5 e Parte II Capitolo 5; del docente |
| 10 | Il problema dello zaino | [3] Capitolo 10 |
| 11 | Il problema del commesso viaggiatore | [3] Capitolo 12 |
| 12 | Equilibri di Nash | [3] Capitolo 17; dispense del docente |
| 13 | Giochi a somma nulla | [3] Capitolo 17; dispense del docente |
| 14 | Programmazione non lineare | [3] Capitolo 4 |
| 15 | Condizioni di ottimalità per problemi vincolati e non vincolati | [3] Capitolo 4 |
| 16 | Metodi risolutivi per problemi vincolati e non vincolati | [3] Capitolo 5; dispense del docente |
| 17 | Geogebra, Excel e AMPL | [3] Capitolo 7; dispense del docente |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
Le competenze e le conoscenze acquisite dagli studenti saranno verificate tramite un esame orale con risoluzione analitica di esercizi o con impiego di software per il calcolo scientifico.
La verifica dell’apprendimento potrà essere effettuata anche per via telematica, qualora le condizioni lo dovessero richiedere.
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.