UNIVERSITÀ di UDINE

Corso di Laurea in Matematica

Programma del corso di

Ricerca Operativa

a.a. 1999-2000

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, teoria dei giochi) 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

PROGRAMMAZIONE NON LINEARE

Metodo del gradiente. Metodo di Newton.

TEORIA DELLE DECISIONI

Criteri in caso di incertezza. Criteri in caso di rischio. Valore atteso dell'informazione. Utilizzazione di informazione aggiuntiva tramite il teorema di Bayes. Alberi di decisione. Valutazione della funzione di utilità tramite lotterie. Valutazione soggettiva delle probabilità tramite lotterie.

OTTIMIZZAZIONE A MOLTI OBIETTIVI

Pareto ottimalità. Strutture di ordine. Funzione di utilità. Teorema di Arrow. Programmazione a molti attributi. Programmazione a molti obiettivi. Tecniche di scalarizzazione. Tecniche interattive.

TEORIA DEI GIOCHI

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

SCHEDULING

Pert. Problemi ad una macchina. Macchine parallele. Modelli job shop.

ROUTING

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

MODULO II

TEORIA DELLE CODE D'ATTESA

Catene di Markov a stati finiti. 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. Formula di Pollaczek-Khinchin.

PROCESSI MARKOVIANI DI DECISIONE

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.

MODELLI DI RICERCA OPERATIVA

Vari casi di applicazioni con utilizzo di pacchetti software (Lingo, Mathematica, Cplex).