B40 SUPPLEMENT B LINEAR PROGRAMMING
Paper Grade Strength Color Texture Cost/Ton
1 8 9 8 $150
2 6 7 5 $110
3556$90
4345$50
time available each week in each department, and it can ob-
tain up to 2000 board feet of oak and 1500 square feet of
pecan veneer each week. The cost of operating each manu-
facturing department is essentially fixed, so RFC would like
to maximize its contribution to overhead (revenue minus
variable costs).
a. Formulate RFC’s problem as a linear program, defin-
ing your variables clearly.
b. Solve the problem (graphically, using the simplex
method, or using a computer) and state what RFC should do
(i.e., explain RFC’s optimal solution in words).
c. What resource is limiting RFC’s production?
3. Western Pulp (WP) produces recycled paperboard for
box manufacturers by combining four grades of recycled pa-
per stock. Each grade of stock has a different strength, color,
and texture. The strength, color, and texture of the paper-
board are approximately a weighted average of those charac-
teristics of the paper inputs. The table gives the characteris-
tics of the paper stocks and their cost per ton. WP has
received an order for 500 tons of paperboard with a strength
rating of at least 7, a color of at least 5, and texture of at least
6. WP would like to determine the least costly mix required
to produce this paperboard.
a. Formulate the problem as a linear program.
b. Solve this problem on a computer and explain the op-
timal solution.
4. Volcano Potato Company (VPC) grows potatoes,
processes them, and then sells three potato products: fresh
potatoes, frozen french fried potatoes, and frozen hash ball
potatoes (shredded and then reconstituted balls of potatoes
with a soft consistency). During the next two months, VPC
expects to harvest 8 million pounds of potatoes. VPC would
like to determine how much of each product should be made
from the potatoes. Potatoes are graded according to quality
on a 0 –5 scale. VPC divides its potatoes into three grades: A,
B, and C. Grade A potatoes have an average quality rating of
4.5; grade B potatoes have an average quality rating of 2.5,
and grade C potatoes have a quality rating below 1 and are
not used for any products. From historical data and esti-
mates based on the current growing season’s weather, VPC
believes the distribution of potato quality will be:
Fresh potatoes earn a profit of $0.40 per pound after
processing costs, but only grade A potatoes can be sold as
fresh potatoes. Frozen french fried potatoes earn $0.32 per
pound after processing costs, but the potatoes used must
have an average quality rating of at least 3.5. Hash balls earn
$0.25 per pound after processing costs, but the potatoes used
must have an average quality rating of at least 3.0. Assume
that these ratings are linear in the sense that the quality rat-
ing of a mixture equals the weighted average of the inputs.
VPC believes it can sell as much french fried and hash ball
potatoes as it can make, but it believes the total demand for
its fresh potatoes during the next two months is 2.5 million
pounds.
a. Formulate a linear programming model to determine
the best use for the potatoes so as to maximize VPC’s
profit.
b. Solve the problem using a computer and explain the
answer in words.
c. Suppose VPC could buy additional grade A potatoes at
$0.35 per pound; how much should it buy? Explain.
5. Manfred Leaks manages a large discount store. His
biggest problem has been scheduling cashiers so that he has
an adequate number without having too many. The store is
open from 9
A.M. to 9 P.M. every day of the week. Based on
historical data, he found that the customer patterns for
Monday to Thursday are essentially the same, but those
for Friday, Saturday, and Sunday are all different. He
divided the day into three 4-hour segments and esti-
mated how many cashiers were needed for each time period
for each day of the week. These are given in the following
table.
Day of Week Mon–Thur Fri Sat Sun
9
A.M.– 1 P.M.6 3104
1
P.M.– 5 P.M.5 81412
5 P.M
.– 9 A.M.8 476
Grade A B C
% of Harvest 50 40 10
Employees must work continuous 8-hour shifts begin-
ning at 9
A.M. or 1 P.M., and their weekly schedules must be
made up of 5 consecutive days of work with 2 consecutive
days off (and they work the same hours each workday).
Manfred would like to devise weekly schedules that will min-
imize the total number of cashiers needed, but the schedules
must be such that the minimum cashier requirements in the
table are satisfied.
a. Formulate Manfred’s problem as a linear program; be
sure to define the variables precisely. (Hint: There are 14
possible schedules; there will be one variable correspond-
ing to each schedule.)
b. Solve the problem using a computer.
c. Is the assumption of divisibility satisfied? Will your an-
swer to this question be true in general? Explain.