## Algebraic Solution

The complete specification of the illustrative programming problem is as follows:

subject to these constraints:

where

Qx > 0, Qy > 0, Sa > 0, Sb > 0, SC > 0

The problem is to find the set of values for variables QX, QY, SA, SB, and SC that maximizes Equation 9.3 and at the same time satisfies the constraints imposed by Equations 9.7, 9.8, and 9.9.

simplex solution method

Iterative technique used to provide algebraic solutions for linear programming problems

As shown previously, a single exact solution to a system of three constraint equations with five unknown variables cannot be determined without further information. A simultaneous solution to the constraint equations must be found, but there are more unknowns (five) than constraint equations (three). Here, a unique solution does not exist; multiple solutions are possible. However, because the solution to any linear programming problem occurs at a corner of the feasible space, values can be determined for some of the unknown variables in Equations 9.7, 9.8, and 9.9. At each corner point, the number of known constraint conditions is exactly equal to the number of unknown variables. In such circumstances, a single unique solution can be found for each variable at each corner point of the feasible space. The optimal solution is that corner point solution with the most desirable value for the objective function.3

Consider Figure 9.9, in which the feasible space for the illustrative problem has been graphed once again. At the origin, where neither X nor Y is produced, QX and QY both equal zero. Slack exists in all inputs, however, so Sa, Sb, and Sc are all greater than zero. Now move up the vertical axis to point K. Here QX and SC both equal zero, because no X is being produced and input C is being used to the fullest extent possible. However, QY, SA, and SB all exceed zero. At point L, QX, Qy, and SA are all positive, but SB and SC equal zero. The remaining corners, M and n, can be examined similarly, and at each of them the number of nonzero-valued variables exactly equals the number of constraints. At each corner point, the constraints can be expressed as a system with three equations and three unknowns that can be solved algebraically.

Solving the constraint equations at each corner point provides values for QX and QY, as well as for SA, SB, and SC. The total profit contribution at each corner is likewise determined by inserting relevant values for QX and QY into the objective function (Equation 9.3). The corner solution that produces the maximum profit is the optimal solution to the linear programming problem.

This iterative process is followed in what is called the simplex solution method. Computer programs find solution values for all variables at each corner point, then isolate that corner point with the optimal solution to the objective function. Highly complex linear programming problems can be solved in only a few seconds when using the simplex method and high-speed desktop computers. They are long and tedious when done by hand. Although it is perhaps not worth delving into the simplex procedure in great detail, the method can be illustrated for the present example.

Although a unique solution for this problem is obtained when any two variables are set equal to zero, it is convenient to begin by setting QX and QY equal to zero and examining the origin solution. Substituting zero values for QX and QY into the constraint Equations 9.7, 9.8, and 9.9 results in a value for each slack variable that equals the total units available: SA = 32, SB = 10, and SC = 21. At the origin, neither X nor Y is produced and no input is used in production. Total profit contribution at the origin corner of the feasible space is zero.

Similarly, it is possible to examine the solution at a second corner point, n in Figure 9.9, where QY and SA equal zero. After making the appropriate substitution into constraint Equation 9.7, the value for QX is

With the value of QX determined, it is possible to substitute into Equations 9.8 and 9.9 and determine values for SB and SC:

3 In almost all linear programming problems, the number of nonzero-valued variables in all corner solutions exactly equals the number of constraints in the problem. Only under a particular condition known as degeneracy, when more than two constraints coincide at a single corner of the feasible space, are there fewer nonzero-valued variables. This condition does not hinder the technique of solution considered in this chapter.