Fornire conoscenze di base, sia metodologiche che quantitative, per la rappresentazione e la soluzione di problemi di ottimizzazione.
Preparare gli studenti all'uso dei modelli di programmazione matematica con particolare attenzione rivolta ai modelli di ottimizzazione a variabili intere e ad alcune loro applicazioni.
Preparare gli studenti all'uso dei modelli di programmazione matematica con particolare attenzione rivolta ai modelli di ottimizzazione a variabili intere e ad alcune loro applicazioni.
scheda docente
materiale didattico
Introduzione alla programmazione lineare a numeri interi (PLI): relazione fra PL e PLI, formulazioni equivalenti, rilassamenti, tecniche standard per la formulazione di problemi di PLI.
Formulazione di tipici problemi di ottimizzazione: localizzazione di impianti, scelta di investimenti, sequenziamento di attività, allocazione di risorse in sistemi informatici, 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, piani di taglio, tecniche di programmazione dinamica (PD).
Matrici totalmente unimodulari.
Il problema di knapsack: branch and bound, algoritmo di PD, dis. cover.
Ottimizzazione su grafi: matching, vertex cover. Grafi euleriani e grafi bipartiti.
Utilizzo di software commerciali per la soluzione di problemi di programmazione matematica.
[2] R. AHUJA, T. MAGNANTI, J. ORLIN, "NETWORK FLOWS", PRENTICE HALL, 1993. (pagine 189-191, 473-475, 494-496)
[3] DISPENSE FORNITE DAL DOCENTE E/O DISPONIBILI SUL WEB.
Programma
Descrizione del processo decisionale.Introduzione alla programmazione lineare a numeri interi (PLI): relazione fra PL e PLI, formulazioni equivalenti, rilassamenti, tecniche standard per la formulazione di problemi di PLI.
Formulazione di tipici problemi di ottimizzazione: localizzazione di impianti, scelta di investimenti, sequenziamento di attività, allocazione di risorse in sistemi informatici, 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, piani di taglio, tecniche di programmazione dinamica (PD).
Matrici totalmente unimodulari.
Il problema di knapsack: branch and bound, algoritmo di PD, dis. cover.
Ottimizzazione su grafi: matching, vertex cover. Grafi euleriani e grafi bipartiti.
Utilizzo di software commerciali 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. (pagine 189-191, 473-475, 494-496)
[3] DISPENSE FORNITE DAL DOCENTE E/O DISPONIBILI SUL WEB.
Modalità Erogazione
Principalmente didattica frontale: lezioni in aula alla lavagna, qualche lezione in laboratorio per l'utilizzo di software commerciali.Modalità Frequenza
Preferibilmente in presenza. In ogni caso, il materiale didattico fornito offre la possibilità agli studenti non frequentanti di prepararsi per l'esame.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.