ITA | ENG
B014966 - FUNDAMENTALS OF OPERATION RESEARCH
Main information
Teaching Language
Course Content
Suggested readings
Learning Objectives
Prerequisites
Teaching Methods
Type of Assessment
Course program
Academic Year 2020-21
Coorte 2018 - 3-years First Cycle Degree (DM 270/04) in Electronics and Telecommunications Engineering
Course year
Third year - First Semester
Belonging Department
Information Engineering (DINFO)
Course Type
Single education field course
Scientific Area
MAT/09 - OPERATIONS RESEARCH
Credits
6
Teaching Hours
54
Teaching Term
14/09/2020 ⇒ 18/12/2020
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 mathematical programming and, in particular, to linear
optimization (both with continuous and discrete variables). Theory and
main algorithms for the solution of linear optimization problems, of
network flows, of integer linear optimization problems.
optimization (both with continuous and discrete variables). Theory and
main algorithms for the solution of linear optimization problems, of
network flows, of integer linear optimization problems.
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
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
Learning Objectives
1) Ability to formulate simple linear programming (LP) and integer linear programming (ILP) models, graph models.
2) Knowledge of theoretical bases of LP, ILP and graph models.
3) Knowledge of algorithms for LP, ILP and graph models.
2) Knowledge of theoretical bases of LP, ILP and graph models.
3) Knowledge of algorithms for LP, ILP and graph models.
Prerequisites
Linear Algebra: vectors, matrices, determinant, linear systems of
equations
equations
Teaching Methods
Front teaching
Type of Assessment
Written (or oral) examination having:
- 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
Schoen, Fondamenti di Ricerca Operativa, ISBN
978-1-105-49496-3, 2012, disponibile su www.lulu.com (http:
//www.lulu.com/spotlight/fabioschoen)
Examples: blending problems, product mix, transportation; introduction
to graph theory; network flows
Introduction to Linear Porgramming (LP). Forms of an LP problem:
solution, bases, feasible solutions; Introduzione alla Programmazione
Lineare (PL). Forma di un problema di PL; soluzioni, basi, soluzioni
ammissibili; basic feasible solutions; fundamental theorem of LP;
geometry of LP
Simplex methods - matrix formulation
Duality theory; definition of dual problems; duality theorems;
interpretation; complementary slackness;
(introduction); 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 in network flow problems.
Shortest paths: Disjkstra algorithm
Maximum flow problem; method of Ford and Fulkerson. Maximum flow /
minimum cut theorem
Network simplex methods
Schoen, Fondamenti di Ricerca Operativa, ISBN
978-1-105-49496-3, 2012, disponibile su www.lulu.com (http:
//www.lulu.com/spotlight/fabioschoen)
Examples: blending problems, product mix, transportation; introduction
to graph theory; network flows
Introduction to Linear Porgramming (LP). Forms of an LP problem:
solution, bases, feasible solutions; Introduzione alla Programmazione
Lineare (PL). Forma di un problema di PL; soluzioni, basi, soluzioni
ammissibili; basic feasible solutions; fundamental theorem of LP;
geometry of LP
Simplex methods - matrix formulation
Duality theory; definition of dual problems; duality theorems;
interpretation; complementary slackness;
(introduction); 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 in network flow problems.
Shortest paths: Disjkstra algorithm
Maximum flow problem; method of Ford and Fulkerson. Maximum flow /
minimum cut theorem
Network simplex methods