UNIVERSITÀ di UDINE

Corso di Laurea in Matematica

Programma del corso di

Ricerca Operativa

a.a. 2002-03

docenti: Franca Rinaldi e Paolo Serafini

Finalità: I due moduli completano gli argomenti del precedente corso di ottimizzazione e offrono una panoramica di tematiche modellistiche sia di tipo teorico (teoria delle decisioni, programmazione a molti obiettivi) che pratico (scheduling, routing, ecc). Inoltre nel secondo modulo si affrontano tipiche tecniche stocastiche di ricerca operativa per affrontare problemi di code d'attesa e di decisione a multiperiodo. Alla fine lo studente dovrebbe essere in grado di individuare il modello matematico più idoneo a rappresentare un problema reale e a fornire possibili soluzioni.

MODULO I

(F. Rinaldi)

PROGRAMMAZIONE DINAMICA (12 ore):

Principio di ottimalità. Equazione di Bellman. Algoritmo di Bellman-Ford per reti generali. Algoritmo per reti acicliche e a livelli. Algoritmo di Floyd-Warshall. Problemi di `knapsack'. Problemi di ottimizzazione combinatoria.

ALGORITMI APPROSSIMATI ED EURISTICI (10) :

Algoritmi approssimati. Ricerca locale. Metodi greedy. Disaggregazione. Tabu search. Simulated annealing.

ROUTING (13)

Problemi di Arc routing. Problemi di Node routing. Routing di veicoli con capacità.

SCHEDULING (13)

Pert. Problemi ad una macchina. Macchine parallele. Problemi Shop-scheduling.

MODULO II

(P. Serafini)

PROCESSI MARKOVIANI DI DECISIONE (15)

Catene di Markov a stati finiti. Formulazione del processo ad orizzonte finito. Valutazione delle politiche e calcolo della politica ottima. Formulazione ad orizzonte infinito con fattore di sconto e con guadagno medio. Risoluzione con la programmazione dinamica e con la programmazione lineare.

TEORIA DELLE CODE D'ATTESA (19)

Processi Markoviani a stati finiti. Processi nascita-morte. Processi di Poisson. Code M/M. Catene di Markov "embedded". Code M/G/1, M/D/1 e M/Er/1. Tempo residuo. Formula di Pollaczek-Khinchin.

TEORIA DELLE DECISIONI (6)

Alberi di decisione Valutazione delle decisioni ottime. Funzione di utilità e lotterie. Valore atteso dell'informazione. Utilizzazione di informazione aggiuntiva tramite il teorema di Bayes. Valutazione soggettiva delle probabilità tramite lotterie. Programmazione lineare stocastica.

TEORIA DEI GIOCHI (8)

Forma estesa e forma normale. Giochi a somma zero. Strategie pure e miste. Esistenza della soluzione e programmazione lineare. Giochi a somma non costante. Equilibrio di Nash. Valore di negoziato. Giochi a n persone. Coalizioni e imputazioni. Nucleo di un gioco. Valore di Shapley.

Modalità d'esame

È prevista una prova orale per ognuno dei moduli.

Per ulteriori informazioni sulla ricerca operativa e sull'ottimizzazione si consulti il sito dell'INFORMS (Institute for Operations Research and Management Science) oppure quello del CIRO (Centro Interuniversitario in Ricerca Operativa)