Anno accademico 2018-2019
RICERCA OPERATIVA
Docenti:
Lancia Giuseppe
Lancia Giuseppe
Anno di corso: 1
Totale crediti: 6
Tipologia: Affine/Integrativa
Periodo didattico: Primo Periodo
Lingua insegnamento: INGLESE
Prerequisiti.
Nozioni di base di matematica discreta, teoria dei grafi, algebra lineare, algoritmi e programmazione
Nozioni di base di matematica discreta, teoria dei grafi, algebra lineare, algoritmi e programmazione
Metodi didattici.
Lezione alla lavagna con uso occasionale di strumenti software di ottimizzazione
Lezione alla lavagna con uso occasionale di strumenti software di ottimizzazione
Modalità di verifica.
Esame scritto con sia domande a scelta multipla che aperte (problemi). I problemi consistono principalmente nella formulazione di un modello matematico (vincoli, variabili e obiettivo) per un problema descritto in termini concreti. Altri problemi possono riguardare l’applicazione di un particolare algoritmo visto a lezione su un insieme di dati specificato.
Esame scritto con sia domande a scelta multipla che aperte (problemi). I problemi consistono principalmente nella formulazione di un modello matematico (vincoli, variabili e obiettivo) per un problema descritto in termini concreti. Altri problemi possono riguardare l’applicazione di un particolare algoritmo visto a lezione su un insieme di dati specificato.
Altre informazioni.
Nessuna
Nessuna
OBIETTIVI FORMATIVI
L’obiettivo culturale del corso è quello di presentare le principali metodologie modellistiche utilizzate nella risoluzione di problemi di ottimizzazione, cercando di distinguere fra problemi facili (polinomiali) e difficili (NP-hard).
Per i primi, lo studente dovrebbe essere in grado di riconoscere un approccio della letteratura ed applicare il relativo algoritmo standard, adattandolo magari al caso specifico. Per i secondi, lo studente dovrebbe essere in grado di disegnare un modello di programmazione lineare intera, individuando vincoli e variabili, da risolvere poi con strumenti software standard per questo tipo di modelli.
CONTENUTI
Vengono presentate le principali metodologie modellistiche e tecniche risolutive utilizzate per problemi di ottimizzazione, sia trattabili che computazionalmente difficili. Vengono definite le tecniche di programmazione matematica basate sulla programmazione lineare, a variabili continue e intere. Viene studiata la geometria della programmazione lineare (poliedri), la dualità, il metodo del branch-and-bound e dei piani di taglio, le matrici totalmente unimodulari. Vengono richiamati i concetti fondamentali di complessità computazionale (problemi polinomiali e NP-hard). Vengono definiti alcuni problemi standard di ottimizzazione su grafi, quali il cammino minimo e massimo, il problema dell’accoppiamento massimo, dell’assegnamento, del minimo albero di supporto, del massimo flusso, del taglio di costo minimo e massimo, del commesso viaggiatore, della copertura di vertici, dell’insieme indipendente. Per i problemi polinomiali, vengono descritti gli algortimi combinatorici della letteratura. Vengono inoltre discussi approcci alternativi tramite modelli di programmazione lineare (intera).
TESTI DI RIFERIMENTO
Dispense del docente. “Ottimizzazione” di Paolo Serafini (Zanichelli). “Lezioni di Ricerca Operativa” di Matteo Fischetti (Libreria Progetto)
