UNIVERSITÀ di UDINE

Corso di Laurea in Informatica

Programma del corso di

Ricerca Operativa

a.a. 2001-2002

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 (6 ore)

Aspetti generali di modellizzazione: identificazione dei vincoli, vincoli rigidi e vincoli flessibili; identificazione degli obiettivi; vincoli e obiettivi. Obiettivi espliciti: ottimi secondo Pareto. Esempio del problema della dieta: modellizzazione con la programmazione lineare e risoluzione con Lingo. Analisi di sensibilità. Identificazione di ulteriori obiettivi. Costruzione della frontiera efficiente. Introduzione dei vincoli di interezza. Raffinamento del modello.

2) PROPRIETÀ DELLA PROGRAMMAZIONE LINEARE (8)

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 PERCORSI (12)

Cammini minimi e massimi. Programmazione dinamica. Principio di ottimalità. Equazione ricorsiva. Algoritmi per reti con cicli e acicliche. Cammini minimi (Floyd- Warshall). Problema del commesso viaggiatore (formulazione con piani di taglio). Circuiti euleriani e accoppiamento. Modelli a reti di flusso. Flusso a costo minimo. Massimo flusso. Trasporto.

4) MODELLI DI ALLOCAZIONE (12)

Assegnamento. `Knapsack'. `Bin packing'. PL con generazione di colonne: `bin packing', massimo flusso, `multicommodity flow'.

5) MODELLI DI SCHEDULAZIONE (12)

Schedulazione a risorsa infinita (solo precedenze): PERT. Schedulazione a risorsa finita: Problemi ad una macchina (varie formulazioni). Problemi a più macchine: job-shop, flow-shop.

Testi di riferimento principali:

Paolo Serafini, Ottimizzazione , Zanichelli, Bologna 2000.

L. Schrage, LINDO: An optimization modeling system, Palo Alto Scientific Press, 1991;

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)