Engineering Optimization, 5th Edition

3 Linear Programming I: Simplex Method

3.1 Introduction

Linear programming ( LP ) is an optimization method applicable for the solution of problems in which the objective function and the constraints appear as linear functions of the decision variables [1–8]. The constraint equations in a linear programming problem may be in the form of equalities or inequalities. The linear programming type of optimization 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, formulated the general linear programming problem and devised the simplex method of solution in 1947 [1]. 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, ...