Chapter 9
Linear Programming
QUESTIONS AND ANSWERS
Q9.1 Give some illustrations of managerial decision situations in which you think the
linear programming technique would be useful.
Q9.1 ANSWER
Linear programming can be used for solving any type of constrained optimization
problem where the relations involved can be approximated by linear equations.
Q9.2 Why can’t linear programming be used in each of the following circumstances
A. Strong economies of scale exist.
B. As the firm expands output, the prices of variable factors of production increase.
C. As output increases, product prices decline.
Q9.2 ANSWER
Q9.3 Do equal distances along a given production process ray in a linear programming
problem always represent an identical level of output?
Q9.3 ANSWER
Linear Programming 231
Q9.4 Assume that output can be produced only using processes A and B. Process A
requires inputs L and K to be combined in the fixed ratio 2L:4K, and process B
requires 4L:2K. Is it possible to produce output efficiently using 3L and 3K? Why or
why not?
Q9.4 ANSWER
If Process A requires 2L:4K and process B requires 4L:2K, then it is possible to
Q9.5 Describe the relative distance method used in graphic linear programming analysis.
Q9.5 ANSWER
For feasible production points located between two production processes, both
processes will be used in production, and these points will be located on isoquants.
Q9.6 Is the number of isocost, isorevenue, or isoprofit lines in a typical two-input bounded
feasible space limited?
Q9.6 ANSWER
Q9.7 In linear programming, why is it so critical that the number of nonzero-valued
variables exactly equal the number of constraints at corners of the feasible space?
Q9.7 ANSWER
The fact that the number of nonzero-valued variables exactly equals the number of
constraints at the corners of the feasible space is important because these points will,
232 Chapter 9
Q9.8 Will maximizing a profit contribution objective function always result in also
maximizing total net profits?
Q9.8 ANSWER
Q9.9 The primal problem calls for determining the set of outputs that will maximize profit,
subject to input constraints.
A. What is the dual objective function?
B. What interpretation can be given to the dual variables called the shadow prices
or implicit values?
C. What does it mean if a dual variable or shadow price equals zero?
Q9.9 ANSWER
A. The dual objective function would be stated in terms of minimizing the value of
inputs used in production. This is a cost-minimization problem, where cost is defined
Q9.10 How are the solution values for primal and dual linear programming problems
actually employed in practice?
Q9.10 ANSWER
Solution values for primal linear programming problems provide the basis for short–
run operating decisions made subject to a wide variety of constraint conditions. They
Linear Programming 233
SELF-TEST PROBLEMS AND SOLUTIONS
ST9.1 Cost Minimization. Idaho Natural Resources (INR) has two mines with different
production capabilities for producing the same type of ore. After mining and
crushing, the ore is graded into three classes: high, medium, and low. The company
has contracted to provide local smelters with 24 tons of high-grade ore, 16 tons of
medium-grade ore, and 48 tons of low-grade ore each week. It costs INR $10,000 per
Minimize Total Cost = $10,000A + $5,000B
subject to
6A + 2B
24 (high-grade ore constraint)
or, in their equality form,
6A + 2B – SH = 24
234 Chapter 9
where
A, B, SH, SM, SL, SA, and SB
0
Here, A and B represent the days of operation per week for each mine; SH, SM, and SL
represent excess production of high-, medium-, and low-grade ore, respectively; and
SA and SB are days per week that each mine is not operated.
A graphic representation of the linear programming problem was also
Substitute A = 2 into the high-grade ore constraint:
6(2) + 2B = 24
12 + 2B = 24
2B = 12
B = 6 days per week
A minimum total operating cost per week of $50,000 is suggested, because
A. How much, if any, excess production would result if the consultant’s operating
recommendation were followed?
Linear Programming 235
B. What would be the cost effect of increasing low-grade ore sales by 50 percent?
E. What increase in the cost of operating mine B would cause INR to change its
current operating decision?
Idaho Natural Resources, Ltd.
10
11
12
Low-grade ore constraint (3)
ST9.1 SOLUTION
A. If the consultant’s operating recommendation of A = 2 and B = 6 were followed, 32
tons of excess low-grade ore production would result. No excess production of high–
236 Chapter 9
B. There would be a zero cost impact of an increase in low-grade ore sales from 48 to
C. If INR didn’t renew a contract to provide one of its current customers with 6 tons of
high-grade ore per week, the high-grade ore constraint would fall from 24 to 18 tons
Linear Programming 237
Therefore, renewing a contract to provide one of its current customers with 6 tons of
high-grade ore per week would result in our earlier operating decision of A = 2 and
D. In general, the isocost relation for this problem is
E. An increase in CB of at least $5,000 to slightly more than $10,000 will shift the
238 Chapter 9
ST9.2 Profit Maximization. Interstate Bakeries, Inc., is an Atlanta-based manufacturer
and distributor of branded bread products. Two leading products, Low Calorie, QA,
and High Fiber, QB, bread, are produced using the same baking facility and staff.
Low Calorie bread requires 0.3 hours of worker time per case, whereas High Fiber
bread requires 0.4 hours of worker time per case. During any given week, a
maximum of 15,000 worker hours are available for these two products. To meet
grocery retailer demands for a full product line of branded bread products, Interstate
A. Set up the linear programming problem that the firm would use to determine
the profit-maximizing output levels for Low Calorie and High Fiber bread.
Show both the inequality and equality forms of the constraint conditions.
B. Completely solve the linear programming problem.
C. Interpret the solution values for the linear programming problem.
D. Holding all else equal, how much would variable costs per unit on High Fiber
bread have to fall before the production level indicated in part B would
change?
ST9.2 SOLUTION
A. First, the profit contribution for Low Calorie bread, QA, and High Fiber bread, QB,
must be calculated.
Linear Programming 239
In equality form, the constraint conditions are:
Here, QA and QB are cases of Low Calorie and High Fiber bread, respectively. SA,
B. By graphing the constraints and the highest possible isoprofit line, the optimal Point
240 Chapter 9
From (3),
From (1),
From (2),
And the total profit contribution per week is:
C. Solution values can be interpreted as follows:
minimum by 5,000 units.
Linear Programming 241
D. $7.67 per case. In the initial problem, there are two feasible solutions that are at the
π = πAQA + πBQB,
or
To intersect the feasible space at point Y rather than point X, the slope of this line
would have to become slightly less negative than -1.33. To solve for the required
242 Chapter 9
Given a price of High Fiber bread of $40 per unit, a profit contribution of $15.33
Therefore, to change the optimal production point from point X to point Y, variable
PROBLEMS AND SOLUTIONS
P9.1 LP Basics. Indicate whether each of the following statements is true or false and
explain why.
A. Constant returns to scale and constant input prices are the only requirements
for a total cost function to be linear.
B. Changing input prices will always alter the slope of a given isocost line.
C. In profit-maximization linear programming problems, negative values for slack
variables imply that the amount of an input resource employed exceeds the
amount available.
D. Equal distances along a given process ray indicate equal output quantities.
E. Nonbinding constraints are constraints that intersect at the optimum solution.
P9.1 SOLUTION
Interstate Bakeries, Inc.
60,000
70,000
Cases of Low
Calorie Bread, QA
Acceptable ratio constraint (3)
High fiber constraint
(2)
244 Chapter 9
the amount of the resource used exceeds the amount available. Thus, slack variables
are included in the general non-negativity requirements for all problems.
P9.2 Fixed Input Combinations. Cherry Devices, Inc., assembles connectors and
terminals for electronic products at a plant in New Haven, Connecticut. The plant
uses labor (L) and capital (K) in an assembly line process to produce output (Q),
where
Q = 0.025L0.5K0.5
MPL = 0.0025(0.5)L-0.5K0.5
=
L
K
0.0125
0.5
0.5
MPK = 0.025(0.5)L0.5K-0.5
=
K
L
0.0125
0.5
0.5
A. Calculate how many units of output can be produced with 4 units of labor and
B. Calculate the change in the marginal product of labor as labor grows from 4 to
Linear Programming 245
C. Assume now and throughout the remainder of the problem that labor and
capital must be combined in the ratio 4L:400K. How much output could be
produced if Cherry has a constraint of L = 4,000 and K = 480,000 during the
coming production period?
D. What are the marginal products of each factor under the conditions described
in part C?
P9.2 SOLUTION
A. With L = 4 and K = 400 available:
B. The MPL is:
246 Chapter 9
Therefore, the change in the MPK is:
C. If L = 4,000 is available and each unit of output requires 4 units of labor, Cherry has
D. One additional unit of labor could be combined with 100 units of surplus capital to
produce 0.25 units of output. Thus, the MPL = 0.25. Because surplus capital is
Linear Programming 247
P9.3 LP Setup and Interpretation. The Syflansyd Nut Company has enjoyed booming
sales following the success of its “Sometimes You Feel Like a Nut, Sometimes You
Don’t” advertising campaign. Syflansyd packages and sells four types of nuts in four
different types of mixed-nut packages. These products include bulk (B), economy (E),
Given available inventory, it is management’s goal to maximize profits by
offering the optimum mix of the four package types. Profit earned per package type
is as follows:
Bulk $0.50
Economy $0.25
Fancy $1.25
Regular $0.75
The composition of each of the four package types can be summarized as follows:
Ounces per Package
Bulk
Economy
Fancy
Regular
Almonds
35
2
3
2
Cashews
35
1
4
2
Filberts
35
1
3
2
Peanuts
35
8
2
6
Solution values for the optimal number of packages to produce (decision variables)
and excess capacity (slack variables) are the following:
B = 0
E = 0
F = 1,100
248 Chapter 9
A. Identify and interpret the appropriate Syflansyd objective function.
B. Using both inequality and equality forms, set up and interpret the resource
constraints facing the Syflansyd Company.
C. Calculate optimal daily profit, and provide a complete interpretation of the full
solution to this linear programming problem.
P9.3 SOLUTION
A. It is management’s goal to maximize profits by offering the optimum mix of the four
B. In their inequality form, the resource constraint equations can be written as:
In equality form, the constraint equations are:
Linear Programming 249
Where B is the bulk package, E is the economy package, F is the fancy package, and
C. Solution values for the optimal number of packages to produce, excess capacity, and
the objective function optimal solution can be interpreted as follows:
Solution Interpretation
Optimal (maximum) daily profit is:
P9.4 Cost Minimization. Delmar Custom Homes (DCH) uses two types of crews on its
Long Island, New York,, home construction projects. Type A crews consist of master
carpenters and skilled carpenters, whereas B crews include skilled carpenters and