19
37) The objective of a linear programming problem is to maximize 1.50A + 1.50B, subject to 3A + 2B ≤ 600,
2A + 4B ≤ 600, 1A + 3B ≤ 420, and A,B ≥ 0.
a. Plot the constraints on the grid below
c. Identify the feasible region and its corner points. Show your work.
d. What is the optimal product mix for this problem?
20
38) Rienzi Farms grows sugar cane and soybeans on its 500 acres of land. An acre of soybeans brings a
$1000 contribution to overhead and profit; an acre of sugar cane has a contribution of $2000. Because of a
government program no more than 200 acres may be planted in soybeans. During the planting season
1200 hours of planting time will be available. Each acre of soybeans requires 2 hours, while each acre of
sugar cane requires 5 hours. The company seeks maximum contribution (profit) from its planting
decision.
a. Formulate the problem as a linear program.
b. Solve using the corner-point method.
39) Suppose that a constraint is given by X + Y ≤ 10. If another constraint is given to be 3X + 2Y ≥ 15, and if
X and Y are restricted to be nonnegative, determine the corners of the feasible solution. If the profit from
X is 5 and the profit from Y is 10, determine the combination of X and Y that will yield maximum profit.
Section 5 Sensitivity Analysis
1) Sensitivity analysis can be applied to linear programming solutions by either (1) trial and error or (2)
the analytic postoptimality method.
2) In sensitivity analysis, a zero shadow price (or dual value) for a resource ordinarily means that the
resource has not been used up.
3) A shadow price (or dual value) reflects which of the following in a maximization problem?
A) the marginal gain in the objective realized by subtracting one unit of a resource
B) the market price that must be paid to obtain additional resources
C) the increase in profit that would accompany one added unit of a scarce resource
D) the reduction in cost that would accompany a one unit decrease in the resource
E) the profit contribution necessary for that item to be included in the optimal solution
4) Suppose that the shadow price for assembly time is $5/hour. The allowable increase for the assembly
time constraint is 40 hours, and the allowable decrease is 30 hours. If all assembly hours were used under
the initial LP solution and workers normally make $4/hour but can work overtime for $6/hour, what
should management do?
A) do not change available hours for assembly time
B) decrease available hours for assembly time by 30 hours
C) increase available hours for assembly time by 40 hours
D) decrease available hours for assembly time by 5 hours
E) increase available hours for assembly time by 5 hours
5) ________ is an analysis that projects how much a solution might change if there were changes in the
variables or input data.
6) Two methods of conducting sensitivity analysis on solved linear programming problems are ________
and ________.
7) A synonym for shadow price is ________.
8) What is the usefulness of a shadow price (or dual value)?
9) What is sensitivity analysis?
10) A manager must decide on the mix of products to produce for the coming week. Product A requires
three minutes per unit for molding, two minutes per unit for painting, and one minute for packing.
Product B requires two minutes per unit for molding, four minutes for painting, and three minutes per
unit for packing. There will be 600 minutes available for molding, 600 minutes for painting, and 420
minutes for packing. Both products have contributions of $1.50 per unit. Answer the following questions;
base your work on the solution panel provided.
A
RHS
Maximize
1.5
Molding
3.
600.
Painting
2.
600.
Packing
1.
420.
Solution —>
150.
337.5
a. What combination of A and B will maximize contribution?
b. What is the maximum possible contribution?
c. Are any resources not fully used up? Explain.
11) A craftsman builds two kinds of birdhouses, one for wrens (X1), and one for bluebirds (X2). Each
wren birdhouse takes four hours of labor and four units of lumber. Each bluebird house requires two
hours of labor and twelve units of lumber. The craftsman has available 60 hours of labor and 120 units of
lumber. Wren houses profit $6 each and bluebird houses profit $15 each.
Use the software output that follows to interpret the problem solution. Include a statement of the solution
quantities (how many of which product), a statement of the maximum profit achieved by your product
mix, and a statement of “resources unused” and “shadow prices.”
12) Suppose that a constraint for assembly time has a shadow price of $50/hour for 15 hours in either
direction and that all available assembly time is currently used (would require overtime to do more). If
the salary of workers is $30 and they receive 50% extra pay for overtime what should management do?
Section 6 Solving Minimization Problems
1) The graphical method of solving linear programs can handle only maximization problems.
2) A difference between minimization and maximization problems is that:
A) minimization problems cannot be solved with the corner-point method.
B) maximization problems often have unbounded regions.
C) minimization problems often have unbounded regions.
D) minimization problems cannot have shadow prices.
E) minimization problems are more difficult to solve than maximization problems.
3) The Queen City Nursery manufactures bags of potting soil from compost and topsoil. Each cubic foot
of compost costs 12 cents and contains 4 pounds of sand, 3 pounds of clay, and 5 pounds of humus. Each
cubic foot of topsoil costs 20 cents and contains 3 pounds of sand, 6 pounds of clay, and 12 pounds of
humus. Each bag of potting soil must contain at least 12 pounds of sand, at least 12 pounds of clay, and at
least 10 pounds of humus. Formulate the problem as a linear program. Plot the constraints and identify
the feasible region. Graphically or with corner points find the best combination of compost and topsoil
that meets the stated conditions at the lowest cost per bag. Identify the lowest cost possible.
Section 7 Linear Programming Applications
1) In linear programming, statements such as “the blend must consist of at least 10% of ingredient A, at
least 30% of ingredient B, and no more than 50% of ingredient C” can be made into valid constraints even
though the percentages do not add up to 100 percent.
2) The diet problem is known in agricultural applications as the:
A) fertilizer problem.
B) feed-mix problem.
C) crop-rotation problem.
D) egg-choice problem.
E) genetic-transformation problem.
3) A financial advisor is about to build an investment portfolio for a client who has $100,000 to invest. The
four investments available are A, B, C, and D. Investment A will earn 4 percent and has a risk of two
“points” per $1,000 invested. B earns 6 percent with 3 risk points; C earns 9 percent with 7 risk points; and
D earns 11 percent with a risk of 8. The client has put the following conditions on the investments: A is to
be no more than one-half of the total invested. A cannot be less than 20 percent of the total investment. D
cannot be less than C. Total risk points must be at or below 1,000.
Let A be the amount invested in investment A, and define B, C, and D similarly.
Formulate the linear programming model.
4) Tom is a habitual shopper at garage sales. Last Saturday he stopped at one where there were several
types of used building materials for sale. At the low prices being asked, Tom knew that he could resell
the items in another town for a substantial gain. Four things stood in his way: he could only make one
round trip to resell the goods; his pickup truck bed would hold only 1000 pounds; the pickup truck bed
could hold at most 70 cubic feet of merchandise; and he had only $200 cash with him. He wants to load
his truck with the mix of materials that will yield the greatest profit when he resells them.
Item
Cubic feet per
unit
Price per unit
Weight per unit
Can resell for
2 × 4 studs
1
$0.10
5 pounds
$0.80
4 × 8 plywood
3
$0.50
20 pounds
$3.00
Concrete blocks
0.5
$0.25
10 pounds
$0.75
Formulate this problem as a linear program.
5) Phil Bert’s Nuthouse is preparing a new product, a blend of mixed nuts. The product must be at most
50 percent peanuts, must have more almonds than cashews, and must be at least 10 percent pecans. The
blend will be sold in one-pound bags. Phil’s goal is to mix the nuts in such a manner that all conditions
are satisfied and the cost per bag is minimized. Peanuts cost $1 per pound. Cashews cost $3 per pound.
Almonds cost $5 per pound and pecans cost $6 per pound. Formulate this problem as a linear program.
6) The property manager of a city government issues chairs, desks, and other office furniture to city
buildings from a centralized distribution center. Like most government agencies, it operates to minimize
its costs of operations. In this distribution center, there are two types of standard office chairs, Model A
and Model B. Model A is considerably heavier than Model B, and costs $20 per chair to transport to any
city building; each model B costs $14 to transport. The distribution center has on hand 400 chairs—200
each of A and B.
The requirements for shipments to each of the city’s buildings are as follows:
Building 1 needs at least 100 of A
Building 2 needs at least 150 of B.
Building 3 needs at least 100 chairs, but they can be of either type, mixed.
Building 4 needs 40 chairs, but at least as many B as A.
Formulate this problem as a linear program. (Hint: there are eight decision variables because we need to
know how many of each chair (A and B) to deliver to each of the four buildings).
7) A stereo mail order center has 8,000 cubic feet available for storage of its private label loudspeakers.
The ZAR3 speakers cost $295 each and require 4 cubic feet of space; the ZAR2ax speakers cost $110 each
and require 3 cubic feet of space; and the ZAR4 model costs $58 and requires 1 cubic foot of space. The
demand for the ZAR3 is at most 20 units per month. The wholesaler has $100,000 to spend on
loudspeakers this month. Each ZAR3 contributes $105, each ZAR2ax contributes $50, and each ZAR4
contributes $28. The objective is to maximize total contribution. Formulate this problem as a linear
program.
8) A feedlot is trying to decide on the lowest cost mix that will still provide adequate nutrition for its
cattle. Suppose that the numbers in the chart represent the number of grams of ingredient per 100 grams
of feed and that the cost of Feed X is $5/100grams, Feed Y is $3/100 grams, and Feed X is $8/100 grams.
Each cow will need 50 grams of A per day, 20 grams of B, 30 grams of C, and 10 grams of D. The feedlot
can get no more than 200 grams per day per cow of any of the feed types. Formulate the problem as a
linear program.
Ingredient
X
A
10
B
30
C
40
D
0
Section 8 The Simplex Method of LP
1) Constraints are needed to solve linear programming problems by hand, but not by computer.
2) Which of the following is an algorithm for solving linear programming problems of all sizes?
A) duplex method
B) multiplex method
C) shadow price method
D) simplex method
E) decision tree method
3) What is the simplex method?
Section 9 Integer and Binary Variables
1) Binary variables can only take on the values of 1 or 2.
2) Computer software provides a simple way to guarantee only integer solutions to linear programming
problems.
3) If we wish to ensure that decision variable values in a linear program are integers rather than fractions,
the generally accepted practice is to round the solutions to the nearest integer values.
4) The main disadvantage of introducing constraints into a linear program that enforce some or all of the
decision variables to be either integer or binary is that:
A) the programs may take longer to solve.
B) the solutions will no longer be optimal.
C) Excel can no longer be used to solve the program.
D) the constraints are difficult to formulate.
E) we cannot have “yes-or-no” decisions in the linear program.
5) Capital Co. is considering 5 different projects. Define Xi as a binary variable that equals 1 if project i is
undertaken and 0 otherwise, for i = 1, 2, 3, 4, 5. Which of the following represents the constraint(s) stating
that projects 2, 3, and 4 cannot all three be undertaken simultaneously?
A) X2 + X3 + X4 ≤ 3
B) X1 + X2 + X3 + X4 + X5 ≤ 3
C) X2 + X3 + X4 ≤ 1
D) X2 + X3 + X4 ≤ 2
E) X2 + X3 ≤ 1 and X3 + X4 ≤ 1
6) Riker Co. is considering which of 4 different projects to undertake in order to maximize its net present
value (NPV). Define Xi as a binary variable that equals 1 if project i is undertaken and 0 otherwise, for
i = 1, 2, 3, 4. The NPV and required capital (in millions) for each project are listed below.
Net Present Value
Capital Required
60
7
50
10
40
6
20
3
Which of the following represents the constraint(s) stating that project 1 must be undertaken and at least
one of the other projects must be undertaken?
A) X1 + X2 ≤ 1, and X1 + X3 ≤ 1, and X1 + X4 ≤ 1
B) X1 ≥1, and X2 + X3 + X4 ≥ 1
C) X1 + X2 ≥ 1, and X1 + X3 ≥ 1, and X1 + X4 ≥ 1
D) X1 ≥1, and X2 + X3 + X4 ≤ 3
E) X1 + X2 + X3 + X4 ≥ 2
7) Riker Co. is considering which of 4 different projects to undertake in order to maximize its net present
value (NPV). Define Xi as a binary variable that equals 1 if project i is undertaken and 0 otherwise, for
i = 1, 2, 3, 4. The NPV and required capital (in millions) for each project are listed below.
Net Present Value
Capital Required
60
7
50
10
40
6
20
3
What is the proper objective function?
A) Max X1 + X2 + X3 + X4
B) Min 60X1 + 50X2 + 40X3 + 20X4
C) Max 60X1 + 50X2 + 40X3 + 20X4
D) Max 7X1 + 10X2 + 6X3 + 3X4
E) Max 170(X1 + X2 + X3 + X4)
8) Data Corp. is considering which of 4 different projects to undertake in order to maximize its net present
value (NPV). Define Xi as a binary variable that equals 1 if project i is undertaken and 0 otherwise, for
i = 1, 2, 3, 4. The NPV and required capital (in millions) for each project are listed below.
Net Present Value
Capital Required
40
9
80
13
10
3
90
8
Which of the following represents the constraint stating that project 3 can be undertaken only if project 2
is undertaken?
A) X2 + X3 ≤ 1
B) X2 – X3 ≤ 0
C) X3 – X2 ≤ 0
D) X2 – X3 ≤ 1
E) X3 – X2 ≤ 1
9) ________ variables allow us to introduce “yes–or-no” decisions into our linear programs and to
introduce special logical conditions.
10) Describe how to incorporate fixed costs into a cost-minimizing linear program, where the fixed cost of
using a machine is incurred if any products are produced on that machine.