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.
Attività formative
Il corso viene svolto in 40 ore di lezione/esercitazione frontale ed
ha luogo nel secondo periodo dell'anno accademico.
Programma del corso
-
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.