4.5 The Simplex Algorithm
The simplex algorithm is a well-known algorithm for solving linear programming problems. These are problems of maximizing a utility function or a cost function subject to a number of linear constraints. The linear programming model is as follows: Maximize
subject to the set of constraints
The simplex algorithm searches for vertices of a polytope that defines the accessible region of the solution space. One goes from vertex to vertex to find the solution. The algorithm assumes nonnegativity. Inequalities are converted into equalities by adding slack variables. Let us take the following example. This example is taken from Design and Planning of Engineering Systems  (Fig. 4-7). Maximize
subject to the constraints
and the nonnegativity constraint and . For each one of the constraints, we add a slack variable , , or . We therefore convert ...