UNIVERSITÀ di UDINE
Corso di Laurea in Informatica
Programma del corso di
Ricerca Operativa
a.a. 1998-99
docente: Paolo Serafini
Finalità: La Ricerca Operativa si occupa di problemi di gestione efficiente tramite l'applicazione sistematica di modelli matematici e di tecniche informatiche. Dei diversi aspetti della Ricerca Operativa (modellistico, matematico e informatico) il corso presenterà soprattutto il primo attraverso una serie di esempi che motiveranno la teoria matematica ed algoritmica. I modelli verranno svolti in classe usando il pacchetto Lingo.
1) INTRODUZIONE ALLA PROGRAMMAZIONE LINEARE (12 ore)
Problema della dieta: Formulazione dei vincoli e degli obiettivi. Risoluzione con Lingo. Analisi di sensibilità. Identificazione di ulteriori obiettivi. Costruzione della frontiera efficiente. Introduzione dei vincoli di interezza. Risoluzione. Raffinamento del modello. Soluzioni finali. Altri semplici modelli di PL: problemi di miscelazione e di 'product-mix'. Utilizzo del Lingo.
2) PROPRIETÀ DELLA PROGRAMMAZIONE LINEARE (6 ore)
Struttura geometrica. Vertici e soluzioni di base. Problema duale. Complementarità. Cenni sul metodo del simplesso. Cenni sul metodo 'branch-and-bound' per variabili intere.
3) MODELLI DI ROUTING (8)
Cammini minimi (algoritmo di Dijkstra) e massimi. Problema del commesso viaggiatore (formulazione con piani di taglio). Minimo albero di supporto (algoritmi di Kruskal e Prim).
4) MODELLI SU RETI DI FLUSSO (6)
Flusso a costo minimo. Massimo flusso. Assegnamento. Trasporto. PL su reti di flusso.
5) MODELLI DI OTTIMIZZAZIONE COMBINATORIA (14)
Accoppiamento. Assegnamento tridimensionale. 'Knapsack'. 'Bin packing'. Modelli di 'staffing'. PL con generazione di colonne: 'cutting stock', massimo flusso, 'crew scheduling'.
6) MODELLI DI PROGRAMMAZIONE DINAMICA DETERMINISTICA (4)
Principio di ottimalità. Equazione ricorsiva. Algoritmi per reti con cicli e reti acicliche. Cammini minimi (Floyd-Warshall). Problemi di 'Knapsack'. Esempi: 'string matching', determinazione fermate autobus, gestione di un magazzino.
7) MODELLI DI DECISIONE IN CONDIZIONE DI INCERTEZZA (4)
Alberi di decisione. Funzione di utilità. Lotterie equivalenti. Probabilità soggettive. Tecniche Bayesiane di valutazione delle probabilità. PL stocastica: formulazione a diversi stadi con diversi scenari.
8) MODELLI DI PROGRAMMAZIONE DINAMICA STOCASTICA (6)
Catene di Markov. Processi Markoviani di decisione a orizzonte finito. Definizione del problema. Calcolo ricorsivo dell'ottimo. MDP a orizzonte infinito con fattore di sconto. Valutazione di una politica. Calcolo dell'ottimo. MDP a orizzonte infinito con guadagno medio. Uso della Programmazione lineare.
Testo di riferimento principale: LINDO: An optimization modeling system, L. Schrage, Palo Alto Scientific Press, 1991;
Altri testi di riferimento
Modalità d'esame
L'esame consiste in una prova orale sul contenuto del corso. Gli studenti che volessero svolgere un progetto di medie dimensioni su tematiche di Ricerca Operativa utilizzando le strutture di laboratorio sono consigliati di inserire nel proprio piano di studi anche il corso "Laboratorio di Ricerca Operativa"
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)