Corso di RICERCA OPERATIVA II

Laurea specialistica - percorso STI

Anno accademico: 2004-2005

Docente: Nome LOCATELLI

Numero di ore: 54
Numero di CFU (Crediti Formativi Universitari): 6

INDICE

1. Obiettivi del corso
2. Competenze attese e propedeuticità
3. Come si svolgono le lezioni (supporti alla didattica in uso alla docenza)
4. Programma/contenuti
5. Materiale didattico di supporto (a cura del docente)
6. Bibliografia (libri, articoli, documenti on-line,...)
7. Controllo dell'appprendimento (durante il corso)
8. Verifica (modalità d'esame)

1. Obiettivi del corso

Il corso verte sulla discussione di problemi di ottimizzazione, in particolare di problemi di ottimizzazione combinatoria, con brevi cenni all'ottimizzazione continua. Si pone come obiettivo quello di familiarizzare lo studente con problemi di ottimizzazione che occorrono frequentemente in applicazioni pratiche, permettendogli di riconoscere la difficoltà del problema (attraverso alcune nozioni di complessità) e fornendogli gli strumenti per risolvere tali problemi. Gli strumenti vanno dagli algoritmi esatti, in grado di restituire sempre la soluzione ottima di un problema, alle euristiche, alle quali ricorrere quando una risoluzione esatta del probema richiederebbe tempi di esecuzione troppo elevati.

2. Competenze attese e propedeuticità

• Competenze attese in ingresso (richieste all'inizio del corso). Per seguire il modulo è consigliabile avere chiare alcune nozioni apprese durante il corso di Ricerca Operativa I, in particolare quelle di problema di programmazione lineare e programmazione lineare intera e alcune sui grafi.
• Eventuali corsi propedeutici (forniscono le "competenze attese in ingresso"). Ricerca Operativa I
• Competenze attese in uscita (acquisite durante il corso). Al termine del modulo lo studente dovrebbe essere in grado di riconoscere un problema di ottimizzazione, essere conscio che la prima questione da porsi al riguardo di tale problema è quella di quanto sia difficile il problema, ovvero in quale classe di complessità esso rientri ed infine, almeno per quel che riguarda i problemi di ottimizzazione trattati a lezione, saper costruire i modelli matematici di tali problemi ed essere in grado di applicare le tecniche di risoluzione (esatte, approssimate o euristiche) viste.

3. Come si svolgono le lezioni (supporti alla didattica in uso alla docenza)

Le lezioni si tengono in aula e sono svolte tipicamente con l'ausilio di lavagna e gesso (più raramente con l'ausilio di lucidi)

4. Programma/contenuti

Definizione dei problemi di ottimizzazione. Alcune nozioni di complessità : classi P e NP, problemi NP-completi, problemi di approssimazione, euristiche. Problemi nella classe P. Problemi di flusso a costo minimo con l'algoritmo del simplesso specializzato per tali problemi. Problemi di flusso massimo e taglio minimo con l'algoritmo di Ford-Fulkerson. Problemi di matching. Problemi del trasporto con l'algoritmo del simplesso specializzato per questi problemi. Problemi di assegnamento con l'algoritmo ungherese per la loro risoluzione. Di tutti questi problemi viene fornito il modello matematico. Problemi NP-completi. Modelli matematici per i due casi visti a lezione: problema dello zaino e problema del commesso viaggiatore. Algoritmi esatti: tecniche di branch-and-bound con relativi esempi sui due problemi trattati; programmazione dinamica con un esempio sul problema dello zaino. Algoritmi di approssimazione: un esempio sul problema del commesso viaggiatore metrico. Tecniche euristiche: mosse greedy, ricerche locali, simulated annealing, algoritmi genetici. Ottimizzazione continua. Problemi vincolati e non vincolati. Ottimi globali e locali. Funzioni convesse. Condizioni di ottimalità. Procedure di ricerca locale nel caso non vincolato.

5. Materiale didattico di supporto (a cura del docente)

Vengono forniti on-line le dispense del corso, vari tipi di esercizi e i testi degli esami scritti degli anni precedenti, con le soluzioni .

6. Bibliografia (libri, articoli, documenti on-line,...)

• C.H. Papadimitriou, K.R. Steiglitz, "Combinatorial optimization: algorithms and complexity", Prentice Hall (solo per eventuali approfondimenti - reperibile in biblioteca)

7. Controllo dell'apprendimento (durante il corso)

Il controllo sull'apprendimento è basato sulla risoluzione in classe di alcuni esercizi durante la quale gli studenti possono interevenire e porre domande per dissipare eventuali dubbi. Le risoluzioni di alcuni esercizi sono fornite in anticipo agli studenti in modo da dar loro la possibilità di seguirle più facilmente.

8. Verifica (modalità d'esame)

La verifica si articolerà in una prova scritta dove verranno proposti esercizi del tipo di quelli risolti in aula e domande più legate alla teoria, attraverso cui si cerca di verificare quanto in profondità è andato lo studio da parte dello studente. Viene anche svolta una prova orale con discussione del compito ed eventuali domande di approfondimento. Viene inoltre data la possibiltà opzionale di implementare uno degli algoritmi visti a lezione.