Contents
Introduction to Operations Research.
Basic algebraic aspects of Linear and Integer Programming.
Convex and polyhedral sets
The concepts of extreme point, vertex and Basic Feasible Solution (BFS).
Graphical solutions of LP problems in 2 dimensions.
The Simplex method: structure and property. The two phases of the method. Convergence of the algorithm.
Duality theory: construction of the dual problem, economic interpretation of duality. Duality theorems. Complementarity.
Classical ILP problems and main modelling techniques.
Modelling with integer and binary variables
Valid inequalities. Algorithms for ILP. Branch & Bound.
The Knapsack Problem.
The Travelling Salesman Problem.
Objectives
D1 - Knowledge and understanding
1 To describe and distinguish the basic geometric aspects of Linear Programming
2 To know the theory of duality in linear programming
3 To explain the optimality conditions in Linear Programming.
4 To deal with the main issues related to post-optimality in linear programming.
D2 - Applying knowledge and understanding
1 Formulate and analyze simple Linear (LP) and Integer Linear Programming (ILP) problems.
2 Solve LP problems via the Simplex method.
3 Use simple software for the solution of LP and ILP problems.
4 Use a simple algebraic modelling language.
D3 - Making judgements
1 Estimate the complexity of the models and solver tools.
2 Interpret the information from the solution of LP and ILP problems.
D4 - Communication skills
1 Discuss the main aspect of Linear programming (feasibility, optimality, duality).
D5 - Learning skills
1 Deepen through personal study, the most recent aspects of Linear Programming
Prerequisites
Linear Algebra
Vector and matrix operations
Solution of systems of linear equations
Teaching Methods
The course consists of lectures and guided exercises in the classroom. In particular, the exercises will be devoted to the solution of problems of linear programming using the simplex method and to the use of simple modelling techniques.
Verification of learning
The final evaluation consists of a written and an oral exam. The written test is oriented to the verification of knowledge and skills acquired in the geometrical aspects of Linear Programming (vertices, BFS, etc.) and the solution of linear programming problems using the simplex method. The oral part will deal with the theoretical aspects of Linear Programming.
Examination sessions are provided in June/July, September/October and February. The exams scheduled in December and April are reserved to “fuori corso”. There are no exam sessions during the teaching period.
Texts
F.S. Hillier, G.J. Lieberman Ricerca Operativa, nona edizione, McGraw--Hill 2010
R. De Leone, C. Lazzari Esercizi di programmazione Lineare e Programmazione Lineare Intera, Aracne, 2007
M. Bruglieri, A. Colorni Ricerca Operativa, Zanichelli 2012.
A. Sassano Modelli e Algoritmi della Ricerca Operativa, Franco Angeli, 1999
R. Tadei e F. Della Croce Ricerca Operativa e Ottimizzazione, Seconda Edizione, Società Editrice Esculapio, 2002
Online notes are available for algebraic and geometric base of Linear Programming, the simplex method and the optimality conditions in linear programming.
