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
Knowledge of the theory and methods of linear optimization, integer
optimization, network flows. To be able to solve small dimensional linear
optimization problems. Knowledge and usage of duality theory. Capability
of solving shortest path and maximum flow problems.
Prerequisites
Linear Algebra: vectors, matrices, determinant, linear systems of
equations
Teaching Methods
Front teaching
Type of Assessment
Oral exam including two numerical exercises. The exam can be
substituted by an equivalent written one
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