Corso di RICERCA OPERATIVA I

Laurea in INFORMATICA - percorso STISI

Anno accademico: 2007-2008

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 principalmente sulla modelizzazione di problemi reali attraverso modelli di Programmazione Lineare e Programmazione Lineare Intera con le relative tecniche di risoluzione. Il corso si pone come obiettivo quello di rendere lo studente capace di costruire almeno modelli semplici, di conoscere i metodi di risoluzione per tali modelli e la teoria che li sottende. L'attenzione č rivolta anche alla capacitą di saper interpretare i risultati ottenuti, in particolare cercando di capire quanto questi siano sensibili rispetto a variazioni dei dati (analisi di sensitivitą). Allo studente vengono anche presentati nozioni basilari sui grafi e il problema del trasporto.

2. Competenze attese e propedeuticità

• Competenze attese in ingresso (richieste all'inizio del corso). L'organizzazione del modulo presuppone una buona conoscenza del calcolo vettoriale e matriciale, necessaria per poter comprendere il funzionamento delle tecniche di risoluzione presentate (algoritmo del simplesso per problemi di PL, algoritmi di taglio e branch-and-bound per i problemi di PLI).
• Eventuali corsi propedeutici (forniscono le "competenze attese in ingresso"). Matematica Discreta.
• Competenze attese in uscita (acquisite durante il corso). Al termine del modulo lo studente dovrebbe essere in grado di costruire modelli di Programmazione Lineare e Programmazione Lineare Intera a partire da problemi reali non eccessivamente complessi. Inoltre, lo studente dovrebbe essere in grado di riconoscere i principi basilari della teoria dei problemi di PL e PLI e riconsocere come questa venga utilizzata nella definizione dei metodi di risoluzione. Infine, lo studente dovrebbe essere in grado di interpretare i risultati e capire quanto questi possano essere influenzati da eventuali oscillazioni dei dati.

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 lucidi e lavagna.

4. Programma/contenuti

Introduzione alla Programmazione Matematica.  Problemi di Programmazione Lineare: modelli costruiti a partire da problemi reali; risultati della teoria con in particolare il teorema fondamentale che consente di restringere la ricerca delle soluzioni ai vertici del problema; il metodo del simplesso con i suoi passi principali; interpretazione geometrica e algebrica del metodo del simplesso; teoria della dualitį con i teoremi fondamentali che legano le risoluzioni dei due problemi primale e duale; il metodo del simplesso duale; analisi di sensitivitį, ovvero l'analisi di quanto le soluzioni finali siano sensibili a variazioni dei dati dei problemi.  Programmazione lineare intera: aspetti teorici ed in particolare i legami tra un problema di PLI ed il suo rilassamento lineare; brevissimi cenni di complessitą; metodi di risoluzione; algoritmi di taglio ed in particolare tagli di Gomory; algoritmi di tipo branch-and-bound.  Grafi: definizioni di base . Il problema del trasporto.

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,...)

• R.J. Vanderbei, "Linear Programming", Kluwer Academic Publishers (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.