Chapter 7 – Intro to Linear Programming
54. The Sanders Garden Shop mixes two types of grass seed into a blend. Each type of grass has been rated (per pound)
according to its shade tolerance, ability to stand up to traffic, and drought resistance, as shown in the table. Type A seed
costs $1 and Type B seed costs $2. If the blend needs to score at least 300 points for shade tolerance, 400 points for traffic
resistance, and 750 points for drought resistance, how many pounds of each seed should be in the blend? Which targets
will be exceeded? How much will the blend cost?
Type A Type B
Shade Tolerance 1 1
Traffic Resistance 2 1
Drought Resistance 2 5
Chapter 7 – Intro to Linear Programming
55. Muir Manufacturing produces two popular grades of commercial carpeting among its many other products. In the
coming production period, Muir needs to decide how many rolls of each grade should be produced in order to maximize
profit. Each roll of Grade X carpet uses 50 units of synthetic fiber, requires 25 hours of production time, and needs 20
units of foam backing. Each roll of Grade Y carpet uses 40 units of synthetic fiber, requires 28 hours of production time,
and needs 15 units of foam backing.
The profit per roll of Grade X carpet is $200 and the profit per roll of Grade Y carpet is $160. In the coming production
period, Muir has 3000 units of synthetic fiber available for use. Workers have been scheduled to provide at least 1800
hours of production time (overtime is a possibility). The company has 1500 units of foam backing available for use.
Develop and solve a linear programming model for this problem.
Chapter 7 – Intro to Linear Programming
56. Does the following linear programming problem exhibit infeasibility, unboundedness, or alternate optimal solutions?
Explain.
Min 1X + 1Y
s.t. 5X + 3Y ≤ 30
3X + 4Y ≥ 36
Y ≤ 7
X , Y ≥ 0
Chapter 7 – Intro to Linear Programming
57. Does the following linear programming problem exhibit infeasibility, unboundedness, or alternate optimal solutions?
Explain.
Min 3X + 3Y
s.t. 1X + 2Y ≤ 16
1X + 1Y ≤ 10
5X + 3Y ≤ 45
X , Y ≥ 0
58. A businessman is considering opening a small specialized trucking firm. To make the firm profitable, it is estimated
that it must have a daily trucking capacity of at least 84,000 cu. ft. Two types of trucks are appropriate for the specialized
operation. Their characteristics and costs are summarized in the table below. Note that truck 2 requires 3 drivers for long
haul trips. There are 41 potential drivers available and there are facilities for at most 40 trucks. The businessman’s
objective is to minimize the total cost outlay for trucks.
Capacity Drivers
Truck Cost (Cu. Ft.) Needed
Small $18,000 2,400 1
Large $45,000 6,000 3
Solve the problem graphically and note there are alternate optimal solutions. Which optimal solution:
a. uses only one type of truck?
b. utilizes the minimum total number of trucks?
c. uses the same number of small and large trucks?
Chapter 7 – Intro to Linear Programming
59. Consider the following linear program:
Max 60X + 43Y
s.t. X + 3Y ≥ 9
6X − 2Y = 12
X + 2Y ≤ 10
X, Y ≥ 0
a. Write the problem in standard form.
b. What is the feasible region for the problem?
c. Show that regardless of the values of the actual objective function coefficients, the optimal solution will occur at one
of two points. Solve for these points and then determine which one maximizes the current objective function.
60. Solve the following linear program graphically.
Max 5X + 7Y
s.t. X ≤ 6
2X + 3Y ≤ 19
X + Y ≤ 8
X, Y ≥ 0
Chapter 7 – Intro to Linear Programming
61. Given the following linear program:
Min 150X + 210Y
s.t. 3.8X + 1.2Y ≥ 22.8
Y ≥ 6
Y ≤ 15
45X + 30Y = 630
X, Y ≥ 0
Solve the problem graphically. How many extreme points exist for this problem?
62. Solve the following linear program by the graphical method.
Max 4X + 5Y
s.t. X + 3Y ≤ 22
−X + Y ≤ 4
Y ≤ 6
2X − 5Y ≤ 0
X, Y ≥ 0
Chapter 7 – Intro to Linear Programming
63. The Alpha Beta Corporation makes laser and ink jet printers for personal computers. Each laser printer yields $40.00
in profits and each ink jet printer provides $20.00. Each of the printers goes through two assembly areas. The following
table provides processing times per unit (in minutes) as well as total available processing times per department:
Printer Dept A Dept B
laser 9 12
ink jet 6 8
total time per day 216 384
Sales commitments require at least 5 laser printers and 10 ink jet printers to be made per day. The company is interested in
determining how many of each printer to produce so as to maximize its profit.
a. Formulate this problem as an LP.
b. Graph this problem.
c. What is the optimal solution?
Chapter 7 – Intro to Linear Programming
64. A small lumber company in the Southeast produces two types of pine boards used in home construction: 2x4s and
2x6s (dimensions in inches). They are attempting to determine how many of each to produce so as to minimize their costs
on a per-minute basis. They have sales commitments to produce four 2x4s and two 2x6s per minute, but they think they
shouldn’t produce any more than eight 2x6s because of market demand. They are also trying to support the community by
employing people. Thus they want to keep at least 12 men employed, but only need 2 men to produce each 2×4 and 1
person to produce each 2×6 per minute. It costs them $.50 to produce 2×4 and $.80 to produce a 2×6 per minute.
a. Formulate this problem as an LP.
b. Graph this problem.
c. List the left boundaries of the unbounded feasible region.
c. What is the optimal solution?
Chapter 7 – Intro to Linear Programming
65. The Northwest Flower Company owns a greenhouse, which furnishes roses and carnations to florists in Oregon,
Washington, and Idaho. The greenhouse can grow any combination of the two flowers. They sell the flowers in “bunches”
with 25 blooms to a bunch. They have 10,000 square feet available for planting this year. Each bunch of roses takes about
4 square feet and each bunch of carnations about 5 square feet. Special fertilizer is required for flowers: roses need 5
pounds and carnations 2 pounds. The availability of the fertilizer is limited to 5000 pounds. Sales commitments require
the company to grow at least 500 bunches of roses. Profit contributions are $6 per bunch of roses and $8 per bunch of
carnations.
a. Formulate this problem as an LP.
b. Graph this problem.
Chapter 7 – Intro to Linear Programming
c. What are the corner points of the feasible region.
c. What is the optimal solution?
Chapter 7 – Intro to Linear Programming
Essay
66. Explain the difference between profit and contribution in an objective function. Why is it important for the decision
maker to know which of these the objective function coefficients represent?
67. Explain how to graph the line x1 − 2x2 ≥ 0.
68. Create a linear programming problem with two decision variables and three constraints that will include both a slack
and a surplus variable in standard form. Write your problem in standard form.
69. Explain what to look for in problems that are infeasible or unbounded.
70. Use a graph to illustrate why a change in an objective function coefficient does not necessarily lead to a change in
the optimal values of the decision variables, but a change in the right-hand sides of a binding constraint does lead to
new values.
71. Explain the concepts of proportionality, additivity, and divisibility.
72. Explain the steps necessary to put a linear program in standard form.
73. Explain the steps of the graphical solution procedure for a minimization problem.
Chapter 7 – Intro to Linear Programming