Ricerca operativa
A.A. 2019/2020
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
Linea Crema
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à. 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 analitici, funzione Lagrangeana, condizioni di Karush-Kuhn-Tucker. 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 analitici, funzione Lagrangeana, condizioni di Karush-Kuhn-Tucker. Metodi iterativi, algoritmo del gradiente.
Prerequisiti
Algebra lineare, algoritmi.
Metodi didattici
Lezioni frontali ed esercitazioni in laboratorio.
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
R.Tadei, F. Della Croce: "Ricerca Operativa e Ottimizzazione", Ed. Esculapio, Bologna 2002
Modalità di verifica dell’apprendimento e criteri di valutazione
Prova pratica e prova orale.
MAT/09 - RICERCA OPERATIVA - CFU: 6
Lezioni: 48 ore
Docente:
Righini Giovanni
Turni:
-
Docente:
Righini GiovanniDocente/i