Titolo insegnamento in inglese: Operations Research
Lingua: italiano
Insegnamento: Ricerca Operativa
Anno di corso: II
CFU: 6
Semestre: 1
Docenti:
- Canale unico: Paola Festa
Insegnamenti propedeutici previsti
Algoritmi e strutture dati I
Obiettivi Formativi
L'insegnamento si prefigge quale obiettivo principale l'introduzione degli studenti all'uso dei modelli di programmazione matematica ed in particolare ai modelli di ottimizzazione lineare (sia continui che a variabili intere) ed alle loro applicazioni nei campi della logistica, dei servizi e della produzione industriale. L'impostazione metodologica del Corso, inoltre, punta al conseguimento dei seguenti ulteriori obiettivi intermedi:
• capacità di formalizzazione dei modelli di ottimizzazione per problemi di logistica, organizza-zione, pianificazione, scheduling, trasporto, flusso su reti e problemi su grafi ed alberi;
• conoscenza della teoria e dei metodi di ottimizzazione lineare continua, di ottimizzazione lineare discreta e di ottimizzazione su grafi, alberi e reti di flusso;
• capacità di utilizzazione dei modelli matematici dei classici problemi di ottimizzazione e dei relativi algoritmi di risoluzione nei campi della Pianificazione della Produzione, della Localizzazione, della Gestione delle Scorte e della Logistica.
Contenuti
Problemi di Programmazione Lineare e Metodo del Simplesso. Definizione e classificazione dei problemi di ottimizzazione e dei problemi di decisione e classificazione dei relativi metodi risolutivi (metodi esatti, metodi di approssimazione e metodi euristici). Programmazione Lineare (PL): il Metodo del Simplesso. Problemi di Programmazione Lineare Intera (1 credito) Metodi esatti per la risoluzione dei problemi di Programmazione Lineare Intera (Branch & Bound; piani di taglio; programmazione dinamica). Esempi di problemi di PLI con matrice dei vincoli uni-modulare: il problema del trasporto ed il problema dell'assegnamento. Problemi dello Zaino. Un algoritmo Branch and Bound per il problema dello Zaino 0/1; un algoritmo greedy per il problema dello Zaino Frazionario; due algoritmi di Programmazione Dinamica per il problema dello Zaino 0/1. Problemi di Ottimizzazione su grafi ed alberi: Vertex Cover ed Albero di Copertura Minimo. Il problema del Vertex Cover: un algoritmo 2-approssimato per il problema del Vertex Cover. Il problema dell'albero di copertura di un grafo a costo minimo (MST): l'algoritmo di Kruskal. Problemi di Ottimizzazione su grafi ed alberi: Problemi di Cammino Minimo. Cammini in un grafo orientato: il problema della raggiungibilità (visita in ampiezza; visita in profondità). Il problema dei cammini minimi: l'algoritmo di Dijkstra; l'algoritmo di Floyd e Warshall. Problemi di Ottimizzazione su grafi ed alberi: Pianificazione di un Progetto e Problema del Massimo Flusso. Pianificazione di un progetto: il Metodo CPM. Problemi di flusso su reti: il problema del massimo flusso; teorema max-flow mincut; algoritmo di Ford-Fulkerson.
Modalità didattiche
Lezioni frontali. Esercitazioni.
Modalità di esame
L'esame si articola in prova scritta e orale.
La prova scritta è a risposta libera, con esercizi numerici.