Contenuti
Analisi della sensitività e analisi parametrica. Analisi post-ottimale per la Programmazione Lineare.
Ottimizzazione su rete: problemi di cammino minimo, massimo flusso e flusso a costo minimo. Il metodo del simplesso per problemi di ottimizzazione su reti.
Metodi a punti interni per la Programmazione Lineare: caratteristiche generali e condizioni di convergenza.
Programmazione Lineare Intera: il problema dello zaino, il problema del Commesso Viaggiatore, problemi di Bin-Packing. Formulazioni e Algoritmi risolutivi (cenni).
Obiettivi
D1 - Conoscenza e capacità di comprensione
Risultati attesi:
1 Padroneggiare i principali strumenti teorici per problemi di ottimizzazione su rete
2. Conoscere gli aspetti fondamentali degli algoritmi a punti interni per la soluzione di problemi di Programmazione Lineare
3. Conoscere le principali caratteristiche di specifici problemi di Programmazione Lineare Intera.
D2 - Capacità di applicare conoscenza e comprensione
Risultati attesi:
1 Conoscere i principali algoritmi risolutivi per problemi di ottimizzazione su rete.
2 Affrontare le problematiche relativa all’analisi postottimale nella Programmazione Lineare.
3 Modellizzare problemi di Programmazione Lineare Intera
D3 - Autonomia di giudizio
Risultati attesi:
1 Interpretare le informazioni ottenute risolvendo un problema di programmazione lineare (PL) o intera (PLI) o su grafo.
2 Valutare diverse tecniche modellistiche basate su grafi e scegliere specifici algoritmi risolutivi ed identificarne punti di forza e debolezza.
D4 - Abilità comunicative
Risultati attesi:
1 Discutere i principali aspetti (ammissibilità, ottimalità, etc) relativi alla Programmazione Lineare Intera e su rete.
D5 - Capacità di apprendimento
Risultati attesi:
1 Studiare in maniera indipendente recenti sviluppi algoritmici dell’area.
2.Approfondire gli aspetti teorici ed algoritmici dell’analisi post-ottimale nella Programmazione Lineare.
3. Approfondire gli aspetti teorici ed algoritmici dell’ottimizzazione su rete.
Prerequisiti
Algebra lineare.
Operazioni su matrici e vettori.
Soluzione di sistemi di equazioni lineari.
Elementi di Programmazione Lineare
Metodi Didattici
Il corso prevede lezioni frontali e attività di laboratorio. In particolare, le attività di laboratorio saranno dedicate alla formulazione e soluzione di problemi di ottimizzazione su rete.
Verifica dell'apprendimento
La prova finale consta di un esame orale volto all’accertamento della conoscenza degli aspetti teorici ed algoritmici dell’ottimizzazione su rete, analisi della sensitività e Programmazione Lineare Intera.
Sono previsti appelli di esame a giugno/luglio, a settembre/ottobre ed a febbraio. Gli appelli di Dicembre ed Aprile sono riservati ai fuori corso. Non sono previsti appelli di esame durante il periodo di svolgimento dei corsi.
Testi
F.S. Hillier, G.J. Lieberman Ricerca Operativa, nona edizione, McGraw--Hill 2010
R.K. Ahuja, T.L. Magnanti, J.B. Orlin Network flows: theory, algorithms, and applications Prentice Hall, 1993
S. Wright Primal--Dual Interior--Point Methods SIAM, 1996.
L. A. Wolsey, G.L. Nemhauser, Integer and Combinatorial, Optimization, Wiley 1999 (Chapter II.2)
