Linear programming, or so-called “solver” PC software, can be used to figure out the best answer to an assortment of questions expressed in terms of functional relationships. In a fundamental sense, linear programming is a straightforward development from the more basic “what if” approach to problem solving. In a traditional “what-if” approach, one simply enters data or a change in input values in a computer spreadsheet and uses spreadsheet formulas and macros to calculate resulting output values. A prime advantage of the “what if” approach is that it allows managers to consider the cost, revenue, and profit implications of changes in a wide variety of operating conditions.
An important limitation of the “what if” method is that it can become a tedious means of searching for the best answer to planning and operating decisions. Linear programming can be thought of as performing “what-if in reverse.” All you do is specify appropriate objectives and a series of constraint conditions, and the software will determine the appropriate input values. When production goals are specified in light of operating constraints, linear programming can be used to identify the cost-minimizing operating plan. Alternatively, using linear programming techniques, a manager might find the profit-maximizing activity level by specifying production relationships and the amount of available resources.
Linear programming has proven to be an adept tool for solving problems encountered in a number of business, engineering, financial, and scientific applications. In a practical sense, typically encountered constrained optimization problems seldom have a simple rule-of-thumb solution. This chapter illustrates how linear programming can be used to quickly and easily solve real-world decision problems.
Linear programming is a useful method for analyzing and solving certain types of management decision problems. To know when linear programming techniques can be applied, it is necessary to understand basic underlying assumptions.
Many production or resource constraints faced by managers are inequalities. Constraints often limit the resource employed to less than or equal to (≤) some fixed amount available. In other instances, constraints specify that the quantity or quality of output must be greater than or equal to (≥) some minimum requirement. Linear programming handles such constraint inequalities easily, making it a useful technique for finding the optimal solution to many management decision problems. Atypical linear programming problem might be to maximize output subject to the constraint that no more than 40 hours of skilled labor per week be used. This labor constraint is expressed as an inequality where skilled labor ≤ 40 hours per week. Such an operating constraint means that no more than 40 hours of skilled labor can be used, but some excess capacity is permissible, at least in the short run. If 36 hours of skilled labor were fruitfully employed during a given week, the 4 hours per week of unused labor is called excess capacity.
As its name implies, linear programming can be applied only in situations in which the relevant objective function and constraint conditions are linear. Typical managerial decision problems that can be solved using the linear programming method involve revenue and cost functions and their composite, the profit function. Each must be linear; as output increases, revenues, costs, and profits must increase in a linear fashion. For revenues to be a linear function of output, product prices must be constant. For costs to be a linear function of output, both returns to scale and input prices must be constant.
Constant input prices, when combined with constant returns to scale, result in a linear total cost function. If both output prices and unit costs are constant, then profit contribution and profits also rise in a linear fashion with output. Product and input prices are relatively constant when a typical firm can buy unlimited quantities of input and sell an unlimited amount of output without changing prices. This occurs under conditions of pure competition. Therefore, linear programming methods are clearly applicable for firms in perfectly competitive industries with constant returns to scale. However, linear programming is also applicable in many other instances. Because linear programming is used for marginal analysis, it focuses on the effects of fairly modest output, price, and input changes. For moderate changes in current operating conditions, a constant-returns-to-scale assumption is often valid. Similarly, input and output prices are typically unaffected by modest changes from current levels. As a result, sales revenue, cost, and profit functions are often linear when only moderate changes in operations are contemplated and use of linear programming methods is valid.
To illustrate, suppose that an oil company must choose the optimal output mix for a refinery with a capacity of 150,000 barrels of oil per day. The oil company is justified in basing its analysis on the $25-per-barrel prevailing market price for crude oil, regardless of how much is purchased or sold. This assumption might not be valid if the companies were to quickly expand refinery output by a factor of 10, but within the 150,000 barrels per day range of feasible output, prices will be approximately constant. Up to capacity limits, it is also reasonable to expect that a doubling of crude oil input would lead to a doubling of refined output, and that returns to scale are constant. In many instances, the underlying assumption of linearity is entirely valid. In other instances in which the objective function and constraint conditions can be usefully approximated by linear relations, the linear programming technique can also be fruitfully applied. Only when objective functions and constraint conditions are inherently nonlinear must more complicated mathematical programming techniques be applied. In most managerial applications, even when the assumption of linearity does not hold precisely, linear approximations seldom distort the analysis.
PRODUCTION PLANNING FOR A SINGLE PRODUCT
Assume that a firm produces a single product, Q, using two inputs, L and K, which might represent labor and capital. Instead of assuming continuous substitution between L and K, as in Chapter 7, assume that Q can be produced using only four input combinations. In other words, four different production processes are available for making Q, each of which uses a different fixed combination of inputs L and K. The production processes might represent four different plants, each with its own fixed asset configuration and labor requirements. Alternatively, they could be four different assembly lines, each using a different combination of capital equipment and labor.
LP: More Than a Visual Approach
LP is often portrayed as a visual means of characterizing management problems. It is—at least when a limited number of products or product dimensions are being analyzed. When the optimal level of production for two products is sought, for example, a simple graph of the appropriate LP problem gives managers a useful intuitive basis for considering the best means of meeting a variety of production criteria. When a multitude of products are offered, or when a large number of production characteristics must be considered, the typical LP problem becomes too complex to be visualized graphically. In such instances, computer-based solutions using spreadsheets offer a tractable alternative for analyzing and solving LP problems. LP techniques are commonly used to solve problems in transportation routing, staff scheduling, and financial planning. Whenever a company needs to move a quantity of goods from and to multiple locations, such as plants, regional warehouses, or retail stores, it faces a practical LP problem. By minimizing route mileage, operating costs can also be minimized, and outlays for capital investment can be kept at a minimum. Many companies routinely save thousands of dollars per year on shipping costs by solving LP problems of this type. Businesses and government agencies use LP methods to solve the problem of scheduling employees’ working hours to meet customer service demands, which might vary by the hour or the day, in light of employee availability and preferences. Other examples of practical applications include models to help investors decide on the optimal allocation of a stock and bond portfolio. Detailed user tips on successful LP applications, often with free follow-up from the author, can be found in an almost limitless number on the Internet. One of the best sites for getting started is sponsored by Lindo Systems, Inc. There you can find LP case studies for telecommunications network design, supply chain management, and so on.
The four production processes are illustrated as rays in Figure. Process A requires the combination of 15 units of L and 1 unit of K for each unit of Q produced. Process B uses 10 units of L and 2 units of K for each unit of output. Processes C and D use 7.5 units of L and 3 units of K, and 5 units of L with 5 units of K, respectively, for each unit of Q produced. Each point along the production ray for process A combines L and K in the ratio 15 to 1; process rays B, C, and D are developed in the same way. Each point along a single production ray combines the two inputs in a fixed ratio, with the ratios differing from one production process to another. If L and K represent labor and capital inputs, the four production processes might be different plants employing different production techniques. Process A is very labor intensive
in comparison with the other production systems, whereas B, C, and D are based on increasingly capital-intensive technologies. Point A1 indicates the combination of L and K required to produce one unit of output using the A process. Doubling both L and K doubles the quantity of Q produced; this is indicated by the distance moved along ray A from A1 to A2. Line segment 0A2 is exactly twice the length of
Production Process Rays in Linear Programming
Production Process Rays in Linear Programming
line segment 0A1 and thus represents twice as much output. Along production process ray A, the distance 0A1 = A1A2 = A2A3 = A3A4 = A4A5. Each of these line segments indicates the addition of one unit of output using increased quantities of L and K in the fixed ratio of 15 to 1.
Output along the ray increases proportionately with increases in the input factors. If each input is doubled, output is doubled; if inputs increase by a factor of 10 percent, output increases by 10 percent. This follows from the linearity assumption noted previously: Each production process must exhibit constant returns to scale.
Output is measured in the same way along the three other production process rays in Figure. Point C1 indicates the combination of L and K required to produce 1 unit of Q using process C. The production of 2 units of Q using that process requires the combination of L and K indicated at point C2; the same is true for points C3, C4, and C5. Although production of additional units using process C is indicated by line segments of equal length, just as for process A, these line segments are of different lengths between the various production systems. Whereas each production process exhibits constant returns to scale, equal distances along different process rays do not ordinarily indicate equal output quantities.
Joining points of equal output on the four production process rays creates a set of isoquant curves. Figure illustrates isoquants for Q = 1, 2, 3, 4, and 5.Each isoquant represents combinations of input factors L and K that can be used to produce a given quantity of output. Production isoquants in linear programming are composed of linear segments connecting the various production process rays.
Each of these isoquant segments is parallel to one another. For example, line segment A1B1 is parallel to segment A2B2; isoquant segment B3C3 is parallel to B2C2. Points along each segment of an isoquant between two process rays represent a combination of output from each of the two adjoining production processes. Consider point X in Figure, which represents production of 4 units of Q using 25 units of L and 16 units of K. None of the available production processes can manufacture Qusing L and K in the ratio of 25 to 16, but that combination is possible by producing part of the output with process C and part with process D. In this case, 2 units of Qcan be produced using process Cand 2 units using process D. Production of 2 units of Q with process C uses 15 units of L and 6 units of K. For the production of 2 units of Q with process D, 10 units each of L and K are necessary. Although no single production system is available that can produce 4 units of Q using 25 units of L and 16 units of K, processes C and D together can produce that combination.
All points lying along production isoquant segments can be interpreted in a similar manner. Each point represents a linear combination of output using the production process systems that bound the particular segment. Point Y in Figure provides another illustration. At Y, 3 units of Qare produced, using a total of 38.5 units of L and 4.3 units of K.2 This input/output combination is possible through a combination of processes Aand B. This can be analyzed algebraically. To produce 1 unit of Qby process Arequires 15 units of L and 1 unit of K. Therefore, to produce 1.7 units of Q requires 25.5 (1.7 _ 15) units of L and 1.7 (1.7 _ 1) units of K. To produce a single unit of Q by process B requires 10 units of L and 2 units of K, so 1.3 units of Qrequires 13 (10 _1.3) units of L and 2.6 (2 _1.3) units of K. Thus, point Ycalls for the production of 3 units of Qin total, 1.7 units by process A and 1.3 units by process B, using a total of 38.5 units of L and 4.3 units of K.
2Another assumption of linear programming is that fractional variables are permissible. In many applications, this assumption is not important. For example, in the present illustration, we might be talking about labor hours and machine hours for the inputs. The solution value calling for L = 38.5 merely means that 38.5 hours of labor are required. In some cases, however, inputs are large (whole plants, for example), and the fact that linear programming assumes divisible variables is important. In such cases, linear programming as described here may be inappropriate, and a more complex technique, integer programming, may be required.
Production Isoquants in Linear Programming
Production Isoquants in Linear Programming
One method of determining the quantity to be produced by each production process at varying points along the isoquant is called the relative distance method. The relative distance method is based on the fact that the location of a point along an isoquant determines the relative shares of production for the adjacent processes. If point X in Figure were on process ray C, all output would be produced using process C. Similarly, if X were on process ray D, all output would be produced using process D. Because point X lies between process rays C and D, both processes C and D will be used to produce this output. Process C will be used relatively more than process D if X is closer to process ray C than to process ray D. Similarly, process D will be used relatively more than process C if X is closer to process ray D than to process ray C. Because point X in Figure lies at the midpoint of the Q = 4 isoquant segment between C4 and D4, it implies production using processes C and D in equal proportions. Thus, at point X, Q = 4, QC = 2, and QD = 2.
The relative proportions of process A and process B used to produce Q = 3 at Point Y can be determined in a similar manner. Because Y lies closer to process ray A than to process ray B, point Y entails relatively more output from process A than from process B. The share of total output produced using process A is calculated by considering the distance B3Y relative to B3A3. The share of total output produced using process B is calculated by considering the distance A3Y relative to A3B3. Starting from point B3, the segment B3Y covers 56.6 percent of the total distance B3A3. This means that at point Y, about 56.6 percent of total output is produced using process A (QA = 0.566 _ 3 = 1.7) and 43.4 percent (= 1.0 – 0.566) using process B (QB = 0.434 _ 3 = 1.3). Alternatively, starting from point A3, note that the segment A3Y covers 43.4 percent of the total distance A3B3. At point Y, 43.4 percent of total output is produced using process B and 56.6 percent using process A. Extreme accuracy would require painstaking graphic detail, but in many instances the relative distance method can adequately approximate production intensities along isoquants.
Least-Cost Input Combinations
Adding isocost curves to a set of isoquants permits one to determine least-cost input combinations for the production of product Q. This is shown in Figure under the assumption that each unit of L costs $3 and each unit of K costs $10. The isocost curve illustrated indicates a total expenditure of $150.
Determination of the Least-Cost Production Process
Determination of the Least-Cost Production Process
The tangency between the isocost curve and the isoquant curve for Q = 3 at point B3 indicates that process B, which combines inputs L and K in the ratio 5 to 1, is the least-cost method of producing Q. For any expenditure level, production is maximized by using process B. Alternatively, process B is the least-cost method for producing any quantity of Q, given the assumed prices for L and K.
Optimal Input Combinations with Limited Resources
Frequently, firms faced with limited inputs during a production period find it optimal to use inputs in proportions other than the least-cost combination. To illustrate, consider the effect of limits on the quantities of L and K available in our example. Assume that only 20 units of L and 11 units of K are available during the current production period and that the firm seeks to maximize output of Q. These constraints are shown in Figure. The horizontal line drawn at L = 20 indicates the upper limit on the quantity of L that can be employed during the production period; the vertical line at K = 11 indicates a similar limit on the quantity of K.
Optimal Input Combination with Limited Resources
Optimal Input Combination with Limited Resources
Production possibilities for this problem are determined by noting that, in addition to limitations on inputs L and K, the firm must operate within the area bounded by production process rays A and D. Combining production possibilities with input constraints restricts the firm to operation within the shaded area on 0PRS in Figure. This area is known as the feasible space in the programming problem. Any point within this space combines L and K in a technically feasible ratio without exceeding availability limits on L and K. Because the firm is trying to maximize production of Q subject to constraints on the use of L and K, it should operate at the feasible space point that touches the highest possible isoquant. This is point R in Figure, where Q = 3. Although it is possible to solve the foregoing problem by using carefully drawn graphs, it is typically easier to combine graphic analysis with analytical techniques to obtain accurate solutions efficiently. For example, consider Figure again. Even if the isoquant for Q = 3 were not drawn, it would be apparent from the slopes of the isoquants for 2 or 4 units of output that the optimal solution to the problem must be at point R. It is obvious from the graph that maximum production is obtained by operating at the point where both inputs are fully employed. Because R lies between production processes C and D, the output-maximizing input combination uses only those two production processes. All 20 units of L and 11 units of K will be employed, because point R lies at the intersection of these two input constraints. Using this information from the graph, it is possible to quickly and easily solve for the optimal quantities to be produced using processes C and D. Recall that each unit of output produced using process C requires 7.5 units of L. Thus, the total L required in process C equals 7.5 _ QC.
Similarly, each unit produced using process D requires 5 units of L, so the total L used in process D equals 5 _ QD. At point R, 20 units of L are being used in processes C and D together, and the following must hold:
A similar relation can be developed for the use of K. Each unit of output produced from process C requires 3 units of K, whereas process D uses 5 units of K to produce each unit of output. The total use of K in processes C and D equals 11 units at point R, so Although linear programming has been widely applied in managerial decision making, it has been used most frequently in production decisions. To illustrate the method, a simple twoinput/ one-output problem is examined. Later sections consider more realistic and complex problems.
Equations 9.1 and 9.2 both must hold at point R. Output quantities from processes C and D at that location are determined by solving these equations simultaneously. Subtracting Equation 9.2 from Equation 9.1 to eliminate the variable QD isolates the solution for QC:
Total output at point R is 3 units, composed of 2 units from process C and 1 unit from process D. The combination of graphic and analytic techniques allows one to obtain precise linear programming solutions with relative ease.
PRODUCTION PLANNING FOR MULTIPLE PRODUCTS
Many production decisions are more complex than the preceding example. Consider the problem of finding the optimal output mix for a multiproduct firm facing restrictions on productive facilities and other inputs. This problem, which is faced by a host of companies producing consumer and producer goods alike, is readily solved with linear programming techniques.
Consider a firm that produces products X and Y and uses inputs A, B, and C. To maximize total profit, the firm must determine optimal quantities of each product subject to constraints imposed on input availability. It is often useful to structure such a linear programming problem in terms of the maximization of profit contribution, or total revenue minus variable costs, rather than to explicitly maximize profits. Of course, fixed costs must be subtracted from profit contribution to determine net profits. However, because fixed costs are constant, maximizing profit contribution is tantamount to maximizing profit. The output mix that maximizes profit contribution also maximizes net profit.
An equation that expresses the goal of a linear programming problem is called the objective function. Assume that the firm wishes to maximize total profits from the two products, X and Y, during each period. If per-unit profit contribution (the excess of price over average variable costs) is $12 for product X and $9 for product Y, the objective function is
QX and QY represent the quantities of each product produced. The total profit contribution, π, earned by the firm equals the per-unit profit contribution of X times the units of X produced and sold, plus the profit contribution of Y times QY.
Constraint Equation Specification
Table specifies the available quantities of each input and their usage in the production of X and Y. This information is all that is needed to form the constraint equations.
The table shows that 32 units of input A are available in each period. Four units of A are required to produce each unit of X, whereas 2 units of A are necessary to produce 1 unit of Y. Because 4 units of A are required to produce a single unit of X, the total amount of A used to manufacture X can be written as 4QX. Similarly, 2 units of A are required to produce each unit of Y, so 2QY represents the total quantity of A used to produce product Y. Summing the quantities of A used to produce X and Y provides an expression for the total usage of A. Because this total cannot exceed the 32 units available, the constraint condition for input A is
The constraint for input B is determined in a similar manner. One unit of input B is necessary to produce each unit of either X or Y, so the total amount of B employed is 1QX + 1QY. The maximum quantity of B available in each period is 10 units; thus, the constraint requirement associated with input B is
Finally, the constraint relation for input C affects only the production of Y. Each unit of Y requires an input of 3 units of C, and 21 units of input C are available. Usage of C is given by the expression 3QY, and the relevant constraint equation is
Constraint equations play a major role in solving linear programming problems. One further concept must be introduced, however, before the linear programming problem is completely specified and ready for solution.
Non negativity Requirement
Because linear programming is merely a mathematical tool for solving constrained optimization problems, nothing in the technique itself ensures that an answer makes economic sense. In a production problem for a relatively unprofitable product, the mathematically optimal output level might be a negative quantity, clearly an impossible solution. In a distribution problem, an optimal solution might indicate negative shipments from one point to another, which again is impossible.
Inputs Available for Production of X and Y
To prevent economically meaningless results, a nonnegativity requirement must be introduced. This is merely a statement that all variables in the problem must be equal to or greater than zero. For the present production problem, the following expressions must be added:
GRAPHIC SPECIFICATION AND SOLUTION
Having specified all the component parts of the firm’s linear programming problem, the problem can now be illustrated graphically and analyzed algebraically. The decision problem is to maximize total profit contribution, π, subject to resource constraints. This is expressed as
Each variable and coefficient is exactly as specified previously.
Graphing the Feasible Space
In Figure, the graph of the constraint equation for input A, 4QX + 2QY = 32, indicates the maximum quantities of X and Y that can be produced given the limitation on the availability of input A. Amaximum of 16 units of Y can be produced if no X is manufactured; 8 units of X can be produced if the output of Y is zero. Any point along the line connecting these two outputs represents the maximum combination of Xand Y that can be produced with no more than 32 units of A. This constraint equation divides the XY plane into two half spaces. Every point lying on the line or to the left of the line satisfies the constraint expressed by the equation 4QX + 2QY ≤ 32; every point to the right of the line violates that expression. Only points on the constraint line or to the left of it are in the feasible space. The shaded area of Figure represents the feasible area limited by the constraint on input A. In Figure, the feasible space is limited further by adding constraints for inputs B and C. The constraint on input B is expressed as QX + QY = 10. If no Y is produced, a maximum of 10 units of X can be produced; if output of X is zero, 10 units of Y can be manufactured. All combinations of X and Y lying on or to the left of the line connecting these two points are feasible with respect to utilization of input B.
Constraint Imposed by Limitations on Input A
Constraint Imposed by Limitations on Input A
The horizontal line at QY = 7 in Figurerepresents the constraint imposed by input C. Because C is used only in the production of Y, it does not constrain the production of X. Seven units are the maximum quantity of Y that can be produced with 21 units of C available. These three input constraints, together with the nonnegativity requirement, completely define the feasible space shown as the shaded area of Figure. Only points within this area meet all constraints.
Graphing the Objective Function
The objective function, π = $12QX + $9QY, can be graphed in QXQY space as a series of isoprofit curves. This is illustrated in Figure, where isoprofit curves for $36, $72, $108, and $144 are shown. Each isoprofit curve illustrates all possible combinations of X and Y that result in a constant total profit contribution. For example, the isoprofit curve labeled π = $36 identifies each combination of X and Y that results in a total profit contribution of $36; all output combinations along the π = $72 curve provide a total profit contribution of $72; and so on. It is clear from Figure that isoprofit curves are a series of parallel lines that take on higher values as one moves upward and to the right.
The general formula for isoprofit curves can be developed by considering the profit function π = aQX + bQY, where a and b are the profit contributions of products X and Y, respectively. Solving the isoprofit function for QY creates an equation of the following form:
Given the individual profit contributions, a and b, the QY intercept equals the profit level of the isoprofit curve divided by the profit per unit earned on QY, π/b. Slope of the objective function is given by the relative profitability of the two products, –a/b. Because the relative profitability of the products is not affected by the output level, the isoprofit curves consist of a series of parallel lines. In this xample, all isoprofit curves have a slope of –12/9, or –1.33.
Because the firm’s objective is to maximize total profit, it should operate on the highest isoprofit curve obtainable. To see this point graphically, Figure combines the feasible space limitations shown in Figure 9.6 with the family of isoprofit curves discussed here. Using this approach, point M in the figure is indicated as the optimal solution. At point M, the firm produces 6 units of X and 4 units of Y, and the total profit is $108 [=($12 _ 6) + ($9 _ 4)], which is the maximum available under the conditions stated in the problem. No other point within the feasible spaces touches so high an isoprofit curve.
Graphic Solution of the Linear Programming Problem
Using the combined graphic and analytical method introduced in the preceding section, M can be identified as the point where QX = 6 and QY = 4. At M, constraints on inputs A and B are binding. At M, 32 units of input A and 10 units of input B are being completely used to produce X and Y. Thus, Equations can be written as equalities and solved simultaneously for QX and QY. Subtracting two times Equation from Equation gives
Notice that the optimal solution to the linear programming problem occurs at a corner point of the feasible space. A corner point is a spot in the feasible space where the X-axis, Y-axis, or constraint conditions intersect. The optimal solution to any linear programming problem always lies at a corner point. Because all of the relations in a linear programming problem must be linear by definition, every boundary of the feasible space is linear. Furthermore, the objective function is linear. Thus, the constrained optimization of the objective function takes place either at a corner of the feasible space or at one boundary face, as is illustrated by Figure.
In Figure, the linear programming example has been modified by assuming that each unit of either Xor Y yields a profit of $5. In this case, the optimal solution to the problem includes any of the combinations of X and Y found along line LM. All of these combinations are feasible and result in a total profit of $50. If all points along line LM provide optimal combinations of output, the combinations found at corners L and Mare also optimal. Because the firm is indifferent about producing at point L or at point M, or at any point in between, any such location provides an optimal solution to the production problem. The search for an optimal solution can be limited to just the corners of each linear programming problem’s feasible space. This greatly reduces the number of necessary computations.
ALGEBRAIC SPECIFICATION AND SOLUTION
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
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.
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:
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.
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.
DUAL OBJECTIVE FUNCTION
In the original or primal problem statement, the goal is to maximize profits, and the (primal) objective function is
The dual problem goal is to minimize implicit values or shadow prices for the firm’s resources. Defining VA, VB, and VC as the shadow prices for inputs A, B, and C, respectively, and π* as the total implicit value of the firm’s fixed resources, the dual objective function (the dual) is
Because the firm has 32 units of A, the total implicit value of input Ais 32 times A’s shadow price, or 32VA. If VA, or input A’s shadow price, is found to be $1.50 when the dual equations are solved, the implicit value of A is $48 (= 32 _ $1.50). Inputs B and C are handled in the same way.
In the primal problem, the constraints stated that the total units of each input used to produce X and Y must be equal to or less than the available quantity of input. In the dual, the constraints state that the total value of inputs used to produce one unit of X or one unit of Y must not be less than the profit contribution provided by a unit of these products. In other words, the shadow prices of A, B, and C times the amount of each of the inputs needed to produce a unit of X or Y must be equal to or greater than the unit profit contribution of X or of Y. Because resources have value only when used to produce output, they can never have an implicit value, or opportunity cost, that is less than the value of output.
In the example, unit profit is defined as the excess of price over variable cost, price and variable cost are both constant, and profit per unit for X is $12 and for Y is $9. As shown in Table, each unit of X requires 4 units of A, 1 unit of B, and 0 units of C. The total implicit value of resources used to produce X is 4VA + 1VB. The constraint requiring that the implicit cost of producing X be equal to or greater than the profit contribution of X is
Because 2 units of A, 1 unit of B, and 3 units of C are required to produce each unit of Y, the second dual constraint is
Because the firm produces only two products, the dual problem has only two constraint equations.
Dual Slack Variables
Dual slack variables can be incorporated into the problem, thus allowing the constraint conditions to be expressed as equalities. Letting LX and LY represent the two slack variables, constraint Equations become
These slack variables are subtracted from the constraint equations, because greater-than-or-equalto inequalities are involved. Using slack variables, the left-hand sides of the constraint conditions are thus decreased to equal the right-hand sides’ profit contributions. Dual slack variables measure the excess of input value over output value for each product. Alternatively, dual slack variables measure the opportunity cost associated with producing X and Y. This can be seen by examining the two constraint equations. Solving constraint Equation for LX, for example, provides
This expression states that LX is equal to the implicit cost of producing 1 unit of X minus the profit contribution provided by that product. The dual slack variable LX is a measure of the opportunity cost of producing product X. It compares the profit contribution of product X, $12, with the value to the firm of the resources necessary to produce it.
Azero value for LX indicates that the marginal value of resources required to produce 1 unit of X is exactly equal to the profit contribution received. This is similar to marginal cost being equal to marginal revenue at the profit-maximizing output level. Apositive value for LX indicates that the resources used to produce X are more valuable, in terms of the profit contribution they can generate, when used to produce the other product Y. A positive value for LX measures the firm’s opportunity cost (profit loss) associated with production of product X. The slack variable LY is the opportunity cost of producing product Y. It will have a value of zero if the implicit value of resources used to produce 1 unit of Yexactly equals the $9 profit contribution provided by that product. A positive value for LY measures the opportunity loss in terms of the foregone profit contribution associated with product Y.
Afirm would not choose to produce if the value of resources required were greater than the value of resulting output. It follows that a product with a positive slack variable (opportunity cost) is not included in the optimal production combination.
Solving the Dual Problem
The dual programming problem can be solved with the same algebraic technique that was employed to obtain the primal solution. In this case, the dual problem is
Because there are only two constraints in this programming problem, the maximum number of nonzero-valued variables at any corner solution is two. One can proceed with the solution by setting three of the variables equal to zero and solving the constraint equations for the values of the remaining two. By comparing the value of the objective function at each feasible solution, the point at which the function is minimized can be determined. This is the dual solution. To illustrate the process, first set VA = VB = VC = 0, and solve for LX and LY:
Because LX and LY cannot be negative, this solution is outside the feasible set. The values just obtained are inserted into Table as solution 1. All other solution values can be calculated in a similar manner and used to complete Table. It is apparent from the table that not all solutions lie within the feasible space. Only solutions 5, 7, 9, and 10 meet the nonnegativity requirement while also providing a number of nonzero-valued variables that are exactly equal to the number of constraints. These four solutions coincide with the corners of the dual problem’s feasible space.
At solution 10, the total implicit value of inputs A, B, and C is minimized. Solution 10 is the optimum solution, where the total implicit value of employed resources exactly equals the $108 maximum profit primal solution. Thus, optimal solutions to primal and dual objective functions are identical.
At the optimal solution, the shadow price for input C is zero, VC = 0. Because shadow price measures the marginal value of an input, a zero shadow price implies that the resource in question has a zero marginal value to the firm. Adding another unit of this input adds nothing to the firm’s maximum obtainable profit. A zero shadow price for input C is consistent with the primal solution that input C is not a binding constraint. Excess capacity exists in C, so additional units of C would not increase production of either X or Y. The shadow price for input A of $1.50 implies that this fixed resource imposes a binding constraint. If an additional unit of
Solutions for the Dual Programming Problem
A is added, the firm can increase total profit by $1.50. It would increase profits to buy additional units of input A at any price less than $1.50 per unit, at least up until the point at which A is no longer a binding constraint. This assumes that the cost of input A is currently fixed. If those costs are variable, the firm would be willing to pay $1.50 above the current price of input A to eliminate this constraint. Because availability of B also imposes an effective constraint, the firm can also afford to pay up to $6 for a marginal unit of B.
Finally, both dual slack variables equal zero at the optimal solution. This means that the implicit value of resources required to produce a single unit of X or Y is exactly equal to the profit contribution provided. The opportunity cost of producing X and Y is zero, meaning that the resources required for their production are not more valuable in some alternative use. This is consistent with the primal solution, because both X and Y are produced at the optimal solution. Any product with a positive opportunity cost is suboptimal and would not be produced.
Using the Dual Solution to Solve the Primal
The dual solution does not indicate optimal amounts of Xand Y. It does, however, provide all the information necessary to determine the optimum output mix. The dual solution shows that input C does not impose a binding constraint on output of X and Y. Further, it demonstrates that π = π* = $108 at the optimum output of X and Y. The dual solution also offers evidence on the value of primal constraint slack variables. To see this, recall the three constraints in the primal problem:
The dual solution indicates that the constraints on Aand B are binding, because both inputs have positive shadow prices, and only resources that are fully utilized have a nonzero marginal value. ccordingly, the slack variables SA and SB equal zero, and the binding primal constraints can be rewritten as
With two equations and only two unknowns, this system can be solved for QX and QY. Multiplying the second constraint by two and subtracting from the first provides
These values of QX and QY, found after learning from the dual which constraints were binding, are identical to the values found by solving the primal problem directly. Having obtained the value for QY, it is possible to substitute value for QY in constraint C and solve for the amount of slack in that resource:
These relations, which allow one to solve either the primal or the dual specification of a linear programming problem and then quickly obtain the solution to the other, can be generalized by the two following expressions:
Equation states that if an ordinary variable in the primal problem takes on a nonzero value in the optimal solution to that problem, its related dual slack variable must be zero. Only if a particular Qi is zero valued in the solution to the primal can its related dual slack variable, Li, take on a nonzero value. A similar relation exists between the slack variables in the primal problem and their related ordinary variables in the dual, as indicated by Equation 9.16. If the primal slack variable is nonzero valued, then the related dual variable will be zero valued, and vice versa.
CONSTRAINED COST MINIMIZATION ANOTHER LP EXAMPLE
Constrained cost-minimization problems are frequently encountered in managerial decision making. One such example is the problem of minimizing advertising expenditures subject to certain audience exposure requirements.
Consider a firm that is planning an advertising campaign for a new product. Goals set for the campaign include exposure to at least 100,000 individuals, no fewer than 80,000 of whom have an annual income of at least $50,000 and no fewer than 40,000 of whom are single. For simplicity, assume that the firm has only radio and television media available for this campaign.
One television advertisement costs $10,000 and is expected to reach an average audience of 20,000 persons. Ten thousand of these individuals will have an income of $50,000 or more, and 4,000 will be single. Aradio advertisement costs $6,000 and reaches a total audience of 10,000, all of whom have at least $50,000 in income. Eight thousand of those exposed to a radio advertisement are single. Table summarizes these data.
The objective is to minimize the cost of the advertising campaign. Because total cost is merely the sum of the amounts spent on radio and television advertisements, the objective function is Minimize Cost = $6,000R + $10,000TV where R and TV represent the number of radio and television ads, respectively, that are employed in the advertising campaign.
This linear programming problem has three constraint equations, including the minimum audience exposure requirement, the audience income requirement, and the marital status requirement. The minimum audience exposure requirement states that the number of persons exposed to radio ads plus the number exposed to television ads must be equal to or greater than 100,000 persons. Algebraically, 10,000 times the number of radio ads plus 20,000 times the number of television advertisements must be equal to or greater than 100,000: 10,000R + 20,000TV ≥ 100,000 The two remaining constraints can be constructed in a similar fashion from the data in Table. The audience income constraint is written 10,000R + 10,000TV ≥ 80,000 and the marital status constraint is given by 8,000R + 4,000TV ≥ 40,000 Combining the cost-minimization objective function with these three constraint conditions written in equality form using slack variables gives the complete linear programming problem:
Advertising Cost-Minimization Linear Programming Problem
SA, SI, and SS are slack variables indicating the extent to which minimums on total audience exposure, exposure to individuals with incomes of at least $50,000, and exposure to single individuals, respectively, have been exceeded. Note that each slack variable is subtracted from the relevant constraint equation because greater-than-or-equal-to inequalities are involved. Excess capacity or nonzero slack variables for any of the constraints mean that audience exposure minimums have been exceeded.
The solution to this linear programming problem is easily obtained using a combination of graphic and analytical methods. Figure illustrates this solution. The feasible space problem is bordered by the three constraint equations and the nonnegativity requirements. An isocost curve shows that costs are minimized at point M, where the total audience exposure and income constraints are binding. With these constraints binding, slack variables SA = SI = 0. Thus.
The firm should employ six radio advertisements and two television advertisements to minimize costs while still meeting audience exposure requirements. Total cost for such a campaign is $56,000.
The dual to the advertising-mix problem is a constrained-maximization problem, because the primal is a minimization problem. The objective function of the dual is expressed in terms of shadow prices or implicit values for the primal constraint conditions. The dual objective function includes an implicit value, or shadow price, for the minimum audience exposure requirement, the audience income requirement, and the marital status requirement. Because constraint limits in the primal problem become the dual objective function coefficients, the dual objective function is Maximize C* = 100,000VA + 80,000VI + 40,000VS where VA, VI, and VS are shadow prices for the minimum audience exposure, audience income, and marital status requirements. Dual constraints are based on the two variables from the primal objective function. Thus, there are two constraint conditions in the dual, the first associated with radio advertisements and the second with television advertisements. Both constraints are of the less-than-or-equal-to type, because primal constraints are of the greater-than-or-equal-to type. The radio advertising constraint limit is the $6,000 radio advertisements coefficient from the primal objective function. Coefficients for each shadow price in this constraint equation are given by the advertising effectiveness measures for a single radio advertisement. The coefficient for the audience exposure shadow price, VA, is 10,000, the number of individuals reached by a single radio advertisement. Similarly, the coefficient for VI is 10,000 and that for VS is 8,000. Thus, the dual radio advertisements constraint is
10,000VA + 10,000VI + 8,000VS ≤ $6,000
The dual television advertising constraint is developed in the same fashion. Because each TV advertisement reaches a total audience of 20,000, this is the coefficient for the VA variable in the second dual constraint equation. Coefficients for VI and VS are 10,000 and 4,000, respectively, because these are the numbers of high-income and single persons reached by one TV advertisement. The $10,000 cost of a television advertisement is the limit to the second dual constraint, which can be written
Solving the Dual
It is possible but difficult to solve this dual problem using a three- imensional graph or the simplex method. However, because the primal problem has been solved already, information from this solution can be used to easily solve the dual. Remember that the solutions to the primal and dual of a single linear programming problem are complementary, and the following must hold:
Because both R and TV have nonzero solutions in the primal, the dual slack variables LR and LTV must equal zero at the optimal solution. Furthermore, because there is excess audience exposure to the single marital status category in the primal solution, SS ≠ 0, the related dual shadow price variable VS must also equal zero in the optimal solution. This leaves only VA and VI as two unknowns in the two-equation system of dual constraints:
Substituting the value $0.40 for VAin either constraint equation produces a value of $0.20 for VI. Finally, substituting the appropriate values for VA, VI, and VS into the dual objective function gives a value of C* = $56,000 [= ($0.40 _ 100,000) + ($0.20 _ 80,000) + ($0 _ 40,000)]. This is the same figure as the $56,000 minimum cost solution to the primal.
Interpreting the Dual Solution
The primal solution tells management the minimum-cost advertising mix. The dual problem results are equally valuable. Each dual shadow price indicates the change in cost that would accompany a one-unit change in the various audience exposure requirements. These prices show the marginal costs of increasing each audience exposure requirement by one unit.
For example, VA is the marginal cost of reaching the last individual in the overall audience. If there were a one-person reduction in the total audience exposure requirement, a cost saving of VA = $0.40 would be realized. The marginal cost of increasing total audience exposure from 100,000 to 100,001 individuals would also be 40¢. Shadow prices for the remaining constraint conditions are interpreted in a similar manner. The shadow price for reaching individuals with incomes of at least $50,000 is VI = $0.20, or 20¢. It would cost an extra 20¢ per person to reach more high-income individuals. Azero value for VS, the marital status shadow price, means that the proposed advertising campaign already reaches more than the 40,000 minimum required number of single persons. Thus, a small change in the marital status constraint has no effect on total costs. By comparing these marginal costs with the benefits derived from additional exposure, management is able to judge the effectiveness of its media advertising campaign. If the expected profit per exposure exceeds 40¢, it would prove profitable to design an advertising campaign for a larger audience. Likewise, if the expected return per exposure to high-income individuals is greater than 20¢, promotion to this category of potential customers should be increased.
Conversely, if marginal profitability is less than marginal cost, audience size and/or income requirements should be reduced. Dual slack variables also have an interesting interpretation. They represent opportunity costs of using each advertising medium. LR measures the excess of cost over benefit associated with using radio, whereas LTV indicates the excess of cost over benefit for television. Since LR = LTV = 0, the marginal benefit derived just equals the marginal cost incurred for both media. Both radio and TV are included in the optimal media mix, as was indicated in the primal solution.
his example again demonstrates the symmetry of the primal and dual specifications of linear programming problems. Either specification can be used to describe and solve the same basic problem. Both primal and dual problem statements and solutions offer valuable insight for decision making.