Learning objectives
This course introduces linear programming and applications. The focus is on economic and geometric interpretations of linear programs and on the formulation and solution of engineering and management problems in terms of linear programs.
Prerequisites
Geometry and Linear Algebra
Course unit content
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.
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
- Note a cura del docente.
Testi di approfondimento:
- 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
Class lectures and recitation sessions
Assessment methods and criteria
Written and oral exam
Other information
- - -
