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.
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
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.
