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

Modulo 1

a. 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 sistemi e reti, data mining, logistica, biologia computazionale ed applicazioni informatiche.

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

Modulo 2

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 e slide a cura dei docenti 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.

Metodi didattici

Lezioni frontali. Esercitazioni numeriche sui diversi algoritmi per la risoluzione di problemi di PL, PLI, SST, CM e FR.

Implementazione in laboratorio mediante linguaggi di programmazione ed uso di risolutori.

Modalità di verifica e valutazione dell'apprendimento

• Esercizi basati sulla risoluzione di problemi di SST, CM e FR. Esercizi sui diversi algoritmi illustrati.

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

Strumenti a supporto della didattica

Materiale didattico, dispense, slides, esercizi ed esempi di codice disponibili in rete. Uso di linguaggi di programmazione e risolutori.

Orario di ricevimento

Consulta il sito web di Daniele Vigo

Consulta il sito web di Roberto Baldacci