292 CHAPTER 7 • LINEAR PROGRAMMING MODELS: GRAPHICAL AND COMPUTER METHODS

Discussion Questions and Problems

Discussion Questions 7-10 A linear program has the objective of maximizing
profit = 12X + 8Y. The maximum profit is $8,000.
7-1 Discuss the similarities and differences between
Using a computer we find the upper bound for profit
minimization and maximization problems using the
on X is 20 and the lower bound is 9. Discuss the
graphical solution approaches of LP.
changes to the optimal solution (the values of the vari-
7-2 It is important to understand the assumptions under- ables and the profit) that would occur if the profit on
lying the use of any quantitative analysis model. X were increased to $15. How would the optimal so-
What are the assumptions and requirements for an lution change if the profit on X were increased to $25?
LP model to be formulated and used?
7-11 A linear program has a maximum profit of $600.
7-3 It has been said that each LP problem that has a One constraint in this problem is 4X + 2Y … 80.
feasible region has an infinite number of solutions. Using a computer we find the dual price for this con-
Explain. straint is 3, and there is a lower bound of 75 and an
7-4 You have just formulated a maximization LP prob- upper bound of 100. Explain what this means.
lem and are preparing to solve it graphically. What 7-12 Develop your own original LP problem with two
criteria should you consider in deciding whether it constraints and two real variables.
would be easier to solve the problem by the corner (a) Explain the meaning of the numbers on the
point method or the isoprofit line approach? right-hand side of each of your constraints.
7-5 Under what condition is it possible for an LP prob- (b) Explain the significance of the technological
lem to have more than one optimal solution? coefficients.
7-6 Develop your own set of constraint equations and in- (c) Solve your problem graphically to find the opti-
equalities and use them to illustrate graphically each mal solution.
of the following conditions: (d) Illustrate graphically the effect of increasing the
(a) an unbounded problem contribution rate of your first variable 1X12 by
(b) an infeasible problem 50% over the value you first assigned it. Does
(c) a problem containing redundant constraints this change the optimal solution?
7-7 The production manager of a large Cincinnati manu- 7-13 Explain how a change in a technological coefficient
facturing firm once made the statement, “I would like can affect a problem’s optimal solution. How can a
to use LP, but it’s a technique that operates under con- change in resource availability affect a solution?
ditions of certainty. My plant doesn’t have that cer-
tainty; it’s a world of uncertainty. So LP can’t be used Problems
here.” Do you think this statement has any merit? 7-14 The Electrocomp Corporation manufactures two elec-
Explain why the manager may have said it. trical products: air conditioners and large fans. The as-
7-8 The mathematical relationships that follow were for- sembly process for each is similar in that both require
mulated by an operations research analyst at the a certain amount of wiring and drilling. Each air con-
Smith–Lawton Chemical Company. Which ones are ditioner takes 3 hours of wiring and 2 hours of drilling.
invalid for use in an LP problem, and why? Each fan must go through 2 hours of wiring and 1 hour
Maximize profit = 4X1 + 3X1X2 + 8X2 + 5X3 of drilling. During the next production period, 240
hours of wiring time are available and up to 140 hours
subject to 2X1 + X2 + 2X3 … 50 of drilling time may be used. Each air conditioner sold
X1 - 4X2 Ú 6 yields a profit of $25. Each fan assembled may be sold
1.5X21 + 6X2 + 3X3 Ú 21 for a $15 profit. Formulate and solve this LP produc-
19X2 - 0.35X3 = 17 tion mix situation to find the best combination of air
conditioners and fans that yields the highest profit.
5X1 + 4X2 + 3 2 X3 … 80 Use the corner point graphical approach.
-X1 - X2 + X3 = 5 7-15 Electrocomp’s management realizes that it forgot to
7-9 Discuss the role of sensitivity analysis in LP. Under include two critical constraints (see Problem 7-14). In
what circumstances is it needed, and under what particular, management decides that there should be a
conditions do you think it is not necessary? minimum number of air conditioners produced in
order to fulfill a contract. Also, due to an oversupply

Note: means the problem may be solved with QM for Windows; means the problem may be
solved with Excel; and means the problem may be solved with QM for Windows and/or Excel.
 DISCUSSION QUESTIONS AND PROBLEMS 293

of fans in the preceding period, a limit should be insists that full employment (i.e., all 160 hours of
placed on the total number of fans produced. time) be maintained for each worker during next
(a) If Electrocomp decides that at least 20 air condi- month’s operations. It requires 20 labor hours to
tioners should be produced but no more than 80 assemble each Alpha 4 computer and 25 labor hours
fans should be produced, what would be the op- to assemble each Beta 5 model. MSA wants to see at
timal solution? How much slack is there for each least 10 Alpha 4s and at least 15 Beta 5s produced
of the four constraints? during the production period. Alpha 4s generate
(b) If Electrocomp decides that at least 30 air condi- $1,200 profit per unit, and Beta 5s yield $1,800 each.
tioners should be produced but no more than Determine the most profitable number of each model
50 fans should be produced, what would be of minicomputer to produce during the coming
the optimal solution? How much slack is there month.
for each of the four constraints at the optimal 7-20 A winner of the Texas Lotto has decided to invest
solution? $50,000 per year in the stock market. Under consid-
7-16 A candidate for mayor in a small town has allocated eration are stocks for a petrochemical firm and a
$40,000 for last-minute advertising in the days pre- public utility. Although a long-range goal is to get
ceding the election. Two types of ads will be used: the highest possible return, some consideration is
radio and television. Each radio ad costs $200 and given to the risk involved with the stocks. A risk in-
reaches an estimated 3,000 people. Each television dex on a scale of 1–10 (with 10 being the most risky)
ad costs $500 and reaches an estimated 7,000 peo- is assigned to each of the two stocks. The total risk
ple. In planning the advertising campaign, the cam- of the portfolio is found by multiplying the risk of
paign manager would like to reach as many people each stock by the dollars invested in that stock.
as possible, but she has stipulated that at least 10 ads The following table provides a summary of the
of each type must be used. Also, the number of radio return and risk:
ads must be at least as great as the number of televi-
sion ads. How many ads of each type should be
used? How many people will this reach? STOCK ESTIMATED RETURN RISK INDEX
7-17 The Outdoor Furniture Corporation manufactures Petrochemical 12% 9
two products, benches and picnic tables, for use in Utility 6% 4
yards and parks. The firm has two main resources:
its carpenters (labor force) and a supply of redwood
for use in the furniture. During the next production The investor would like to maximize the return on
cycle, 1,200 hours of labor are available under a the investment, but the average risk index of the in-
union agreement. The firm also has a stock of 3,500 vestment should not be higher than 6. How much
feet of good-quality redwood. Each bench that Out- should be invested in each stock? What is the aver-
door Furniture produces requires 4 labor hours and age risk for this investment? What is the estimated
10 feet of redwood; each picnic table takes 6 labor return for this investment?
hours and 35 feet of redwood. Completed benches 7-21 Referring to the Texas Lotto situation in Problem 7-20,
will yield a profit of $9 each, and tables will result suppose the investor has changed his attitude about
in a profit of $20 each. How many benches and the investment and wishes to give greater emphasis
tables should Outdoor Furniture produce to obtain to the risk of the investment. Now the investor
the largest possible profit? Use the graphical LP wishes to minimize the risk of the investment as
approach. long as a return of at least 8% is generated. Formu-
7-18 The dean of the Western College of Business must late this as an LP problem and find the optimal solu-
plan the school’s course offerings for the fall semes- tion. How much should be invested in each stock?
ter. Student demands make it necessary to offer at What is the average risk for this investment? What is
least 30 undergraduate and 20 graduate courses in the estimated return for this investment?
the term. Faculty contracts also dictate that at least 7-22 Solve the following LP problem using the corner
60 courses be offered in total. Each undergraduate point graphical method. At the optimal solution, cal-
course taught costs the college an average of $2,500 culate the slack for each constraint:
in faculty wages, and each graduate course costs
$3,000. How many undergraduate and graduate Maximize profit = 4X + 4Y
courses should be taught in the fall so that total fac- subject to 3X + 5Y … 150
ulty salaries are kept to a minimum? X - 2Y … 10
7-19 MSA Computer Corporation manufactures two mod-
5X + 3Y … 150
els of minicomputers, the Alpha 4 and the Beta 5. The
firm employs five technicians, working 160 hours X, Y Ú 0
each per month, on its assembly line. Management
294 CHAPTER 7 • LINEAR PROGRAMMING MODELS: GRAPHICAL AND COMPUTER METHODS

7-23 Consider this LP formulation: olives to grow on their own and results in a smaller
size olive. It also, though, permits olive trees to be
Minimize cost
= $X + 2Y spaced closer together. The yield of 1 barrel of olives
subject to
by pruning requires 5 hours of labor and 1 acre of
X + 3Y Ú 90 land. The production of a barrel of olives by the nor-
8X + 2Y Ú 160 mal process requires only 2 labor hours but takes
3X + 2Y Ú 120 2 acres of land. An olive grower has 250 hours of
labor available and a total of 150 acres for growing.
Y … 70
Because of the olive size difference, a barrel of olives
X, Y Ú 0 produced on pruned trees sells for $20, whereas a
Graphically illustrate the feasible region and apply barrel of regular olives has a market price of $30. The
the isocost line procedure to indicate which corner grower has determined that because of uncertain
point produces the optimal solution. What is the cost demand, no more than 40 barrels of pruned olives
of this solution? should be produced. Use graphical LP to find
(a) the maximum possible profit.
7-24 The stock brokerage firm of Blank, Leibowitz, and
(b) the best combination of barrels of pruned and
Weinberger has analyzed and recommended two
regular olives.
stocks to an investors’ club of college professors.
(c) the number of acres that the olive grower should
The professors were interested in factors such as
devote to each growing process.
short-term growth, intermediate growth, and divi-
dend rates. These data on each stock are as follows: 7-27 Consider the following four LP formulations. Using
a graphical approach, determine
(a) which formulation has more than one optimal
STOCK ($)
solution.
LOUISIANA GAS TRIMEX INSULATION (b) which formulation is unbounded.
FACTOR AND POWER COMPANY (c) which formulation has no feasible solution.
Short-term growth .36 .24 (d) which formulation is correct as is.
potential, per dollar
invested Formulation 1 Formulation 3
Intermediate growth 1.67 1.50 Maximize 10X1 + 10X2 Maximize 3X1 + 2X2
potential (over next subject to 2X1 … 10 subject to X1 + X2 Ú 5
three years), per
dollar invested 2X1 + 4X2 … 16 X1 Ú 2
Dividend rate 4% 8% 4X2 … 8 2X2 Ú 8
potential X1 = 6
Formulation 2 Formulation 4
Each member of the club has an investment goal of
(1) an appreciation of no less than $720 in the short Maximize X1 + 2X2 Maximize 3X1 + 3X2
term, (2) an appreciation of at least $5,000 in the subject to X1 … 1 subject to 4X1 + 6X2 … 48
next three years, and (3) a dividend income of at 2X2 … 2 4X1 + 2X2 … 12
least $200 per year. What is the smallest investment
X1 + 2X2 … 2 3X2 Ú 3
that a professor can make to meet these three goals?
2X1 Ú 2
7-25 Woofer Pet Foods produces a low-calorie dog food
for overweight dogs. This product is made from beef 7-28 Graph the following LP problem and indicate the
products and grain. Each pound of beef costs $0.90, optimal solution point:
and each pound of grain costs $0.60. A pound of the
Maximize profit = $3X + $2Y
dog food must contain at least 9 units of Vitamin 1
and 10 units of Vitamin 2. A pound of beef contains subject to 2X + Y … 150
10 units of Vitamin 1 and 12 units of Vitamin 2. A 2X + 3Y … 300
pound of grain contains 6 units of Vitamin 1 and 9 (a) Does the optimal solution change if the profit per
units of Vitamin 2. Formulate this as an LP problem unit of X changes to $4.50?
to minimize the cost of the dog food. How many (b) What happens if the profit function should have
pounds of beef and grain should be included in each been $3X + $3Y?
pound of dog food? What is the cost and vitamin 7-29 Graphically analyze the following problem:
content of the final product?
Maximize profit = $4X + $6Y
7-26 The seasonal yield of olives in a Piraeus, Greece,
vineyard is greatly influenced by a process of branch subject to X + 2Y … 8 hours
pruning. If olive trees are pruned every two weeks, 6X + 4Y … 24 hours
output is increased. The pruning process, however,
requires considerably more labor than permitting the
 DISCUSSION QUESTIONS AND PROBLEMS 295

(a) What is the optimal solution? (c) If the right-hand side of constraint 1 were in-
(b) If the first constraint is altered to X + 3Y … 8, creased by 10 units, how much would the profit
does the feasible region or optimal solution increase?
change? 7-34 The computer output on the next page is for a prod-
7-30 Examine the LP formulation in Problem 7-29. The uct mix problem in which there are two products and
problem’s second constraint reads three resource constraints. Use the output to help
1time available on machine 22
you answer the following questions. Assume that
6X + 4Y … 24 hours
you wish to maximize profit in each case.
If the firm decides that 36 hours of time can be made (a) How many units of product 1 and product 2
available on machine 2 (namely, an additional 12 should be produced?
hours) at an additional cost of $10, should it add the (b) How much of each of the three resources is be-
hours? ing used? How much slack is there for each con-
7-31 Consider the following LP problem: straint? Which of the constraints are binding,
and which are nonbinding?
Maximize profit = 5X + 6Y (c) What are the dual prices for each resource?
subject to 2X + Y … 120 (d) If you could obtain more of one of the resources,
2X + 3Y … 240 which one should you obtain? How much should
X, Y Ú 0 you be willing to pay for this?
(e) What would happen to profit if, with the original
(a) What is the optimal solution to this problem? output, management decided to produce one
Solve it graphically. more unit of product 2?
(b) If a technical breakthrough occurred that raised 7-35 Graphically solve the following problem:
the profit per unit of X to $8, would this affect
the optimal solution? Maximize profit = 8X1 + 5X2
(c) Instead of an increase in the profit coefficient X subject to X1 + X2 … 10
to $8, suppose that profit was overestimated and X1 … 6
should only have been $3. Does this change the
X1, X2 Ú 0
optimal solution?
7-32 Consider the LP formulation given in Problem 7-31. (a) What is the optimal solution?
If the second constraint is changed from 2X + (b) Change the right-hand side of constraint 1 to
3Y … 240 to 2X + 4Y … 240, what effect will this 11 (instead of 10) and resolve the problem.
have on the optimal solution? How much did the profit increase as a result of
7-33 The computer output given below is for Problem 7-31. this?
Use this to answer the following questions. (c) Change the right-hand side of constraint 1 to 6
(a) How much could the profit on X increase or de- (instead of 10) and resolve the problem. How
crease without changing the values of X and Y in much did the profit decrease as a result of this?
the optimal solution? Looking at the graph, what would happen if the
(b) If the right-hand side of constraint 1 were in- right-hand-side value were to go below 6?
creased by 1 unit, how much would the profit (d) Change the right-hand-side value of constraint
increase? 1 to 5 (instead of 10) and resolve the problem.

Output for Problem 7-33

296 CHAPTER 7 • LINEAR PROGRAMMING MODELS: GRAPHICAL AND COMPUTER METHODS

Output for Problem 7-34

Output for Problem 7-35

How much did the profit decrease from the orig- They discovered that their supplies were just about
inal profit as a result of this? gone
(e) Using the computer output on this page, what is When, what to their joy, Prince William found
the dual price of constraint 1? What is the lower A pile of coconuts on the ground.
bound on this? “Each will bring 60 rupees,” said Prince Richard
(f) What conclusions can you draw from this re- with a grin
garding the bounds of the right-hand-side values As he almost tripped over a lion skin.
and the dual price? “Look out!” cried Prince Robert with glee
7-36 Serendipity* As he spied some more lion skins under a tree.
The three princes of Serendip “These are worth even more—300 rupees each
Went on a little trip. If we can just carry them all down to the beach.”
They could not carry too much weight; Each skin weighed fifteen pounds and each coconut,
More than 300 pounds made them hesitate. five,
They planned to the ounce. When they returned to But they carried them all and made it alive.
Ceylon The boat back to the island was very small

*The word serendipity was coined by the English writer Horace Walpole after a fairy tale titled The Three Princes of Serendip. Source of problem is unknown.
 DISCUSSION QUESTIONS AND PROBLEMS 297

15 cubic feet baggage capacity—that was all. The QM for Windows output is shown below.
Each lion skin took up one cubic foot (a) How much money should be invested in the
While eight coconuts the same space took. money market fund and the stock fund? What is
With everything stowed they headed to sea the total risk?
And on the way calculated what their new wealth (b) What is the total return? What rate of return is
might be. this?
“Eureka!” cried Prince Robert, “Our worth is so (c) Would the solution change if risk measure for
great each dollar in the stock fund were 14 instead
That there’s no other way we could return in this of 12?
state. (d) For each additional dollar that is available, how
Any other skins or nut that we might have brought much does the risk change?
Would now have us poorer. And now I know what— (e) Would the solution change if the amount that
I’ll write my friend Horace in England, for surely must be invested in the money market fund were
Only he can appreciate our serendipity.” changed from $40,000 to $50,000?
Formulate and solve Serendipity by graphical LP in 7-38 Refer to the Bhavika Investments (Problem 7-37) situ-
order to calculate “what their new wealth might be.” ation once again. It has been decided that, rather than
7-37 Bhavika Investments, a group of financial advisors minimize risk, the objective should be to maximize re-
and retirement planners, has been requested to pro- turn while placing restriction on the amount of risk.
vide advice on how to invest $200,000 for one of its The average risk should be no more than 11 (with a to-
clients. The client has stipulated that the money tal risk of 2,200,000 for the $200,000 invested). The
must be put into either a stock fund or a money mar- linear program was reformulated, and the QM for
ket fund, and the annual return should be at least Windows output is shown on the next page.
$14,000. Other conditions related to risk have also (a) How much money should be invested in the
been specified, and the following linear program money market fund and the stock fund? What is
was developed to help with this investment decision: the total return? What rate of return is this?
(b) What is the total risk? What is the average risk?
Minimize risk = 12S + 5M
(c) Would the solution change if return for each dol-
subject to
lar in the stock fund were 0.09 instead of 0.10?
S + M = 200,000 total investment is (d) For each additional dollar that is available, what
$200,000 is the marginal rate of return?
0.10S + 0.05M Ú 14,000 return must be at least (e) How much would the total return change if
$14,000 the amount that must be invested in the money
M Ú 40,000 at least $40,000 must market fund were changed from $40,000 to
be in money market $50,000?
fund Problems 7-39 to 7-44 test your ability to for-
mulate LP problems that have more than two vari-
S, M Ú 0
ables. They cannot be solved graphically but will
where give you a chance to set up a larger problem.
S = dollars invested in stock fund 7-39 The Feed ‘N Ship Ranch fattens cattle for local
M = dollars invested in money market fund farmers and ships them to meat markets in Kansas

Output for Problem 7-37

298 CHAPTER 7 • LINEAR PROGRAMMING MODELS: GRAPHICAL AND COMPUTER METHODS

Output for Problem 7-38

City and Omaha. The owners of the ranch seek to

DEPARTMENT
determine the amounts of cattle feed to buy so that UNIT
minimum nutritional standards are satisfied, and at PRODUCT WIRING DRILLING ASSEMBLY INSPECTION PROFIT ($)
the same time total feed costs are minimized. The XJ201 0.5 0.3 0.2 0.5 9
feed mix can be made up of the three grains that XM897 1.5 1 4 1 12
contain the following ingredients per pound of feed:
TR29 1.5 2 1 0.5 15
BR788 1 3 2 0.5 11
FEED (OZ.)
INGREDIENT STOCK X STOCK Y STOCK Z
A 3 2 4 The production available in each department each
month, and the minimum monthly production re-
B 2 3 1
quirement to fulfill contracts, are as follows:
C 1 0 2
D 6 8 4
MINIMUM
CAPACITY PRODUCTION
The cost per pound of stocks X, Y, and Z are $2, $4, DEPARTMENT (HOURS) PRODUCT LEVEL
and $2.50, respectively. The minimum requirement Wiring 15,000 XJ201 150
per cow per month is 4 pounds of ingredient A, 5 Drilling 17,000 XM897 100
pounds of ingredient B, 1 pound of ingredient C, and
Assembly 26,000 TR29 300
8 pounds of ingredient D.
The ranch faces one additional restriction: it can Inspection 12,000 BR788 400
only obtain 500 pounds of stock Z per month from
the feed supplier regardless of its need. Because
there are usually 100 cows at the Feed ‘N Ship The production manager has the responsibility of
Ranch at any given time, this means that no more specifying production levels for each product for the
than 5 pounds of stock Z can be counted on for use coming month. Help him by formulating (that is,
in the feed of each cow per month. setting up the constraints and objective function)
(a) Formulate this as an LP problem. Weinberger’s problem using LP.
(b) Solve using LP software. 7-41 Outdoor Inn, a camping equipment manufacturer in
7-40 The Weinberger Electronics Corporation manufac- southern Utah, is developing a production schedule
tures four highly technical products that it supplies for a popular type of tent, the Double Inn. Orders
to aerospace firms that hold NASA contracts. Each have been received for 180 of these to be delivered
of the products must pass through the following de- at the end of this month, 220 to be delivered at the
partments before they are shipped: wiring, drilling, end of next month, and 240 to be delivered at the
assembly, and inspection. The time requirement in end of the month after that. This tent may be pro-
hours for each unit produced and its corresponding duced at a cost of $120, and the maximum number
profit value are summarized in the following table: of tents that can be produced in a month is 230.
 DISCUSSION QUESTIONS AND PROBLEMS 299

The company may produce some extra tents in one TABLE FOR PROBLEM 7-43
month and keep them in storage until the next MCA Income Statement Month Ended September 30
month. The cost for keeping these in inventory for
1 month is estimated to be $6 per tent for each tent REGULAR INTELLIGENT
left at the end of the month. Formulate this as an LP MODEMS MODEMS
problem to minimize cost while meeting demand Sales $450,000 $640,000
and not exceeding the monthly production capacity. Less: Discounts 10,000 15,000
Solve it using any computer software. (Hint: Define
Returns 12,000 9,500
variables to represent the number of tents left over at
Warranty replacements 4,000 2,500
the end of each month.)
Net sales $424,000 $613,000
7-42 Outdoors Inn (see Problem 7-41) expanded its tent-
Sales costs
making operations later in the year. While still mak-
ing the Double Inn tent, it is also making a larger Direct labor 60,000 76,800
tent, the Family Rolls, which has four rooms. The Indirect labor 9,000 11,520
company can produce up to a combined total of 280 Materials cost 90,000 128,000
tents per month. The following table provides the Depreciation 40,000 50,800
demand that must be met and the production costs Cost of sales $199,000 $267,120
for the next 3 months. Note that the costs will in- Gross profit $225,000 $345,880
crease in month 2. The holding cost for keeping a Selling and general expenses
tent in inventory at the end of the month for use in General expenses—variable 30,000 35,000
the next month is estimated to be $6 per tent for the General expenses—fixed 36,000 40,000
Double Inn and $8 per tent for the Family Rolls. De- Advertising 28,000 25,000
velop a linear program to minimize the total cost.
Sales commissions 31,000 60,000
Solve it using any computer software.
Total operating cost $125,000 $160,000
Pretax income $100,000 $185,880
DEMAND COST TO DEMAND COST TO Income taxes (25%) 25,000 46,470
FOR PRODUCE FOR PRODUCE
DOUBLE DOUBLE FAMILY FAMILY Net income $ 75,000 $139,410
MONTH INN INN ROLLS ROLLS
Third, MCA is experiencing a problem affecting
1 185 $120 60 $150
the intelligent modems model. Its component supplier
2 205 $130 70 $160 is able to guarantee only 8,000 microprocessors for
3 225 $130 65 $160 November delivery. Each intelligent modem requires
one of these specially made microprocessors. Alter-
native suppliers are not available on short notice.
7-43 Modem Corporation of America (MCA) is the MCA wants to plan the optimal mix of the two
world’s largest producer of modem communication modem models to produce in November to maxi-
devices for microcomputers. MCA sold 9,000 of the mize profits for MCA.
regular model and 10,400 of the smart (“intelligent”) (a) Formulate, using September’s data, MCA’s prob-
model this September. Its income statement for the lem as a linear program.
month is shown in the table on this page. Costs pre- (b) Solve the problem graphically.
sented are typical of prior months and are expected to (c) Discuss the implications of your recommended
remain at the same levels in the near future. solution.
The firm is facing several constraints as it pre-
7-44 Working with chemists at Virginia Tech and George
pares its November production plan. First, it has ex-
Washington Universities, landscape contractor
perienced a tremendous demand and has been
Kenneth Golding blended his own fertilizer, called
unable to keep any significant inventory in stock.
“Golding-Grow.” It consists of four chemical com-
This situation is not expected to change. Second, the
pounds, C-30, C-92, D-21, and E-11. The cost per
firm is located in a small Iowa town from which ad-
pound for each compound is indicated as follows:
ditional labor is not readily available. Workers can
be shifted from production of one modem to an-
other, however. To produce the 9,000 regular CHEMICAL COMPOUND COST PER POUND ($)
modems in September required 5,000 direct labor C-30 0.12
hours. The 10,400 intelligent modems absorbed C-92 0.09
10,400 direct labor hours.
D-21 0.11
E-11 0.04
300 CHAPTER 7 • LINEAR PROGRAMMING MODELS: GRAPHICAL AND COMPUTER METHODS

The specifications for Golding-Grow are as follows:

CRUDE A CRUDE B
(1) E-11 must constitute at least 15% of the blend;
(2) C-92 and C-30 must together constitute at least Cost per gallon $0.42 $0.47
45% of the blend; (3) D-21 and C-92 can together Ingredient 1 40% 52%
constitute no more than 30% of the blend; and (4) Other ingredients 60% 48%
Golding-Grow is packaged and sold in 50-pound
bags. In order to achieve the desired octane ratings, at
(a) Formulate an LP problem to determine what least 41% of Regular gasoline should be Ingredient
blend of the four chemicals will allow Golding 1; at least 44% of Premium gasoline must be Ingre-
to minimize the cost of a 50-pound bag of the dient 1, and at least 48% of Super gasoline must be
fertilizer. Ingredient 1. Due to current contract commitments,
(b) Solve using a computer to find the best solution. Raptor Fuels must produce as least 20,000 gallons of
7-45 Raptor Fuels produces three grades of gasoline— Regular, at least 15,000 gallons of Premium, and at
Regular, Premium, and Super. All of these are least 10,000 gallons of Super. Formulate a linear
produced by blending two types of crude oil— program that could be used to determine how much
Crude A and Crude B. The two types of crude of Crude A and Crude B should be used in each of
contain specific ingredients which help in deter- the gasolines to meet the demands at the minimum
mining the octane rating of gasoline. The impor- cost. What is the minimum cost? How much of
tant ingredients and the costs are contained in the Crude A and Crude B are used in each gallon of the
following table: different types of gasoline?

Internet Homework Problems

See our Internet home page, at www.pearsonhighered.com/render, for additional homework
problems, Problems 7-46 to 7-50.

Case Study
Mexicana Wire Works
Ron Garcia felt good about his first week as a management management trainee. Ron studied operations management in his
trainee at Mexicana Wire Winding, Inc. He had not yet devel- MBA program in southern California, so I think he is competent
oped any technical knowledge about the manufacturing to help us with a problem we have been discussing for a long
process, but he had toured the entire facility, located in the sub- time without resolution. I’m sure that each of you on my staff
urbs of Mexico City, and had met many people in various areas will give Ron your full cooperation.”
of the operation. Vivian turned to José Arroyo, production control manager.
Mexicana, a subsidiary of Westover Wire Works, a Texas “José, why don’t you describe the problem we are facing?”
firm, is a medium-sized producer of wire windings used in mak- “Well,” José said, “business is very good right now. We are
ing electrical transformers. Carlos Alverez, the production con- booking more orders than we can fill. We will have some new
trol manager, described the windings to Garcia as being of equipment on line within the next several months, which will
standardized design. Garcia’s tour of the plant, laid out by take care of our capacity problems, but that won’t help us in
process type (see Figure 7.20), followed the manufacturing se- April. I have located some retired employees who used to work
quence for the windings: drawing, extrusion, winding, inspec- in the drawing department, and I am planning to bring them in
tion, and packaging. After inspection, good product is packaged as temporary employees in April to increase capacity there.
and sent to finished product storage; defective product is stored Because we are planning to refinance some of our long-term
separately until it can be reworked. debt, Vivian wants our profits to look as good as possible in
On March 8, Vivian Espania, Mexicana’s general manager, April. I’m having a hard time figuring out which orders to run
stopped by Garcia’s office and asked him to attend a staff meet- and which to back order so that I can make the bottom line look
ing at 1:00 P.M. as good as possible. Can you help me with this?”
“Let’s get started with the business at hand,” Vivian said, Garcia was surprised and apprehensive to receive such an
opening the meeting. “You all have met Ron Garcia, our new important, high-profile assignment so early in his career.
 CASE STUDY 301

FIGURE 7.20
Finished
Mexicana Wire Winding, Office Wire Drawing Product
Inc. Storage

Rework
Packaging Department

Winding
Receiving and
Raw Material Storage
Extrusion Rejected
Product
Storage
Inspection

Recovering quickly, he said, “Give me your data and let me Plant Capacity (Hours)
work with it for a day or two.”
DRAWING EXTRUSION WINDING PACKAGING
April Orders 4,000 4,200 2,000 2,300
Product W0075C 1,400 units
Note: Inspection capacity is not a problem; we can work overtime, as neces-
Product W0033C 250 units sary, to accommodate any schedule.

Product W0005X 1,510 units

Product W0007X 1,116 units Bill of Labor (Hours/Unit)

Note: Vivian Espania has given her word to a key customer that PRODUCT DRAWING EXTRUSION WINDING PACKAGING
we will manufacture 600 units of product W0007X and 150 units
of product W0075C for him during April W0075C 1.0 1.0 1.0 1.0
W0033C 2.0 1.0 3.0 0.0
Standard Cost W0005X 0.0 4.0 0.0 3.0
W0007X 1.0 1.0 0.0 2.0
SELLING
PRODUCT MATERIAL LABOR OVERHEAD PRICE

W0075C $33.00 $ 9.90 $23.10 $100.00

Discussion Questions
W0033C 25.00 7.50 17.50 80.00
1. What recommendations should Ron Garcia make, with
W0005X 35.00 10.50 24.50 130.00
what justification? Provide a detailed analysis with charts,
W0007X 75.00 11.25 63.75 175.00 graphs, and computer printouts included.
2. Discuss the need for temporary workers in the drawing
Selected Operating Data department.
Average output per month = 2,400 units 3. Discuss the plant layout.
Average machine utilization = 63%
Source: Professor Victor E. Sower, Sam Houston State University. This case
Average percentage of production set to rework department = material is based on an actual situation, with names and data altered for confi-
5% (mostly from Winding Department) dentiality.
Average no. of rejected units awaiting rework = 850 (mostly from
Winding Department)

Internet Case Study

See our Internet home page, at www.pearsonhighered.com/render, for this additional case
study: Agri Chem Corporation. This case involves a company’s response to an energy shortage.
302 CHAPTER 7 • LINEAR PROGRAMMING MODELS: GRAPHICAL AND COMPUTER METHODS

Bibliography
Bassamboo, Achal, J. Michael Harrison, and Assaf Zeevi. “Design and Con- Fourer, Robert. “Software Survey: Linear Programming,” OR/MS Today 36, 3
trol of a Large Call Center: Asymptotic Analysis of an LP-Based (June 2009): 46–55.
Method,” Operations Research 54, 3 (May–June 2006): 419–435. Gass, Saul I. “The First Linear-Programming Shoppe,” Operations Research
Behjat, Laleh, Anthony Vannelli, and William Rosehart. “Integer Linear Pro- 50, 1 (January–February 2002): 61–68.
gramming Model for Global Routing,” INFORMS Journal on Comput- Greenberg, H. J. “How to Analyze the Results of Linear Programs—Part 1:
ing 18, 2 (Spring 2006): 137–150. Preliminaries,” Interfaces 23, 4 (July–August 1993): 56–68.
Bixby, Robert E. “Solving Real-World Linear Programs: A Decade and More Greenberg, H. J. “How to Analyze the Results of Linear Programs—Part 3:
of Progress,” Operations Research 50, 1 (January–February 2002): 3–15. Infeasibility Diagnosis,” Interfaces 23, 6 (November–December 1993):
Bodington, C. E., and T. E. Baker. “A History of Mathematical Programming 120–139.
in the Petroleum Industry,” Interfaces 20, 4 (July–August 1990): Hafizoĝlu, A. B., and M Azizoĝlu. “Linear Programming Based Approaches
117–132. for the Discrete Time/Cost Trade-off Problem in Project Networks,”
Boros, E., L. Fedzhora, P. B. Kantor, K. Saeger, and P. Stroud. “A Large-Scale Journal of the Operational Research Society 61 (April 2010): 676–685.
Linear Programming Model For Finding Optimal Container Inspection Higle, Julia L., and Stein W. Wallace. “Sensitivity Analysis and Uncertainty in
Strategies,” Naval Research Logistics 56, 5 (August 2009): 404–420. Linear Programming,” Interfaces 33, 4(July–August 2003): 53–60.
Chakravarti, N. “Tea Company Steeped in OR,” OR/MS Today 27, 2 (April Murphy, Frederic H. “ASP, the Art and Science of Practice: Elements of a
2000): 32–34. Theory of the Practice of Operations Research: Expertise in Practice,”
Ching, Wai-Ki, Wai-On Yuen, Michael K. Ng, and Shu-Qin Zhang. “A Linear Interfaces 35, 4 (July–August 2005): 313–322.
Programming Approach for Determining Optimal Advertising Policy,” Orden, A. “LP from the ‘40s to the ‘90s,” Interfaces 23, 5 (September–-
IMA Journal of Management Mathematics 17, 1 (2006): 83–96. October 1993): 2–12.
Dantzig, George B. “Linear Programming Under Uncertainty,” Management Romeijn, H. Edwin, Ravindra K. Ahuja, James F. Dempsey, and Arvind
Science 50, 12 (December 2004): 1764–1769. Kumar. “A New Linear Programming Approach to Radiation Therapy
Desroisers, Jacques. “Air Transat Uses ALTITUDE to Manage Its Aircraft Treatment Planning Problems,” Operations Research 54, 2 (March–April
Routing, Crew Pairing, and Work Assignment,” Interfaces 30, 2 2006): 201–216.
(March–April 2000): 41–53. Rubin, D. S., and H. M. Wagner. “Shadow Prices: Tips and Traps for
Dutta, Goutam, and Robert Fourer. “A Survey of Mathematical Programming Managers and Instructors,” Interfaces 20, 4 (July–August 1990):
Applications in Integrated Steel Plants,” Manufacturing & Service Oper- 150–157.
ations Management 3, 4 (Fall 2001): 387–400. Wendell, Richard E. “Tolerance Sensitivity and Optimality Bounds in Linear
Farley, A. A. “Planning the Cutting of Photographic Color Paper Rolls for Ko- Programming,” Management Science 50, 6 (June 2004) 797–803.
dak (Australasia) Pty. Ltd.,” Interfaces 21, 1 (January–February 1991):
92–106.

Appendix 7.1 Excel QM

Using the Excel QM add-in can help you easily solve linear programming problems. Excel QM
automates the spreadsheet preparation for the use of the Solver add-in. We will illustrate this
using the Flair Furniture example.
To begin, from the Add-Ins tab in Excel 2010, click Excel QM and then select Linear, Inte-
ger & Mixed Integer Programming from the drop-down menu, as shown in Program 7.7A. The
Excel QM Spreadsheet Initialization window opens, and in it you enter the problem title, the
number of variables, the number of constraints (do not count the nonnegativity constraints), and
specify whether the problem is a maximization or minimization problem. This is illustrated in
Program 7.7B. When finished, click OK.
When the initialization process is finished, a spreadsheet is prepared for data input, as
shown in Program 7.7C. In this screen, enter the data in the section labeled Data. Specify the
type of constraint (less-than, greater-than, or equal-to) and change the variable names and the
constraint names, if desired.
Program 7.7D presents the same spreadsheet as Program 7.7C, with the data input and the
variable names changed. Once the data have been entered, from the Data tab, select Solver. The
Solver Parameters window opens, as shown in Program 7.7E. Excel QM will have made all the
necessary inputs and selections, so simply click OK to find the solution.
The solution is displayed in Program 7.7F. In addition to the optimal values for the decision
variables and the profit, the solution also includes slack or surplus for each constraint. You can
obtain additional information from the Solver Results window that opens. Select a type of report
(if any) and click OK. Any report that you selected will be placed on a separate worksheet.
 APPENDIX 7.1 EXCEL QM 303

PROGRAM 7.7A
Using Excel QM in Excel
2010 for the Flair
Furniture Example From the Add-Ins tab,
click Excel QM.

From the drop-down Excel QM

menu, click Linear, Integer &
Mixed Integer Programming.

PROGRAM 7.7B
Using the Excel QM
Spreadsheet
Initialization Window
Enter the title.

Enter the number of constraints

and the number of variables.

Click OK.
Select Maximize.
304 CHAPTER 7 • LINEAR PROGRAMMING MODELS: GRAPHICAL AND COMPUTER METHODS

PROGRAM 7.7C
Type over the variable
An Excel QM Initialized Instructions for specifying the
names to change them.
Spreadsheet type of constraint are here.
Note special Instructions to
enter the = constraint. Type
over the sign to change it.

Input data here. Nothing outside

this Data area should be changed.

PROGRAM 7.7D
Excel QM Spreadsheet
After Data Input for Flair
Furniture On the Data tab, click Solver.

Instructions to access Solver are here.

 APPENDIX 7.1 EXCEL QM 305

PROGRAM 7.7E
The Excel Solver
Parameters Window

When the window opens, just

click Solve. Excel QM has
already entered inputs for the
Solver Parameter is dialog box.

PROGRAM 7.7F
Additional results are available
Excel QM output for Flair by selecting any of these and
Furniture and the Solver clicking OK.
Results Window

Solution is shown here.