4.1 Slack Variables
and the Pivot
4.2 The Simplex Method: Solving Standard Maximization Problems
The simplex method starts with the selection of one corner point from the feasible region. Systematically, another corner point is found that tries to improve the value of the objective function. Ultimately, an optimum solution is reached, or it is seen that no such solution exists.
The understanding behind the simplex method is this: In any linear programming problem, there is a feasible region. If there are only two unknowns, we can draw the region and solve graphically as previously seen; if there are three unknowns, it is a solid region in space; and if there are four or more unknowns, it is an abstract higher-dimensional region. However, it is a faceted region with corners, and it is at one of these corners that we will find the optimal solution. It is with this unknowns of 3 or more variables that we see the benefit of the simplex method.
A linear programming problem is in standard maximum form if the following conditions are satisfied:
1. The objective function is to be maximized.
2. All variables are nonnegative (