What is a standard maximization problem?
The Simplex Method is easiest to apply to a type of linear programming problem called the standard maximization problem.
A standard maximization problem is a type of linear programminbn g problem in which the objective function is to be maximized and has the form
z = a1 x1 + a2 x2 + … + an xn
where a1, …, an are real numbers and x1, …, xn are decision variables. The decision variables must represent non-negative values. The other constraints for the standard maximization problem have the form
b1 x1 + b2 x2 + … + bn xn ≤ c
where b1, …, bn and c are real numbers and c ≥ 0.
There are other types of linear programming problems (we’ll examine some of these in the next section), but in this section all of the problems are standard maximization problems. For instance, the craft brewery problem is a standard maximization problem. Even though the letter describing the variable P is not the same as z, it still fits the standard maximization form:
Since this example has only two decision variables x1 and x2, this example does not exploit the full power of the Simplex Method. However this problem and similar problems are useful for demonstrating the Simplex Method and we’ll focus on them to begin with. Once the strategy for solving the standard maximization problem has been established, we’ll extend the strategy to more complex problems.