Docente

Prof. Paolo serafini paolo.serafini@uniud.it sito web

Crediti

6 CFU

Finalità

La Ricerca Operativa si occupa di problemi di gestione efficiente affrontati con modelli matematici e algoritmici. Il corso vuole fornire allo studente gli strumenti principali per progettare un modello a partire da un problema reale e la necessaria comprensione delle strutture matematiche e algoritmiche dei modelli, con particolare riguardo alla programmazione lineare. A questo fine vengono presentati doversi modelli e per la maggior parte i modelli sono risolti usando Excel o pacchetti di programmazione lineare.

Programma

- Introduzione alla programmazione lineare
Modellizzazione: identificazione delle grandezze, dei vincoli e degli obiettivi. Ottimi di Pareto. 
Esempio della dieta: modello di programmazione lineare. Analisi di sensibilità. Identificazione di ulteriori obiettivi. Frontiera efficiente. Vincoli di interezza.

- Proprietà della programmazione lineare
Struttura geometrica. Vertici e soluzioni di base. Problema duale. Complementarità. Cenni del metodo del simplesso. Metodo branch-and-bound per variabili intere.

- Modelli di percorsi 
Programmazione Dinamica. Principio di ottimalità. Equazione ricorsiva. Cammini minimi (Bellman-Ford, Dijkstra, Floyd-Warshall).

- Modelli di percorsi con capacità
Cammini minimi con capacità: reti di flusso. Flussi di costo minimo. Massimo flusso. Minimi tagli. Esempi di applicazione dei flussi: assegnazione seggi elettorali.

- Modelli di percorsi con vincoli sui nodi o sugli archi
Problema del commesso viaggiatore (formulazione con piani di taglio). Circuiti Euleriani. Minimi alberi di supporto (Kruskal e Prim).

- Modelli di allocazione
Assegnamento. Accoppiamento. Esempi di applicazioni ad eventi sportivi. Knapsack. Bin packing. Modelli di turnazione. Generazione di colonne: cutting stock, massimo flusso. Vehicle routing problems.

- Schedulazione 
Schedulazione a risorsa infinita: PERT. Schedulazione a risorsa finita: problemi a una macchina, macchine parallele, flow-shop, job-shop e open-shop. Schedulazione periodica.

Il piano dettagliato delle lezioni si trova al sito http://users.dimi.uniud.it/~paolo.serafini/ROINF****.html

Bibliografia

Paolo Serafini, Ricerca Operativa, Springer, 2009.
Paolo Serafini, Ottimizzazione, Zanichelli, Bologna 2000.
L. Schrage, LINDO: An optimization modeling system, Palo Alto Scientific Press, 1991

Modalità d'esame

Esame orale con possibilità di presentare e discutere un progettino.