Ricerca operativa (2004/2005)

Corso disattivato non visibile

Codice insegnamento
4S00001
Docente
Angelo Pica
crediti
5
Altri corsi di studio in cui è offerto
Lingua di erogazione
Italiano
Sede
VERONA
Periodo
1° Q - 2° anno e successivi dal 27-set-2004 al 26-nov-2004.
Pagina Web
http://profs.sci.univr.it/~pica/

Orario lezioni

Obiettivi formativi

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.

Programma

# 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 corso viene svolto in 40 ore di lezione/esercitazione frontale ed ha luogo nel primo periodo dell'anno accademico.

Modalità d'esame

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.

Materiale didattico

Documenti

Condividi