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 54 ore di lezione/esercitazione frontale
ed ha luogo nel primo 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
c, del vettore b 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.
- Problema dell'assegnamento. Accoppiamento di massima
cardinalità. Assegnamento di costo minimo.
- Ottimizazione lineare discreta. Esempi di problemi nella
classe. Tecniche di rilassamento. Algoritmi di
branch-and-bound.