
3
The Simplex Method
3.1 Introduction
In this chapter the simplex method, which is an important and well-known
method to solve linear programming problems, is developed. The simplex
method was conceived by Dantzig (1948), still remains a powerful class of
methods, and is often the main strategy for solving linear programs in commer-
cial software. We know by the Fundamental Theorem of Linear Programming
in Chapter 2 that if an LP has a finite optimal solution, then it can be attained
at an extreme point and therefore at some basic feasible solution. The basic
strategy of the simplex method is to explore the extreme points of the feasible
region of an