Programma del corso di Ricerca Operativa II

 

 

 

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): Algoritmi di PD per il knapsack 0-1, intero capacitato e non capacitato.

Ottimizzazione su grafi: Matching, Minimo vertex cover, Massimo Flusso, Massimo stabile. Grafi euleriani e grafi bipartiti.

Utilizzo di un software commerciale per la soluzione di problemi di programmazione matematica.

 

 

 

Testi di riferimento:

[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.