00884 - RICERCA OPERATIVA

Conoscenze e abilità da conseguire

Al termine del corso, lo studente conosce i principali modelli ed algoritmi per la programmazione lineare e intera.

Contenuti

1. Modelli matematici di problemi di ottimizzazione

Definizione di modello matematico, variabili decisionali, funzione obiettivo e requisiti o vincoli. Tecniche di modellizzazione matematica.

Esempi di modelli matematici tratti da problemi del mondo reale.

2. Programmazione Lineare Continua (PLC) ed intera (PLI).

Modelli matematici a variabili continue. Risoluzione geometrica. Teoria della PLC ed algoritmo del simplesso

Modelli matematici a variabili intere. Interpretazione geometrica. Proprietà dei problemi di PLI. Tecniche di rilassamento. Algoritmi cutting-plane (CP). Metodo branch-and-bound (B&B). Applicazioni della tecnica B&B.

3. Elementi di teoria dei grafi e principali problemi.

Principali definizioni della teoria dei grafi. Alberi di supporto di costo minimo (SST). Cammini minimi (CM). Problemi di flusso in rete (FR), flusso massimo, flusso a costo minimo. Assegnamento lineare.

Testi/Bibliografia

Dispense/slide a cura del docente disponibili online

Testi per sola consultazione:

• Matteo Fischetti, Lezioni di Ricerca Operativa, Libreria Progetto.
• C. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, NY.
• R.K.Ahuja, T.L.Magnanti, J.B.Orlin, "Network flows: theory, algorithms and applications", Prentice Hall.
• M. Gondran, M. Minoux, “Graphs and Algorithms”, John Wiley.
• M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows, Wiley.

Metodi didattici

Lezioni ed esercitazioni in aula

Modalità di verifica e valutazione dell'apprendimento

La verifica dell'apprendimento avviene mediante una prova scritta, che ha lo scopo di esaminare l'acquisizione delle conoscenze previste dal programma del corso.

 

Orario di ricevimento

Consulta il sito web di Alessandro Hill