Learning objectives
The goal of this course is to introduce linear programming as a
mathematical technique to model decision and optimization problems
relevant in engineering, management science and other applications, as
well as methods for solving the resulting models and interpret the
solutions.
Prerequisites
Basic notions of linear algebra and geometry.
Course unit content
This course is an introduction to Linear Programming and applications. The focus is
on economic and geometric interpretations of linear programs, the
formulation of engineering and management problems in terms of linear
programs, as well as on the methods for solving the resulting models and
interpret their solutions. Topics include: formulation and interpretations
of linear programs, the geometry of linear programs, linear programming
algorithms, including the simplex method, duality theory, optimization of
network flows, applications to problems of production, transportation,
diet, product specifications and satisfaction of demand. Theory of matrix games.
Full programme
1. LINEAR PROGRAMMING. Linear programming (LP) problems and their
formulation: the diet and blending problem, the activity-analysis
(product-mix) problem, the transportation problem, investment problems;
two-variables problems and their graphic solution; LP terminology. The
geometry ol LP: polyhedra, convex sets, basic feasible solutions and
vertices. The Fundamental Theorem of LP. Applications to problems of
production: optimum product lines and production processes in presence
of limited resources, transportation routing, meeting product
specifications, satisfaction of demand. General cases and examples
Techniques of LP: the simplex method and its implementation; geometric
and economic interpretations of the simplex method. Examples. Duality
theory: the dual problem; relations between the primal and the dual
problem: weak and strong duality; economoc interpretation of the dual
problem; duality theory and the simplex method; sensitivity analysis. 2.
NETWORK OPTIMIZATION PROBLEMS. Graphs, trees and networks. The
maximum flow problem and the minimum cost flow problem. Applications
to the assignment problem, the transportation problem, the shortest path
problem. Some network algorithms. MATRIX GAMES AND LINEAR PROGRAMMING.
Two person games with constant sum. Matrix Games. Pure and mixed strategies.
Fundamental theorem of games. Matrix games and lineare programming.
Bibliography
- Course notes.
Other reference books:
- R. Dorfman, P. A. Samuelson, R. M. Solow, Linear programming and
economic analysis, Dover Publications, Inc., New York, 1987, reprint of
the 1958 edition.
- D. Gale, The theory of linear economic models, McGraw-Hill Book Co.,
Inc., New York-Toronto-London, 1960.
- F. S. Hillier, G. J. Lieberman, Introduzione alla ricerca operativa, Ottava
edizione, McGraw-Hill, Milano, 2006.
Teaching methods
The course will be given in presence. The theoretical topics of the course are presented during class lectures
and illustrated with significant examples, applications and several
exercises. Homework assignments are proposed during the course, which
are then discussed in recitation sessions during class time.
Assessment methods and criteria
The final exam consists of a written part, where students are required to
solve some exercises, and of an oral part about the theoretical topics and
the applications discussed during the course.
Other information
- - -
2030 agenda goals for sustainable development
- - -
