Insegnamento
RICERCA OPERATIVA 1
IN11112347, A.A. 2013/14

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea magistrale in
INGEGNERIA INFORMATICA
IN0521, ordinamento 2009/10, A.A. 2013/14
1085735
Crediti formativi 9.0
Denominazione inglese OPERATIONS RESEARCH 1
Dipartimento di riferimento Dipartimento di Ingegneria dell'Informazione (DEI)
Obbligo di frequenza No
Lingua di erogazione ITALIANO
Sede PADOVA

Docenti
Responsabile MATTEO FISCHETTI MAT/09

Mutuazioni
Codice Insegnamento Responsabile Corso
IN11112347 RICERCA OPERATIVA 1 MATTEO FISCHETTI IN0524

Dettaglio crediti formativi
Tipologia Ambito Disciplinare Settore Scientifico-Disciplinare Crediti
AFFINE/INTEGRATIVA Attività formative affini o integrative MAT/09 9.0

Modalità di erogazione
Periodo di erogazione Primo semestre
Anno di corso I Anno
Modalità di erogazione frontale

Organizzazione della didattica
Tipo ore Crediti Ore di
Corso
Ore Studio
Individuale
Turni
LEZIONE 9.0 72 153.0 Nessun turno

Calendario
Inizio attività didattiche 26/09/2016
Fine attività didattiche 25/01/2014

Commissioni d'esame
Commissione Dal Al Membri
7 A.A. 2016/2017 01/10/2016 15/03/2018 FISCHETTI MATTEO (Presidente)
SALVAGNIN DOMENICO (Membro Effettivo)
ROMANIN JACUR GIORGIO (Supplente)
6 A.A. 2015/2016 01/10/2015 15/03/2017 FISCHETTI MATTEO (Presidente)
MONACI MICHELE (Membro Effettivo)
ROMANIN JACUR GIORGIO (Supplente)
5 A.A. 2014/2015 01/10/2014 15/03/2016 FISCHETTI MATTEO (Presidente)
MONACI MICHELE (Membro Effettivo)
ROMANIN JACUR GIORGIO (Supplente)
SALVAGNIN DOMENICO (Supplente)
01/10/2013 15/03/2015 FISCHETTI MATTEO (Presidente)
MONACI MICHELE (Membro Effettivo)
SALVAGNIN DOMENICO (Supplente)

Syllabus
Prerequisiti: Nozioni di base di informatica e di calcolo matriciale
Conoscenze e abilita' da acquisire: Individuare e classificare un modello matematico di decisione (decisori, obiettivi, variabili, vincoli, dati, contesto decisionale). Conoscere i fondamenti della Ricerca Operativa, ed in particolare le tecniche di ottimizzazione per problemi di tipo lineare e di tipo combinatorio, applicandole ad esempi (semplificati) di interesse applicativo.
Modalita' di esame: Tradizionale
Criteri di valutazione: Prova scritta
Contenuti: Problemi di ottimizzazione. Programmazione Lineare (PL). Programmazione Lineare Intera (PLI). Teoria della Complessita` Computazionale. Teoria dei Grafi. Problemi NP-completi.
Attivita' di apprendimento previste e metodologie di insegnamento: Problemi di ottimizzazione: Programmazione matematica e programmazione convessa.
Programmazione Lineare (PL) : Generalita`. Modelli di PL. Geometria della PL. Algoritmo del simplesso: metodo delle 2 fasi, forma matriciale e tableau, simplesso rivisto. Degenerazione. Dualita` in PL. Algoritmo del simplesso duale. Analisi di sensitivita`.
Programmazione Lineare Intera (PLI): Modelli di PLI. Totale unimodularita`. Metodo dei piani di taglio di Chvatal-Gomory. Algoritmo branch-and-bound. Problema di separazione ed algoritmo branch-and-cut.
Teoria della Complessita` Computazionale: Classi P, NP, co-NP e problemi NP-completi. Riduzioni polinomiali.
Teoria dei Grafi: Definizioni. Problemi polinomiali (con modelli ed algoritmi di risoluzione): albero minimo, cammini minimi, flussi.
Problemi NP-completi (con modelli ed algoritmi di risoluzione): knapsack, commesso viaggiatore, set covering e set packing, alberi di Steiner, plant location.
Eventuali indicazioni sui materiali di studio:
Testi di riferimento:
  • Matteo Fischetti, Lezioni di Ricerca Operativa. Padova: Progetto, 1999. Cerca nel catalogo