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 [13] (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 ...