ITA | ENG
B027531 - FUNDAMENTALS OF OPERATIONAL RESEARCH
Main information
Teaching Language
Course Content
Suggested readings
Learning Objectives
Prerequisites
Teaching Methods
Type of Assessment
Course program
Academic Year 2021-22
Coorte 2021 - Second Cycle Degree in COMPUTER SCIENCE
Course year
First year - First Semester
Belonging Department
Statistics, IT and its applications "G. Parenti" (DISIA)
Course Type
Single education field course
Scientific Area
MAT/09 - OPERATIONS RESEARCH
Credits
6
Teaching Hours
48
Teaching Term
13/09/2021 ⇒ 23/12/2021
Attendance required
No
Type of Evaluation
Final Grade
Course Content
show
Course program
show
Lectureship
Mutuality
Course teached as:
B000072 - FONDAMENTI DI RICERCA OPERATIVA
3-years First Cycle Degree (DM 270/04) in COMPUTER ENGINEERING
B000072 - FONDAMENTI DI RICERCA OPERATIVA
3-years First Cycle Degree (DM 270/04) in COMPUTER ENGINEERING
Teaching Language
Italian
Course Content
Introduction to optimization models and to Linear Programming (with both continuous and discrete variables). Theory and main algorithms for the solution of linear optimization problems, possibly involving also integer variables. Theory and main algorithms for network flow prroblems.
Suggested readings (Search our library's catalogue)
Fabio Schoen, Fondamenti di Ricerca Operativa.
https://www.amazon.it/Fondamenti-Ricerca-Operativa-Fabio-Schoen/dp/1542342023/ref=sr_1_5?s=books&ie=UTF8&qid=1506496891&sr=1-5&keywords=fabio+schoen#customerReviews
https://www.amazon.it/Fondamenti-Ricerca-Operativa-Fabio-Schoen/dp/1542342023/ref=sr_1_5?s=books&ie=UTF8&qid=1506496891&sr=1-5&keywords=fabio+schoen#customerReviews
Learning Objectives
To be able to formulate optimization models to address practical problems.
To be able to analytically solve small linear optimization problems, possibly with integer variables or with network constraints.
Knowledge of the main algorithms and theoretical results for linear optimization, possibly with also integer variables or with network constraints.
To be able to analytically solve small linear optimization problems, possibly with integer variables or with network constraints.
Knowledge of the main algorithms and theoretical results for linear optimization, possibly with also integer variables or with network constraints.
Prerequisites
Linear Algebra: vectors, matrices, determinant, linear systems of equations.
Teaching Methods
Front teaching.
Type of Assessment
Written or oral examination consisting of:
- theoretical questions to verify the knowledge of simple mathematical programming models and of the theoretical bases of algorithms for LP, ILP and for graph models;
- practical exercises to verify the knowledge of algorithms for LP, ILP and for graph models.
- theoretical questions to verify the knowledge of simple mathematical programming models and of the theoretical bases of algorithms for LP, ILP and for graph models;
- practical exercises to verify the knowledge of algorithms for LP, ILP and for graph models.
Course program
1. Linear Optimization
Introduction to the modeling approach and formulation of simple Linear Programming models.
Introduction to Linear Porgramming (LP). Standard Form of an LP problem:
solution, bases, basic feasible solutions; geometric interpretation of bases.
The Fundamental Theorem of LP. Geometry of LP.
Simplex method - matrix formulation.
Duality theory; definition of dual problems; duality theorems;
interpretation of the dual problem; complementary slackness;
dual simplex method.
Sensitivity analysis: sensitivity on the right hand side; sensitivity on cost
coefficients; adding a variable or a constraint.
2. Integer Linear Programming (ILP)
Examples of ILP problems and models.
Links between LP and ILP.
General purpose methods for ILP: cutting plane methods (Gomory), Branch and Bound.
3. Network Flows
Bases and basic solutions. Network flow problems.
Shortest paths: Disjkstra algorithm. Maximum flow problem: method of Ford and Fulkerson. Maximum flow /
minimum cut theorem.
Introduction to the modeling approach and formulation of simple Linear Programming models.
Introduction to Linear Porgramming (LP). Standard Form of an LP problem:
solution, bases, basic feasible solutions; geometric interpretation of bases.
The Fundamental Theorem of LP. Geometry of LP.
Simplex method - matrix formulation.
Duality theory; definition of dual problems; duality theorems;
interpretation of the dual problem; complementary slackness;
dual simplex method.
Sensitivity analysis: sensitivity on the right hand side; sensitivity on cost
coefficients; adding a variable or a constraint.
2. Integer Linear Programming (ILP)
Examples of ILP problems and models.
Links between LP and ILP.
General purpose methods for ILP: cutting plane methods (Gomory), Branch and Bound.
3. Network Flows
Bases and basic solutions. Network flow problems.
Shortest paths: Disjkstra algorithm. Maximum flow problem: method of Ford and Fulkerson. Maximum flow /
minimum cut theorem.