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

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.

slack variables

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:

Algebraic Solution

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

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 formula

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

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:

Equations results in two equations

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

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:

Slack Variables at the Solution Point

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

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.

Shadow Prices

To examine the duality concept, the idea of implicit values or shadow prices must be introduced. In the primal linear programming problem discussed previously, the values QX and QY maximize the firm’s profit subject to constraints imposed by limitations of input factors A, B, and C. Duality theory indicates that an identical operating decision would result if one had instead chosen to minimize the costs of resources employed in producing QX and QY, subject to an output constraint. The key to this duality is that relevant costs are not the acquisition costs of inputs but, rather, the economic costs of using them. For a resource that is available in a fixed amount, this cost is not acquisition cost but opportunity cost. Consider, for example, a skilled labor force employed by a firm. If workers are fully utilized producing valuable products, a reduction in skilled labor will reduce valuable output, and an increase in skilled labor will increase the production of valuable output. If some labor is shifted from the production of one product to another, the cost of using skilled labor in this new activity is the value of the original product that can no longer be produced. The marginal cost of a constrained resource that is fully utilized is its opportunity cost as measured by the value of foregone production.

If a limited resource such as skilled labor is not fully utilized, then at least the last unit of that resource is not productive and its marginal value is zero. Acquiring additional excess resources does not increase valuable output. The firm would incur a zero opportunity cost if it applied currently unused resources in some different activity. The economic value, or opportunity cost, of a constrained resource depends on the extent to which it is utilized. When a limited resource is fully utilized, its marginal value in use is positive. When a constrained resource is not fully utilized, its marginal value in use is zero. Minimizing the value of limited resources used to produce valuable output is nothing more than minimizing the opportunity cost of employing those resources. Minimization of opportunity costs is equivalent to maximizing the value of output produced with those resources.

Because the economic value of constrained resources is determined by their value in use rather than by historical acquisition costs, such amounts are called implicit values or shadow prices. The term shadow price is used because it represents the price that a manager would be willing to pay for additional units of a constrained resource. Comparing the shadow price of a resource with its acquisition price indicates whether the firm has an incentive to increase or decrease the amount acquired during future production periods. If shadow prices exceed acquisition prices, the resource’s marginal value exceeds marginal cost and the firm has an incentive to expand employment. If acquisition cost exceeds the shadow price, there is an incentive to reduce employment. These relations and the importance of duality can be clarified by relating the dual to the linear programming problem discussed previously.

All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd Protection Status

Managerial Economics Topics