SITE TITLE

LOGO DIETI

Ricerca operativa

Titolo insegnamento in inglese: Operations Research

Lingua: Italiano

Insegnamento: Ricerca operativa

Anno di corso: III

CFU: 6

SSD: MAT/09

Ore di lezione: 48

Semestre: 1

Modulo: Nessuno

Codice: 26266-26427

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 min-cut; algoritmo di Ford-Fulkerson.

Propedeuticità: Algoritmi e strutture dati I

Modalità didattiche: Lezioni frontali. Esercitazioni.

Materiale didattico: 

Appunti e Dispense del Corso

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008

Modalità di esame: 

L'esame si articola in prova

Scritta e orale

 

 

 

     

 

 

 

 

 

 

 

 

 

 

 

In caso di prova scritta i quesiti sono

 

 

 

A risposta libera

 

 

Esercizi numerici

 

Altro

 

Docente : Festa Paola