An Introduction to the Mathematical Theory of Linear Programming

Abstract

This paper is an attempt to provide a relatively self-contained and basic mathematical justification for the LP problem and the simplex method of solving it. The first two parts of the paper outline the aspects of the abstract concepts of vectors, vector spaces, matrices, and transformation which are important to the theoretical foundation of LP methods. Part III gives a concise mathematical statement of the general LP problem. Two examples are included to point out some practical applications and to show the methods which can be employed to convert a variety of problems and conditions to the form of the generally stated problem. Part IV introduces the concept of convexity and shows the importance it plays in LP theory. Several vital theorems are stated and proved. Part V describes the simplex method of solving a problem, theoretically verifies its workability, and uses the simplex method to constructively show that certain assumptions made in Part IV could indeed be made. Hence, Part V completes the theoretical foundation. Part VI shows how the theoretically verified simplex method can be turned into a mechanical computational procedure by explaining the simplex algorithm and tableau. Finally, an example problem is solved to help clarify the workings of the algorithm and tableau.