3 Linear Programming I: Simplex Method
3.1 Introduction
Linear programmingis an optimization method applicable for the solution of prob-
lems in which the objective function and the constraints appear as linear functions
of the decision variables. The constraint equations in a linear programming problem
may be in the form of equalities or inequalities. The linear programming type of opti-
mization problem was first recognized in the 1930s by economists while developing
methods for the optimal allocation of resources. During World War II the U.S. Air
Force sought more effective procedures of allocating resources and turned to linear
programming. George B. Dantzig, who was a member of the Air Force group, for-
mulated the general linear programming problem and devised the simplex method of
solution in 1947. This has become a significant step in bringing linear programming into
wider use. Afterward, much progress was made in the theoretical development and in
the practical applications of linear programming. Among all the works, the theoretical
contributions made by Kuhn and Tucker had a major impact in the development of the
duality theory in LP. The works of Charnes and Cooper were responsible for industrial
applications of LP.
Linear programming is considered a revolutionary development that permits us to
make optimal decisions in complex situations. At least four Nobel Prizes were awarded
for contributions related to linear programming. For example, when the Nobel Prize
in Economics was awarded in 1975 jointly to L. V. Kantorovich of the former Soviet
Union and T. C. Koopmans of the United States, the citation for the prize mentioned
their contributions on the application of LP to the economic problem of allocating
resources [3.14]. George Dantzig, the inventor of LP, was awarded the National Medal
of Science by President Gerald Ford in 1976.
Although several other methods have been developed over the years for solving LP
problems, the simplex method continues to be the most efficient and popular method for
solving general LP problems. Among other methods, Karmarkar’s method, developed in
1984, has been shown to be up to 50 times as fast as the simplex algorithm of Dantzig. In
this chapter we present the theory, development, and applications of the simplex method
for solving LP problems. Additional topics, such as the revised simplex method, duality
Engineering Optimization: Theory and Practice, Fourth Edition Singiresu S. Rao^119
Copyright © 2009 by John Wiley & Sons, Inc.
