Operations Research
A.Y. 2020/2021
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
Single session
Responsible
Lesson period
Second semester
Live lectures will be recorded and made available on-line. Some lectures could be pre-recorded; in this case the lectures scheduled according to the timetable will be used for revising and possibly clarifying the content of the video-lectures.
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. Iterative 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. Iterative methods, gradient algorithm.
Prerequisites for admission
Linear algebra
Teaching methods
The course takes place through lectures and practical exercises
Teaching Resources
Hillier and Liebermann,
Introduction to Operations Research
Introduction to Operations Research
Assessment methods and Criteria
The exam consists of two tests: one at the PC and an oral one.
In the lab exam two or three exercises are proposed; the student is required to write the mathematicl model of an optimization problem described in natural language, to solve it with a math programming solver and to correctly interpret its output answering some questions. The oral exam encompasses the whole content of the course and its weight is 6/30.
In the lab exam two or three exercises are proposed; the student is required to write the mathematicl model of an optimization problem described in natural language, to solve it with a math programming solver and to correctly interpret its output answering some questions. The oral exam encompasses the whole content of the course and its weight is 6/30.
Professor(s)