ALGEBRAIC SPECIFICATION AND SOLUTION - Managerial Economics

Many linear programming problems contain too many variables and constraints to allow solution by graphic analysis. Algebraic methods often must be employed. Algebraic techniques are of great ractical relevance because they can be used to solve complex linear programming problems with user-friendly computer software.

Graphic Solution of a Linear Programming Problem When the Objective Function Coincides with a Boundary of the Feasible Space

slack variables

The concept of slack variables must be introduced to solve linear programming problems algebraically. In the case of less-than-or-equal-to constraints, slack variables are used to increase the left side to equal the right side limits of the constraint conditions. In the illustrative problem, one slack variable is added to each constraint to account for excess capacity. The firm is faced with capacity constraints on input factors A, B, and C, so the algebraic specification of the problem contains three slack variables: SA, indicating the units of A that are not used in any given solution; SB, representing unused units of B; and SC, which measures the unused units of C. With slack variables, each constraint equation becomes an equality rather than an inequality.

The introduction of slack variables not only simplifies algebraic analysis, but slack variables’ solution values also provide useful information. In a production problem, for example, slack variables with zero values at the optimal solution indicate inputs that are limiting factors and cause bottlenecks. Slack variables with positive values at the optimal solution indicate excess capacity in the related input factor. Slack variables cannot take on negative values, because this would imply that the amount of resource use exceeds available supply. The information provided by slack variable solution values is important in long-range planning and is a key benefit derived from algebraic solution methods.

Algebraic Solution

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

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

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.

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, 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). 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 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, where QY and SA equal zero. After making the appropriate substitution into constraint Equation

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

and

Determination of Zero-Valued Variables at Corners of the Feasible Space

Next, assign zero values to SB and SA to reach solution values for point M. Substituting zero values for SA and SB in Equations results in two equations with two unknowns:

Multiplying Equation by two and subtracting this result from Equationprovides the solution value for QX:

Then, substituting 6 for QX in Equation finds QY = 4. Total profit contribution in this case is $108 [= ($12 _ 6) + ($9 _ 4)]. Similar algebraic analysis provides the solution for each remaining corner of the feasible space. However, rather than work through those corner solutions, the results are shown in Table. It is apparent, just as illustrated in the earlier graphic analysis, that the optimal solution occurs at point M, where 6 units of X and 4 units of Y are produced. Total profit is$108, which exceeds the profit at any other corner of the feasible space.

Slack Variables at the Solution Point

At each corner point solution, values for each slack variable are also determined. For example, at the optimal solution (corner M) reached in the preceding section, SA and SB both equal zero, meaning that inputs A and B are used to the fullest extent possible. SC is not equal to zero and must be solved for. To find the solution for SC, QY = 4 is substituted into Constraint Equation:

The optimal combination of X and Y completely exhausts available quantities of inputs A and B, but 9 units of input C remain unused. Because inputs A and B impose effective constraints on the firm’s profits, more of each must be acquired to expand output. Input C is in excess supply, so the firm would certainly not want more capacity of C; it might even attempt to reduce its purchases of C during future periods. If C is a fixed facility, such as a machine tool, the firm might offer some of that excess capacity to other companies.

Algebraic Solution to a Linear Programming Problem

Computer-Based Solution Methods

The linear programming problem illustrated thus far is simple by design. It can be solved graphically and algebraically to illustrate the linear programming technique using both methods. However, linear programming problems encountered in the real world are often quite complex and frequently involve a large number of constraints and output variables. Such problems are too complicated to solve graphically. The geometry is messy for three outputs and impossible for four or more. In real-world applications, computer software programs use algebraic techniques to handle large numbers of variables and constraints.

For every maximization problem in linear programming, there exists a symmetrical minimization problem; for every minimization problem, there exists a symmetrical maximization problem.

the duality concept

Pairs of related maximization and minimization problems are known as primal and dual linear programming problems. The concept of duality demonstrates the symmetry between the value of a firm’s products and the value of resources used in production. With the duality concept, it is possible to show that value maximization can be attained by focusing on either resource requirements and the revenue-generating capability of a firm’s products or on the cost of resources and their productivity. In addition to providing valuable insight into the economics of optimal resource employment, duality provides the key to solving difficult constrained optimization problems. Because of the symmetry between primal and dual problem specifications, either one can be constructed from the other and the solution to either problem can be used to solve both. This is helpful because it is sometimes easier to obtain the solution to the dual problem than to the original or primal problem.

Finally, the duality concept also allows one to evaluate the solution to a constrained decision problem in terms of the activity required for optimization and in terms of the economic impact of constraint conditions. Analysis of the constraint conditions and slack variable solutions frequently provides important information for long-range planning. In fact, the primal solution is often described as a tool for short-run operating decisions, whereas the dual solution is often seen as a tool for long-range planning. The duality concept shows how operating decisions and long-range planning are related.