UNIVERSITÀ di UDINE
Corso di Laurea in Matematica
Programma del corso di
Ricerca Operativa
a.a. 1997-98
doc. Paolo Serafini; ric. Franca Rinaldi
Finalità: Il primo modulo completa gli argomenti del precedente corso di ottimizzazione, fornendo le basi matematiche e le conoscenze algoritmiche per diversi modelli di ricerca operativa. 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. Nel secondo modulo si affrontano tipiche tecniche stocastiche di ricerca operativa per affrontare problemi di code d'attesa e di decisione a multiperiodo. L'enfasi nel secondo modulo sarà posta maggiormente sull'aspetto modellistico della ricerca operativa, studiando quegli argomenti, quali la teoria delle decisioni, l'ottimizzazione a molti obiettivi e la teoria dei giochi, che permettono di dare un fondamento rigoroso alla fase modellistica. Verranno inoltre forniti esempi concreti di modelli tipici di ricerca operativa.
MODULO I
DUALITÀ (10)
Definizioni. Condizioni di ottimalità. Esempi. Dualità e convessità. Proprietà differenziali della dualità. Dualità e sensibilità.
RETI DI FLUSSO (18)
Condizioni di ottimalità: curva Gamma. Rete residua. Algoritmi polinomiali per Cammino minimo (algoritmo di Dijkstra) e Massimo flusso. Strutture dati per Cammino minimo. Ammissibilità primale con massimo flusso, e duale con cammino minimo. Metodo `out of kilter'. Algoritmi di riscalamento. Applicazione al problema dell'assegnamento pesato. Simplesso su reti di flusso.
PROGRAMMAZIONE DINAMICA DETERMINISTICA (12)
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 controllo ottimo. Problemi di ottimizzazione combinatoria.
ALGORITMI APPROSSIMATI (8)
Definizioni. Algoritmi per Delta-TSP e per `knapsack'. Schemi di approssimazione polinomiali e completamente polinomiali. Algoritmi approssimati per `Bin-packing'. Complessità computazionale e approssimabilità. Approssimazione e PL.
RICERCA LOCALE (4)
Definizioni. Applicazione al TSP. Simulated annealing. Altre euristiche.
PROGRAMMAZIONE NON LINEARE (10)
Ricerca unidimensionale. Metodo del gradiente. Velocità di convergenza. Metodo di Newton. Problemi con vincoli. Problemi non differenziabili
METODI AI PUNTI INTERNI (6)
Metodo di Karmarkar. Metodi di barriera.
MODULO II
TEORIA DELLE CODE D'ATTESA (12)
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 (12)
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 DECISIONI (6)
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 (6)
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 (12)
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.
MODELLI DI RICERCA OPERATIVA (24)
Modelli di `staffing'. Modelli PERT deterministici e stocastici, `crashing'. Modelli multiperiodo determistici e stocastici. `Multicommodity flows'. Modelli di PL intera. Schedulazione.