|
Insegnamento
RICERCA OPERATIVA 1
IN11112347, A.A. 2019/20
Informazioni valide per gli studenti immatricolati nell'A.A. 2019/20
Dettaglio crediti formativi
Tipologia |
Ambito Disciplinare |
Settore Scientifico-Disciplinare |
Crediti |
AFFINE/INTEGRATIVA |
Attività formative affini o integrative |
MAT/09 |
9.0 |
Organizzazione dell'insegnamento
Periodo di erogazione |
Primo semestre |
Anno di corso |
I Anno |
Modalità di erogazione |
frontale |
Tipo ore |
Crediti |
Ore di didattica assistita |
Ore Studio Individuale |
LEZIONE |
9.0 |
72 |
153.0 |
Inizio attività didattiche |
30/09/2019 |
Fine attività didattiche |
18/01/2020 |
Visualizza il calendario delle lezioni |
Lezioni 2019/20 Ord.2009
|
Commissioni d'esame
Commissione |
Dal |
Al |
Membri |
10 A.A. 2019/2020 |
01/10/2019 |
15/03/2021 |
FISCHETTI
MATTEO
(Presidente)
SALVAGNIN
DOMENICO
(Membro Effettivo)
FERRANTE
AUGUSTO
(Supplente)
FERRARI
CARLO
(Supplente)
|
9 A.A. 2018/2019 |
01/10/2018 |
15/03/2020 |
FISCHETTI
MATTEO
(Presidente)
SALVAGNIN
DOMENICO
(Membro Effettivo)
FERRANTE
AUGUSTO
(Supplente)
PIETRACAPRINA
ANDREA ALBERTO
(Supplente)
|
Prerequisiti:
|
Nozioni di base di informatica e di calcolo matriciale |
Conoscenze e abilita' da acquisire:
|
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. Essere in grado di classificare un modello matematico di decisione (decisori, obiettivi, variabili, vincoli, dati, contesto decisionale). |
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.
|
|
|