 |
Mauro DELL'AMICO
Professore Ordinario
Dipartimento di Scienze e Metodi dell'Ingegneria
|
Insegnamento: Ricerca Operativa
Ingegneria Informatica (MO) (Offerta formativa 2023)
Obiettivi formativi
Fornire la basi delle tecniche di Ricerca Operativa
Prerequisiti
Conoscenze di algebra lineare e programmazione
Programma del corso
Introduzione alla ricerca operativa.
Programmazione lineare 3CFU
Soluzione ingenua di semplici LP
Le operazioni Tableau e Pivot
L'algoritmo Simplex (nozioni di base)
Gestione di problemi non limitati
Geometria del Simplex Inizializzazione del Simplex
Ciclo di degenerazione e uso della regola di Bland
Notazione matriciale Dualità: variabili duali e programma lineare duale
Teorema della dualità forte
Condizioni di ortogobnalità
Comprendere il problema duale: i costi ombra
Analisi di sensibilità
Programmazione lineare intera 2CFU
Variabili intere e variabili a valore reale
Metodo del piano di taglio (generalità e tagli di Gomory)
Metodo Branch and Bound (generalità, strategie di ricerca, B&B per il problema di knapsack, B&B standard per PLI)
Programmazione dinamica (generalità, DP per il problema di knapsack 01, versione del peso e versione del costo, algoritmo di Bellman-Ford per il problema del percorso più breve)
Complessità computazionale 0,5CFU
Generalità
Teoria dei grafi 0.5CFU
Generalità
Problema del percorso più breve (algoritmo di Dijkstra)
Metodi didattici
Lezioni frontali, lezioni online ed esercitazioni d'aula
Testi di riferimento
R. Baldacci, M. Dell'Amico
Fondamenti di Ricerca Operativa,
Pitagoraed. - Bologna
M. Dell'Amico
120 Esercizi di Ricerca Operativa
Pitagora ed. - Bologna
Verifica dell'apprendimento
Esame scritto
Si compone di tre parti
1 Alcune domande di teoria
contenuto: domande riguardanti la parte teorica del corso (definizioni, teoremi, ecc.)
durata 25'
non sono ammessi testi o appunti
non è ammessa la calcolatrice
2 Modello matematico
contenuto:
progettazione di un modello di programmazione lineare per un problema dato
sono ammessi testi e appunti
è consentita la calcolatrice
3 Esercizii di programmazione lineare e teoria dei grafi
contenuto: soluzione di 2 esercizi numerici su : programmazione lineare, programmazione intera, teoria dei grafi.
sono ammessi testi e appunti
è consentita la calcolatrice
Le parti 2-3 hanno una durata complessiva di 1:30-2:00 ore
Valutazione: parte 1: da -5 a 10 (punteggio minimo 3), parte 2 e 3: fino a 27
Dopo l'esame scritto
Il docente può richiedere un'interrogazione orale per valutare il voto finale.
Lo studente può richiedere un'interrogazione orale per valutare il voto finale.
L'orale determina il voto finale che può essere superiore o inferiore al voto dell'esame scritto, di solito di 4 punti al massimo.
Risultati attesi
Conoscenza e capacità di comprensione: comprendere le caratteristiche di problemi di ottimizzazione e decisione.
Capacità di applicare conoscenze e e comprensione : Capacità di scrivere modelli di problemi di ottimizzazione e decisione.
Capacità di risolvere semplici problemi applicati di PLC e PLI