Ricerca operativa
A.A. 2023/2024
Obiettivi formativi
L'insegnamento si propone di introdurre la Ricerca Operativa, ossia lo studio scientifico dei metodi per risolvere problemi decisionali complessi con l'aiuto del calcolatore. Lo scopo è imparare a costruire modelli matematici di problemi di ottimizzazione, saper classificare i modelli e conoscere i fondamenti matematici delle tecniche algoritmiche che ne consentono la soluzione.
Risultati apprendimento attesi
Gli studenti svilupperanno la capacità di riconoscere problemi di ottimizzazione in diversi contesti, la capacità di formularli in termini matematici, di classificarli e conosceranno le proprietà matematiche che stanno alla base degli algoritmi sviluppati per risolverli.
Periodo: Secondo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento può essere seguito come corso singolo.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Secondo semestre
Programma
Introduzione:
· Introduzione alla Ricerca Operativa. Origini, applicazioni, relazioni con altre discipline.
· Modelli matematici. Dati, variabili, vincoli, funzioni obiettivo, decisori.
Programmazione lineare (PL):
· Applicazioni. Esempi di problemi di programmazione lineare.
· Definizioni e proprietà. Forma generale dei problemi di PL, forma alle disuguaglianze con relativa interpretazione geometrica, forma standard. Soluzioni di base e teorema fondamentale della PL.
· Dualità. Lemma di Farkas. Teorema della dualità in forma debole ed in forma forte. Teorema degli scarti complementari. Interpretazione economica della PL.
· Algoritmi. Forme canoniche. Algoritmo del simplesso primale e duale.
· Algoritmo del simplesso rivisto.
· Analisi post-ottimale. Analisi di sensitività e analisi parametrica.
Programmazione a molti obiettivi (PMO):
· Applicazioni. Esempi di problemi di programmazione a molti-obiettivi.
· Definizioni e proprietà. Dominanza, soluzioni di Pareto, regione Pareto-ottima, punto-utopia.
· Algoritmi per la determinazione della regione Pareto-ottima. Metodo dei pesi. Metodo dei vincoli. Interpretazione geometrica. Soluzione di esercizi di programmazione lineare a due obiettivi tramite analisi parametrica.
· Criteri per la scelta della soluzione. Criterio degli standard, criterio delle curve di indifferenza, criterio del punto-utopia, criterio della massima curvatura.
Programmazione lineare intera (PLI):
· Applicazioni. Esempi di problemi di programmazione lineare intera e di ottimizzazione combinatoria. Uso delle variabili binarie per la modellizzazione di condizioni logiche.
· Definizioni e proprietà. Rilassamento continuo, gap di integralità. Altri tipi di rilassamento.
· Algoritmi. Branch-and-bound.
Programmazione non lineare (PNL):
· Applicazioni. Esempi di problemi di programmazione non lineare.
· Definizioni e proprietà. Vettore gradiente, matrice Hessiana. Convessità e programmazione convessa. Condizioni KKT per la programmazione non-lineare vincolata.
· Algoritmi. Algoritmi per l'ottimizzazione mono-dimensionale. Metodi iterativi, algoritmo del gradiente.
· Introduzione alla Ricerca Operativa. Origini, applicazioni, relazioni con altre discipline.
· Modelli matematici. Dati, variabili, vincoli, funzioni obiettivo, decisori.
Programmazione lineare (PL):
· Applicazioni. Esempi di problemi di programmazione lineare.
· Definizioni e proprietà. Forma generale dei problemi di PL, forma alle disuguaglianze con relativa interpretazione geometrica, forma standard. Soluzioni di base e teorema fondamentale della PL.
· Dualità. Lemma di Farkas. Teorema della dualità in forma debole ed in forma forte. Teorema degli scarti complementari. Interpretazione economica della PL.
· Algoritmi. Forme canoniche. Algoritmo del simplesso primale e duale.
· Algoritmo del simplesso rivisto.
· Analisi post-ottimale. Analisi di sensitività e analisi parametrica.
Programmazione a molti obiettivi (PMO):
· Applicazioni. Esempi di problemi di programmazione a molti-obiettivi.
· Definizioni e proprietà. Dominanza, soluzioni di Pareto, regione Pareto-ottima, punto-utopia.
· Algoritmi per la determinazione della regione Pareto-ottima. Metodo dei pesi. Metodo dei vincoli. Interpretazione geometrica. Soluzione di esercizi di programmazione lineare a due obiettivi tramite analisi parametrica.
· Criteri per la scelta della soluzione. Criterio degli standard, criterio delle curve di indifferenza, criterio del punto-utopia, criterio della massima curvatura.
Programmazione lineare intera (PLI):
· Applicazioni. Esempi di problemi di programmazione lineare intera e di ottimizzazione combinatoria. Uso delle variabili binarie per la modellizzazione di condizioni logiche.
· Definizioni e proprietà. Rilassamento continuo, gap di integralità. Altri tipi di rilassamento.
· Algoritmi. Branch-and-bound.
Programmazione non lineare (PNL):
· Applicazioni. Esempi di problemi di programmazione non lineare.
· Definizioni e proprietà. Vettore gradiente, matrice Hessiana. Convessità e programmazione convessa. Condizioni KKT per la programmazione non-lineare vincolata.
· Algoritmi. Algoritmi per l'ottimizzazione mono-dimensionale. Metodi iterativi, algoritmo del gradiente.
Prerequisiti
Algebra lineare
Metodi didattici
L'insegnamento è impartito mediante lezioni ed esercitazioni frontali. E' fortemente consigliata la frequenza, soprattutto alle esercitazioni.
Materiale di riferimento
M. Caramia, S. Giordani, F. Guerriero, R. Musmanno, D. Pacciarelli,
Ricerca Operativa
ISEDI, 2015
M. Fischetti: Lezioni di Ricerca Operativa,
Edizioni Libreria Progetto, Padova
Ricerca Operativa
ISEDI, 2015
M. Fischetti: Lezioni di Ricerca Operativa,
Edizioni Libreria Progetto, Padova
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste in due prove, una in laboratorio e una orale.
Nella prova scritta in laboratorio (durata 3 ore) vengono proposti allo studente alcuni esercizi in cui si richiede che lo studente scriva il modello matematico di un problema di ottimizzazione descritto in linguaggio naturale, lo risolva con l'uso di un solutore di programmazione matematica e ne interpreti correttamente l'output, rispondendo ad alcune domande. Il risultato è un intervallo (di 6/30) nel quale cade il voto finale. L'esito della prova scritta viene comunicato sulla webpage dell'insegnamento. Nella prova orale si verifica la conoscenza dei contenuti teorici dell'insegnamento.
Nella prova scritta in laboratorio (durata 3 ore) vengono proposti allo studente alcuni esercizi in cui si richiede che lo studente scriva il modello matematico di un problema di ottimizzazione descritto in linguaggio naturale, lo risolva con l'uso di un solutore di programmazione matematica e ne interpreti correttamente l'output, rispondendo ad alcune domande. Il risultato è un intervallo (di 6/30) nel quale cade il voto finale. L'esito della prova scritta viene comunicato sulla webpage dell'insegnamento. Nella prova orale si verifica la conoscenza dei contenuti teorici dell'insegnamento.
Siti didattici
Docente/i