ECTS - University of Pisa
| Modules | Area | Type | Hours | Teacher(s) | |
| RICERCA OPERATIVA | MAT/09 | LEZIONI | 90 |
|
Il corso si prefigge l'obiettivo di guidare lo studente nella formulazione di modelli matematici per problemi di ottimizzazione lineare (discreta e continua) a risorse limitate, e di illustrare tecniche algoritmiche per la loro risoluzione.
Lo studente acquisirà competenze che gli permetteranno di formulare modelli di ottimizzazione lineare continua e discreta, compresi quelli di flusso su reti. Apprenderà inoltre proprietà matematiche che lo condurranno alla progettazione di approcci algoritmici di base per due importanti classi di problemi di ottimizzazione: problemi di flusso su rete e programmazione lineare.
The student who successfully completes the course will be able to demonstrate a solid knowledge of the methodologies and algorithms concerning solution of basic optimization problems. He/she will acquire ability in formulation of mathematical models of decisional problems. The student will also be aware of the basic theory of optimization.
Durante la prova scritta (durata 2.5 ore) lo studente deve risolvere esercizi che mostreranno l'abilità acquisita nel calcolare correttamente alcuni apssi degli algoritmi proposti a lezione.
Durante la prova orale lo studente deve mostrare di conoscere la bse teorica con cui sono costruiti gli algoritmi presentati e mostrare di aver capito le idee alla base dei medesimi algoritmi.
During the written exam (2.5 hours) the student is asked to solve exercises in order to demonstrate the ability to put into practice the basic algorithms of linear and non linear optimization. During the oral exam the student will be assessed on his/her ability to approach problems and to know theory about the described optimization models.
Methods:
Further information:
The final test is composed by a written exam followed by an oral exam. Both each part contributes 50% to the definition of the final grade.
Lo studente sarà in grado di formulare modelli matematici per alcuni problemi applicativi, e risolvere problemi di flusso su rete e problemi di programmazione lineare. Una parte del corso è dedicata alla programmazione lineare intera ed ai suoi metodi risolutivi. Mentre la parte finale coprirà l'ottimizzazione continua e i suoi principali metodi risolutivi.
The student will be able to formulate mathematical models of linear optimization both continuous and discrete. Particula emphasis will be devoted to symplex methods in classical format or in neworks variant. A part of the course will be dedicated to integer linear programming while the final part will cover continuous optimization both unconstrained and constrained.
Elementi di algebra lineare, di algoritmica e di calculus in più variabili.
Fundamentals of linear algebra, algorithmics and calculus in several variables
Lezioni frontali e studio individuale. La frequenza seppur non obbligatoria è fortemente raccomandata.
Delivery: face to face
Learning activities:
Attendance: Advised
Teaching methods:
Formulazione di problemi di ottimizzazione: dati, variabili, vincoli. Problemi di produzione, di trasporto, di assegnamento. Variabili discrete e continue. Modelli standard per software esistenti. Programmazione Lineare. Soluzioni ammissibili ed ottime. Poledri e loro rappresentazione geometrica e matriciale. Teorema fondamentale della PL. Soluzioni di base e vertici. Teoria della dualità e test di ottimalità. Algoritmo del simplesso primale. Algoritmo del simplesso duale. Il caso delle variabili intere e binarie. Le valutazioni superiori ed inferiori. Algoritmi "greedy". Il metodo dei piani di taglio. Piani di taglio di Gomory.
Problemi su reti. Cammini minimi, flusso massimo, flusso di costo minimo. Matrici di incidenza, capacità, costi, bilanci. Alberi di copertura e basi. Poliedro dei flussi. Flussi di base su reti non capacitate e capacitate. La tecnica della tripartizione degli archi. Problema dei potenziali. Potenziali di base. Teorema di Bellman. Algoritmo del simplesso su reti non capacitate; algoritmo del simplesso su reti capacitate. L'algoritmo di Ford-Fulkerson.
Il metodo del "Branch and Bound". Il problema dello zaino ed il problema del "commesso viaggiatore". Cenni di complessità computazionale.
Metodi di ottimizzazione continua non vincolata: discesa e gradiente.La teoria di Lagrange-Kuhn-Tucker per l'ottimizzazione vincolata. Metodi di ottimizzazione vincolata
Mathematical models for optimization decisional problems. Linear Programming and simplex algorithm. Network flow problems, solution methods and algorithms: minimum cost, shortest path, maximum flow. Discrete optimization: "branch and bound", cutting planes. Traveling salesman problem and knapsack problem. Unconstrained continuous optimization: gradient and descent methods. Theory and methods of continuous constrained optimization.
Pappalardo M., Passacantando M., “Ricerca Operativa”, Pisa University Press.
F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli.
Prova scritta seguita da una prova orale. Sono ammessi alla prova orale solamente gli studenti che hanno superato la prova scritta.
Written and oral exam.
