CHAPTER 9--LINEAR PROGRAMMING
Student: ___________________________________________________________________________
3. When the primal LP problem is to maximize revenue subject to various input constraints, the shadow prices
4. If the primal objective function is to minimize cost subject to output constraints, the dual objective function is
7. If the objective function is to maximize revenue subject to a binding labor constraint, then the shadow price
14. To determine the quantity to be produced by each production process at varying points along an isoquant,
22. If a linear programming problem involves the minimization of advertising costs subject to audience marital
26. Linear Programming Concepts. Indicate whether each of the following statements is true or false. Defend
your answer.
27. LP Basics. Indicate whether each of the following statements is true or false and why.
28. Fixed Input Relations. Extreme Biking, Inc., assembles high-end extreme mountain bicycles at a plant in
Lexington, Massachusetts. The plant uses labor (L) and capital (K) in an assembly line process to produce
output (Q) where:
Q
= 0.01L1/2K1/2
MPL
MPK
29. Return Maximization. The American Balanced Fund is an open-end investment company (mutual fund)
designed to meet the needs of investors planning for future retirement. ABF seeks to provide current income
plus capital growth by investing in a diversified portfolio of high-quality stocks and investment-grade bonds.
The fund's bylaws state that at least 30% of the portfolio must be invested in bonds in order to reduce downside
risk during bear markets. The fund's growth potential is maintained by a requirement that the share of the
portfolio invested in common stocks must be at least as large as the share devoted to bonds. Like most mutual
funds, ABF is prohibited from using leverage (borrowing) to enhance investor ABF returns. Without leverage,
stock and bond investments cannot exceed 100% of ABF's portfolio. And finally, the fund's investment
management committee currently projects an expected return of 10% on stocks and 8% on bonds.
30. Optimal Production. Canine Products, Inc., produces and markets a new moist and chewy nugget dog food
called "Chow Hound" being test marketed in the San Diego market. This product is similar to several others
offered by Canine Products, and can be produced with currently available equipment and personnel using any of
three alternative product methods. Method A requires 6 hours of labor and 1 processing facility hour to produce
100 bags of dog food, QA. Method B requires 3 labor and 3 processing facility hours per QB. Method C requires
2 labor hours and 4 processing facility hours per unit of QC. Because of slack demand for other products CP
currently has 15 labor hours and 5 processing facility hours available per week for producing Chow Hound.
31. Optimal Production. Video-Scapes, Inc. (VSI) is a rapidly growing landscaping service in Oakland,
California that specializes in merging videos of one's home and property with changeable computer-generated
graphics of various landscape details. VSI offers budget landscaping designs for $1,500 and deluxe designs for
$3,000. Both services use scarce computing, creative and consulting resources. Each budget design requires 4
hours of computer time, 2 hours of creative time, and 4 hours of consulting time with the client. Each deluxe
design requires 6 hours of computer time, 6 hours of creative time, and 4 hours of consulting time. VSI
currently has 60 hours of computer time, 42 hours of creative time, and 36 hours of consulting time available on
a weekly basis. What output mix would be optimal if VSI wishes to maximize total sales revenue?
32. Optimal Lending. Penny Lane is a senior loan officer with Citrus National Bank in Tampa, Florida. Lane
33. Optimal Production. Ozark Telephone, Inc. (OTI) is a small telephone company offering local dial-tone
service to its franchised areas in rural southeastern Missouri. A new office park development site is being
planned within OTI's territory and John Sample, a network engineer, has to maximize the conversation capacity
per line under cost and technology constraints using both traditional copper-wire lines and new fiber-optic lines.
OTI wants to gradually move into the all-digital communication environment possible with fiber-optics, so a
company policy has been adopted specifying that at least 3 fiber-optic lines be employed for every 2 copper
lines on new installations. To minimize the need to quickly retrain its linemen, OTI wants at least 30% of new
telephone lines installed to be copper. No existing telephone facilities run to the development site, and OTI
must use its own facilities to carry the traffic (it cannot lease capacity from any other local telephone company).
Finally, current costs and technologies dictate that 1 fiber line can carry the equivalent of 5 copper lines at the
same cost to OTI. That is, if one copper line can carry one telephone conversation, fiber optic lines can carry
five conversations at no cost penalty. Sample's objective is to maximize the capacity per line of the
transmissions facilities being built to carry traffic to/from the office park.
34. Cost Minimization. Environmental Products, Inc. manufactures surfactants used in fertilizers and
herbicides (surfactants minimize runoff). Environmental Products uses two manufacturing processes, each
having advantages. The Hidex process is more expensive ($0.50 per gallon of Hidex) but produces more
surfactant and fewer emissions of the pollutant toxide per gallon used. The Lodex process is less efficient in
producing surficants but, is less expensive ($0.25 per gallon of Lodex). The Lodex also has the advantage of
producing fewer pollutants per gallon used in the production process.
To satisfy contracts with its customers, Environmental Products must produce at least 240 gallons of surfactants
per hour. Each gallon of Hidex used in the production process generates 4 gallons of surfactant and 10 parts per
million (ppm) of toxide. Each gallon of Lodex produces 3 gallons of surfactant and 6 ppm of toxide. The EPA
limits toxide emissions to 600 ppm per hour. In addition, municipal regulations limit emissions of solids to 180
ppm per hour, and the Hidex process produces solids at a rate of 2 ppm per gallon used and the Lodex process
produces 3 ppm per gallon used.
35. Profit Maximization. Samantha Spade & Associates, Ltd. is a small architectural firm located in Portland,
Oregon, specializing in the preparation of multi-family residential housing complex, R, and commercial retails,
C, architectural designs. Prevailing prices in the market are $10,000 for residential housing designs and $25,000
for commercial retail designs.
Six architects run the firm, and work a 50-hour workweek, 50 weeks per year. They are assisted by six drafting
personnel and two secretaries, all of whom work a typical 40-hour workweek, 50 weeks per year. The firm must
decide how to target its promotional efforts so as to best use its resources during the coming year. Based on
previous experience, the firm expects that an average of 150 hours of architect and 100 hours of drafting time
will be required for each residential housing complex design, whereas commercial retail design will require an
average of 250 architect hours and 200 drafting hours. Fifty hours of secretarial time will also be required for
each architectural design. In addition, variable computer and other processing costs are expected to average
$1,000 per residential design and $1,500 per commercial retail design.
CHAPTER 9--LINEAR PROGRAMMING Key
3. When the primal LP problem is to maximize revenue subject to various input constraints, the shadow prices
4. If the primal objective function is to minimize cost subject to output constraints, the dual objective function is
7. If the objective function is to maximize revenue subject to a binding labor constraint, then the shadow price
14. To determine the quantity to be produced by each production process at varying points along an isoquant,
22. If a linear programming problem involves the minimization of advertising costs subject to audience marital
24. When some capacity constraints are binding, although others are nonbinding:
A. the shadow price for new capacity is positive.
B. the shadow price for output is positive.
C. the marginal revenue product for new capacity is positive.
D. the marginal product of new capacity is positive.
25. The cost of capacity subject to constraints is:
A. variable.
B. sunk.
C. semi-variable.
D. nonzero.
your answer.
A.
Linear programming can be used for solving any type of constrained optimization problem where the relations involved can be
approximated by linear equations.
B.
Linear revenue, cost and profit relations will be observed when output prices, input prices, and average variable costs are constant.
C.
Equal distances along a given production process ray in a linear programming problem always represent an identical level of output
D.
At isoquant segment midpoints, each adjacent production process must be used to produce 50% of output efficiently.
E.
Maximizing a LP profit contribution objective function always results in also maximizing total net profits.
27. LP Basics. Indicate whether each of the following statements is true or false and why.
A.
In profit maximization linear programming problems, negative values for slack variables are impossible.
B.
Binding constraints indicate positive slack variables at the optimum solution.
C.
Points not on process rays represent unattainable technologies.
D.
Constant input prices is the only requirement for a total cost function to be linear.
E.
Changing input prices will not alter the slope of a given isoquant line.
28. Fixed Input Relations. Extreme Biking, Inc., assembles high-end extreme mountain bicycles at a plant in
Lexington, Massachusetts. The plant uses labor (L) and capital (K) in an assembly line process to produce
output (Q) where:
Q
= 0.01L1/2K1/2
MPL
MPK
A.
Calculate how many units of output can be produced with 25 units of labor and 400 units of capital, and with 225 units of labor and
3,600 units of capital. Are returns to scale increasing, constant, or diminishing?
B.
Calculate the change in the marginal product of labor as labor grows from 25 to 36 units, holding capital constant at 400 units.
Similarly, calculate the change in the marginal product of capital as capital grows from 400 to 625 units, holding labor constant at 25
units. Are returns to each factor increasing, constant, or diminishing?
C.
Assume now and throughout the remainder of the problem that labor and capital must be combined in the ratio 25L:400K. How much
output could be produced if the company faces a constraint of L = 25,000 and K = 500,000 during the coming production period?
D.
What are the marginal products of each factor under the conditions described in part C?
DMPL=
0.0167 - 0.02 = -0.003
The change in MPK is:
29. Return Maximization. The American Balanced Fund is an open-end investment company (mutual fund)
designed to meet the needs of investors planning for future retirement. ABF seeks to provide current income
plus capital growth by investing in a diversified portfolio of high-quality stocks and investment-grade bonds.
The fund's bylaws state that at least 30% of the portfolio must be invested in bonds in order to reduce downside
risk during bear markets. The fund's growth potential is maintained by a requirement that the share of the
portfolio invested in common stocks must be at least as large as the share devoted to bonds. Like most mutual
funds, ABF is prohibited from using leverage (borrowing) to enhance investor ABF returns. Without leverage,
stock and bond investments cannot exceed 100% of ABF's portfolio. And finally, the fund's investment
management committee currently projects an expected return of 10% on stocks and 8% on bonds.
A.
Set up and interpret the linear programming problem ABF would use to determine the optimal portfolio percentage holdings in stocks
(S) and bonds (B). Use both the inequality and equality forms of the constraint conditions.
B.
Use a graph to determine the optimal solution, and check your answer algebraically. Interpret the solution.
C.
Holding all else equal, how much would the expected return on bonds have to rise before the optimal investment policy determined in
part A would change?
D.
What is the maximum share of the portfolio that could be converted into cash if management projects a downturn in both stock and
bond prices?
A.
In this problem, the goal is to maximize expected return, R, subject to the various stock, bond and leverage constraints. The relevant
linear programming problem is:
Maximize:
R
= 0.1S + 0.08B
Subject to:
B
³ 0.3
S - B
³ 0 (or S ³ B)
S + B
£ 1
or, in equality form:
(2)
0.7 - 0.3 - LS
= 0
LS
= 0.4
And the expected return
is:
R
=
0
.
1
S
+
0
.
0
8
B
=
0
.
1
(
0
.
7
)
+
0
.
0
8
(
0
.
3
)
=
0
.
0
9
4
o
r
9
.
4
%
Solution values can be
interpreted as follows:
S = 0.7
T
h
e
o
B = 0.30
T
LB = 0
A
LS = 0.4
A
LL = 0
A
30. Optimal Production. Canine Products, Inc., produces and markets a new moist and chewy nugget dog food
called "Chow Hound" being test marketed in the San Diego market. This product is similar to several others
offered by Canine Products, and can be produced with currently available equipment and personnel using any of
three alternative product methods. Method A requires 6 hours of labor and 1 processing facility hour to produce
100 bags of dog food, QA. Method B requires 3 labor and 3 processing facility hours per QB. Method C requires
2 labor hours and 4 processing facility hours per unit of QC. Because of slack demand for other products CP
currently has 15 labor hours and 5 processing facility hours available per week for producing Chow Hound.
A.
Using the equality form of the constraint conditions, set up and interpret the linear program Canine Products would use to maximize
production of Chow Hound given currently available resources.
B.
Calculate and interpret all solution values.
A.
In determining an optimal use of its resources, the company will seek to maximize output subject to limitations on scarce labor and
production facilities. Thus, the relevant linear programming problem can be written, in equality form, as:
Maximize:
Q
= QA + QB + QC
Subject to:
(1)
6QA + 3QB + 2QC + SL
= 15
(Labor constraint)
(2)
QA + 3QB + 4Q C + SP
= 5
(Production facility constraint)
QA, QB, QC, SL, SP
³ 0
Here QA, QB and QC represent output from each production method (in hundreds of bags). SL and SP represent excess labor and
production facility capacity, respectively.
B.
From the graph we see
that the maximum output
level will be reached on
the Q = 3 isoquant where
QC = S L = SP = 0. Thus,
the primal constraints
become a system of two
equations and two
unknowns that can be
solved algebraically.
Take (1) minus (2),
From (1),
6(2) + 3QB
= 15
3QB
= 3
QB
= 1(00)
Then, from the objective
function:
Q
= QA + QB
+ QC
= 2 + 1 + 0
= 3(00)
Summarizing from
above, solutions and an
interpretation of these
values are as follows:
QA = 2
2(00) units
of output
are
produced
31. Optimal Production. Video-Scapes, Inc. (VSI) is a rapidly growing landscaping service in Oakland,
California that specializes in merging videos of one's home and property with changeable computer-generated
graphics of various landscape details. VSI offers budget landscaping designs for $1,500 and deluxe designs for
$3,000. Both services use scarce computing, creative and consulting resources. Each budget design requires 4
hours of computer time, 2 hours of creative time, and 4 hours of consulting time with the client. Each deluxe
design requires 6 hours of computer time, 6 hours of creative time, and 4 hours of consulting time. VSI
currently has 60 hours of computer time, 42 hours of creative time, and 36 hours of consulting time available on
a weekly basis. What output mix would be optimal if VSI wishes to maximize total sales revenue?
A.
Using the equality form of the constraint conditions, set up and interpret the linear program that VSI might use to determine an optimal
weekly service mix.
B.
Solve for and interpret all solution values.
32. Optimal Lending. Penny Lane is a senior loan officer with Citrus National Bank in Tampa, Florida. Lane
33. Optimal Production. Ozark Telephone, Inc. (OTI) is a small telephone company offering local dial-tone
service to its franchised areas in rural southeastern Missouri. A new office park development site is being
planned within OTI's territory and John Sample, a network engineer, has to maximize the conversation capacity
per line under cost and technology constraints using both traditional copper-wire lines and new fiber-optic lines.
OTI wants to gradually move into the all-digital communication environment possible with fiber-optics, so a
company policy has been adopted specifying that at least 3 fiber-optic lines be employed for every 2 copper
lines on new installations. To minimize the need to quickly retrain its linemen, OTI wants at least 30% of new
telephone lines installed to be copper. No existing telephone facilities run to the development site, and OTI
must use its own facilities to carry the traffic (it cannot lease capacity from any other local telephone company).
Finally, current costs and technologies dictate that 1 fiber line can carry the equivalent of 5 copper lines at the
same cost to OTI. That is, if one copper line can carry one telephone conversation, fiber optic lines can carry
five conversations at no cost penalty. Sample's objective is to maximize the capacity per line of the
transmissions facilities being built to carry traffic to/from the office park.
A.
Using the inequality form of the constraint conditions, set up and interpret the linear programming problem Sample would use to
determine the optimal percentage of copper and fiber-optic lines. Also formulate the problem using the equality form of the constraint
conditions.
B.
With a graph, determine the optimal solution; check your solution algebraically. Fully interpret solution values.
C.
Holding all else equal, how much would the capacity of fiber optic lines have to fall to alter the optimal construction mix determined in
part B?
D.
Calculate the opportunity cost, measured in terms of conversation capacity per line, of OTI's 30% copper line constraint.
34. Cost Minimization. Environmental Products, Inc. manufactures surfactants used in fertilizers and
herbicides (surfactants minimize runoff). Environmental Products uses two manufacturing processes, each
having advantages. The Hidex process is more expensive ($0.50 per gallon of Hidex) but produces more
surfactant and fewer emissions of the pollutant toxide per gallon used. The Lodex process is less efficient in
producing surficants but, is less expensive ($0.25 per gallon of Lodex). The Lodex also has the advantage of
producing fewer pollutants per gallon used in the production process.
To satisfy contracts with its customers, Environmental Products must produce at least 240 gallons of surfactants
per hour. Each gallon of Hidex used in the production process generates 4 gallons of surfactant and 10 parts per
million (ppm) of toxide. Each gallon of Lodex produces 3 gallons of surfactant and 6 ppm of toxide. The EPA
limits toxide emissions to 600 ppm per hour. In addition, municipal regulations limit emissions of solids to 180
ppm per hour, and the Hidex process produces solids at a rate of 2 ppm per gallon used and the Lodex process
produces 3 ppm per gallon used.
A.
Set up and interpret the linear program Environmental Products would use to minimize hourly costs.
B.
Calculate, graph, and interpret all relevant solution values.
C.
Holding all else equal, how much would the price of Lodex have to rise before Hidex would be used exclusively to produce surfactants?
Explain.
35. Profit Maximization. Samantha Spade & Associates, Ltd. is a small architectural firm located in Portland,
Oregon, specializing in the preparation of multi-family residential housing complex, R, and commercial retails,
C, architectural designs. Prevailing prices in the market are $10,000 for residential housing designs and $25,000
for commercial retail designs.
Six architects run the firm, and work a 50-hour workweek, 50 weeks per year. They are assisted by six drafting
personnel and two secretaries, all of whom work a typical 40-hour workweek, 50 weeks per year. The firm must
decide how to target its promotional efforts so as to best use its resources during the coming year. Based on
previous experience, the firm expects that an average of 150 hours of architect and 100 hours of drafting time
will be required for each residential housing complex design, whereas commercial retail design will require an
average of 250 architect hours and 200 drafting hours. Fifty hours of secretarial time will also be required for
each architectural design. In addition, variable computer and other processing costs are expected to average
$1,000 per residential design and $1,500 per commercial retail design.
A.
Set up the linear programming problem the firm would use to determine the profit-maximizing output levels for residential and
commercial designs. Show both the inequality and equality forms of the constraint conditions.
B.
Completely solve and interpret the solution values for the linear programming problem.
C.
Calculate maximum possible net profits per year for the firm assuming that architects draw a salary of $100,000 per year, drafting
personnel earn $65,000 per year, secretaries are paid $20 per hour, and fixed overhead (including promotion and other expenses)
averages $50,000.
D.
After considering the above data, one senior architect recommended reducing one drafting personnel to part-time status (adjusting
salary accordingly) while retaining the rest of the current staff full-time. What are net profits per year under this suggestion?
