Ricerca operativa (2007/2008)

Corso disattivato non visibile

Codice insegnamento
4S00001
Crediti
6
Coordinatore
Angelo Pica
Altri corsi di studio in cui è offerto
Altri corsi di studio in cui è offerto
L'insegnamento è organizzato come segue:
Modulo Crediti Settore disciplinare Periodo Docenti
Modulo base 5 SECS-S/06-METODI MATEMATICI DELL'ECONOMIA E DELLE SCIENZE ATTUARIALI E FINANZIARIE 1° Q Angelo Pica
Modulo avanzato 1 SECS-S/06-METODI MATEMATICI DELL'ECONOMIA E DELLE SCIENZE ATTUARIALI E FINANZIARIE 1° Q Angelo Pica

Obiettivi formativi

Modulo: Modulo base
-------
Il corso si propone di introdurre lo studente ad alcune problematiche di base inerenti al campo dell'ottimizzazione, con particolare riferimento alla Programmazione Lineare ed alcuni problemi di Ottimizzazione su reti ed ai relativi algoritmi di risoluzione. Viene inoltre fornito qualche cenno di modellistica, mediante l'analisi di semplici problemi lineari che rientrano in questa casistica e la conseguente formulazione matematica.
Questo modulo è comune agli studenti del Corso di Laurea in Matematica applicata, del Corso di Laurea in Informatica e del Corso di Laurea Specialistica in Sistemi intelligenti e multimediali.


Modulo: Modulo avanzato
-------
Si faccia riferimento al modulo base.
Questo modulo è riservato agli studenti del Corso di Laurea in Matematica applicata.

Programma

Modulo: Modulo base
-------
* Modelli ed algoritmi - Processi decisionali. Problemi di ottimizzazione e di esistenza: funzione obiettivo, vincoli e variabili decisionali. Esempi di classi di problemi. Classi di algoritmi: algoritmi greedy, di ricerca locale ed enumerativi.
* Programmazione lineare e dualità - Il problema di programmazione lineare: definizione, regole di trasformazione ed interpretazione geometrica dei dati. Il problema duale: coppia simmetrica e coppia asimmetrica, tabella delle corrispondenze, interpretazione geometrica. Programmazione lineare su coni: teorema fondamentale delle disuguaglianze lineari e procedura Simplesso-su-coni. Direzioni ammissibili e direzioni di crescita. Teorema debole e teorema forte della dualità e loro conseguenze. Primale e duale ristretti. Algoritmo del Simplesso Primale-Duale: procedura ed interpretazione grafica. Teorema degli scarti complementari e sue conseguenze. Matrici di base e basi complementari: definizione, ammissibilità e degenerazione. Condizioni di ottimo. Algoritmi del Simplesso Primale e del Simplesso Duale e loro interpretazione grafica. Cenni sul simplesso a variabili limitate. Riottimizzazione: variazione del vettore dei costi, del vettore dei termini noti ed aggiunta di vincoli al primale.
* Problema di flusso di costo minimo - Formulazione e regole di trasformazione. Problema duale (di potenziale). Visita di un grafo. Condizioni degli scarti complementari e relativa curva. Algoritmo Primale-Duale: soluzione iniziale, fase primale e fase duale. Soluzioni di base: matrice ed albero di base, visite anticipata e posticipata di un albero per la determinazione di soluzioni complementari. Simplesso-per-flusso e Simplesso-per-potenziale.
* Problema di flusso massimo - Problema di flusso e problema di taglio. Condizioni di ottimalità. Algoritmo di Edmonds e Karp.
* Problema dei cammini minimi - Formulazione. Condizioni di ottimalità (di Bellman). Algoritmo SPT ed algoritmo di Dijkstra.

Il modulo viene svolto in 40 ore di lezione/esercitazione frontale ed ha luogo nel primo periodo dell'anno accademico.


Modulo: Modulo avanzato
-------
* Programmazione lineare intera.

Un programma più dettagliato sarà disponibile quanto prima nella pagina personale del docente nel sito di Facoltà.

Modalità d'esame

Modulo: Modulo base
-------
La verifica del profitto avviene mediante una prova scritta. La votazione riportata nella prova è quella definitiva, fatto salvo il diritto di ciascuno studente di richiedere l'effettuazione di un esame orale, le cui modalità vanno definite caso per caso.


Modulo: Modulo avanzato
-------
Si faccia riferimento al modulo base.