CdSMATEMATICA
Codice072AA
CFU6
PeriodoPrimo semestre
LinguaItaliano
| Moduli | Settore/i | Tipo | Ore | Docente/i | |
| RICERCA OPERATIVA | MAT/09 | LEZIONI | 60 |
|
Il corso presenta i principali aspetti teorici e pratici relativi alla definizione e alla risoluzione di modelli matematici di ottimizzazione per problemi reali. In particolare, vengono introdotte proprietà matematiche di base e alcune delle principali tecniche algoritmiche per la risoluzione di tre grandi famiglie di problemi di ottimizzazione: i problemi di Programmazione Lineare, i Problemi di flusso su rete e i problemi di Programmazione Lineare Intera.
The course will introduce the student to the main mathematical properties and algorithmic approaches of Operations Research, the discipline aiming at formulating and solving mathematical models for decision problems stated in an optimization form. At the end of the course the student will know the mathematical foundations and some relevant solution algorithms for two important classes of "easy" problems, that is Network Flow problems and Linear Programming. Furthermore, she/he will be able to formulate "hard" optimization problems via Integer Linear Programming, and to solve them by exploiting some relevant mathematical properties of this class of problems.
La verifica delle conoscenze avverrà attraverso la valutazione dell'elaborato scritto e attraverso la valutazione delle risposte fornite in sede di prova orale. Verranno inoltre stimolate domande da parte degli studenti nel corso delle lezioni, per una verifica in itinere.
Through the written and the oral examination. Moreover, a discussion with the students will be stimulated during the lessons, to assess the acquired knowledge also in real time.
Al termine del corso lo studente sarà in grado di formulare e risolvere problemi di ottimizzazione appartenenti alle classi studiate nel corso, ovvero Programmazione Lineare, Problemi di flusso su rete e Programmazione Lineare Intera.
At the end of the course the student will be able to formulate and solve optimization problems belonging to the classes studied in the course, i.e. Linear Programming, Network flow problems and Integer Linear Programming.
La verifica delle capacità acquisite avverrà attraverso l'analisi delle risposte fornite in sede di elaborato scritto e in sede di prova orale.
All the skills will be assessed during the written and the oral examination.
Saranno acquisite abilità di modellazione matematica e di risoluzione algoritmica di problemi di ottimizzazione.
Capabilities of mathematical modelling and solving optimization problems via efficient algorithmic approaches will be achieved.
Le abilità di modellazione matematica e di risoluzione algoritmica verranno verificate, oltre che in sede d'esame, nel corso delle esercitazioni in classe.
All the behaviors will be assessed during the written and the oral examination, and through class exercises.
Sono consigliate conoscenze di base di analisi matematica, geometria e algebra lineare.
Si assume inoltre una conoscenza di base dei concetti di algoritmo e di analisi della sua complessità computazionale.
A basic knowledge of analysis, geometry and linear algebra is recommended.
Moreover, a basic knowledge of the concepts of algorithm and computational complexity is assumed.
Gli argomenti del corso verranno presentati tramite lezioni, con il supporto di esercitazioni.
Teaching methods:
- Lectures
- Exercises
-
Problemi e modelli (4 ore)
- Problemi decisionali, di ottimizzazione e di esistenza
- Esempi di problemi di ottimizzazione
Programmazione Lineare (PL) (20 ore)
- Problemi e modelli di PL
- Geometria della PL: poliedri e loro rappresentazione
- Teoria matematica della dualità
- Algoritmo del simplesso primale e sua interpretazione geometrica
- Teorema degli scarti complementari
- Algoritmo del simplesso duale e sua interpretazione geometrica
Problemi di flusso su rete (16 ore)
- Problemi e modelli di PL su reti
- Cammini minimi
- Flusso massimo
- Flusso di costo minimo
Programmazione Lineare Intera (PLI) (20 ore)
- Problemi e modelli di Ottimizzazione Combinatoria e di PLI
- Tecniche di modellazione
- Tecniche di dimostrazione di ottimalità
- Algoritmi euristici
- Tecniche di rilassamento
- Algoritmi enumerativi
Problems and models (4 hours)
- Decision problems, optimization problems, feasibility problems
- Examples of optimization problems
Linear Programming (LP) (20 hours)
- LP problems and models
- Geometry of LP: polyhedra and their representation
- Duality theory in LP
- Primal Simplex algorithm with related geometrical interpretation
- Complementary Slackness Theorem
- Dual Simplex algorithm with related geometrical interpretation
Network flow problems (16 hours)
- LP problems and models on networks
- Shortest paths
- Maximum flow
- Minimum cost flow
Integer Linear Programming (ILP) (20 hours)
- Combinatorial Optimization and ILP: problems and models
- Modelling techniques
- Proof of optimality
- Heuristic algorithms
- Relaxations
- Enumerative algorithms
Appunti di Ricerca Operativa e prove d'esame (con e senza svolgimento) sono disponibili sulla pagina web del corso:
http://didawiki.di.unipi.it/doku.php/matematica/ro/start
Testi di consultazione consigliati:
-
F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli, Milano, 1999
-
Massimo Pappalardo, Mauro Passacantando "Ricerca Operativa", Plus, 2010
Appunti di Ricerca Operativa, exam exercises (with and without solution): available on the web page of the course.
Suggested:
-
F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli, Milano (1999)
-
Massimo Pappalardo, Mauro Passacantando "Ricerca Operativa", Plus, 2010
Si consiglia di contattare il docente.
Please contact the teacher.
Prova scritta seguita da una prova orale. La prova scritta dura un'ora e trenta minuti, consta di tre esercizi, e copre tutti gli argomenti trattati durante il corso. Durante la prova scritta non è possibile consultare libri o appunti.
I contenuti della prova d'esame sono quelli presentati durante l'anno accademico a cui si riferisce l'appello, anche per gli studenti che avessero seguito il corso in anni precedenti.
La prova orale viene effettuata nello stesso appello della prova scritta, normalmente nei giorni immediatamente successivi a quelli di pubblicazione dell'esito della prova scritta.
Written exam followed by an oral exam. The written exam, of 1.5 hours, consists of 3 exercises, and covers all of the topics of the course. Textbooks and student notes are forbidden during the written exam.
Both the written and the oral exams refer to the topics of the current academic year, also for those students who attended the course in previous years.
The oral exam is performed jointly with the written exam, usually a few days later the date of publication of the results of the written exam.