UNIVERSITÀ di UDINE

Corso di Laurea in Informatica

Programma del corso di

Ricerca Operativa

a.a. 1999-2000

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 (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 (16)

Cammini minimi (algoritmo di Dijkstra) 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. Minimo albero di supporto (algoritmi di Kruskal e Prim). Modelli a reti di flusso. Flusso a costo minimo. Massimo flusso. Trasporto.

4) MODELLI DI ALLOCAZIONE (14)

Assegnamento. Assegnamento tridimensionale. `Knapsack'. `Bin packing'. Modelli di `staffing'. PL con generazione di colonne: `cutting stock', massimo flusso, `crew scheduling'.

5) MODELLI DI SCHEDULAZIONE (14)

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 e open-shop. Esempi di applicazioni.

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)