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. (CAP. 2, 5, PARTE DEL 6 E DEL 7).
[2] R. AHUJA, T. MAGNANTI, J. ORLIN, "NETWORK FLOWS", PRENTICE HALL, 1993. (PG. 189-191, 473-475, 494-496)
[3] DISPENSE FORNITE DAL DOCENTE E/O DISPONIBILI SUL WEB.

Modalità Erogazione

lezioni frontali, esercitazioni, prove in laboratorio informatico

Modalità Valutazione

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.