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.