B024412 - INTRODUCTION TO OPTIMIZATION

italian

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)

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.

Linear Algebra: vectors, matrices, determinant, linear systems of
equations

Front teaching

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.

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