Tan S.T. Finite Mathematics for the Managerial, Life, and Social Sciences
Подождите немного. Документ загружается.
Since the most negative entry in the last row (20) occurs in the x-column, we
choose the x-column as the pivot column. Proceeding with the first iteration, we
obtain the following sequence of tableaus:
After one iteration we are at the point (3, 0, 0) with P 60. (See Figure 4.) Since
the most negative entry in the last row is , we choose the y-column as the pivot
column. Proceeding with this iteration, we obtain
16
3
212 4 LINEAR PROGRAMMING: AN ALGEBRAIC APPROACH
xyzu√ wP Constant
3 1 21000 9
2 3 10100 8
1 2 30010 7
20 12 180001 0
xyzu√ wP Constant
1
1
3
2
3
1
3
000 3
2 3 10100 8
1 2 30010 7
20 12 180001 0
xyzu√ wP Constant
1
1
3
2
3
1
3
000 3
0
7
3
1
3
2
3
100 2
0
5
3
7
3
1
3
010 4
0
1
3
6
1
3
4
2
3
0
001 60
xy zu√ wP Constant
1
1
3
2
3
1
3
000 3
01
1
7
2
7
3
7
00
6
7
0
5
3
7
3
1
3
010 4
0
1
3
6
1
3
4
2
3
0
001 60
xy z u √ wP Constant
10
5
7
3
7
1
7
00
1
7
9
01
1
7
2
7
3
7
00
6
7
00
1
7
8
1
7
5
7
10
1
7
8
00
3
7
8
3
7
6
1
7
6
01 64
4
7
Pivot
씮
row
앖
Pivot
column
Ratio
7
1
7
8
2
4
9
3
3
R
2
2R
1
⎯⎯⎯⎯→
R
3
R
1
R
4
20R
1
Pivot
row
앖
Pivot
column
씮
Ratio
9
12
5
6
7
R
1
⎯→
1
3
앖
Pivot
column
Ratio
—
1
19
5
R
2
⎯→
3
7
R
1
R
2
⎯⎯⎯⎯→
R
3
R
2
R
4
R
2
16
3
5
3
1
3
87533_04_ch4_p201-256 1/30/08 9:51 AM Page 212
All entries in the last row are nonnegative, so we have reached the optimal solution.
We conclude that x 2, y 1, z 1, u 0, √ 0, w 0, and P 70.
The feasible set S for the problem is the hexahedron shown in Figure 5 on
page 214. It is the intersection of the half-spaces determined by the planes P
1
, P
2
,
and P
3
with equations 3x y 2z 9, 2x 3y z 8, x 2y 3z 7,
respectively, and the coordinate planes x 0, y 0, and z 0. That portion of
the figure showing the feasible set S is shown in Figure 4. Observe that the first
iteration of the simplex method brings us from A(0, 0, 0) with P 0 to B(3, 0, 0)
with P 60. The second iteration brings us from B(3, 0, 0) to CÓ
, , 0Ô with
P 64 , and the third iteration brings us from CÓ , , 0Ô to the
point H(2, 1, 1) with an optimal value of 70 for P.
6
7
19
7
4
7
6
7
19
7
4.1 THE SIMPLEX METHOD: STANDARD MAXIMIZATION PROBLEMS 213
z
y
S
H(2, 1, 1)
E 0, ,
17
7
5
7
D 0, , 0
8
3
B(3, 0, 0)
C , , 0
19
7
6
7
x
F 0, 0,
7
3
G , 0,
12
7
13
7
A(0, 0, 0)
The second iteration brings us to the point Ó , , 0Ô with P (See Figure 4.)64
4
7
.
6
7
19
7
xy z u √ wP Constant
10
5
7
3
7
1
7
00
1
7
9
01
1
7
2
7
3
7
00
6
7
00 1
1
1
8
1
5
8
1
7
8
01
00
3
7
8
3
7
6
1
7
6
01 64
4
7
xyz u √ wP Constant
100
1
7
8
1
1
8
1
5
8
02
010
1
5
8
1
7
8
1
1
8
01
001
1
1
8
1
5
8
1
7
8
01
000
4
9
9
7
9
1
9
9
170
FIGURE 4
The simplex method brings us from the
point A to the point H, at which the
objective function is maximized.
R
3
⎯→
7
18
⎯⎯⎯⎯→
R
4
R
3
38
7
R
2
1
7
R
3
R
1
5
7
R
3
Since there is a negative number in the last row of the simplex tableau, we perform
another iteration, as follows:
87533_04_ch4_p201-256 1/30/08 9:51 AM Page 213
APPLIED EXAMPLE 5
Production Planning Ace Novelty Company
has determined that the profit for each type-A, type-B, and type-C souvenir
that it plans to produce is $6, $5, and $4, respectively. To manufacture a type-A
souvenir requires 2 minutes on machine I, 1 minute on machine II, and 2 minutes
on machine III. A type-B souvenir requires 1 minute on machine I, 3 minutes on
machine II, and 1 minute on machine III. A type-C souvenir requires 1 minute on
machine I and 2 minutes on each of machines II and III. Each day there are
3 hours available on machine I, 5 hours available on machine II, and 4 hours
available on machine III for manufacturing these souvenirs. How many souvenirs
of each type should Ace Novelty make per day in order to maximize its profit?
(Compare with Example 1, Section 2.1.)
Solution
The given information is tabulated as follows:
Time Available
Type A Type B Type C (min)
Machine I $2 $1 $1 180
Machine II $1 $3 $2 300
Machine III $2 $1 $2 240
Profit per Unit $6 $5 $4
Let x, y, and z denote the respective numbers of type-A, type-B, and type-C sou-
venirs to be made. The total amount of time that machine I is used is given by
2x y z minutes and must not exceed 180 minutes. Thus, we have the in-
equality
2x y z 180
Similar considerations on the use of machines II and III lead to the inequalities
x 3y 2z 300
2x y 2z 240
214 4 LINEAR PROGRAMMING: AN ALGEBRAIC APPROACH
FIGURE 5
The feasible set S is obtained from the
intersection of the half-spaces deter-
mined by P
1
, P
2
, and P
3
with the coordi-
nate planes x 0, y 0, and z 0.
z
y
x
P
2
(2x + 3y + z = 8)
P
1
(3x + y + 2z = 9)
S
P
3
(x + 2y + 3z = 7)
H(2, 1, 1)
G , 0,
13
7
12
7
D 0, , 0
8
3
B(3, 0, 0)
C , , 0
19
7
6
7
F 0, 0,
7
3
E 0, ,
17
7
5
7
87533_04_ch4_p201-256 1/30/08 9:51 AM Page 214
The profit resulting from the sale of the souvenirs produced is given by
P 6x 5y 4z
The mathematical formulation of this problem leads to the following standard
linear programming problem: Maximize the objective (profit) function P 6x
5y 4z subject to
2x y z 180
x 3y 2z 300
2x y 2z 240
x 0, y 0, z 0
Introducing the slack variables u, √, and w gives the system of linear equations
2x y z u 180
x 3y 2z √ 300
2x y 2z w 240
6x 5y 4z P 0
The tableaus resulting from the use of the simplex algorithm are
4.1 THE SIMPLEX METHOD: STANDARD MAXIMIZATION PROBLEMS 215
xyzu√ wP Constant
2 1 11000 180
1 3 20100 300
2 1 20010 240
6 5 40001 0
xyzu√ wP Constant
1
1
2
1
2
1
2
000 90
1 3 20100 300
2 1 20010 240
6 5 40001 0
xyzu√ wP Constant
1
1
2
1
2
1
2
000 90
0
5
2
3
2
1
2
100 210
0011010 60
0 2 1 3001 540
xyzu√ wP Constant
1
1
2
1
2
1
2
000 90
01
3
5
1
5
2
5
00 84
0011010 60
0 2 1 3001 540
Ratio
240
2
120
300
1
300
180
2
90
Pivot
씮
row
앖
Pivot
column
Ratio
210
5/2
84
90
1/2
180
R
2
R
1
⎯⎯⎯→
R
3
2R
1
R
4
6R
1
Pivot
row
씮
앖
Pivot
column
R
1
⎯→
1
2
R
2
⎯→
2
5
87533_04_ch4_p201-256 1/30/08 9:51 AM Page 215
xyz u √ wP Constant
10
1
5
3
5
1
5
00 48
01
3
5
1
5
2
5
00 84
001 1 010 60
00
1
5
1
5
3
4
5
0 1 708
From the final simplex tableau, we read off the solution
x 48 y 84 z 0 u 0 √ 0 w 60 P 708
Thus, in order to maximize its profit, Ace Novelty should produce 48 type-A
souvenirs, 84 type-B souvenirs, and no type-C souvenirs. The resulting profit is
$708 per day. The value of the slack variable w 60 tells us that 1 hour of the
available time on machine III is left unused.
Interpreting Our Results Let’s compare the results obtained here with those
obtained in Example 7, Section 2.2. Recall that, to use all available machine time on
each of the three machines, Ace Novelty had to produce 36 type-A, 48 type-B, and
60 type-C souvenirs. This would have resulted in a profit of $696. Example 5 shows
how, through the optimal use of equipment, a company can boost its profit while
reducing machine wear!
Problems with Multiple Solutions and Problems
with No Solutions
As we saw in Section 3.3, a linear programming problem may have infinitely many solu-
tions. We also saw that a linear programming problem may have no solution. How do
we spot each of these phenomena when using the simplex method to solve a problem?
A linear programming problem will have infinitely many solutions if and only if
the last row to the left of the vertical line of the final simplex tableau has a zero in a
column that is not a unit column. Also, a linear programming problem will have no
solution if the simplex method breaks down at some stage. For example, if at some
stage there are no nonnegative ratios in our computation, then the linear programming
problem has no solution (see Exercise 44).
216 4 LINEAR PROGRAMMING: AN ALGEBRAIC APPROACH
⎯⎯⎯→
R
4
2R
2
R
1
1
2
R
2
Explore & Discuss
Consider the linear programming problem
Maximize P 4x 6y
subject to 2x y 10
2x 3y 18
x 0, y 0
1. Sketch the feasible set for the linear programming problem.
2. Use the method of corners to show that there are infinitely many optimal solutions. What
are they?
3. Use the simplex method to solve the problem as follows.
a. Perform one iteration on the initial simplex tableau and conclude that you have
arrived at an optimal solution. What is the value of P, and where is it attained? Com-
pare this result with that obtained in step 2.
b. Observe that the tableau obtained in part (a) indicates that there are infinitely many
solutions (see the comment above on multiple solutions). Now perform another itera-
tion on the simplex tableau using the x-column as the pivot column. Interpret the final
tableau.
87533_04_ch4_p201-256 1/30/08 9:51 AM Page 216
4.1 THE SIMPLEX METHOD: STANDARD MAXIMIZATION PROBLEMS 217
1. Solve the following linear programming problem by the
simplex method:
Maximize P 2x 3y 6z
subject to 2x 3y z 10
x y 2z 8
2y 3z 6
x 0, y 0, z 0
2. The LaCrosse Iron Works makes two models of cast-iron
fireplace grates, model A and model B. Producing one
model-A grate requires 20 lb of cast iron and 20 min of
labor, whereas producing one model-B grate requires 30 lb
of cast iron and 15 min of labor. The profit for a model-A
grate is $6, and the profit for a model-B grate is $8. There
are 7200 lb of cast iron and 100 labor-hours available each
week. Because of a surplus from the previous week, the
proprietor has decided that he should make no more than
150 units of model-A grates this week. Determine how
many of each model he should make in order to maximize
his profit.
Solutions to Self-Check Exercises 4.1 can be found on
page 221.
4.1 Exercises
4.1 Self-Check Exercises
4.1 Concept Questions
1. Give the three characteristics of a standard maximization
linear programming problem.
2. a. When the initial simplex tableau is set up, how is the
system of linear inequalities transformed into a system
of linear equations? How is the objective function P
c
1
x
1
c
2
x
2
c
n
x
n
rewritten?
b. If you are given a simplex tableau, how do you deter-
mine whether the optimal solution has been reached?
3. In the simplex method, how is a pivot column selected? A
pivot row? A pivot element?
In Exercises 1–10, determine whether the given simplex
tableau is in final form. If so, find the solution to the
associated regular linear programming problem. If not,
find the pivot element to be used in the next iteration of
the simplex method.
5. xyzu√wP Constant
1
1
3
0
1
3
0
2
3
0
1
3
0 2001 10 6
0
2
3
1
1
3
0
1
3
0
1
3
3
0 4010 21 17
6. xy zu √wP Constant
1
2
0
1
4
1
1
4
00
1
2
9
1
2
1
3
4
0
1
4
00
2
2
1
20 30 010 30
10
1
2
6
3
2
01 63
7. xyzst u √ P Constant
5
2
30100 40 46
1 00010 00 9
0 10001 00 12
0 01000 10 6
180 200 0 0 0 0 300 1 1800
8. xyz st u √ P Constant
100
2
5
0
6
5
8
5
04
000
2
5
1
6
5
8
5
05
010 00 1 00 12
001 00 0 10 6
000 72016 12 1 4920
1. xy u √ P Constant
01
5
7
1
7
0
2
7
0
10
3
7
2
7
0
3
7
0
00
1
7
3
3
7
1
22
7
0
2. xy u√ P Constant
11 100 6
10110 2
30 501 30
3. xyu√ P Constant
0
1
2
1
1
2
02
1
1
2
0
1
2
04
0
1
2
0
3
2
112
4. xy zu√ P Constant
305110 28
213010 16
208031 48
87533_04_ch4_p201-256 1/30/08 9:51 AM Page 217
218 4 LINEAR PROGRAMMING: AN ALGEBRAIC APPROACH
9. xy zu √ P Constant
10
3
5
0
1
5
030
01
1
5
9
1
3
5
010
00
2
5
6
001 60
10. xyzu √ wP Constant
0
1
2
01
1
2
00 2
1
1
2
10
1
2
00 13
2
1
2
00
3
2
10 4
1300 101 26
In Exercises 11–25, solve each linear programming prob-
lem by the simplex method.
11. Maximize P 3x 4y
subject to x y 4
2x y 5
x 0, y 0
12. Maximize P 5x 3y
subject to x y 80
3x 90
x 0, y 0
13. Maximize P 10x 12y
subject to x 2y 12
3x 2y 24
x 0, y 0
14. Maximize P 5x 4y
subject to 3x 5y 78
4x y
36
x 0, y 0
15. Maximize P 4x 6y
subject to 3x y 24
2x y 18
x 3y 24
x 0, y 0
16. Maximize P 15x 12y
subject to x y 12
3x y 30
10x 7y 70
x 0, y 0
17. Maximize P 3x 4y 5z
subject to x y z 8
3x 2y
4z 24
x 0, y 0, z 0
18. Maximize P 3x 3y 4z
subject to x y 3z 15
4x 4y 3z 65
x 0, y 0, z 0
19. Maximize P 3x 4y z
subject to 3x 10y 5z 120
5x 2y 8z 6
8x 10y 3z 105
x 0, y 0, z
0
20. Maximize P x 2y z
subject to 2x y z 14
4x 2y 3z 28
2x 5y 5z 30
x 0, y 0, z 0
21. Maximize P 4x 6y 5z
subject to x y z 20
2x 4y 3z 42
2x 3z 30
x 0, y 0, z 0
22. Maximize P x
4y 2z
subject to 3x y z 80
2x y z 40
x y z 80
x 0, y 0, z 0
23. Maximize P 12x 10y 5z
subject to 2x y z 10
3x 5y z 45
2x 5y z 40
x 0, y 0, z 0
24. Maximize P 2x 6y 6z
subject to 2x y
3z 10
4x y 2z 56
6x 4y 3z 126
2x y z 32
x 0, y 0, z 0
25. Maximize P 24x 16y 23z
subject to 2x y 2z 7
2x 3y z 8
x 2y 3z 7
x 0, y 0, z 0
26. Rework Example 3 using the y-column as the pivot column
in the first iteration of the simplex method.
27. Show that the following linear programming problem
Maximize P 2x 2y 4z
subject to 3x 3y 2z 100
5x 5y 3z 150
x 0, y 0, z 0
has optimal solutions x 30, y 0, z 0, P 60 and
x 0, y 30, z 0, P 60.
87533_04_ch4_p201-256 1/30/08 9:51 AM Page 218
4.1 THE SIMPLEX METHOD: STANDARD MAXIMIZATION PROBLEMS 219
28. M
ANUFACTURING
—P
RODUCTION
S
CHEDULING
A company
manufactures two products, A and B, on two machines, I
and II. It has been determined that the company will real-
ize a profit of $3/unit of product A and a profit of $4/unit
of product B. To manufacture 1 unit of product A
requires 6 min on machine I and 5 min on machine II. To
manufacture 1 unit of product B requires 9 min on
machine I and 4 min on machine II. There are 5 hr of
machine time available on machine I and 3 hr of machine
time available on machine II in each work shift. How
many units of each product should be produced in each
shift to maximize the company’s profit? What is the
largest profit the company can realize? Is there any time
left unused on the machines?
29. M
ANUFACTURING
—P
RODUCTION
S
CHEDULING
National
Business Machines Corporation manufactures two models
of fax machines: A and B. Each model A costs $100 to
make, and each model B costs $150. The profits are $30 for
each model-A and $40 for each model-B fax machine. If
the total number of fax machines demanded each month
does not exceed 2500 and the company has earmarked no
more than $600,000/month for manufacturing costs, find
how many units of each model National should make each
month in order to maximize its monthly profit. What is the
largest monthly profit the company can make?
30. M
ANUFACTURING
—P
RODUCTION
S
CHEDULING
Kane Man-
ufacturing has a division that produces two models
of hibachis, model A and model B. To produce each
model-A hibachi requires 3 lb of cast iron and 6 min of
labor. To produce each model-B hibachi requires 4 lb of
cast iron and 3 min of labor. The profit for each model-
A hibachi is $2, and the profit for each model-B hibachi
is $1.50. If 1000 lb of cast iron and 20 labor-hours are
available for the production of hibachis each day, how
many hibachis of each model should the division pro-
duce in order to maximize Kane’s profit? What is the
largest profit the company can realize? Is there any raw
material left over?
31. A
GRICULTURE
—C
ROP
P
LANNING
A farmer has 150 acres of
land suitable for cultivating crops A and B. The cost of cul-
tivating crop A is $40/acre whereas that of crop B
is $60/acre. The farmer has a maximum of $7400 available
for land cultivation. Each acre of crop A requires
20 labor-hours, and each acre of crop B requires 25 labor-
hours. The farmer has a maximum of 3300 labor-hours
available. If he expects to make a profit of $150/acre on
crop A and $200/acre on crop B, how many acres of each
crop should he plant in order to maximize his profit? What
is the largest profit the farmer can realize? Are there any
resources left over?
32. I
NVESTMENTS
—A
SSET
A
LLOCATION
A financier plans to
invest up to $500,000 in two projects. Project A yields a
return of 10% on the investment whereas project B yields
a return of 15% on the investment. Because the investment
in project B is riskier than the investment in project A, the
financier has decided that the investment in project B
should not exceed 40% of the total investment. How much
should she invest in each project in order to maximize the
return on her investment? What is the maximum return?
33. I
NVESTMENTS
—A
SSET
A
LLOCATION
Ashley has earmarked at
most $250,000 for investment in three mutual funds: a
money market fund, an international equity fund, and a
growth-and-income fund. The money market fund has
a rate of return of 6%/year, the international equity fund
has a rate of return of 10%/year, and the growth-and-
income fund has a rate of return of 15%/year. Ashley has
stipulated that no more than 25% of her total portfolio
should be in the growth-and-income fund and that no more
than 50% of her total portfolio should be in the interna-
tional equity fund. To maximize the return on her invest-
ment, how much should Ashley invest in each type of
fund? What is the maximum return?
34. M
ANUFACTURING
—P
RODUCTION
S
CHEDULING
A division of
the Winston Furniture Company manufactures dining
tables and chairs. Each table requires 40 board feet of
wood and 3 labor-hours. Each chair requires 16 board feet
of wood and 4 labor-hours. The profit for each table is $45,
and the profit for each chair is $20. In a certain week, the
company has 3200 board feet of wood available and
520 labor-hours available. How many tables and chairs
should Winston manufacture in order to maximize its
profit? What is the maximum profit?
35. M
ANUFACTURING
—P
RODUCTION
S
CHEDULING
A company
manufactures products A, B, and C. Each product is
processed in three departments: I, II, and III. The total
available labor-hours per week for departments I, II, and III
are 900, 1080, and 840, respectively. The time require-
ments (in hours per unit) and profit per unit for each prod-
uct are as follows:
Product A Product B Product C
Dept. I $ 2 $ 1 $ 2
Dept. II $ 3 $ 1 $ 2
Dept. III $ 2 $ 2 $ 1
Profit $18 $12 $15
How many units of each product should the company pro-
duce in order to maximize its profit? What is the largest
profit the company can realize? Are there any resources
left over?
36. M
ANUFACTURING
—P
RODUCTION
S
CHEDULING
Ace Novelty
manufactures “Giant Pandas” and “Saint Bernards.” Each
Panda requires 1.5 yd
2
of plush, 30 ft
3
of stuffing, and 5
pieces of trim; each Saint Bernard requires 2 yd
2
of plush,
35 ft
3
of stuffing, and 8 pieces of trim. The profit for each
Panda is $10, and the profit for each Saint Bernard is $15.
If 3600 yd
2
of plush, 66,000 ft
3
of stuffing and 13,600
pieces of trim are available, how many of each of the
stuffed animals should the company manufacture to maxi-
mize its profit? What is the maximum profit?
87533_04_ch4_p201-256 1/30/08 9:51 AM Page 219
220 4 LINEAR PROGRAMMING: AN ALGEBRAIC APPROACH
37. A
DVERTISING
—T
ELEVISION
C
OMMERCIALS
As part of a cam-
paign to promote its annual clearance sale, Excelsior Com-
pany decided to buy television advertising time on Station
KAOS. Excelsior’s television advertising budget is
$102,000. Morning time costs $3000/minute, afternoon
time costs $1000/minute, and evening (prime) time costs
$12,000/minute. Because of previous commitments,
KAOS cannot offer Excelsior more than 6 min of prime
time or more than a total of 25 min of advertising time over
the 2 weeks in which the commercials are to be run. KAOS
estimates that morning commercials are seen by 200,000
people, afternoon commercials are seen by 100,000 people,
and evening commercials are seen by 600,000 people.
How much morning, afternoon, and evening advertising
time should Excelsior buy to maximize exposure of its
commercials?
38. I
NVESTMENTS
—A
SSET
A
LLOCATION
Sharon has a total of
$200,000 to invest in three types of mutual funds: growth,
balanced, and income funds. Growth funds have a rate of
return of 12%/year, balanced funds have a rate of return of
10%/year, and income funds have a return of 6%/year. The
growth, balanced, and income mutual funds are assigned
risk factors of 0.1, 0.06, and 0.02, respectively. Sharon has
decided that at least 50% of her total portfolio is to be in
income funds and at least 25% in balanced funds. She has
also decided that the average risk factor for her investment
should not exceed 0.05. How much should Sharon invest in
each type of fund in order to realize a maximum return on
her investment? What is the maximum return?
Hint: The constraint for the average risk factor for the investment
is given by 0.1x 0.06y 0.02z 0.05(x y z).
39. M
ANUFACTURING
—P
RODUCTION
C
ONTROL
Custom Office
Furniture is introducing a new line of executive desks made
from a specially selected grade of walnut. Initially, three
models—A, B, and C—are to be marketed. Each model-A
desk requires 1 hr for fabrication, 1 hr for assembly, and
1 hr for finishing; each model-B desk requires 1 hr for fabri-
cation, 1 hr for assembly, and 1 hr for finishing; each model-
C desk requires 1 hr, hr, and hr for fabrication, assembly,
and finishing, respectively. The profit on each model-A desk
is $26, the profit on each model-B desk is $28, and the profit
on each model-C desk is $24. The total time available in the
fabrication department, the assembly department, and the
finishing department in the first month of production is
310 hr, 205 hr, and 190 hr, respectively. To maximize Cus-
tom’s profit, how many desks of each model should be made
in the month? What is the largest profit the company can
realize? Are there any resources left over?
40. M
ANUFACTURING
—P
REFABRICATED
H
OUSING
P
RODUCTION
Boise Lumber has decided to enter the lucrative prefabricated
housing business. Initially, it plans to offer three models:
standard, deluxe, and luxury. Each house is prefabricated and
partially assembled in the factory, and the final assembly is
completed on site. The dollar amount of building material
required, the amount of labor required in the factory for pre-
fabrication and partial assembly, the amount of on-site labor
required, and the profit per unit are as follows:
1
2
3
4
1
2
1
2
1
4
Standard Deluxe Luxury
Model Model Model
Material $6,000 $8,000 $10,000
Factory Labor (hr) $ 240 $ 220 $ 200
On-site Labor (hr) $ 180 $ 210 $ 300
Profit $3,400 $4,000 $5,000
For the first year’s production, a sum of $8,200,000 is bud-
geted for the building material; the number of labor-hours
available for work in the factory (for prefabrication and
partial assembly) is not to exceed 218,000 hr; and the
amount of labor for on-site work is to be less than or equal
to 237,000 labor-hours. Determine how many houses of
each type Boise should produce (market research has con-
firmed that there should be no problems with sales) to max-
imize its profit from this new venture.
41. M
ANUFACTURING
—C
OLD
F
ORMULA
P
RODUCTION
Beyer
Pharmaceutical produces three kinds of cold formulas: I,
II, and III. It takes 2.5 hr to produce 1000 bottles of for-
mula I, 3 hr to produce 1000 bottles of formula II, and 4 hr
to produce 1000 bottles of formula III. The profits for each
1000 bottles of formula I, formula II, and formula III are
$180, $200, and $300, respectively. Suppose, for a certain
production run, there are enough ingredients on hand to
make at most 9000 bottles of formula I, 12,000 bottles of
formula II, and 6000 bottles of formula III. Furthermore,
suppose the time for the production run is limited to a max-
imum of 70 hr. How many bottles of each formula should
be produced in this production run so that the profit is max-
imized? What is the maximum profit realizable by the
company? Are there any resources left over?
42. P
RODUCTION
—J
UICE
P
RODUCTS
CalJuice Company has
decided to introduce three fruit juices made from blending
two or more concentrates. These juices will be packaged in
2-qt (64-oz) cartons. One carton of pineapple–orange juice
requires 8 oz each of pineapple and orange juice concen-
trates. One carton of orange–banana juice requires 12 oz of
orange juice concentrate and 4 oz of banana pulp concentrate.
Finally, one carton of pineapple–orange–banana juice
requires 4 oz of pineapple juice concentrate, 8 oz of orange
juice concentrate, and 4 oz of banana pulp. The company has
decided to allot 16,000 oz of pineapple juice concentrate,
24,000 oz of orange juice concentrate, and 5000 oz of banana
pulp concentrate for the initial production run. The company
has also stipulated that the production of pineapple–
orange–banana juice should not exceed 800 cartons. Its profit
on one carton of pineapple–orange juice is $1.00, its profit on
one carton of orange–banana juice is $.80, and its profit on
one carton of pineapple–orange–banana juice is $.90. To
realize a maximum profit, how many cartons of each blend
should the company produce? What is the largest profit it can
realize? Are there any concentrates left over?
43. I
NVESTMENTS
—A
SSET
A
LLOCATION
A financier plans to invest
up to $2 million in three projects. She estimates that project
A will yield a return of 10% on her investment, project B
will yield a return of 15% on her investment, and project C
87533_04_ch4_p201-256 1/30/08 9:51 AM Page 220
4.1 THE SIMPLEX METHOD: STANDARD MAXIMIZATION PROBLEMS 221
will yield a return of 20% on her investment. Because of the
risks associated with the investments, she decided to put not
more than 20% of her total investment in project C. She also
decided that her investments in projects B and C should not
exceed 60% of her total investment. Finally, she decided that
her investment in project A should be at least 60% of her
investments in projects B and C. How much should the
financier invest in each project if she wishes to maximize the
total returns on her investments? What is the maximum
amount she can expect to make from her investments?
44. Consider the linear programming problem
Maximize P 3x 2y
subject to x y 3
x 2
x 0, y 0
a. Sketch the feasible set for the linear programming
problem.
b. Show that the linear programming problem is un-
bounded.
c. Solve the linear programming problem using the sim-
plex method. How does the method break down?
d. Explain why the result in part (c) implies that no solu-
tion exists for the linear programming problem.
In Exercises 45–48, determine whether the statement is
true or false. If it is true, explain why it is true. If it is
false, give an example to show why it is false.
45. If at least one of the coefficients a
1
, a
2
,..., a
n
of the
objective function P a
1
x
1
a
2
x
2
a
n
x
n
is posi-
tive, then (0, 0,..., 0) cannot be the optimal solution of
the standard (maximization) linear programming problem.
46. Choosing the pivot row by requiring that the ratio associ-
ated with that row be the smallest ensures that the iteration
will not take us from a feasible point to a nonfeasible point.
47. Choosing the pivot column by requiring that it be the col-
umn associated with the most negative entry to the left of
the vertical line in the last row of the simplex tableau
ensures that the iteration will result in the greatest increase
or, at worse, no decrease in the objective function.
48. If, at any stage of an iteration of the simplex method, it is
not possible to compute the ratios (division by zero) or the
ratios are negative, then we can conclude that the standard
linear programming problem has no solution.
4.1 Solutions to Self-Check Exercises
1. Introducing the slack variables u, √, and w, we obtain the
system of linear equations
2x 3y z u 10
x y 2z √ 8
2y 3z w 6
2x 3y 6z P 0
The initial simplex tableau and the successive tableaus
resulting from the use of the simplex procedure follow:
All entries in the last row are nonnegative, and the tableau
is final. We conclude that x 4, y 0, z 2, and P 20.
2. Let x denote the number of model-A grates and y the num-
ber of model-B grates to be made this week. Then the
profit function to be maximized is given by
P 6x 8y
The limitations on the availability of material and labor
may be expressed by the linear inequalities
20x 30y 7200 or 2x 3y 7200
20x 15y 6000 or 4x 3y 1200
Finally, the condition that no more than 150 units of
model-A grates be made this week may be expressed by
the linear inequality
x 150
Thus, we are led to the following linear programming
problem:
Maximize P 6x 8y
subject to 2x 3y 720
4x 3y 1200
x 150
x 0, y 0
xyzu√ wP Constant
2 3 11000 10
1 1 20100 8
0 2 30010 6
2 3 60001 0
xyzu√ wP Constant
2 3 11000 10
1 1 20100 8
0
2
3
100
1
3
02
2 3 60001 0
xyzu√ wPConstant
2
7
3
010
1
3
08
1
1
3
001
2
3
04
0
2
3
100
1
3
02
2100021 12
xyzu√ wPConstant
0301210 0
1
1
3
00 1
2
3
04
0
2
3
10 0
1
3
02
0
1
3
00 2
2
3
120
Ratio
6
3
2
8
2
4
10
1
10
Pivot
씮
row
앖
Pivot column
R
1
R
3
⎯⎯⎯→
R
2
2R
3
R
4
6R
3
Ratio
—
4
1
4
8
2
4
Pivot
씮
row
앖
Pivot column
R
1
2R
2
⎯⎯⎯→
R
4
2R
2
R
3
⎯→
1
3
87533_04_ch4_p201-256 1/30/08 9:51 AM Page 221