GEOMETRY AND OPERATIONAL RESEARCH B
GEOMETRY (1 credits) | OPERATIONS RESEARCH (3 credits) |
Learning outcomes of the course unit
The 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
Basic linear algebra.
Course contents summary
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.
Recommended readings
Lecture notes.