MA380 LINEAR PROGRAMMING (3 Cr.)

COURSE DESCRIPTION

Prerequisite:  MA211 Introduction to Matrix Theory and Linear Algebra

General Introduction and Goals

Introduction to the fundamental principles and techniques of linear programming with strong emphasis on mathematical modeling, analysis, and application to nontrivial problems arising in various areas of the physical, social, and decision sciences.

Linear programming is one of the most extensively developed and frequently utilized optimization techniques; enjoys a phenomenal diversity of applications in mathematics, engineering, military, agriculture, industry, production and inventory control, economics, finance, and transportation, among others; occupies a central position in the rapidly expanding discipline of Operations Research; and has been instrumental in the creation and advancement of several new areas of modern applied mathematics. The ubiquity and immense utility of linear programming, the simplicity, beauty, and accessibility of the underlying mathematics, its enormous capability for modeling and solving a vast array of concrete real-world problems, and its intimate connections with computer science provide ample justification for the formal introduction of an undergraduate course on linear programming. This and the two companion courses MA 381 and MA 485 will expose the students to a wide variety of useful and challenging mathematical modeling problems and provide them with an appreciation for, an understanding of, and a facility in the use of mathematics in other fields. Furthermore, these courses will make the students aware of a broad range of career opportunities, help them in the job market, and guide them in exploring the possibility of pursuing graduate programs in some areas of the decision sciences.

Course Content

1.       Introduction

1. The origins and scope of linear programming
2. The role of linear programming in operations research
3. The place of linear programming in applied mathematics

2.       Linear Programming

1. The linear programming model
2. Fundamental assumptions of linear programming
3. The geometry and graphical solution of two-variable linear programming problems
4. Problem formulation: product mix problems, diet problems, blending problems, cutting stock problems, production planning problems, inventory control problems, work scheduling problems, capital budgeting problems, financial planning problems; multiperiod decision problems, multiperiod production planning problems, multiperiod financial planning problems, multiperiod work scheduling problems, transportation problems, transshipment problems, assignment problems, network flow problems, . . .

3.       The Simplex Method

1. The geometry of the simplex method
2. The transition from geometry to algebra
3. The algebra of the simplex method
4. The simplex algorithm
5. Termination criteria: optimality and unboundedness
6. Alternate optimal solutions
7. Degeneracy and convergence of the simplex algorithm
8. The big M method
9. The two-phase method
10. The simplex algorithm for problems containing free variables, variables with upper and lower bounds, and mixed constraints
11. Computational complexity and efficiency of the simplex algorithm
12. Computer packages

4.       Duality in Linear Programming

1. Examples of dual problems
2. Economic interpretation of the dual problem
3. The dual of a general linear programming problem
4. Relationships between the primal and dual problems
5. Duality theorems and their consequences
6. Geometric interpretation of duality and complementary slackness
7. The dual simplex algorithm

5.       Sensitivity (Postoptimality) Analysis

1. The graphical approach to sensitivity analysis
2. The general approach to sensitivity analysis
3. Introduction of an additional inequality constraint
4. Introduction of an additional equality constraint
5. Cost ranging of a nonbasic cost coefficient
6. Cost ranging of a basic cost coefficient
7. Right-hand side ranging
8. Changes in the input-output coefficients in basic and nonbasic column vectors
9. Multiparameter sensitivity analysis
10. Duality and sensitivity analysis
11. The computer and sensitivity analysis

6.       Special Types of Linear Programming Problems

1. Transportation problems
2. The transportation simplex algorithm
3. Sensitivity analysis for transportation problems
4. Transshipment problems
5. Assignment problems
6. Multidivisional problems

7.       Applications of Linear Programming

1. Goal programming
2. Matrix games
3. Best approximation problems
4. Separable convex programming
5. Sequential linearization methods