Ricerca operativa

A.A. 2021/2022
6
Crediti massimi
48
Ore totali
SSD
MAT/09
Lingua
Italiano
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.
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.
Prerequisiti
Algebra lineare
Metodi didattici
Il corso si svolge 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
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 del corso. Nella prova orale si verifica la conoscenza dei contenuti teorici del corso.
MAT/09 - RICERCA OPERATIVA - CFU: 6
Lezioni: 48 ore
Docente/i
Ricevimento:
su appuntamento
via Celoria 18, terzo piano