Background and Goals: A fundamental problem is the allocation of constrained resources such as funds among investment possibilities or personnel among production facilities. Each such problem has as it’s goal the maximization of some positive objective such as investment return or the minimization of some negative objective such as cost or risk. Such problems are called Optimization Problems. Linear Programming deals with optimization problems in which both the objective and constraint functions are linear (the word "programming" is historical and means "planning" rather that necessarily computer programming). In practice, such problems involve thousands of decision variables and constraints, so a primary focus is the development and implementation of efficient algorithms. However, the subject also has deep connections with higher-dimensional convex geometry. A recent survey showed that most Fortune 500 companies regularly use linear programming in their decision making. This course will present both the classical and modern approaches to the subject and discuss numerous applications of current interest.

Content: Formulation of problems from the private and public sectors using the mathematical model of linear programming. Development of the simplex algorithm; duality theory and economic interpretations. Postoptimality (sensitivity) analysis; algorithmic complexity; the ellipsoid method; scaling algorithms; applications and interpretations. Introduction to transportation and assignment problems; special purpose algorithms and advanced computational techniques. Students have opportunities to formulate and solve models developed from more complex case studies and use various computer programs.

Subsequent Courses: IOE 610 (Linear Programming II) and IOE 611 (Nonlinear Programming)