REVISED

M07_REND6289_10_IM_C07.QXD 5/7/08 12:05 PM Page 1

Linear Programming Models:

C H A P T E R
7
Graphical and Computer Methods

TEACHING SUGGESTIONS model). Here, the issue is the source of data. When accountants
tell you a profit contribution is $8.50 per unit, is that figure
Teaching Suggestion 7.1: Draw Constraints for a
accurate within 10% or within 10¢? The solution to an LP problem
Graphical LP Solution.
can change dramatically if the input parameters are not exact.
Explain constraints of the three types (S, =, S) carefully the first
time you present an example. Show how to find the X , X inter- Mention that sensitivity analysis also has other names, such as
1 2
right-hand-
side ranging, post-optimality analysis, and parametric programming.
cepts so a straight line can be drawn. Then provide some practice
in determining which way the constraints point. This can be done
by picking a few X1, X2 coordinates at random and indicating ALTERNATIVE EXAMPLES
which direction fulfills the constraints. Alternative Example 7.1: Hal has enough clay to make 24 small
Teaching Suggestion 7.2: Feasible Region Is a Convex Polygon. vases or 6 large vases. He only has enough of a special glaz- ing
Explain Dantzing’s discovery that all feasible regions are convex compound to glaze 16 of the small vases or 8 of the large vases.
(bulge outward) polygons (many-sided figures) and that the opti- Let X1 = the number of small vases and X2 = the number of large
mal solution must lie at one of the corner points. Draw both con- vases. The smaller vases sell for $3 each, while the larger vases
vex and concave figures to show the difference. would bring $9 each.
Teaching Suggestion 7.3: Using the Iso-Profit Line Method. (a) Formulate the problem.
This method can be much more confusing than the corner point ap- (b) Solve graphically.
proach, but it is faster once students feel comfortable drawing the SOLUTION:
profit line. Start your first line at a profit figure you know is lower (a) Formulation
than optimal. Then draw a series of parallel lines, or run a ruler
paral- lel, until the furthest corner point is reached. See Figures 7.6 OBJECTIVE FUNCTION:
and 7.7. Maximize $3X1 + $9X2
Teaching Suggestion 7.4: QA in Action Boxes in the LP Subject to : Clay constraint: 1X1 + 4X2 “
Chapters. There are a wealth of motivating tales of real-world LP 24 Glaze constraint: 1X1 + 2X2 “ 16
applica- tions in Chapters 7–9. The airline industry in particular is
(b) Graphical solution
a major LP user.
Teaching Suggestion 7.5: Feasible Region for
15
the Minimization Problem.
Students often question the open area to the right of the
constraints in a minimization problem such as that in Figure 7.10.
You need to explain that the solution is not unbounded in a
X2 = Number of Large Vases

minimization problem as it is in a maximization problem.

Teaching Suggestion 7.6: Infeasibility. 10
This problem is especially common in large LP formulations since (0, 8)
many people will be providing input constraints to the problem. Glaze Constraint
This is a real-world problem that should be expected.
(0, 6)
Teaching Suggestion 7.7: Alternative Optimal Solutions. B
This issue is an important one that can be explained in a positive
way. Managers appreciate having choices of decisions that can be 5 (8, 4) Clay Constraint
made with no penalty. Students can be made aware that
alternative optimal solutions will arise again in the transportation C
model, as- signment model, integer programming, and the chapter Feasible Region
on net- work models. A (24, 0)
(0, 0)
Teaching Suggestion 7.8: Importance of Sensitivity Analysis. 0 D (16, 0)
Sensitivity analysis should be stressed as one of the most 0 5 10 15 20 25
important LP issues. (Actually, the issue should arise for X1 = Number of Small Vases
discussion with every
88
CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS 89

Point X1 X2 Income applied to minimization problems. Conceptually, isoprofit and

iso- cost are the same.
A 0 0 $0
B 0 6 54
The major differences between minimization and maximiza-
C 8 4 60* tion problems deal with the shape of the feasible region and the
D 16 0 48 di- rection of optimality. In minimization problems, the region
must be bounded on the lower left, and the best isocost line is the
*Optimum income of $60 will occur by making and sell- one closest to the zero origin. The region may be unbounded on
ing 8 small vases and 4 large vases. the top and right and yet be correctly formulated. A maximization
Draw an isoprofit line on the graph from (20, 0) to (0, 6X\c) as the prob- lem must be bounded on the top and to the right. The
$60 isoprofit line. isoprofit line yielding maximum profit is the one farthest from the
zero origin.
Alternative Example 7.2: A fabric firm has received an order
for cloth specified to contain at least 45 pounds of cotton and 25 7-2. The requirements for an LP problem are listed in Section
pounds of silk. The cloth can be woven out on any suitable mix of 7.2. It is also assumed that conditions of certainty exist; that is,
two yarns, A and B. Material A costs $3 per pound, and B costs $2 co- efficients in the objective function and constraints are known
per pound. They contain the following proportions of cotton and with certainty and do not change during the period being studied.
silk (by weight): An- other basic assumption that mathematically sophisticated
students should be made aware of is proportionality in the
Yarn Cotton (%) Silk (%) objective func- tion and constraints. For example, if one product
uses 5 hours of a machine resource, then making 10 of that
A 30 50
B 60 10
product uses 50 hours of machine time.
LP also assumes additivity. This means that the total of all
ac- tivities equals the sum of each individual activity. For
What quantities (pounds) of A and B yarns should be used to mini- example, if the objective function is to maximize P = 6X1 + 4X2,
mize the cost of this order? and if X1 =
Objective function: min. C = 3A + 2B X2 = 1, the profit contributions of 6 and 4 must add up to produce
Constrains: 0.30A + 0.60B “ 45 lb a sum of 10.
(cotton) 7-3. Each LP problem that has a feasible solution does have an
0.50A + 0.10B “ 25 lb (silk) infinite number of solutions. Only one of the points in the feasible
region usually yields the optimal solution, but all of the points
Simultaneous solution of the two constraint equations reveals that yield a feasible solution. If we consider the region to be continu-
A = 39 lb, B = 55 lb. ous and accept noninteger solutions as valid, there will be an infi-
The minimum cost is C = $3A + $2B = 3(39) + (2)(55) = nite number of feasible combinations of X1 and X2.
$227.
7-4. If a maximization problem has many constraints, then it can
300 be very time consuming to use the corner point method to solve it.
Such an approach would involve using simultaneous equations to
solve for each of the feasible region’s intersection points. The iso-
250 profit line is much more effective if the problem has numerous
constraints.
7-5. A problem can have alternative optimal solutions if the
200 isoprofit or isocost line runs parallel to one of the problem’s con-
Pounds of Yarn B

straint lines (refer to Section 7.7 in the chapter).

150 7-6. This question involves the student using a little originality
to develop his or her own LP constraints that fit the three condi-
tions of (1) unboundedness, (2) infeasibility, and (3) redundancy.
100 These conditions are discussed in Section 7.7, but each student’s
min C graphical displays should be different.
7-7. The manager’s statement indeed had merit if the manager
50 understood the deterministic nature of linear programming input
data. LP assumes that data pertaining to demand, supply, materi-
als, costs, and resources are known with certainty and are constant
during the time period being analyzed. If this production manager
50 100 150 200 250 operates in a very unstable environment (for example, prices and
Pounds of Yarn A availability of raw materials change daily, or even hourly), the
model’s results may be too sensitive and volatile to be trusted.
SOLUTIONS TO DISCUSSION QUESTIONS AND PROBLEMS The application of sensitivity analysis might be trusted. The
7-1. Both minimization and maximization LP problems employ applica- tion of sensitivity analysis might be useful to determine
the basic approach of developing a feasible solution region by whether LP would still be a good approximating tool in decision
graphing each of the constraint lines. They can also both be solved making.
by applying the corner point method. The isoprofit line method is 7-8. The objective function is not linear because it contains the
used for maximization problems, whereas the isocost line is product of X1 and X2, making it a second-degree term. The first,
second, fourth, and sixth constraints are okay as is. The third and
90 CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS

fifth constraints are nonlinear because they contain terms to the 7-14.
second degree and one-half degree, respectively.
140
7-9. For a discussion of the role and importance of sensitivity
analysis in linear programming, refer to Section 7.8. It is needed
especially when values of the technological coefficients and con- b
120
tribution rates are estimated—a common situation. When all
model values are deterministic, that is, known with certainty, sen- Drilling Constraint
sitivity analysis from the perspective of evaluating parameter ac- 100
curacy may not be needed. This may be the case in a portfolio se-

Number of Fans, X2
lection model in which we select from among a series of bonds
whose returns and cash-in values are set for long periods. 80 Optimal Solution
7-10. If the profit on X is increased from $12 to $15 (which is (X1 = 40, X2 = 60)
less than the upper bound), the same corner point will remain opti- c
mal. This means that the values for all variables will not change 60
from their original values. However, total profit will increase by
$3 per unit for every unit of X in the original solution. If the profit
is increased to $25 (which is above the upper bound), a new 40
Wiring Constraint
corner point will be optimal. Thus, the values for X and Y may Feasible Region
change, and the total profit will increase by at least $13 (the
amount of the increase) times the number of units of X in the 20
original solution. The increase should normally be even more than
this because the original optimal corner point is no longer optimal. a d
0
Another corner point is optimal and will result in an even greater 0 20 40 60 80 100 120
profit.
7-11. If the right-hand side of the constraint is increased from 80 Number of Air Conditioners, X1
to 81, the maximum total profit will increase by $3, the amount of
the dual price. If the right-hand side is increased by 10 units (to
Let: X1 = number of air conditioners to be produced
90), the maximum possible profit will increase by 10(3) = $30
and will be $600 + $30 = $630. This $3 increase in profit will re- X2 = number of fans to be
sult for each unit we increase the righthand side of the constraint produced Maximize profit = 25X1 +
until we reach 100, the upper bound. The dual price is not relevant 15X2
beyond 100. Similarly, the maximum possible total profit will de- subject to 3X1 + 2X2 “ 240 (wiring)
crease by $3 per unit that the right-hand side is decreased until 2X1 + 1X2 “ 140 (drilling)
this value goes below 75.
X1, X2 “ 0
7-12. The student is to create his or her own data and LP formula- Profit at point a (X1 = 0, X2 = 0) = $0
tion. (a) The meaning of the right-hand-side numbers (resources) Profit at point b (X1 = 0, X2 = 120)
is to be explained. (b) The meaning of the constraint coefficient
= 25(0) + (15)(120) = $1,800
(in terms of how many units of each resource that each product re-
quires) is also to be explained. (c) The problem is to be solved Profit at point c (X1 = 40, X2 = 60)
graphically. (d) A simple sensitivity analysis is to be conducted by = 25(40) + (15)(60) = $1,900
changing the contribution rate (Cj value) of the X1 variable. For Profit at point d (X1 = 70, X2 = 0)
ex- ample, if C1 was $10 as the problem was originally formulated,
the student should resolve with a $15 value and compare = 25(70) + (15)(0) = $1,750
solutions. The optimal solution is to produce 40 air conditioners and 60 fans
during each production period. Profit will be $1,900.
7-13. A change in a technological coefficient changes the feasi-
ble solution region. An increase means that each unit produced re-
quires more of a scarce resource (and may lower the optimal
profit). A decrease means that because of a technological
advance- ment or other reason, less of a resource is needed to
produce 1 unit. Changes in resource availability also change the
feasible re- gion shape and can increase or decrease profit.
CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS 91

7-15.
140
T 80

120 Constraints
(57.14, 57.14)
100
(26.67, 80)
b Isoprofit Line
80
e
X2
c Optimal Solution
60 175.,10
10

40 10 200
R
Feasible Region
20
Optimal corner point R = 175, T = 10,
Audience = 3,000(175) + 7,000(10) = 595,000 people
0 a d 7-17. X1 = number of benches produced
0 20 40 60
80 100 120 X2 = number of tables produced
X1
Maximize profit = $9X1 + $20X2
Maximize profit = 25X1 + subject to 4X1 + 6X2 “
15X2 subject to 3X1 + 2X2 “ 1,200 hours 10X1 + 35X2
240 “ 3,500 pounds
X,X “
0
1 2
2X1 + 1X2 “ Profit at point a (X = 0, X = 100) = $2,000
140
1 2
X1 “ Profit at point b (X = 262.5, X = 25) = $2,862.50
20
X2 “ 80 1 2
X,X“ 0 Profit at point c (X1 = 300, X2 = 0) = $2,700
12
Profit at point a (X1 = 20, X2 = 0)
= 25(20) + (15)(0) = $500 300
Profit at point b (X1 = 20, X2 = 80)
= 25(20) + (15)(80) = $1,700
250
Profit at point c (X1 = 40, X2 = 60)
= 25(40) + (15)(60) = $1,900
Profit at point d (X1 = 70, X2 = 0) 200
= 25(70) + (15)(0) = $1,750
Profit at point e (X1 = 26.67, X2 = 80)
X2 150
= 25(26.67) + (15)(80) =
$1,867
Hence, even though the shape of the feasible region changed from a
Problem 7-14, the optimal solution remains the same. 100
Optimal Solution,
7-16. Let R = number of radio ads; T = number of TV ads. $2862.50 Profit
Maximize exposure = 3,000R + 7,000T
50
Subject to: 200R + 500T “ 40,000
Feasible Region b
(budget)
R “ 10 0 c
T “ 10 0 50 100 150 200 250 300 350 400
R“ T X1
R, T “
0
92 CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS

7-18. X1 = number of Alpha 4 computers

60 X2 = number of Beta 5 computers
X1 + X2 = 60 Maximize profit = $1,200X1 + $1,800X2
subject to 20X1 + 25X2 = 800 hours
50
(total hours = 5 workers
Feasible Region × 160 hours each)
X1 “ 10
40
X2 “ 15
Corner points: a(X1 = 10, X2 = 24), profit = $55,200
X2 30 b
X2 = 20 b(X1 = 211f,2 X= 15), profit = $52,500
Point a is optimal.
20 a 7-20. Let P = dollars invested in petrochemical; U = dollars
Optimal Solution
invested in utility
X1 = 30 Maximize return = 0.12P +
10 0.06U Subject to:
P + U = 50,000 total investment is $50,000
0 9P + 4U “ 6(50,000) average risk must be less 6 [or
0 10 20 30 40 50 60 total less than 6(50,000)]
X1 P, U “ 0
U
X1 = number of undergraduate courses 75,000
X2 = number of graduate courses Constraints
Minimize cost = $2,500X1 +
$3,000X2 subject to X1 S 30 50,000
X2 “ 20
Isoprofit line
X1 + X2 “ 60
20000,30000
Total cost at point a (X1 = 40, X2 = 20)
= 2,500(40) + (3,000)
(20)
33,333.33 50,000
= $160,000 P
Total cost at point b (X1 = 30, X2 = 30) Corner points
= 2,500(30) + (3,000)(30) Return =
= $165,000 P U 0.12P + 0.06U
Point a is optimal. 0 50,000 3,000
20,000 30,000 4,200
7-19.
40 The maximum return is $4,200.
The total risk is 9(20,000) + 4(30,000) =
300,000, so average risk = 300,000/(50,000) = 6
7-21. Let P = dollars invested in petrochemical; U = dollars
30 invested in utility
Minimize risk = 9P +
Optimal Solution 4U Subject to:
P + U = 50,000 total investment is $50,000
a Feasible Region is Heavily Shaded Line
X2 20
U
66,666.67
Constraints
b 50,000
10

Isoprofit line

0
0 10
20 30 40
50000,0
X1
33,333.34 50,000
P
CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS 93

0.12P + 0.06U “ 0.08(50,000) return must be at Note that this problem has one constraint with a negative sign.
least 8% This may cause the beginning student some confusion in plotting
P, U “ 0 the line.
Corner points 7-23. Point a lies at intersection of constraints (see figure
RISK = below): 3X + 2Y = 120
P U 9P + 4U X + 3Y = 90
50,000 0 450,000 Multiply the second equation by —3 and add it to the first (the
16,666.67 33,333.33 283,333.3 method of simultaneous equations):
The minimum risk is 283,333.33 on $50,000 so the average risk is 3X + 2Y = 120
283,333.33/50,000 = 5.67. The return would be —3X — 9Y = —270
0.12(16,666.67) + 0.06(33,333.33) = $4,000 (or 8% of — 7Y = —150  Y = 21.43 and X = 25.71
$50,000) Cost = $1X + $2Y = $1(25.71) + ($2)(21.43)
7-22. = $68.57
50 7-24. X1 = $ invested in Louisiana Gas and Power
X2 = $ invested in Trimex Insulation
5X + 3Y S 150
Co. Minimize total investment = X1 +
40 X2 subject to $0.36X1 + $0.24X2 “
Isoprofit Line Indicates that Optimal Solution Lies at Point a $720
$1.67X1 + $1.50X2 “ $5,000
30
Y
(X = 18 34 , Y = 18 34 , Profit = $150 ) 0.04X1 + 0.08X2 “ $200
20 Investment at a is $3,333.
a X – 2Y S 10 Investment at b is $3,179. k optimal
solution Investment at c is $5,000.
10 Feasible Region
3X + 5Y S 150 Short-term growth is $926.09.
Intermediate-term growth is $5,000.
Dividends are $200.
0
0 10 20 30 40 50 See graph.
X

Figure for Problem 7-23.

80
8X + 2Y  160 Y  70

60

Feasible Region

Y 40

20 a

X + 3Y 90
3X + 2Y  120

0
0 20 40 60 80 100
X Isoprofit Line Indicates
That Optimal Solution
Lies At Point a
94 CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS

Figure for Problem 7-24.

4,000

a (X1 = 0, X2 = 3,333)

3,000 Feasible Region

X2 2,000 b (X1 = 1358.7 X2 = 1820.6)

1,000
c (X1 = 5,000, X2 = 0)

0
0 1,000 2,000 3,000 4,000 5,000
X1

7-25. Let B = pounds of beef in each pound of dog food

G = pounds of grain in each pound of dog 1X1 + 2X2 “ 150 (acres)
food Minimize cost = 0.90B + 0.60G X1 “ 40 (barrels)
Subject to: X1, X2 “ 0
B+G=1 the total weight should be 1 a. Corner point a = (X1 = 0, X2 = 0), profit = 0 Corner
pound point b = (X1 = 0, X2 = 75), profit = $2,250 Corner
10B + 6G “ 9 at least 9 units of Vitamin
point c = (X1 = 25, X2 = 62Z\x), profit =
1 12B + 9G “ 10 at least 10 units of Vitamin $2,375 optimal profit
2 B, G “ 0
Corner point d = (X1 = 40,kX2 = 25), profit = $1,550
G Corner point e = (X1 = 40, X2 = 0), profit = $800
1.5 Constraints
b. Produce 25 barrels of pruned olives and 62Z\x barrels
of regular olives.
1.1111 c. Devote 25 acres to pruning process and 125 acres to
1 regular process.
Isoprofit line

125

0.8330.9
B
0.75, 0.25 100
b

The feasible corner points are (0.75, 0.25) and (1,0). The mini- 75
c
Optimal Solution
mum cost solution X2
B = 0.75 pounds of beef, G = 0.25 pounds of grain, cost =
50
$0.825,
Vitamin 1 content = 10(0.75) + 6(0.25) = 9 Feasible Regiond
Vitamin 2 content = 12(0.75) + 9(0.25) = 11.25
25
7-26. Let X1 = number of barrels of pruned olives
X2 = number of barrels of regular olives a e
0
Maximize profit = $20X1 + $30X2 0
25 50 75 100 125 150
subject to 5X1 + 2X2 “ 250 (labor hours)
X1
CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS 95

7-27. Formulation 4:
Formulation 1: 8

6
Infeasible Solution Region
X2 4

X2 4 Feasible Region
2
2 1
0
0 1 2 3 4 6 8 10 12
0
X1
0 2 4 6 8 10 12
X1
Formulation 4 appears to be proper as is. Note that the constraint
Formulation 2: 4X1 + 6X2 ÷ 48 is redundant.
7-28. Using the isoprofit line or corner point method, we see that
2 point b (where X = 37.5 and Y = 75) is optimal if the profit
= $3X + $2Y. If the profit changes to $4.50 per unit of X, the opti-
mal solution shifts to point c. If the objective function becomes P
= $3X + $3Y, the corner point b remains optimal.

X2 1
150
Profit Line for 3X1 + 3X2

Line For X1 + 2X2

Feasible Region
a Profit Line for 4.50X1 + 2X2
0
0 1 2 3 100
X1
X b
While formulation 2 is correct, it is a special case. X1 2
+ 2X2 = 2
line—this is also the same slope as the isoprofit line X1 + 2X2 and
Profit Line for 3X1 + 2X2
hence there will be more than one optimal solution. As a matter of
50
fact, every point along the heavy line will provide an “alternate
optimum.”
Formulation 3:
c
5 0
0 50 100 150
Unbounded Region
X1
4

X2
2

0
0 1 2 3 4 5 6
X1
96 CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS

7-29. The optimal solution of $26 profit lies at the point X = 2, 7-30.
Y = 3.
12
8

10

6
8 6X + 4Y = 36

Y 6
Y 4
(X = 5, Y = 11/2 ; Profit = $29 )
Profit = 4X + 6Y = $26 4

2 2 1X + 2Y = 8

0
0 2 4 6 8 10 12
0
0 2 4 6 8 X
X
Using the corner point method, we determine that the optimal so-
lution mix under the new constraint yields a $29 profit, or an in-
If the first constraint is altered to 1X + 3Y S 8, the feasible region
crease of $3 over the $26 profit calculated. Thus, the firm should
and optimal solution shift considerably, as shown in the next
column. not add the hours because the cost is more than $3.
7-31. a. The corner points and profits are
8
X = 0, Y = 0, profit = 0
X = 60, Y = 0, profit = 300
X = 30, Y = 60, profit = 510 k Optimal solution
6 X = 0, Y = 80, profit = 480
b. If profit = 8X + 6Y, the optimal solution is at the
Profit = 4X + 6Y = $21.71 same corner point but profit increases.
X = 0, Y = 0, profit = 0
Y 4
X = 60, Y = 0, profit = 480
Optimal solution at X = 30, Y = 60, profit = 600 k Optimal solution
X = 26/7, Y = 1 5/7
X = 0, Y = 80, profit = 480
2 1X + 3Y = 8

Y
120

0
0 2 4 6 8
X
80

60

30 60 120
X
CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS 97

c. If profit = 3X + 6Y, a new corner point is optimal. a. The feasible corner points and their profits are:
X = 0, Y = 0, profit = 0 Feasible corner points Profit = 8X1 + 5X2

X = 60, Y = 0, profit = 180 (0,0) 0

(6,0) 48
X = 30, Y = 60, profit = 450 (6,4) 68
X = 0, Y = 80, profit = 480 k Optimal solution (0,10) 50
7-32. The corner points change and the new optimal solution is The optimal solution is X1 = 6, X2 = 4, profit = $68.
X = 40, Y = 40, and profit = 440. The corner points are
b. The feasible corner points and their profits are:
X = 0, Y = 0, profit = 0
Feasible corner points Profit = 8X1 + 5X2
X = 60, Y = 0, profit = 300
(0,0) 0
X = 40, Y = 40, profit = 440 k Optimal (6,0) 48
solution X = 0, Y = 60, profit = 360 (6,5) 73
(0,11) 55
7-33. a. It could increase by 7 (for an upper limit of 12) or de-
crease by 1 (for a lower limit of 4). The new optimal solution is X1 = 6, X2 = 5, profit = $73. Profit
b. Profit would increase by the dual value of 0.75. increased $5, so this is the dual price for constraint 1.
c. Profit would increase by 10 times the dual price or c. The feasible corner points and their profits are:
10(0.75) = $7.50. Feasible corner points Profit = 8X1 + 5X2
7-34. a. 25 units of product 1 and 0 units of product 2. (0,0) 0
b. All of resource 3 is being used (there is no slack for (6,0) 48
constraint 3). A total of 25 units of resource 1 is being (0,6) 30
used since there were 45 units available and there are 20 As a result of this change, the feasible region got smaller. Profit
units of slack. A total of 75 units of product 2 being used decreased by $20. The right-hand side decreased by 4 units, and
since there were 87 units available and there are 12 units the profit decreased by 4 x dual price.
of slack.
d. The feasible corner points and their profits are:
c. The dual price for constraint 1 is 0, for constraint 2 is
0, and for constraint 3 is 25. Feasible corner points Profit = 8X1 + 5X2
d. You should try to obtain resource 3 because the dual (0,0) 0
price is 25. This means profit will increase by 25 for (5,0) 40
each unit of resource 3 that we obtain. Therefore, we (0,5) 25
should pay up to $25 for this.
As a result of this change, the feasible region got smaller. Profit
e. If management decided to produce one more unit of
decreased by $28. Although there was a 5-unit change in the right-
product 2 (currently 0 units are being produced), the total
hand side of constraint 1, the dual price found in part b is not valid
profit would decrease by 5 (the amount of the reduced
when the right-hand side of this constraint goes below 6 (which is
cost).
a 4-unit decrease).
7-35.
e. The computer output indicates that the dual price for constraint
X2 1 is $5, but this is valid up to a lower bound of 6. Once the right-
10 hand side goes lower than this, the dual price is no longer
Constraints relevant.
g. When the right-hand side goes beyond the limits, a new corner
point becomes optimal so the dual price is no longer relevant.

6,4
Isoprofit line

6 10
X1
98 CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS

7-36. Let: X1 = number of coconuts carried 7-39. a. Let: X1 = number of pounds of stock X purchased per
X2 = number of skins carried cow each month
Maximize profit = 60X1 + 300X2 (in rupees) X2 = number of pounds of stock Y purchased per
subject to 5X1 + 15X2 S 300 pounds cow each month
1
8X1+ 1X S 15 cubic feet X3 = number of pounds of stock Z purchased per
X1, X2 S 0 cow each month
At point a: (X1 = 0, X2 = 15), P = 4,500 rupees At Four pounds of ingredient Z per cow can be transformed to:
point b: (X1 = 24, X2 = 12), P = 1,440 + 3,600 4 pounds × (16 oz/lb) = 64 oz per cow
= 5,040 rupees At 5 pounds = 80 oz
point c: (X1 = 60, X2 = 0), P = 3,600 rupees 1 pound = 16 oz
The three princes should carry 24 coconuts and 12 lions’ skins. 8 pounds = 128 oz
This will produce a wealth of 5,040 rupees. 3X1 + 2X2 + 4X3 “ 64 (ingredient A
requirement) 2X1 + 3X2 + 1X3 “ 80 (ingredient
20 B requirement) 1X1 + 0X2 + 2X3 “ 16
(ingredient C requirement) 6X1 + 8X2 + 4X3 “
128 (ingredient D requirement)
a X3 S 5 (stock Z limitation)
15 Minimize cost = $2X1 + $4X2 + $2.50X3
Number of Lion Skins, X2

Optimal Solution b. Cost = $80

X1 = 40 lbs. of X
b
X2 = 0 lbs. of Y
10 X3 = 0 lbs. of Z
7-40. Let: X1 = number units of XJ201 produced X2
= number units of XM897 produced X3
Feasible Region = number units of TR29 produced X4 =
5 number units of BR788 produced
Maximize profit = 9X1 + 12X2 + 15X3 + 11X4
subject to
0.5X1 + 1.5X2 + 1.5X3 + 1X4 S 15,000 (hours of wiring
c
0 time available)
0 30 60 90 120
Number of Coconuts, X1
0.3X1 + 1X2 + 2X3 + 3X4 S 17,000 (hours of drilling
time available)
7-37. a. $120,000 in money market fund; $80,000 in stock fund;
total risk = 1,560,000 0.2X1 + 4X2 + 1X3 + 2X4 S 26,000 (hours of assembly
time available)
b. Total return = $14,000. Rate of return =
14,000/200,000 = 0.07 0.5X1 + 1X2 + 0.5X3 + 0.5X4 S 12,000 (hours of
inspection time)
c. The investments would not change since 14 is less than
X1 “ 150 (units of
the upper bound for this coefficient. The total risk would
increase. XJ201) X2 “ 100 (units
d. The total risk would worsen by 2 (the dual value) per of XM897) X3 “ 300
additional dollar. (units of TR29) X4 “
e. No. The amount invested in the money market fund is 400 (units of BR788)
greater than $50,000 for the original solution.
7-41. Let
7-38. a. $40,000 in money market fund; $160,000 in stock fund; SN1 = number of standard racquets produced in current month on
total return = 18,000 normal time
b. Total risk = 12(160,000) + 5(40,000) = 2,120,000. SO1 = number of standard racquets produced in current month on
Average risk = 2,120,000/200,000 = 10.6. overtime
c. No. The change is above the lower bound. SN2 = number of standard racquets produced in next month on
normal time
d. Dual value = 0.10 = 10% SO2 = number of standard racquets produced in next month on
e. Total return would change by (dual price)(change in overtime
RHS) = (—0.05)(10,000) = —500. PN1 = number of professional racquets produced in current month
on normal time
CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS 99

PO1 = number of professional racquets produced in current b.

month on overtime X2
PN2 = number of professional racquets produced in next month
on normal time 15,400
PO2 = number of professional racquets produced in next month
on overtime
P = $534,339
IS = number of standard racquets left in inventory at end of cur-
rent month
8,000
IP = number of professional racquets left in inventory at end of b
current month Optimal
Minimize cost = 40SN1 + 50SO1 + 44SN2 + 55SO2 + P = $629,000
60PN1
+70PO1 + 66PN2 +77 PO2 + 2IS + 2IP c
Subject to: 27,750 X1
IS = SN1 + SO1 –180 Standard racquets remaining is
c. The optimal solution suggests making all MCA
number
regular modems. Students should discuss the implications
produced less demand
of shipping no MCA intelligent modems.
IP = PN1 + PO1 – 90 Professional racquets remaining is
7-43. Minimize cost = 12X1 + 9X2 + 11X3 + 4X4
number produced less demand
SN2 + SO2 + IS “ 200 Demand for standard racquets next
month
PN2 + PO2 +IP “ 120 Demand for professional racquets subject to X1 + X2 + X3 + X4 = 50
next X4 S 7.5
month X1 + X2 S 22.5
SN1 + PN1 “ 230 Capacity in current month on X2 + X3 S 15.0
normal
time Solution
SO1 + PO1 “ 80 Capacity in current month on : X1 = 7.5 pounds of C-30
overtime SN2 + PN2 “ 230 Capacity next month on X2 = 15 pounds of C-92
normal time SO2 + PO2 “ 80 Capacity next month on X3 = 0 pounds of D-21
overtime
All variables “ 0
7-42. a. Let: X1 = number of MCA regular modems made and
sold in November
X2 = number of MCA intelligent modems made X4 = 27.5 pounds of E-11
and sold in November Cost = $3.35.
Data needed for variable costs and contribution margin (refer to 7-44. Let A1 = gallons of crude A used in Regular
the table on the bottom of this page):
A2 = gallons of crude A used in Premium
Hours needed to produce each modem:
A3 = gallons of crude A used in Super

MCA regular 5,000 hours B1 = gallons of crude B used in Regular

= 9,000 modems =0.555 hour/modem
B2 = gallons of crude B used in Premium
MCA intelligent 10,400 hours
= 10,400 modems =1.0 hour/modem B3 = gallons of crude B used in Super
Maximize profit = $22.67X1 + $29.01X2 Minimize cost = 0.42A1 + 0.42A2 + 0.42A3 +
subject to 0.555X1 + 1.0X2 S 15,400 (direct labor hours) 0.47B1 +
0.47B2 + 0.47B3
Subject to
X2 S 8,000 (intelligent modems) 0.40A1 + 0.52B1 S 0.41(A1 + B1)

Table for Problem 7-42(a)

MCA REGULAR MCA INTELLIGENT
MODEM MODEM
Total Per Unit Total Per
Unit
Net sales $424,000 $47.11 $613,000 $58.94
Variable costsa
Direct labor 60,000 6.67 76,800 7.38
Indirect labor 9,000 1.00 11,520 1.11
Materials 90,000 10.00 128,000 12.31
General expenses 30,000 3.33 35,000 3.37
Sales commissions 31,000 3.44 60,000 5.76
Total variable costs $220,000 $24.44 $311,320 $29.93
Contribution margin $204,000 $22.67 $301,680 $29.01
a
Depreciation, fixed general expense, and advertising are excluded from the calculations.
100 CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS

0.40A2 + 0.52B2 S 0.44(A2 + B2)

subject to X1 + X2 “ 60 (pounds per bag)
0.40A3 + 0.52B3 S 0.48(A3 +
X1 S 30 (pounds compost per bag)
B3) A1 + B1 S 20,000
X2 “ 40 (pounds sewage per bag)
A2 + B2 S
Corner point a:
15,000 A3 + B3 (X1 = 30, X2 = 40)  cost = 5(30) + (4)(40) = $3.10
S 10,000 Corner point b:
A1, A2, A3, B1, B2, B3 S 0 (X1 = 30, X2 = 30)  cost = 5(30) + (4)(30) = $2.70
The solution is Corner point c:
A1 = 18,333.33 gallons of crude A used in Regular; A2 (X1 = 60, X2 = 0)  cost = 5(60) + (4)(0) = $3.00
= 10,000 gallons of crude A used in Premium; A 3 =
3,333.33 gallons of crude A used in Super; B1 = 60
1.666.67 gallons of crude B used in Regular, B2 =
5,000 gallons of crude B used in Premium ; B3 =
6,666.67 gallons of crude B used in Super; total cost =
$19,566.67.
a
40
SOLUTIONS TO INTERNET HOMEWORK PROBLEMS
7-45.
X2 b Feasible Region
300 Optimal Solution

250
20

200
a

c
X2 150
0
b 0 20 40 60
X1
100

7-47.

50 Feasible Region 250,000

X1 + X2 = 100,000

0 200,000
0 50 100 150 200c 250 300 350 X1 = 125,000
X1
X1 = number of model A tubs
150,000
produced X2 = number of model B X2 = 100,000
X2
tubs produced Maximize profit = a
90X1 + 70X2 100,000 Feasible Region
subject to 125X1 + 100X2 “ 25,000 is this Line
(steel)
20X1 + 30X2 “ 6,000 (zinc)
X1, X2 “ 0
50,000
Profit at point a (X1 = 0, X2 = 200) = $14,000
Profit at point b (X1 = 85.71, X2 = 142.86) = $17,714.10
Profit at point c (X1 = 200, X2 = 0) = $18,000 0 b
a

optimal solution 0 50,000 100,000 150,000 200,000 250,000

X1
7-46. Let: X1 = number of pounds of compost in each bag
X2 = number of pounds of sewage waste in each bag
Minimize cost = 5X1 + 4X2 (in cents)
CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS 101

X1 = $ invested in Treasury notes

X2 = $ invested in bonds
7-49. Maximize Z = [220 — (0.45)(220) — 44 — 20]X1
Maximize ROI = 0.08X1 +
+ [175 — (0.40)(175) — 30 — 20]X2
0.09X2 = 57X1 + 55X2
Constraints:
X1 S $125,000 X1+ X S2 390 production limit
X “ $100,000
2
X+X = 2.5X1 + 2.4X2 S 960 labor hours
$250,000
1 2
Corner points:
X1, X2 “ 0
X1 = 384, X2 = 0, profit = $21,888
Point a (X1 = 150,000, X2 = 100,000), ROI = $21,000

a
X1 = 0, X2 = 390, profit = $21,450
optimal solution
X1 = 240, X2 = 150, profit = $21,930
Point b (X1 = 250,000, X2 = 0), ROI = $20,000
Students should point out that those three options are so close in
7-48. profit that production desires and sensitivity of the RHS and cost
coefficient are important issues. This is a good lead-in to the dis-
3,000X1 + 1,250X2  100,000
80
cussion of sensitivity analysis. As a matter of reference, the right-
X1  5
X1  25 hand side ranging for the first constraint is a production limit
b
Optimal Exposure Rating from 384 to 400 units. For the second constraint, the hours may
range only from 936 to 975 without affecting the solution.
60 The objective function coefficients, similarly, are very sensi-
tive. The $57 for X1 may increase by 29 cents or decrease by $2.
The $55 for X2 may increase by $2 or decrease by 28 cents.
X2 40
SOLUTION TO MEXICANA WIRE WORKS CASE
1. Maximize P = 34 W75C + 30 W33C + 60 W5X + 25 W7X
20 Feasible Region X2  10 subject to:
c
1 W75C S 1,400
a d
1 W33C S 250
0 1 W5X S 1,510
0
5 10 15 20 25 30 35 1 W7X S 1,116
X1 1 W75C + 2 W33C + 0 W5X + 1 W7X S 4,000
Let: X1 = number of TV spots 1 W75C + 1 W33C + 4 W5X + 1 W7X S 4,200
X2 = number of newspaper ads 1 W75C + 3 W33C + 0 W5X + 0 W7X S 2,000
Maximize exposures = 35,000X1 + 20,000X2 1 W75C + 0 W33C + 3 W5X + 2 W7X S 2,300
subject to 3000X1 + 1,250X2 “ $100,000 1 W75C S 150
X1 S5 1 W7X S 600
X1 S 25 Solution: Produce:
X2 “ 10 1,100 units of W75C—backorder 300 units
Point a (X1 = 5, X2 = 10), exposure = 250 units of W33C—backorder 0 units
375,000 Point b (X1 = 5, X2 = 68), 0 units of W5X—backorder 1,510 units
exposure = 175,000 600 units of W7X—backorder 516 units
+ Maximized profit will be $59,900. By addressing quality
1,360,000 problems listed earlier, we could increase our capacity by up to
= 1,535,000 3% reducing our backorder level.
(optimal) 2. Bringing in temporary workers in the Drawing Department
Point c (X1 = 25, X2 = 20), exposure = would not help. Drawing is not a binding constraint. However, if
875,000
+ 400,000
= 1,275,000
Point d (X1 these former employees could do rework, we could reduce our re-
= 25, = 10), exposure = 875,000
work inventory and fill some of our backorders thereby increasing
X2 + 200,000 profits. We have about a third of a month’s output in rework inven-
= 1,075,000 tory. Expediting the rework process would also free up valuable
cash.
102 CHAPTER 7 LINEAR PROGRAMMING MODELS : GRAPHICAL AND COMPUTER METHODS

3. The plant layout is not optimum. When we install the new X3 S 490 X7 S 1,280
equip- ment, an opportunity for improving the layout could arise.
X4 S 160 X8 S 840
Exchang- ing the locations for packaging and extrusion would
create a better flow of our main product. Also, as we improve our Current natural gas usage = 85,680 cu. ft. × 103/day
20 percent curtailment = 68,554 cu. ft. × 103/day
quality and re- duce our rework inventory, we could capture some of
Hence, the ninth constraint is:
the space now used for rework storage and processing and put it to
8X1 + 10X2 + 12X3 + 12X4 + 7X5 + 18X6 + 20X7 + 14X8
productive use.
Our machine utilization of 63% is quite low. Most manufac- S 68,544
turers strive for at least an 85% machine utilization. If we could The following is the production schedule (tons/day);
determine the cause(s) of this poor utilization, we might find a key X1 = 1,200 X5 = 560
to a dramatic increase in capacity. X2 = 540 X6 = 1,200
X3 = 490 X7 = 423.2
INTERNET CASE STUDY: X4 = 160 X8 = 840
AGRI-CHEM CORPORATION Objective function value = $487,192
This case demonstrates an interesting use of linear programming Because of the natural gas curtailment, the caustic soda pro-
in a production setting. duction is reduced from 1280 tons/day to 425 tons/day.
Let X1 = ammonia For a 40 percent natural gas curtailment, the ninth constraint is:
X2 = ammonium phosphate 8X1 + 10X2 + 12X3 + 12X4 + 7X5 + 18X6 + 20X7 + 14X8
X3 = ammonium nitrate S 51,408
X4 = urea The optimal solution results in the following production
X5 = hydrofluoric acid schedule:
X6 = chlorine X1 = 1200 X5 = 560
X7 = caustic soda
X2 = 540 X6 = 718,2
X8 = vinyl chloride monomer Objective
X3 = 490 X7 = 0
function:
X4 = 160 X8 = 840
Maximize Profit = 80X1 + 120X2 + 140X3 + 140X4 + 90X5
+ 70X6 + 60X7 + 90X8 Objective function value: $428,075.6
Subject to the following constraints: The caustic soda production is eliminated completely and the
chlorine production is reduced from 1,200 to 720 tons/day.
X1 S 1,200 X5 S 560
X2 S 540 X6 S 1,200