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 knowledge of linear algebra and geometry.
Course unit content
This course introduces 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.
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.
Bibliography
- Course notes.
Other 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.
- D. G. Luenberger, Linear and nonlinear programming, Second edition, Springer, New York, 2003.
- R. J. Vanderbei, Linear progamming: Foundations and Extensions.
Teaching methods
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
- - -
