Operations Research
A.Y. 2019/2020
Learning objectives
The course aims to introduce Operations Research, i.e. the scientific study of methods for solving complex decision problems with the help of a computer. The aim is to learn to construct mathematical models of optimization problems, knowing how to classify models and to know the mathematical foundations of algorithmic techniques that allow them to be solved.
Expected learning outcomes
Students will develop the ability of recognizing optimization problems, formulating them in mathematical models and they will know the mathematical properties that underlie the algorithms developed to solve them.
Lesson period: Second semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Milan
Responsible
Lesson period
Second semester
Course syllabus
Introduction. Examples of Linear Programming (LP) and Integer LP models (ILP). LP: graphical solution and description of the simplex algorithm, first and second phases. Duality: Farkas lemma, weak and strong duality theorems, dual simplex algorithm. Sensitivity analysis. ILP: unimodularity, cutting plane methods and Branch & Bound technique. Network optimization: models and algorithms for spanning tree, minimum cost path, maximum flow and maximum flow at minimum cost problems.
Prerequisites for admission
Linear algebra
Teaching methods
The course takes place through lectures and practical exercises, with the aid of either a traditional blackboard or a tablet
Teaching Resources
Ricerca Operativa
M. Caramia, S. Giordani, F. Guerriero, R. Musmanno, D. Pacciarelli
ISEDI, 2014, ISBN:9788880083764, 688 pagine, € 45,00 (2015)
or
M. Fischetti: Lezioni di Ricerca Operativa,
Edizioni Libreria Progetto, Padova
and
M. Dell'Amico: 120 esercizi di ricerca operativa,
Pitagora Editrice, Bologna
M. Caramia, S. Giordani, F. Guerriero, R. Musmanno, D. Pacciarelli
ISEDI, 2014, ISBN:9788880083764, 688 pagine, € 45,00 (2015)
or
M. Fischetti: Lezioni di Ricerca Operativa,
Edizioni Libreria Progetto, Padova
and
M. Dell'Amico: 120 esercizi di ricerca operativa,
Pitagora Editrice, Bologna
Assessment methods and Criteria
The exam consists of a written test and an obligatory oral exam.
For example, the written test requires:
- the construction of LP or ILP models of simple optimization problems;
- the graphical solution of LP models in two variables;
- the application of the Branch & Bound technique to ILP problems in two variables or to "knapsack" problems;
- the identification of Gomory cuts starting from the optimal tableau of the continuous relaxation of a ILP problem;
- the application of network optimization algorithms to small examples.
The exercises have contents and difficulties similar to those faced in the exercises carried out in the classroom.
Consultation of texts or notes is not permitted.
The oral test consists of a brief discussion of the written task and an interview aimed at ascertaining the knowledge of the main theorems (and the related proofs) that are the foundation of the LP and the ILP theories.
For example, the written test requires:
- the construction of LP or ILP models of simple optimization problems;
- the graphical solution of LP models in two variables;
- the application of the Branch & Bound technique to ILP problems in two variables or to "knapsack" problems;
- the identification of Gomory cuts starting from the optimal tableau of the continuous relaxation of a ILP problem;
- the application of network optimization algorithms to small examples.
The exercises have contents and difficulties similar to those faced in the exercises carried out in the classroom.
Consultation of texts or notes is not permitted.
The oral test consists of a brief discussion of the written task and an interview aimed at ascertaining the knowledge of the main theorems (and the related proofs) that are the foundation of the LP and the ILP theories.
MAT/09 - OPERATIONS RESEARCH - University credits: 6
Lessons: 48 hours
Professor:
Trubian Marco
Shifts:
-
Professor:
Trubian MarcoProfessor(s)