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.
F. Schoen, Fondamenti di Ricerca Operativa, Seconda edizione 2017 (in Italian)
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.
Development of an adequate expression and technical discussion of own arguments (CT3)
Prerequisites
Linear Algebra: vectors, matrices, determinant, linear systems of
equations
Teaching Methods
Front teaching
Type of Assessment
Oral or written exam including numerical and theoretical exercises. The exam can be
substituted by two intermediate written tests.
Course program
1. Introduction to Linear Programming and Integer Linear Programming. Examples of problem solving: mathematical formulation and resolution of representative problems via the Excel tools.
2. Linear Porgramming (LP). Standard form of an LP problem:
solution, bases, feasible solutions; basic feasible solutions; fundamental theorem of LP;
geometry of LP
Simplex methods - dictionary formulation
Duality theory; definition of dual problems; duality theorems;
interpretation; complementary slackness; duality and game theory
(introduction); dual simplex method.
Sensitivity analysis; sensitivity on the right hand side; sensitivity on cost
coefficients; adding a variable or a constraint.
3. 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.
4. Network Flows
Bases and basic solutions in network flow problems.
Minimum cost flow problem.
Shortest paths: Dijkstra algorithm
Maximum flow problem; method of Ford and Fulkerson. Maximum flow /
minimum cut theorem