Nuova ricerca

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