CHAPTER 8
Linear Programming Applications
TEACHING SUGGESTIONS
Teaching Suggestion 8.1: Importance of Formulating Large LP Problems.
Since computers are used to solve virtually all business LP problems, the most important thing a
Teaching Suggestion 8.2: Note on Production Scheduling Problems.
The Greenberg Motor example in this chapter is largest large problem in terms of the number of
Teaching Suggestion 8.3: Labor Planning Problem—Hong Kong Bank of Commerce.
This example is a good practice tool and lead-in for the Chase Manhattan Bank case at the end of
the chapter. Without this example, the case would probably overpower most students.
Teaching Suggestion 8.4: Ingredient Blending Applications.
Three points can be made about the two blending examples in this chapter. First, both the diet
and fuel blending problems presented here are tiny compared to huge real-world blending
ALTERNATIVE EXAMPLES
Alternative Example 8.1: Natural Furniture Company manufactures three outdoor products,
chairs, benches, and tables. Each product must pass through the following departments before it
is shipped: sawing, sanding, assembly, and painting. The time requirements (in hours) are
summarized in the tables below.
The production time available in each department each week and the minimum weekly
production requirement to fulfill contracts are as follows:
Minimum
Capacity
Production
Department
(In Hours)
Product
Level
Sawing
450
Chairs
100
400
Benches
625
550
Hours Required
Unit
Product
Sanding
Assembly
Painting
Profit
Chairs
1.0
2.0
1.5
$15
Benches
1.5
2.0
2.0
$10
2.0
2.5
2.0
$20
Let
X1 = Number of chairs produced
The objective function is
Maximize profit = 15X1 + 10X2 + 20X3
Constraints
1.5X1 + 1.5X2 + 2.0X3 450 hours of sawing available
What mix of products would yield maximum profit?
Solving with computer software we get: X1= 100 chairs; X2 = 50 benches; X3 = 112.5 tables;
profit = 4250.
Alternative Example 8.2: A phosphate manufacturer produces three grades of phosphate, A, B,
and C, which yield profit of $40, $50, and $60 per kilogram, respectively. The products require
Grade
Grade
Grade
Available
A
B
C
Resources
Labor hours
4
4
5
80 hr
Raw material #1
Raw material #2
Formulate as an LP problem to maximize profit.
Objective function
Maximize profit = 40(800)A + 50(700)B + 60(800)C
Constraints
Labor: 4A + 4B +5C 80
SOLUTIONS TO PROBLEMS
8-1. Since the decision centers about the production of the two different cabinet models, we let
X1 = number of French Provincial cabinets produced each day
X2 = number of Danish Modern cabinets produced each day
Objective: maximize revenue = $28X1 + $25X2
subject to
Problem 8-1 solved by computer:
Produce 60 French Provincial cabinets (X1) per day
8-2. Let X1 = dollars invested in Los Angeles municipal bonds
X2 = dollars invested in Thompson Electronics
X3 = dollars invested in United Aerospace
X4 = dollars invested in Palmer Drugs
or
.8X1 – .2X2 – .2X3 – .2X4 – .2X5 0
X2 + X3 + X4 .4 (X1 + X2 + X3 + X4 + X5) (combination of electronics, aerospace, and
drugs)
or
–0.4X1 + 0.6X2 + 0.6X3 + 0.6X4 – 0.4X5 0
(X5 0.5X1) rewritten as
8-3. Minimize staff size = X1 + X2 + X3 + X4 + X5 + X6
where
Xi = number of workers reporting for start of work at period i (with i = 1, 2, 3, 4, 5, or 6)
X1 + X2 12
The computer solution is to hire 30 workers:
16 begin at 7 A.M.
9 begin at 3 P.M.
2 begin at 7 P.M.
8-4. Let X1 = number of pounds of oat product per horse each day
Minimize cost = 0.09X1 + 0.14X2 + 0.17X3
subject to
2X1 + 3X2 + 1X3 6 (ingredient A)
1
2
X1 + 1X2 +
1
2
X3 2 (ingredient B)
1
2
1
2
1
2
1
2
Solution: X1 = 1
1
3
X2 = 0
1
3
8-5.
Let E1, E2, and E3 represent the ending inventory for the three months respectively. Let RT1,
RT2, and RT3 represent the reguar production for the three months and OT1, OT2, and OT3 rep-
resent the overtime production quantities during the three months respectively. Then the formu-
lation is:
subject to
RT1 < 200 June regular production
RT2 < 200 July regular production
RT3 < 200 August regular production
8-6. Let
T = number of TV ads
R = number of radio ads
B = number of billboard ads
  10
R10
 10
 10
8-7. Let: X1 = number of newspaper ads placed
X2 = number of TV spots purchased
Note that the problem is not limited to unduplicated exposure (e.g., one person seeing the Sunday
newspaper three weeks in a row counts for three exposures).
Problem 8-7 solved by computer:
Buy 20 Sunday newspaper ads (X1)
8-8. Let Xij = number of new leases in month i for j-months, i = 1, . . . , 6; j = 3, 4, 5
Minimize cost = 1260X13 + 1260X23 + 1260X33 + 1260X43 + 840X53 + 420X63 + 1600X14 +
1600X24 + 1600X34 + 1200X44 + 800X54 + 400X64+ 1850X15 + 1850X25 +
1480X35 + 1110X45 + 740X55 + 370X65
subject to: X13 + X14 + X15 420 – 390
X13 + X14 + X15 + X23 + X24 + X25 400 – 270
Solving this on the computer results in the following solution:
X15 = 30 5-month leases in March
X25 = 100 5-month leases in April
8-9. The linear program has the same constraints as in problem 8-8. The objective function
changes and is now:
Minimize cost = 1260(X13 + X23 + X33 + X43 + X53 + X63) + 1600(X14 + X24 + X34 + X44 + X54 +
X64) + 1850(X15 + X25 + X35 + X45 + X55 + X65)
Solving this on the computer results in the following solution:
X15 = 30 5-month leases in March
X25 = 100 5-month leases in April
8-10. Let Xij = number of students bused from sector i to school j
Objective: minimize total travel miles =
5XAB + 8XAC + 6XAE
+ 0XBB + 4XBC + 12XBE
subject to
XAB + XAC + XAE = 700 (number of students in sector A)
XBB + XBC + XBE = 500 (number of students in sector B)
XCB + XCC + XCE = 100 (number of students in sector C)
XDB + XDC + XDE = 800 (number of students in sector D)
All variables 0
Solution: XAB = 400
XAE = 300
XBB = 500
8-11. Maximize number of rolls of Supertrex sold = 20X1 + 6.8X2 + 12X3 – 65,000X4
where X1 = dollars spent on advertising
subject to
X1 + X2 + X3 $17,000 (budgeted)
X1 $3,000 (advertising constraint)
X2 0.05X3 (or X2 – 0.05X3 0) (ratio of displays to inventory)
The store will sell 327,000 rolls of Supertrex.
8-12. Minimize total cost = $0.60X1 + 2.35X2 + 1.15X3 + 2.25X4 + 0.58X5 + 1.17X6 + 0.33X7
subject to
295X1 + 1,216X2 + 394X3 +358X4 + 128X5+ 118X6 + 279X7 1,500
295X1 + 1,216X2 + 394X3 +358X4 + 128X5+ 118X6 + 279X7 900
Problem 8-12 solved by computer:
The meal plan for the evening is
No milk (X1 = 0)
0.499 pound of ground meat (X2)
0.173 pound of chicken (X3)
Each meal has a cost of $1.75.
The meal is fairly well-balanced (two meats, a green vegetable, and a potato). The weight of
each item is realistic. This problem is very sensitive to changing food prices.
Sensitivity analysis when prices change:
Milk increases 10 cents/lb: no change in price or diet
If meat and fish are omitted from the problem, the solution is
chicken = 0.774 lb
milk = 1.891 lb
8-13. a. Let X1 = no. of units of internal modems produced per week
X2 = no. of units of external modems produced per week
Objective function analysis: First find the time used on each test device:
hours on test device 1
1 2 3 4 5 6
7 3 12 6 18 17
60
X X X X X X+ + + + +
=
Thus, the objective function is
maximize profit = (revenue) – (material cost) – )test cost)
= (200X1 + 120X2 + 180X3 + 130X4 + 430X5 + 260X6 – 35X1 – 25X2 – 40X3 – 45X4 – 170X5
– 60X6)
1 2 3 4 5 6
7 3 12 6 18 17
15 60
X X X X X X+ + + + +
−
maximize profit = $161.35X1 + 92.95X2 + 135.50X3 + 82.50X4 + 249.80X5 + 191.75X6
subject to
7X1 + 3X2 + 12X3 + 6X4 + 18X5 + 17X6 < 120(60) Minutes on test device 1
All variables 0
b. The solution is
X1 = 496.55 internal modems
8-14. a. Let Xi = no. of trained technicians available at start of month i
Yi = no. of trainees beginning in month i
subject to
130X1 – 90Y1 40,000 (Aug. need, hours)
130X2 – 90Y2 45,000 (Sept. need)
130X3 – 90Y3 35,000 (Oct. need)