Linear Programming:

Modeling Examples

Chapter 4

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-1

Chapter Topics

A Product Mix Example

A Diet Example
 An Investment Example
A Marketing Example

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-2

A Product Mix Example
Problem Definition (1 of 8)
T-shirt/Sweatshirt manufacturing company.
■ Must complete production within 72 hours
■ Truck capacity is 1,200 standard sized-boxes. Standard size box
holds 12 T-shirts. A 12-sweatshirt box is three times the size of a
standard box.
■ $25,000 available for a production run.
■ There are 500 dozen blank sweatshirts and 500 dozen blank T-
shirts in stock.
■ How many dozens (boxes) of each type of shirt to produce?
■ Sweatshirt with Front Print
■ Sweatshirt with Front and Back Print
■ T-shirt with Front Print
■ T-shirt with Front and Back Print
4-3
A Product Mix Example (2 of 8)

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-4

A Product Mix Example
Data (3 of 8)

Processing Cost Profit

Time (hr) ($) ($)
Per dozen per dozen per dozen
Sweatshirt - F 0.10 $36 $90
Sweatshirt – B/F 0.25 48 125
T-shirt - F 0.08 25 45
T-shirt - B/F 0.21 35 65
72 25,000

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-5

 A Product Mix Example
Model Construction (4 of 8)
Decision Variables:
x1 = sweatshirts, front printing
x2 = sweatshirts, back and front printing
x3 = T-shirts, front printing
x4 = T-shirts, back and front printing
Objective Function:
Maximize Z = $90x1 + $125x2 + $45x3 + $65x4
Model Constraints:
0.10x1 + 0.25x2+ 0.08x3 + 0.21x4  72 hr
3x1 + 3x2 + x3 + x4  1,200 boxes
$36x1 + $48x2 + $25x3 + $35x4  $25,000
x1 + x2  500 dozen sweatshirts
x3 + x4  500 dozen T-shirts
Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-6
A Product Mix Example
Solution with QM for Windows (7 of 8)

Exhibit 4.3
Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-7
A Product Mix Example
Solution with QM for Windows (8 of 8)

Exhibit 4.4
Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-8
A Diet Example
Data and Problem Definition (1 of 5)
Breakfast Food Fat Cholesterol Iron Calcium Protein Fiber Cost
Cal (g) (mg) (mg) (mg) (g) (g) ($)
1. Bran cereal (cup) 90 0 0 6 20 3 5 0.18
2. Dry cereal (cup) 110 2 0 4 48 4 2 0.22
3. Oatmeal (cup) 100 2 0 2 12 5 3 0.10
4. Oat bran (cup) 90 2 0 3 8 6 4 0.12
5. Egg 75 5 270 1 30 7 0 0.10
6. Bacon (slice) 35 3 8 0 0 2 0 0.09
7. Orange 65 0 0 1 52 1 1 0.40
8. Milk-2% (cup) 100 4 12 0 250 9 0 0.16
9. Orange juice (cup) 120 0 0 0 3 1 0 0.50
10. Wheat toast (slice) 65 1 0 1 26 3 3 0.07

The dietition wants the breakfast to include at least 420

calories, 5 milligrams of iron, 400 milligrams of calcium, 20
grams of protein, 12 grams of fiber, and must have no more
than 20 grams of fat and 30 milligrams of cholesterol.
Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-9
A Diet Example
Model Construction – Decision Variables (2 of 5)

x1 = cups of bran cereal

x2 = cups of dry cereal
x3 = cups of oatmeal
x4 = cups of oat bran
x5 = eggs
x6 = slices of bacon
x7 = oranges
x8 = cups of milk
x9 = cups of orange juice
x10 = slices of wheat toast
Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-10
A Diet Example
Model Summary (3 of 5)
Minimize Z = 0.18x1 + 0.22x2 + 0.10x3 + 0.12x4 + 0.10x5 + 0.09x6
+ 0.40x7 + 0.16x8 + 0.50x9 + 0.07x10
subject to:
90x1 + 110x2 + 100x3 + 90x4 + 75x5 + 35x6 + 65x7
+ 100x8 + 120x9 + 65x10  420 calories
2x2 + 2x3 + 2x4 + 5x5 + 3x6 + 4x8 + x10  20 g fat
270x5 + 8x6 + 12x8  30 mg cholesterol
6x1 + 4x2 + 2x3 + 3x4+ x5 + x7 + x10  5 mg iron
20x1 + 48x2 + 12x3 + 8x4+ 30x5 + 52x7 + 250x8
+ 3x9 + 26x10  400 mg of calcium
3x1 + 4x2 + 5x3 + 6x4 + 7x5 + 2x6 + x7
+ 9x8+ x9 + 3x10  20 g protein
5x1 + 2x2 + 3x3 + 4x4+ x7 + 3x10  12 g fiber
xi  0, for all j
Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-11
 OPTIMUM SOLUTION
 X3 = 1.025 cups of outmeal
 X8 = 1.241 cups of milk

 X10 = 2.975 slices of wheat tost

(Cost) Z = $0.509

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-12

An Investment Example

$70,000 (All of it) to divide between several investments

• Municipal bonds – 8.5% annual return
• Certificates of deposit – 5%
• Treasury bills – 6.5%
• Growth stock fund – 13%
- No more than 20% of investment should be in
Municipal Bonds
- The amount invested in deposit cannot exceed the
amount invested in the other three alternatives.
- At least 30% in treasury bills and deposit
- Amount invested in deposits and treasury bills should
be no less than in bonds and stock funds; the ratio should
be at least 1.2 to 1. 4-13
 How much to invest in each alternative
to maximize the return???

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-14

 Max Z = $0.085x1 + 0.05x2 + 0.065x3 + 0.130x4

Z = total return from all investments

0.085*1 = return from the investment in
municipal bonds

0.05*2 = return from the investment in

certificates of deposit

0.065*3 = return from the investment in treasury

bills

0.130*4 = return from the investment in growth

stock fund

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-15

 The first constraint states that no more
than 20% of the total investment should
be in municipal bonds.

The total investment is $70,000; 20% of

$70,000 is $14,000. Thus, this constraint is

x1 <= $14,000

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-16

 The second constraint indicates that the
amount invested in certificates of deposit
should not exceed the amount invested in
the other three alternatives. Because the
investment in certificates of deposit is x2
and the amount invested in the other
alternatives is x1 + x3 + x4, the constraint is

x2 <= x1 + x3 + x4

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-17

 The third constraint specifies that at least
30% of the investment should be in
treasury bills and certificates of deposit.
Because 30% of $70,000 is $21,000 and the
amount invested in certificates of deposit
and treasury bills is represented by x2 + x3,
the constraint is

x2 + x3 >= $21,000

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-18

 The fourth constraint states that the ratio of
the amount invested in certificates of deposit
and treasury bills to the amount invested in
municipal bonds and the growth stock fund
should be at least 1.2 to 1:

[(x2 + x3)/(x1 + x4)] >=1.2

Converted into standard form:

-1.2x1 + x2+ x3 -1.2 x4 >=0

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-19

 Finally, the investor wants to
invest the entire $70,000 in the
four alternatives. Thus, the sum
of all the investments in the four
alternatives must equal $70,000:

x1 + x2 + x3 + x4 = $70,000

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-20

An Investment Example
Model Summary (1 of 4)
Maximize Z = $0.085x1 + 0.05x2 + 0.065 x3+ 0.130x4
subject to:
x1  $14,000
x2 - x1 - x3- x4  0
x2 + x3  $21,000
-1.2x1 + x2 + x3 - 1.2 x4  0
x1 + x2 + x3 + x4 = $70,000
x1, x2, x3, x4  0
where
x1 = amount ($) invested in municipal bonds
x2 = amount ($) invested in certificates of deposit
x3 = amount ($) invested in treasury bills
x4 = amount ($) invested in growth stock fund

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-21

 The optimum solution is

x3 = $38,181.82 invested in treasury bonds

x4 = $31,818.18 invested in a growth stock

fund

Z = $6,818.18

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-22

 An Investment Example

 What if we change the constraint

defining the entire amount of fund to
invest as follows?
x1 + x2 + x3 + x4 <= $70000
What changes to be made to the LP
model ???

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-23

 Maximize Z = $0.085x1 + 0.05x2 +
0.065 x3+ 0.130x4
subject to:
x1  $14,000
x2 - x1 - x3- x4  0
x2 + x3  $21,000
-1.2x1 + x2 + x3 - 1.2 x4  0
x1 + x2 + x3 + x4 = $70,000
x1, x2, x3, x4  0

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-24

 Recall that "no more than 20% of the total
investment should be in municipal bonds." The total
investment is no longer exactly $70,000, but the sum
of all four investments, x1 + x2 + x3 + x4. The
constraint showing that the amount invested in
municipal bonds, x1, as a percentage (or ratio) of
this total cannot exceed 20% is written as

x1/(x1 + x2 + x3 + x4)<=0.20

Rewriting this constraint to eliminate the fractional

relationship between variables results in

0.8x1 – 0.2x2 – 0.2x3 – 0.2x4<=0

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-25

 The constraint which requires that at least 30% of
the total investment (x1 + x2 + x3 + x4) should be
in treasury bills and CDs (x2 + x3), is formulated
similarly as

(x2+x3)/(x1+x2+x3+x4)>=0.30

and

-0.3x1 + 0.7x2 + 0.7x3 – 0.3x4 >=0

Because the entire $70,000 does not have to be

invested, the last constraint becomes

x1 + x2 + x3 + x4 <=70,000

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-26

 Maximize Z = $0.085x1 + 0.05x2 + 0.065 x3+
0.130x4
subject to:
0.8x1 – 0.2x2 – 0.2x3 – 0.2x4<=0
x2 - x1 - x3- x4  0
-0.3x1 + 0.7x2 + 0.7x3 – 0.3x4 >=0
-1.2x1 + x2 + x3 - 1.2 x4  0
x1 + x2 + x3 + x4 <= $70,000
x1, x2, x3, x4  0

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-27

 Exercise
Labor Scheduling
 XYZ Bank is a busy bank that has
requirements for between 10 and 18
tellers depending on the time of day.
 Lunchtime, from noon to 2 P.M., is
usually heaviest.
 The table below indicates the tellers
needed at various hours that the bank is
open.
Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-28
 Exercise
Labor Scheduling
Time Number of Time Number of
Period Tellers Required Period Tellers Required
9 AM - 10 AM 10 1 PM - 2 PM 18
10 AM - 11 AM 12 2 PM - 3 PM 17
11 AM - Noon 14 3 PM - 4 PM 15
Noon - 1 PM 16 4 PM - 5 PM 10

4-29
 Exercise
Labor Scheduling
 The bank now employs 12 full-time tellers, but
many people are on its roster of available part-
time employees.
 A part-time employee must put in exactly 4
hours per day but can start anytime between 9
A.M. and 1 P.M.
 Fulltimers, on the other hand, work from 9 A.M.
to 5 P.M. but are allowed 1 hour for lunch.
 Half the full-timers eat at 11 A.M., the other
half at noon.

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-30

 Exercise
Labor Scheduling
 By corporate policy, the bank limits part-time hours to a
maximum of 50% of the day’s total requirement.
 Part-timers earn $6 per hour (or $24 per day) on
average, whereas full-timers earn $75 per day in salary
and benefits on average.
Develop en LP model to determine the
number of full-time and part-time tellers to
keep in the payroll to minimize the total man-
power cost.
Note that the bank will release 1 or more of its full-time
tellers if it is profitable to do so.

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-31

 Labor Scheduling Exercise

Decision Variables are:

F = Full-time tellers
P1 = Part-time tellers starting at 9 AM (leaving at 1 PM)
P2 = Part-time tellers starting at 10 AM (leaving at 2 PM)
P3 = Part-time tellers starting at 11 AM (leaving at 3 PM)
P4 = Part-time tellers starting at noon (leaving at 4 PM)
P5 = Part-time tellers starting at 1 PM (leaving at 5 PM)

4-32
 Labor Scheduling Exercise
Objective is to minimize total daily
manpower cost

Min Z= = $75F + $24(P1 + P2 + P3 + P4 + P5)

4-33
 Labor Scheduling Exercise
 For each hour, the available labor-hours
must be at least equal to the required labor-
hours.
 Only 12 full-time tellers are available
 Part-time worker-hours cannot exceed 50%
of total hours required each day, which is
the sum of the tellers needed each hour.
 How to formulate these constraints????

Copyright © 2010 Pearson Education, Inc. Publishing as Prentice Hall 4-34

 Labor Scheduling Exercise
For each hour, the available labor-hours must be
at least equal to the required labor-hours.
F+ P1 ≥ 10 (9 AM - 10 AM needs)
F+ P1+ P2 ≥ 12 (10 AM - 11 AM needs)
1/2 F+ P1+ P2+ P3 ≥ 14 (11 AM - 11 AM needs)
1/2 F+ P1+ P2+ P3+ P4 ≥ 16 (noon - 1 PM needs)
F + P2+ P3+ P4+ P5 ≥ 18 (1 PM - 2 PM needs)
F + P3+ P4+ P5 ≥ 17 (2 PM - 3 PM needs)
F + P4+ P5 ≥ 15 (3 PM - 7 PM needs)
F + P5 ≥ 10 (4 PM - 5 PM needs)

4-35
 Labor Scheduling Exercise

Only 12 full-time tellers are available, so

F ≤ 12

4-36
 Labor Scheduling Exercise
Part-time worker-hours cannot
exceed 50% of total hours required
each day, which is the sum of the
tellers needed each hour.
4(P1 + P2 + P3 + P4 + P5) ≤ .50(10 + 12 + 14 + 16 + 18
+ 17 + 15 + 10) or
4(P1+ P2+ P3+ P4+ P5) ≤ .50(112)

F, P1, P2, P3, P4, P5 ≥ 0

4-37
 Labor Scheduling Exercise
Minimize total daily
= $75F + $24(P1 + P2 + P3 + P4 + P5)
manpower cost
F + P1 ≥ 10 (9 AM - 10 AM needs)
F + P1 + P2 ≥ 12 (10 AM - 11 AM needs)
1/2 F + P1 + P2 + P3 ≥ 14 (11 AM - 11 AM needs)
1/2 F + P1 + P2 + P3 + P4 ≥ 16 (noon - 1 PM needs)
F + P2 + P3 + P4 + P5 ≥ 18 (1 PM - 2 PM needs)
F + P3 + P4 + P5 ≥ 17 (2 PM - 3 PM needs)
F + P4 + P5 ≥ 15 (3 PM - 7 PM needs)
F + P5 ≥ 10 (4 PM - 5 PM needs)
F ≤ 12
4(P1 + P2 + P3 + P4 + P5) ≤ .50(112)

F, P1, P2, P3, P4, P5 ≥ 0

4-38
 Labor Scheduling Exercise

Minimize total daily

= $75F + $24(P1 + P2 + P3 + P4 + P5)
manpower
There are two cost
alternate optimal solutions to this
problem
F+P but both will cost $1,086
≥ 10 (9 per day
AM - 10 AM needs)
1
F + P1 + P2 ≥ 12 (10 AM - 11 AM needs)
1/2 F + P1 + P2First
+ P3 Second
≥ 14 (11 AM - 11 AM needs)
1/2 F + P1 + Solution
P2 + P3 + P4 Solution
≥ 16 (noon - 1 PM needs)
F +FP2 +=P310
+ P4 + P5 ≥ 18
F (1=PM10- 2 PM needs)
F P1 +=P30+ P4 + P5 ≥ 17
P1 (2=PM6 - 3 PM needs)
F + P4 + P5 ≥ 15 (3 PM - 7 PM needs)
F P2 = 7 + P5 P2 (4=PM1 - 5 PM needs)
≥ 10
F P3 = 2 P3 = 2
≤ 12
P4 = 2 P4 = 2
4(P1 + P25 +=P33+ P4 + P5) ≤ .50(112)
P5 = 3
F, P1, P2, P3, P4, P5 ≥ 0

4-39