Ricerca operativa
A.A. 2020/2021
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 non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Secondo semestre
Le lezioni in modalità sincrona verranno registrate e rese disponibili on-line per la fruizione asincrona. Alcune lezioni potranno essere pre-registrate; in tal caso le lezioni previste dall'orario costituiranno momento di revisione e approfondimento di quanto proposto in modalità asincrona.
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à. 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.
· 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.
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à. 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.
· 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.
Algoritmi. Algoritmi per l'ottimizzazione mono-dimensionale. Metodi iterativi, algoritmo del gradiente.
Prerequisiti
Algebra lineare
Metodi didattici
Il corso si svolge mediante lezioni ed esercitazioni frontali
Materiale di riferimento
C. Vercellis: "Modelli e Decisioni", Ed. Esculapio, Bologna 1997.
R.Tadei, F. Della Croce: "Ricerca Operativa e Ottimizzazione", Ed. Esculapio, Bologna 2002
Ricerca Operativa
M. Caramia, S. Giordani, F. Guerriero, R. Musmanno, D. Pacciarelli,
ISEDI, 2015
M. Fischetti: Lezioni di Ricerca Operativa,
Edizioni Libreria Progetto, Padova
M. Dell'Amico: 120 esercizi di ricerca operativa,
Pitagora Editrice, Bologna
R.Tadei, F. Della Croce: "Ricerca Operativa e Ottimizzazione", Ed. Esculapio, Bologna 2002
Ricerca Operativa
M. Caramia, S. Giordani, F. Guerriero, R. Musmanno, D. Pacciarelli,
ISEDI, 2015
M. Fischetti: Lezioni di Ricerca Operativa,
Edizioni Libreria Progetto, Padova
M. Dell'Amico: 120 esercizi di ricerca operativa,
Pitagora Editrice, Bologna
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 vengono proposti allo studente due o tre 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. Nella prova orale si verifica la conoscenza dei contenuti teorici del corso. Il peso della prova orale è di 6/30.
Nella prova scritta in laboratorio vengono proposti allo studente due o tre 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. Nella prova orale si verifica la conoscenza dei contenuti teorici del corso. Il peso della prova orale è di 6/30.
Docente/i