Management Science Linear Programming III

Linear Programming III

Bumho Son
College of Business Administration, CAU
Management Science Linear Programming III

Modeling Examples

2
Management Science Linear Programming III

LP Application Topics
▪ A Product Mix Example
▪ A Diet Example
▪ An Investment Example
▪ A Marketing Example
▪ A Transportation Example
▪ A Blend Example
▪ A Multiperiod Scheduling Example
▪ A Data Envelopment Analysis Example

3
Management Science Linear Programming III

Product Mix Example

▪ Four-product T-shirt/sweatshirt manufacturing company.
▪ Must complete production within 72 hours
▪ Truck capacity = 1,200 standard sized boxes.
▪ Standard size box holds12 T-shirts.
▪ One-dozen sweatshirts box is three times size of standard box.
▪ $25,000 available for a production run.
▪ 500 dozen blank T-shirts and sweatshirts in stock.
▪ How many dozens (boxes) of each type of shirt to produce?

4
Management Science Linear Programming III

Product Mix Example

5
Management Science Linear Programming III

Product Mix Example: Data

▪ Resource requirements for the product mix example

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

6
Management Science Linear Programming III

Product Mix Example: Model Construction

▪ 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

7
 Management Science Linear Programming III

Diet Program Example

▪ 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.

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

8
Management Science Linear Programming III

Diet Program Example: Model Construction

▪ Decision variables
▪ 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

9
Management Science Linear Programming III

Diet Program Example: Model Construction

▪ Model
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
xi  0, for all j

10
Management Science Linear Programming III

Investment Example
▪ An investor has $70,000 to divide among several instruments.
Municipal bonds have an 8.5% return, CD’s a 5% return, t-bills a 6.5%
return, and growth stock 13%.

▪ The following guidelines have been established:

▪ No more than 20% in municipal bonds
▪ Investment in CDs should not exceed the other three alternatives
▪ At least 30% invested in treasury bills and CDs
▪ More should be invested in CDs and treasury bills than in municipal bonds and
growth stocks by a ratio of 1.2 to 1
▪ All $70,000 should be invested

11
Management Science Linear Programming III

Investment Example: Model Construction

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

12
Management Science Linear Programming III

Marketing Example
▪ Budget limit $100,000
▪ Television time for four commercials
▪ Radio time for 10 commercials
▪ Newspaper space for 7 ads
▪ Resources for no more than 15 commercials and/or ads

Exposure
(people/ad or Cost
commercial)
Television Commercial 20,000 $15,000

Radio Commercial 12,000 6,000

Newspaper Ad 9,000 4,000

13
Management Science Linear Programming III

Marketing Example: Model Construction

▪ Model

Maximize Z = 20,000x1 + 12,000x2 + 9,000x3

subject to:
15,000x1 + 6,000x 2+ 4,000x3  100,000
x1  4
x2  10
x3  7
x1 + x2 + x3  15
x1, x2, x3  0
where
x1 = number of television commercials
x2 = number of radio commercials
x3 = number of newspaper ads

14
Management Science Linear Programming III

Marketing Example: Excel Solver

▪ Optimal solution
▪ 1.818 television commercials
▪ 10 radio commercials Does it makes sense?
Round up or down?
▪ 3.182 newspaper ads

15
Management Science Linear Programming III

Marketing Example: Excel Solver – Integer Solution

Decision variables

Click on “int” for

integer.

16
Management Science Linear Programming III

Marketing Example: Excel Solver – Integer Solution

Integer solution Better solution—17,000

more total exposures—
than rounded-down solution

17
Management Science Linear Programming III

Transportation Example

18
Management Science Linear Programming III

Transportation Example: Model Construction

▪ Model

Minimize Z = $16x1A + 18x1B + 11x1C + 14x2A + 12x2B + 13x2C + 13x3A + 15x3B + 17x3C
subject to:
x1A + x1B+ x1C  300
x2A+ x2B + x2C  200
x3A+ x3B + x3C  200
x1A + x2A + x3A = 150
x1B + x2B + x3B = 250
x1C + x2C + x3C = 200
All xij  0

19
Management Science Linear Programming III

Transportation Example: Excel Solver

=C5+D5+E5
=C5+C6+C7
We can add equality (“=“) constraints

20
Management Science Linear Programming III

Multiperiod Scheduling Example

Production Capacity: 160 computers per week
50 more computers with overtime

Assembly Costs: $190 per computer regular time;

$260 per computer overtime

Inventory Holding Cost: $10/computer per week

Order schedule: Week Computer Orders

1 105
2 170
3 230
4 180
5 150
6 250

21
Management Science Linear Programming III

Multiperiod Scheduling Example: Model Construction

▪ Decision variables

rj = regular production of computers in week j

(j = 1, 2, …, 6)
oj = overtime production of computers in week j
(j = 1, 2, …, 6)
ij = extra computers carried over as inventory in week j
(j = 1, 2, …, 5)

22
Management Science Linear Programming III

Multiperiod Scheduling Example: Model Construction

▪ Model

Minimize Z = $190(r1 + r2 + r3 + r4 + r5 + r6) + $260(o1+o2

+o3 +o4+o5+o6) + 10(i1 + i2 + i3 + i4 + i5)
subject to:
rj  160 computers in week j (j = 1, 2, 3, 4, 5, 6)
oj  50 computers in week j (j = 1, 2, 3, 4, 5, 6)
r1 + o1 - i1 = 105 week 1
r2 + o2 + i1 - i2 = 170 week 2
r3 + o3 + i2 - i3 = 230 week 3
r4 + o4 + i3 - i4 = 180 week 4
r5 + o5 + i4 - i5 = 150 week 5
r6 + o6 + i5 = 250 week 6
rj, oj, ij  0

23
Management Science Linear Programming III

Tax Firm Example

▪ Mission
▪ To offer Affordable and Professional tax services and advice to individuals and
small business
▪ Description
▪ AP is a small Alameda, CA based tax services office that has been around since
2004
▪ Specialize in corporate and individual tax returns and are looking to expand
their operations
▪ Maximize profit within the limitations of the current resources

▪ Current prices to process returns:

• Corporate $500(/week)
• Personal $200(/week)
• Prices are competitive in the local market

24
Management Science Linear Programming III

Tax Firm Example: Resource

• Resources • The number of hours they can work(/week)

• 4 accountants • Accountants
• 1 book keeper • 1 Accountant ≤ 40 hours accounting
• 2 secretaries • Book Keepers
• 1 Bookkeeper ≤ 40 hours book keeping
• Secretaries
• 1 Secretary ≤ 40 hours of administrative work

25
Management Science Linear Programming III

Tax Firm Example: Requirement

▪ On average, each type of return requires some work

▪ Personal return
• 1 hour Accountant work(/week)
• 1 hour Secretary work(/week)

▪ Corporate returns
• 2 hours Accountant work(/week)
• 2 hour Bookkeeper work(/week)
• 1 hour Secretary work(/week)

26
Management Science Linear Programming III

Tax Firm Example: Cost

• Hourly wage • Weekly wages:

• Accountant = $50 • Accountant = $2,000
• Book keeper = $20 • Book keeper = $800
• Secretary = $15 • Secretary = $600

• Paid at 40 hours/week • Tax returns processed can not be a negative number

• Demand is unlimited

27
Management Science Linear Programming III

Tax Firm Example: Questions

▪ How to optimally utilize the existing resources?

▪ How sensitive is the optimal solution to the fee structure?

▪ How to expand the business?

28
Management Science Linear Programming III

Tax Firm Example: Set Up the LP Formula

▪ The firm must decide how to target it’s efforts to best utilize its
available resources

▪ What is the objective?

▪ What are the decision variables?
▪ What are the constraints?

29
Management Science Linear Programming III

Tax Firm Example: Objective Function

▪ Objective: Maximize profit

▪ Profit = Revenue - Cost

▪ Assume a fixed cost of $6000 per week

▪ Cost = Salary + Fixed Costs
= $2000 * 4 + $800 * 1 + $600 * 2 + $6000
= $16,000

▪ Maximize Profit → Maximize Revenue, since the cost is fixed

30
Management Science Linear Programming III

Tax Firm Example: Decision Variables

▪ Decision variables:
▪ 𝑋1 is the number of personal returns
▪ 𝑋2 is the number of corporate returns

▪ Maximize Revenue = $200 * 𝑿𝟏 + $500 * 𝑿𝟐

31
Management Science Linear Programming III

Tax Firm Example: Constraints

Accountant hours X1 + 2 X2 ≤ 160

Bookkeeper hours 2 X2 ≤ 40

Secretary hours X1 + X2 ≤ 80

Non-negativity X1, X2 ≥ 0

32
Management Science Linear Programming III

Tax Firm Example: Excel Solver

Revenue

33
Management Science Linear Programming III

Tax Firm Example: Optimal Solution

▪ The firm should process 60 Personal and 20 Corporate returns weekly
with the available resources

▪ The firm will generate a maximum revenue of $22,000 and a maximum

profit of $6000 in a week

▪ Need to check
▪ Bottlenecks? Redundancies?
▪ How robust is the solution to the fee structure?
▪ How shall the firm expand the business?

34
Management Science Linear Programming III

Tax Firm Example: Sensitivity Analysis

35
Management Science Linear Programming III

Tax Firm Example: Sensitivity Analysis

▪ There will be no change to the number of returns processed if
▪ The fee for Personal returns is increased by up to (but not including) $300 or
decreased by up to (but not including) $200
▪ The fee for Corporate returns is increased to infinity or decreased by up to (but
not including) $300

▪ The optimal solution is quite robust with respect to the fee structure

36
Management Science Linear Programming III

Tax Firm Example: Sensitivity Analysis

Cost of personnel
Secretary = $15/hour, book keeper = $20/hour

Shadow price tell us how much the optimal solution can be increased or decreased
if we change the right hand side values (resources available) with one unit 1.

37
Management Science Linear Programming III

Tax Firm Example: Sensitivity Analysis

▪ No change to revenue if the hour for accountants is increased

▪ If the hour for secretaries is increased by 60 hrs, the firm can increase
its revenues to $34,000 ($22,000+200*60)

▪ If hours for Book keepers is increased by 120 hrs, the firm should not
process personal returns at all

38
Management Science Linear Programming III

Tax Firm Example: Recommendation

▪ Increase the number of hrs for Secretaries by 60 hrs
▪ This means, hire 1 secretary full time and 1 half time

▪ No need to hire more accountants

▪ After expansion, optimal profit = $34,000 (new rev) - $16,000 (previous

cost) – $900 (added cost to hire secretaries) = $17,100

▪ Previous profit was $6,000 (=$22,000 (previous rev) - &16,000 (previous

cost))

39
Management Science Linear Programming III

Q&A

40