Ricerca operativa (2015/2016)

Codice insegnamento
4S00001
Docente
Romeo Rizzi
Coordinatore
Romeo Rizzi
crediti
6
Settore disciplinare
MAT/09 - RICERCA OPERATIVA
Lingua di erogazione
Italiano
Periodo
II semestre dal 1-mar-2016 al 10-giu-2016.

Orario lezioni

Obiettivi formativi

Il corso si propone di introdurre lo studente ad alcuni modelli ed ad alcune metodologie di base nel campo dell'Ottimizzazione, con particolare riferimento alla programmazione dinamica, all'ottimizzazione combinatorica, ai grafi, alla programmazione lineare. Vengono anche forniti cenni ed esempi di teoria della complessita' cercando di trasmetterne l'impatto metodologico. Viene inoltre illustrato il ruolo che la programmazione lineare intera riveste nella comunita' della ricerca operativa.

Programma

Nozioni di base: modelli ed algoritmi, complessita' computazionale, ricorsione ed induzione, invarianti e monovarianti, grafi, insiemi convessi, poliedri e coni.

Alcuni dei modelli in Programmazione Dinamica: massima sottosequenza crescente, massima sottosequenza comune, zaino pesato e non.

Alcuni dei modelli in grafi: cammini Euleriani ed Hamiltoniani, grafi planari e i loro duali, grafi bipartiti, cammini minimi, alberi ricoprenti di peso minimo, massimo flusso e minimo taglio, massimo matching.

Programmazione lineare: formulazione di problemi di programmazione lineare; forme equivalenti, forma standard; struttura matematica, approccio grafico, proprietà.
L’algoritmo del simplesso: vertici e soluzioni di base; condizioni di ottimalità; forma tableau del simplesso, il problema ausiliario; metodo delle due fasi.
Teoria della dualità: il teorema fondamentale di dualità; algoritmo del simplesso duale; interpretazione economica; analisi di sensitività.
Programmazione lineare intera: il metodo dei tagli, il branch and bound.
Ottimizzazione su reti: albero di supporto di costo minimo, cammino minimo, flusso massimo.

Un piu' esteso programma nelle intenzioni, un programma dell'edizione precedente, ed il programma giornaliero del corso sono disponibili alla pagina del corso:

http://profs.sci.univr.it/~rrizzi/classes/RO/index.html

Modalità d'esame

Prova scritta finale.

Trovate i testi degli scritti precedenti e relative correzioni alla pagina del corso:
http://profs.sci.univr.it/~rrizzi/classes/RO/index.html

La prova dura circa 4 ore ed avviene tipicamente in aula delta. Portarsi maglioncino, merendina, colori e fogli predisposti come reputate possano aiutarvi ad una migliore resa.

Opinione studenti frequentanti - 2015/2016