Contenuti

Introduzione alla Ricerca Operativa.
Aspetti algebrici e geometrici di base della Programmazione Lineare e della Programmazione Intera. 
Insiemi convessi ed insiemi poliedrali.
I concetti di punto estremo, vertice e soluzione di base.
Risoluzione grafica di problemi in 2 dimensioni.
Algoritmo del Simplesso: struttura e proprietà. Le due fasi del metodo del simplesso. Convergenza dell'algoritmo.
Teoria della dualità: costruzione del problema duale, interpretazione economica della dualità. Teoremi di dualità. Complementarità.
Problemi classici di PLI e principali tecniche di modellizzazione.
Modellizzazione mediante variabili intere e binarie.
Disuguaglianze valide per PLI. Metodi risolutivi per problemi di PLI. Branch & Bound.
Il problema dello zaino.
Il problema del Commesso Viaggiatore

Obiettivi

D1 - Conoscenza e capacità di comprensione
Risultati attesi:
1 Illustrare e distinguere gli aspetti geometrici di base della Programmazione Lineare 
2 Conoscere la teoria della dualità nella Programmazione Lineare
3 Saper illustrare le condizioni di ottimalità della Programmazione Lineare


D2 - Capacità di applicare conoscenza e comprensione
Risultati attesi:
1 Modellizzare semplici problemi di programmazione lineare e intera
2 Risolvere problemi di Programmazione Lineare mediante il metodo del Simplesso.
3 Utilizzare semplici software per la soluzione di problemi PL e PLI.
4 Utilizzare efficientemente un semplice linguaggio di specifica algebrica

D3 - Autonomia di giudizio
Risultati attesi:
1 Valutare la complessità dei modelli di Programmazione Lineare adottati, e degli strumenti necessari alla loro soluzione.
2 Interpretare le informazioni ottenute risolvendo un problema di programmazione lineare (PL) o intera (PLI).

D4 - Abilità comunicative
Risultati attesi:
1 Discutere i principali aspetti (ammissibilità, ottimalità, etc) relativi alla Programmazione Lineare.


D5 - Capacità di apprendimento
Risultati attesi:
1 Approfondire, mediante studio personale, gli aspetti più recenti della Programmazione Lineare
2 Studiare in maniera indipendente recenti sviluppi algoritmici dell’area.

Prerequisiti

Algebra lineare.
Operazioni su matrici e vettori.
Soluzione di sistemi di equazioni lineari.

Metodi Didattici

Il corso prevede lezioni frontali ed esercitazioni guidate in aula. In particolare le esercitazioni saranno dedicate alla soluzione di problemi di Programmazione Lineare mediante il metodo del simplesso ed all'apprendimento di semplici tecniche di modellazione matematica.

Verifica dell'apprendimento

La prova finale consta di uno scritto ed un orale. La prova scritta è orientata alla verifica delle conoscenze e competenze acquisite relative agli aspetti geometrici della Programmazione Lineare (vertici, BFS etc) ed alla risoluzione di problemi di Programmazione Lineare mediante il metodo del simplesso. La prova orale sarà volta all’accertamento che gli aspetti teorici relativi alla Programmazione Lineare siano stati correttamente acquisiti.

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. De Leone, C. Lazzari Esercizi di programmazione Lineare e Programmazione Lineare Intera, Aracne, 2007
M. Bruglieri, A. Colorni Ricerca Operativa, Zanichelli 2012.
A. Sassano Modelli e Algoritmi della Ricerca Operativa, Franco Angeli, 1999
R. Tadei e F. Della Croce Ricerca Operativa e Ottimizzazione, Seconda Edizione, Società Editrice Esculapio, 2002

Sono disponibili online note relative agli algebrici e geometrici di base della Programmazione Lineare, al metodo del simplesso ed alle condizioni di ottimalità nella Programmazione Lineare.

Latest News