Programma

INTRODUZIONE ALLA PROGRAMMAZIONE LINEARE A NUMERI INTERI (PLI): RELAZIONE FRA PL E PLI, FORMULAZIONI EQUIVALENTI, RILASSAMENTI, MATRICI TOTALMENTE UNIMODULARI, TECNICHE STANDARD PER LA FORMULAZIONE DI PROBLEMI DI PLI. FORMULAZIONE DI TIPICI PROBLEMI DI OTTIMIZZAZIONE: LOCALIZZAZIONE DI IMPIANTI, SCELTA DI INVESTIMENTI, SEQUENZIAMENTO DI ATTIVITÀ, OTTIMIZZAZIONE SU RETI, TRASPORTI, SET COVERING, SET PARTITIONING, SET PACKING, TURNI DEL PERSONALE.SOLUZIONE ESATTA DI PROBLEMI DI PROGRAMMAZIONE LINEARE A NUMERI INTERI: BRANCH AND BOUND, IL PROBLEMA DI KNAPSACK, PIANI DI TAGLIO.METODI DI PROGRAMMAZIONE DINAMICA (PD): ALGORITMO DI PD PER IL KNAPSACK CAPACITATO, ALGORITMO DI PD PER IL KNAPSACK INTERO NON CAPACITATO.OTTIMIZZAZIONE SU GRAFI: MATCHING, MINIMO COVER, MASSIMO FLUSSO, MASSIMO STABILE. GRAFI EULERIANI E GRAFI BIPARTITI.UTILIZZO DI UN SOFTWARE COMMERCIALE PER LA SOLUZIONE DI PROBLEMI DI PROGRAMMAZIONE MATEMATICA.

Testi Adottati

[1] M. FISCHETTI, "LEZIONI DI RICERCA OPERATIVA", EDIZIONI LIBRERIA PROGETTO PADOVA, ITALIA, 1995. (CHAP. 2, 5, part of 6 and 7).
[2] R. AHUJA, T. MAGNANTI, J. ORLIN, "NETWORK FLOWS", PRENTICE HALL, 1993. (PG. 189-191, 473-475, 494-496)
[3] Dispense del docente disponibili sulla pagina web del corso

Modalità Erogazione

principalmente didattica frontale: lezioni in aula alla lavagna, qualche lezione in laboratorio

Modalità Valutazione

Scritto e orale La verifica dell’apprendimento avviene attraverso una prova scritta della durata di circa 2 ore e da una prova orale da svolgersi nello stello appello. Lo scritto è organizzato attraverso un certo numero di esercizi (tipicamente da 3 a 5), finalizzati a verificare il livello di comprensione effettiva dei concetti più teorici e la capacità degli studenti di applicare le tecniche spiegate a lezione.