Course teached as: 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.
Fabio Schoen, Fondamenti di Ricerca Operativa, ISBN
978-1-105-49496-3, 2012, disponibile su www.lulu.com (http:
//www.lulu.com/spotlight/fabioschoen)
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.
Prerequisites
Linear Algebra: vectors, matrices, determinant, linear systems of
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.
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