Ricerca operativa (Programmazione lineare e su grafi)

Introduzione alla ricerca operativa. Problemi e modelli. Modelli matematici. Problemi di programmazione matematica. Problemi di programmazione lineare (PL). Un problema di programmazione dei trasporti.

Insiemi convessi, involucro convesso, combinazioni convesse. Coni, involucro conico, combinazioni coniche. Problemi di PL in forma standard. Poliedri. La regione ammissibile di un problema di PL è un poliedro.

Vertici e direzioni di recessione di un poliedro. Il teorema di rappresentazione dei poliedri. Esistenza delle soluzioni ottime di un problema di PL: il teorema fondamentale della PL.

Basi e soluzioni di base di un problema di PL in forma primale standard. Soluzioni di base ammissibili e degeneri. Corrispondenza biunivoca tra i vertici del poliedro che definisce la regione ammissibile del problema di PL e le corrispondenti soluzioni di base ammissibili.

Esercitazione: Dimostrazione dell'esistenza di una soluzione ottima di un problema di PL tramite l'uso del problema duale.

Teoria della dualità. Il duale associato a un problema di PL in forma standard. Dualità debole e dualità forte. Condizioni di esistenza di una soluzione ottima di un problema di PL.

Esercitazione: Dimostrazione dell'esistenza di una soluzione ottima di un problema di PL tramite l'uso del problema duale.

Soluzioni di base duali. Soluzioni di base duali ammissibili e degeneri. Corrispondenza biunivoca tra i vertici del poliedro che definisce la regione ammissibile del problema duale e le soluzioni di base duali ammissibili. Teorema degli scarti complementari. Soluzioni di base complementari. Condizioni di ottimalità di una soluzione di base.

L'algoritmo del simplesso primale.

Correttezza dell'algoritmo del simplesso primale.

Esercitazione: Esercizi sull'algoritmo del simplesso primale, analisi dei cambi di base degenere e non degenere.

L'algoritmo del simplesso duale.

Il problema ausiliario per la ricerca di una prima base duale ammissibile.

Esercitazione: Esercizi sull'algoritmo del simplesso duale.

Programmazione a variabili intere. Rilassamenti continui. Piani di taglio. Tagli di Gomory.

Esercitazione: Esercizi sulla programmazione a variabili intere: rilassamenti e tagli di Gomory.

Richiami sulla teoria dei grafi: cammini e cicli orientati e non orientati. Connessione e forte connessione. Alberi, alberi di copertura. La matrice di incidenza associata a un grafo orientato. Proprietà della matrice di incidenza.

Caratterizzazione degli alberi di copertura mediante sottomatrici di rango massimo della matrice di incidenza. Il problema del flusso di costo minimo: formulazione esplicita e compatta mediante la matrice di incidenza.

L'algoritmo del simplesso su reti per il problema del flusso di costo minimo senza capacità superiori sugli archi.

Esercitazione: Esercizi sull'algoritmo del simplesso su reti senza capacità superiori sugli archi.

L'algoritmo del simplesso su reti in presenza di capacità superiori sugli archi. Soluzioni di base primali e duali, degenerazione.

Esercitazione: Esercizi sull'algoritmo del simplesso su reti in presenza di capacità superiori sugli archi.

Il problema della ricerca dell'albero dei cammini di costo minimo di radice data. Formulazione come problema di flusso di costo minimo. Condizioni di esistenza di una soluzione ottima. Algoritmo SPT.

L'algoritmo di Dijkstra: correttezza e complessità. Cenni sulla correttezza e sulla complessità dell'Algoritmo SPT in presenza di costi negativi sugli archi. Il problema del massimo flusso su una rete. Formulazione come problema di flusso di costo minimo.

L'algoritmo di Ford-Fulkerson e di Edmonds-Karp per il problema del flusso massimo. Tagli su una rete.

Esercitazione: Esercizi sull'algoritmo di Edmonds e Karp.

Il duale del problema del massimo flusso su una rete e sua interpretazione come la ricerca di un taglio di capacità minima. Il teorema Max-Flow Min Cut. Generalità sui metodi del Branch and Bound.

Problema del commesso viaggiatore (TSP): formulazione nel caso simmetrico e asimmetrico. Risoluzione con il metodo Branch and Bound del TSP simmetrico: algoritmo del nodo più vicino, r-albero di costo minimo.

Esercitazione: Esercizi sul problema TSP simmetrico.