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
Crema
Responsible
Lesson period
Second semester
Course syllabus
INTRODUCTION:
· Introduction to Operations Research. Origins, applications, relations with other disciplines.
· Mathematical models. Data, variables, constraints, objective functions, decision-makers.
LINEAR PROGRAMMING (LP):
· Applications. Examples of linear programming problems.
· Definitions and properties. General form ol LP problems; inequalities form with its geometrical interpretation; standard form. Base solutions and fundamental theorem of LP.
· Duality. Weak and strong duality theorems. Complementary slackness theorem. Economic interpretation of LP.
· Algorithms. Canonical forms. Primal and dual simplex algorithms.
· Post-optimal analysis. Sensitivity analysis and parametric analysis.
MULTI-OBJECTIVE PROGRAMMING (MOP):
· Applications. Examples of multi-objective programming problems.
· Definitions and properties. Dominance, Pareto solutions, Pareto-optimal set, utopistic solution.
· Algorithms for finding the Pareto set. Weigths method. Constraints method.
Geometric interpretation. Solution of linear programming exercises with two objectrives via parametric analysis.
· Criteria for the choice of a solution. Standards criterion, indifference curves criterion, utopistic solution criterion.
INTEGER LINEAR PROGRAMMING (ILP):
· Applications. Examples of integer linear programming and combinatorial optimization problems.
Use of binary variables for modeling logical conditions.
· Definitions and properties. Linear relaxation, integrality gap. Other types of relaxation.
· Algorithms. Branch-and-bound.
NON-LINEAR PROGRAMMING (NLP):
· Applications. Examples of non-linear programming problems.
· Definitions and properties. Gradient vector, Hessian matrix. Convexity and convex programming.
· Algorithms. Algorithms for mono-dimensional optimization. Analytical methods, Lagrangean function,
Karush-Kuhn-Tucker conditions. Itarative methods, gradient algorithm.
· Introduction to Operations Research. Origins, applications, relations with other disciplines.
· Mathematical models. Data, variables, constraints, objective functions, decision-makers.
LINEAR PROGRAMMING (LP):
· Applications. Examples of linear programming problems.
· Definitions and properties. General form ol LP problems; inequalities form with its geometrical interpretation; standard form. Base solutions and fundamental theorem of LP.
· Duality. Weak and strong duality theorems. Complementary slackness theorem. Economic interpretation of LP.
· Algorithms. Canonical forms. Primal and dual simplex algorithms.
· Post-optimal analysis. Sensitivity analysis and parametric analysis.
MULTI-OBJECTIVE PROGRAMMING (MOP):
· Applications. Examples of multi-objective programming problems.
· Definitions and properties. Dominance, Pareto solutions, Pareto-optimal set, utopistic solution.
· Algorithms for finding the Pareto set. Weigths method. Constraints method.
Geometric interpretation. Solution of linear programming exercises with two objectrives via parametric analysis.
· Criteria for the choice of a solution. Standards criterion, indifference curves criterion, utopistic solution criterion.
INTEGER LINEAR PROGRAMMING (ILP):
· Applications. Examples of integer linear programming and combinatorial optimization problems.
Use of binary variables for modeling logical conditions.
· Definitions and properties. Linear relaxation, integrality gap. Other types of relaxation.
· Algorithms. Branch-and-bound.
NON-LINEAR PROGRAMMING (NLP):
· Applications. Examples of non-linear programming problems.
· Definitions and properties. Gradient vector, Hessian matrix. Convexity and convex programming.
· Algorithms. Algorithms for mono-dimensional optimization. Analytical methods, Lagrangean function,
Karush-Kuhn-Tucker conditions. Itarative methods, gradient algorithm.
Prerequisites for admission
Linear algebra, algorithms.
Teaching methods
Lectures and lab sessions.
Teaching Resources
C. Vercellis: "Modelli e Decisioni", Ed. Esculapio, Bologna 1997.
R.Tadei, F. Della Croce: "Ricerca Operativa e Ottimizzazione", Ed. Esculapio, Bologna 2002
R.Tadei, F. Della Croce: "Ricerca Operativa e Ottimizzazione", Ed. Esculapio, Bologna 2002
Assessment methods and Criteria
Practical exam and oral exam.
MAT/09 - OPERATIONS RESEARCH - University credits: 6
Lessons: 48 hours
Professor:
Righini Giovanni
Shifts:
-
Professor:
Righini GiovanniProfessor(s)