CdSINFORMATICA
Codice029AA
CFU6
PeriodoPrimo semestre
LinguaItaliano
Moduli | Settore/i | Tipo | Ore | Docente/i | |
RICERCA OPERATIVA | MAT/09 | LEZIONI | 48 |
|
The course will introduce the student to the main tools and techniques of Operations Research, the discipline of formulating and solving mathematical models corresponding to finding the "best possible" solutions to decision problems. At the end of the course the student will have a basic knowledge of the main issues arising when creating a mathematical model that need be practically solved in "reasonable" time, which is usually a nontrivial task in that most optimization problem are inherently "hard". In particular the student will know the mathematical foundations and the most relevant implementation details (complexity, data structures, ...) of the solution algorithms for two important classes of "easy" problems (network flows and linear programming); furthermore, she/he will be able to construct formulations using the most useful formalism in practice, that of Integer Linear Programming.
The written and oral exam aim at verifying that the student has understood the main algorithmic techniques presented during the course, their theoretical foundations, and she/he is capable of formulating mathematical models of simple fragments of reality with at least a basic understanding of the impact of the modeling choices on the difficulty of the resulting optimization problem.
Methods:
- Final oral exam
- Final written exam
Further information:
The written exam usually consists in solving exercises covering all the material of the course, and in particular (but not exclusively) the algorithmic aspects. A sufficient (or almost so) written exam is a prerequisite to the oral exam; it is only waived for student successfully passing the two in-course tests. The oral exam will in any case cover all the theoretical and algorithmic material of the course.
Delivery: face to face
Attendance: Advised
Learning activities:
- attending lectures
- individual study
Teaching methods:
- Lectures
1. Introduzione ai problemi di Ricerca Operativa. Formulazioni matematiche di alcune situazioni reali. Un problema di programmazione dei trasporti. Problemi di produzione. Problemi di miscelazione ottimale. Problemi di flusso su reti. Il problema del cammino minimo. Problemi di flusso di costo minimo.
2. Programmazione lineare. Elementi di analisi convessa: insiemi convessi, involucro convesso, combinazioni convesse, coni. Geometria della programmazione lineare (PL). Proprieta' dei poliedri. Vertici e direzioni di recessione di un poliedro. Teorema di rappresentazione dei poliedri (senza dimostrazione). Risoluzione geometrica della PL. Metodo delle curve di livello.
Teorema fondamentale della PL. Teoria della dualita'. Dualita' debole, dualita' forte. Teorema degli scarti complementari.
Soluzioni di base degeneri, non degeneri e complementari. Algoritmo del simplesso primale e duale.
Il problema ausiliario per la determinazione di una prima base duale ammissibile.
Problemi di programmazione lineare a variabili intere. Esempi, il problema dello zaino. Rilassamenti continui, piani di taglio, tagli di Gomory.
3. Programmazione lineare su grafi. Alcuni elementi di teoria dei grafi: cammini, cicli, alberi di copertura, matrici di incidenza.
Il problema del flusso di costo minimo, principali proprieta': esistenza di una soluzione ottima, teorema dell'interezza.
L'algoritmo del simplesso su reti per il problema del flusso di costo minimo senza capacita' superiori sugli archi.
L'algoritmo del simplesso su reti per il problema del flusso di costo minimo con capacita' superiori sugli archi.
Il problema della ricerca dell'albero dei cammini di costo minimo. Formulazione come problema di flusso di costo minimo, condizioni di esistenza di una soluzione ottima, algoritmo SPT. L'algoritmo di Dijkstra per il problema dell'albero dei cammini minimi con costi positivi sugli archi. Convergenza e complessita'. Il duale del problema dell'albero dei cammini minimi: connessioni con le condizioni di esistenza del problema e con l' algoritmo SPT.
Problema del flusso massimo: formulazione, teorema max-flow-min-cut, algoritmo di Ford-Fulkerson, algoritmo di Edmons-Karp per la ricerca del cammino aumentante. Problema duale del problema del flusso massimo: relazioni con il problema della ricerca del taglio di capacit\'a minima. Teorema max flow-min cut.
Metodo Branch and Bound: regole generali, applicazione alla risoluzione di un problema di Programmazione Lineare Intera in 2 variabili. Il problema del commesso viaggiatore (TSP):
formulazione nel caso simmetrico e asimmetrico.
Risoluzione del TSP simmetrico con il metodo Branch and Bound: algoritmo del nodo pi\'u vicino per la valutazione superiore, rilassamento definito dal r-albero di costo minimo.
The course will cover the following material:
- Linear Programs: = definitions, geometrical and algebraic properties , duality theory , the primal and dual simplex algorithm;
- Network Flow problems and algorithms: = Maximum Flows , Min-Cost Flows;
- Integer Linear Programs: = Cutting plane methods , "Branch and Bound methods.
M. Pappalardo, M. Passacantando, Ricerca Operativa, Pisa University Press, 2012.
Pappalardo M., Passacantando M., “Ricerca Operativa”, Pisa University Press, 2012.
Prova scritta ed orale