IE 101: Introduction to Operations Research

4. Linear Programming Applications

Hyun-Jung Kim
 Chapter 4: Linear Programming
Applications
 Media Selection
 Portfolio Planning Problem
 Product Mix Problem
 Production Scheduling
 Workforce Assignment
 Blending Problem
 Chapter 4: Linear Programming
Applications
 Media Selection
 Portfolio Planning Problem 1st topic today!
 Product Mix Problem
 Production Scheduling
 Workforce Assignment
 Blending Problem
 Financial Applications

 LP can be used in financial decision-making that

involves make-or-buy, portfolio selection, financial
planning, and more.

 Portfolio selection problems involve choosing specific

investments – for example, stocks and bonds – from a
variety of investment alternatives.

 This type of problem is faced by managers of banks,

mutual funds, and insurance companies.

 The objective function usually is maximization of

expected return or minimization of risk.
 Portfolio Planning Problem (1)

 Woori Savings has 20,000,000,000 won available for

investment.

 It wishes to invest over the next four months

 To maximize the total interest earned over the four month

period

 Must have at least 10,000,000,000 won available at the start of

the fifth month for a high rise building venture in which it will
be participating.
 Portfolio Planning Problem (2)
 Woori Savings wishes to invest only in

 2-month government bonds (earning 2% over the 2-month

period) and

 3-month construction loans (earning 6% over the 3-month

period).

 Each of these is available each month for investment.

 Funds not invested in these two investments are liquid

and earn 0.75% per month when invested locally.

Easy and quick to access – like cash

 Portfolio Planning Problem (3)
 Formulate a linear program to

 Help Woori Savings determine how to invest over the next

four months

 Woori Savings does not want to have more than

8,000,000,000 won in either government bonds or
construction loans at all times.
 Portfolio Planning Problem (4)
 Define the decision variables

gj = amount of new investment in

government bonds in month j
cj = amount of new investment in
construction loans in month j
lj = amount invested locally in month j,

where j = 1,2,3,4
 Portfolio Planning Problem (5)
 Define the objective function
Maximize total interest earned from the 4-month period investment.

MAX S (interest rate on investment)(amount invested)

MAX .02g1 + .02g2 + .02g3 + .02g4 +

.06c1 + .06c2 + .06c3 + .06c4 +

.0075l1 + .0075l2 + .0075l3 + .0075l4

 Portfolio Planning Problem (6)

 Define the constraints

Month 1's total investment limited to 20,000,000,000 won:
(1) g1 + c1 + l1 = 20,000,000,000

Month 2's total investment limited to principle and interest

invested locally in Month 1:
(2) g2 + c2 + l2 = 1.0075l1
or g2 + c2 – 1.0075l1 + l2 = 0
 Portfolio Planning Problem (7)
 Define the constraints (continued)

Month 3's total investment amount limited to

principle and interest invested in government bonds
in Month 1 and locally invested in Month 2:

(3) g3 + c3 + l3 = 1.02g1 + 1.0075l2

or – 1.02g1 + g3 + c3 – 1.0075l2 + l3 = 0
 Portfolio Planning Problem (8)

 Define the constraints (continued)

Month 4's total investment limited to principle and interest

invested in construction loans in Month 1, government
bonds in Month 2, and locally invested in Month 3:
(4) g4 + c4 + l4 = 1.06c1 + 1.02g2 + 1.0075l3
or – 1.02g2 + g4 – 1.06c1 + c4 – 1.0075l3 + l4 = 0

10,000,000,000 won must be available at the start of

Month 5:
(5) 1.06c2 + 1.02g3 + 1.0075l4 > 10,000,000,000
`
 Portfolio Planning Problem (9)

 Define the constraints (continued)

No more than 8,000,000,000 won in government

bonds at any time:
(6) g1 < 8,000,000,000
(7) g1 + g2 < 8,000,000,000
(8) g2 + g3 < 8,000,000,000
(9) g3 + g4 < 8,000,000,000
 Portfolio Planning Problem (10)
 Define the constraints (continued)

No more than 8,000,000,000 won in construction

loans at any time:
(10) c1 < 8,000,000,000
(11) c1 + c2 < 8,000,000,000
(12) c1 + c2 + c3 < 8,000,000,000
(13) c2 + c3 + c4 < 8,000,000,000

Nonnegativity: gj, cj, lj > 0 for j = 1,2,3,4

 Chapter 4: Linear Programming
Applications
 Media Selection
 Portfolio Planning Problem
 Product Mix Problem 2nd topic today!
 Production Scheduling
 Workforce Assignment
 Blending Problem
 Product Mix Problem (1)
Floataway Tours has 420,000,000 won that can be
used to purchase new rental boats for hire during the
summer. The boats can
be purchased from two
different manufacturers.
Floataway Tours would
like to purchase at least 50 boats and would like to
purchase the same number from Sleekboat as from
Racer to maintain goodwill. At the same time,
Floataway Tours wishes to have a total seating
capacity of at least 200.
 Product Mix Problem (2)
Formulate this problem as a linear program.

Cost Maximum Expected

Boat Builder (won) Seating Daily Profit
Speedhawk Sleekboat 6,000,000 3 70,000 won
Silverbird Sleekboat 7,000,000 5 80,000 won
Catman Racer 5,000,000 2 50,000 won
Classy Racer 9,000,000 6 110,000 won
 Product Mix Problem (3)
 Define the decision variables
x1 = number of Speedhawks ordered
x2 = number of Silverbirds ordered
x3 = number of Catmans ordered
x4 = number of Classys ordered
 Define the objective function
Maximize total expected daily profit:
Max: (Expected daily profit per unit) x (Number of units)

Max: 70,000 x1 + 80,000 x2 +

50,000 x3 + 110,000 x4

Question: Does this make sense? What assumptions are being used?
 Product Mix Problem (4)

 Assumes that they can use all the capacity that

they purchase…

 But, what if the market for rental boats dries up?

Clear water & good business… Trouble to rent boats…

 Product Mix Problem (5)
 Define the constraints
(1) Spend no more than 420,000,000 won:
6,000,000 x1 + 7,000,000 x2 +
5,000,000 x3 + 9,000,000 x4 < 420,000,000

(2) Purchase at least 50 boats:

x1 + x2 + x3 + x4 > 50

(3) Number of boats from Sleekboat equals number of

boats from Racer:
x1 + x2 = x3 + x4 or x1 + x2 - x3 - x4 = 0
 Product Mix Problem (6)
 Define the constraints (continued)
(4) Capacity at least 200:
3x1 + 5x2 + 2x3 + 6x4 > 200

Nonnegativity of variables:
xj > 0, for j = 1,2,3,4
 Product Mix Problem (7)
 Complete Formulation

Max 70,000 x1 + 80,000 x2 + 50,000 x3 + 110,000 x4

s.t.
6,000,000 x1 + 7,000,000 x2 +
5,000,000 x3 + 9,000,000 x4 < 420,000,000

x1 + x2 + x3 + x4 > 50
x1 + x 2 - x3 - x4 = 0
3x1 + 5x2 + 2x3 + 6x4 > 200

x1, x2, x3, x4 > 0

 Product Mix Problem (8)
 Output

OBJECTIVE FUNCTION VALUE = 5040.000

Variable Value Reduced Cost
x1 28.000 0.000
x2 0.000 2.000
x3 0.000 12.000
I divided
x4 28.000 0.000
these money
Constraint Slack/Surplus Dual Price values by
1 0.000 12.000 1,000
2 6.000 0.000
3 0.000 -2.000
4 52.000 0.000
 In-Class Activity: Product Mix Problem to MAX Profit

Max 70 x1 + 80 x2 + 50 x3 + 110 x4
s.t.
C1: 6 x1 + 7 x2 + 5 x3 + 9 x4 < 420 Using ONLY the sensitivity report
C2: x1 + x2 + x3 + x4 > 50 shown, answer the following
C3: x1 + x2 – x3 – x4 = 0 questions (OR state why you
C4: 3 x1 + 5 x2 + 2 x3 + 6 x4 > 200 cannot answer)
C5-8: x1, x2, x3, x4 > 0 NOTE: Optimal profit = 5,040
Let Pi denote profit of boat i

Adjustable Cells 1) If P4 = 200, find optimal solution and

Final Reduced Objective Allowable Allowable profit?
Cell Name Value Cost Coefficient Increase Decrease 2) If P3 = 65, what is the optimal
$D$12 X1 28 0 70 45 1.875 solution and profit?
$E$12 X2 0 2 80 2 1E+30 3) If RHS of C1 = 425, find optimal
$F$12 X3 0 12 50 12 1E+30 profit?
$G$12 X4 28 0 110 1E+30 16.36363636 4) If RHS of C1 = 380, find optimal
profit?
5) If RHS of C3 = 50, find optimal
Constraints
profit?
Final Shadow Constraint Allowable Allowable
6) If RHS of C3 = 100, find optimal
Cell Name Value Price R.H. Side Increase Decrease profit?
$E$17 #1 420.0 12.0 420 1E+30 45
7) If P2 = 81 and P3 = 55, find optimal
$E$18 #2 56.0 0.0 50 6 1E+30 solution and profit?
$E$19 #3 0.0 -2.0 0 70 30
8) If RHS of C1 = 390 and RHS of C4 =
$E$20 #4 252.0 0.0 200 52 1E+30 226, find optimal solution and profit?
 Chapter 4: Linear Programming
Applications
 Media Selection
 Portfolio Planning Problem
 Product Mix Problem
 Production Scheduling
 Workforce Assignment
 Blending Problem Next topic
 Blending Problems in General
 Blending problems
 Combine various ingredients to create a product that
 Satisfies various content constraints (e.g., nutrition) with the
 Goal of minimizing the cost (typically)

 Examples:
 Gasoline company (e.g., various grades of gas)
 Food products (e.g., what to put in a can of spaghetti sauce)
 Cell phone company (e.g., various grades of service offerings)
 Cafeteria
…
 Blending Problem:
Example from Food Festival
APPLICATION: Dietary optimization

 Very commonly given example for LP

 Objective: Minimize cost of weekly food
 Constraints:
 Minimum amount of each nutrient/day average
 Maximum amount of each nutrient/day average
 Minimum calories/day average
 Must have 3 units of kimchee/day average
 …
 Parameters
 Calories per unit of food
 Nutrients per unit of food
 Cost per unit of food
 Types of food considered
 Who might use this kind of model? Cafeteria, restaurant, sports club,
Olympics, etc.
 Blending Problem (1)
 Kim Feed Company blends dry pet food
 Consists of 4 raw grains.
 Their dry pet food advertises:
 Each 500 gram packet meets the minimum daily requirements for vitamin
C, protein and iron.
 The cost of each raw grain as well as the vitamin C, protein, and iron units
per kg of each grain are summarized next

Vitamin C Protein Iron

Grain Units/kg Units/kg Units/kg Cost/kg
1 9 12 0 750 won
2 16 10 14 900 won
3 8 10 15 800 won
4 10 8 7 700 won
 Blending Problem (2)

Kim Feed Company wants to

 Produce the 500 g mixture at minimum cost and

 Meet the minimum daily requirements of
 6 units of vitamin C,
 5 units of protein, and
 5 units of iron.
 Blending Problem (3)
 Define the decision variables

xj = the kg of grain j (j = 1,2,3,4)

used in the 500 g mixture

 Define the objective function

Minimize the total cost for a 500 gram mixture:

MIN 750 x1 + 900 x2 + 800 x3 + 700 x4

 Blending Problem (4)
Define the constraints
 Total weight of the mix is 500 g (0.5 kg):
(1) x1 + x2 + x3 + x4 = .5 kg

 Total amount of Vitamin C in the mix is at least 6 units:

(2) 9x1 + 16x2 + 8x3 + 10x4 > 6

 Total amount of protein in the mix is at least 5 units:

(3) 12x1 + 10x2 + 10x3 + 8x4 > 5

 Total amount of iron in the mix is at least 5 units:

(4) 14x2 + 15x3 + 7x4 > 5

 Nonnegativity of variables: xj > 0 for all j

 Blending Problem (5)
 Output

OBJECTIVE FUNCTION VALUE = 406

VARIABLE VALUE REDUCED COSTS
X1 0.099 0.000
X2 0.213 0.000
X3 0.088 0.000
X4 0.099 0.000
 An optimal blend has about
 0.10 kg of grain 1,
 0.21 kg of grain 2,
 0.09 kg of grain 3, and
 0.10 kg of grain 4.
 The mixture costs Kim Feed Company 406 won
 Chapter 4: Linear Programming
Applications
 Media Selection
 Portfolio Planning Problem
 Product Mix Problem
 Production Scheduling Next topic
 Workforce Assignment
 Blending Problem
 Operations Management Applications
 LP can be used in operations management to aid in decision-
making about product mix, production scheduling, staffing,
inventory control, capacity planning, and other issues.

 An important application of LP is multi-period planning such

as production scheduling.

 Usually the objective is to establish an efficient, low-cost

production schedule for one or more products over several
time periods.

 Typical constraints include limitations on production capacity,

labor capacity, storage space, and more.
 Production Scheduling (1)
 A and B are the owners of Cutie Custom Wheels.

 They have just received orders for 1,000 standard wheels and 1,250 deluxe
wheels next month and for 800 standard and 1,500 deluxe the following
month. All orders must be filled.

 The cost of making standard wheels is $10

 The cost of making deluxe wheels is $16.

 Over-time rates are 50% higher.

 There are 1,000 hours of regular time and 500 hours of overtime available each
month.
 It takes .5 hour to make a standard wheel and .6 hour to make a deluxe wheel.

 The cost of storing a wheel from one month to the next is $2.
 Production Scheduling (2)
 Define the Decision Variables

 We want to determine the regular-time and overtime

production quantities in each month for standard and
deluxe wheels.

Month 1 Month 2
Wheel Reg. Time Overtime Reg. Time Overtime
Standard SR1 SO1 SR2 SO2
Deluxe DR1 DO1 DR2 DO2
 Production Scheduling (3)
 Define the Decision Variables

We also want to determine the inventory quantities

for standard and deluxe wheels.

SI = number of standard wheels held in

inventory from month 1 to month 2
DI = number of deluxe wheels held in
inventory from month 1 to month 2
 Production Scheduling (4)
 Define the Objective Function

We want to minimize total production and inventory

costs for standard and deluxe wheels.
Min (production cost per wheel)
x (number of wheels produced)
+ (inventory cost per wheel)
x (number of wheels in inventory)
Min 10SR1 + 15SO1 + 10SR2 + 15SO2
+ 16DR1 + 24DO1 + 16DR2 + 24DO2
+ 2SI + 2DI
 Production Scheduling (5)
 Define the Constraints

Production Month 1 = (Units Required) + (Units Stored)

Standard:
(1) SR1 + SO1 = 1,000 + SI or SR1 + SO1 - SI = 1,000
Deluxe:
(2) DR1 + DO1 = 1,250 + DI or DR1 + DO1 - DI = 1,250

Production Month 2 = (Units Required) - (Units Stored)

Standard:
(3) SR2 + SO2 = 800 - SI or SR2 + SO2 + SI = 800
Deluxe:
(4) DR2 + DO2 = 1,500 - DI or DR2 + DO2 + DI = 1,500
 Production Scheduling (6)
 Define the Constraints (continued)

Reg. Hrs. Used Month 1 < Reg. Hrs. Avail. Month 1

(5) .5SR1 + .6DR1 < 1000
OT Hrs. Used Month 1 < OT Hrs. Avail. Month 1
(6) .5SO1 + .6DO1 < 500
Reg. Hrs. Used Month 2 < Reg. Hrs. Avail. Month 2
(7) .5SR2 + .6DR2 < 1000
OT Hrs. Used Month 2 < OT Hrs. Avail. Month 2
(8) .5SO2 + .6DO2 < 500
 Production Scheduling (7)
 Output

Objective Function Value = 67500.000

Variable Value Reduced Cost
SR1 500.000 0.000
SO1 500.000 0.000
SR2 200.000 0.000
SO2 600.000 0.000
DR1 1250.000 0.000
DO1 0.000 2.000
DR2 1500.000 0.000
DO2 0.000 2.000
SI 0.000 2.000
DI 0.000 2.000
 Chapter 4: Linear Programming
Applications
 Media Selection
 Portfolio Planning Problem
 Product Mix Problem
 Production Scheduling
 Workforce Assignment Next topic
 Blending Problem
 Workforce Assignment Example
 Formulate an LP for Ch. 4 Problem 8 (don’t solve)
 Police officers work in 8 hour shifts
 Shifts starts at 8 am, noon, 4 pm, 8 pm, midnight and 4 am
 During this time Minimum # of Officers
8:00 am – Noon 5
Noon- 4:00 pm 6
4:00 pm – 8:00 pm 10
8:00 – Midnight 7 Officers starting at
Midnight – 4:00 am 4 4:00 am will “roll
4:00 am – 8:00 am 6 over” into the next
day and count for
8:00 am to Noon
 GOAL: Minimize total number of officers required
 HINT: Let x1 = # of officers starting at 8 am, …
 Workforce Assignment Example
 Decision variables
 x1 = # of officers starting at 8 am
 x2 = # of officers starting at noon
 x3 = # of officers starting at 4 pm
 x4 = # of officers starting at 8 pm
 x5 = # of officers starting at midnight
 x6 = # of officers starting at 4 am
 Objective Function
 Min x1 + x2 + x3 + x4 + x5 + x6
 Constraints
 8:00 am – Noon C1: x1 + x6 > 5
 Noon – 4:00 pm C2: x1 + x2 >6
 Etc…
 Workforce Assignment (1)
 National Wing Company (NWC) is gearing up for the
new B-48 contract. NWC has agreed to produce 20
wings in April, 24 in May, and 30 in June.

 Currently, NWC has 100 fully qualified workers.

 A fully qualified worker can either be placed in

production or can train new recruits. A new recruit
can be trained to be an apprentice in one month.

 After another month, the apprentice becomes a

qualified worker. Each trainer can train two recruits.
 Workforce Assignment (2)
 The production rate and salary per employee type is listed
below.

Type of Production Rate Wage

Employee (Wings/Month) Per Month
Production .6 $3,000
Trainer .3 $3,300
Apprentice .4 $2,600
Recruit .05 $2,200

At the end of June, NWC wishes to have no recruits or

apprentices, but have at least 140 full-time workers.
 Workforce Assignment (3)
 Define the Decision Variables

Pi = number of producers in month i

(where i = 1, 2, 3 for April, May, June)
Ti = number of trainers in month i
(where i = 1, 2 for April, May)
Ai = number of apprentices in month i
(where i = 2, 3 for May, June)
Ri = number of recruits in month i
(where i = 1, 2 for April, May)
 Workforce Assignment (4)
 Define the Objective Function

Minimize total wage cost for producers, trainers,

apprentices, and recruits for April, May, and June:

Min 3000P1 + 3300T1 + 2200R1 + 3000P2 + 3300T2

+ 2600A2+2200R2 + 3000P3 + 2600A3
 Workforce Assignment (5)
 Define the Constraints

Total production in Month 1 (April) must equal or

exceed contract for Month 1:
(1) .6P1 + .3T1 +.05R1 > 20

Total production in Months 1-2 (April, May) must

equal or exceed total contracts for Months 1-2:
(2) .6P1 + .3T1 + .05R1 + .6P2 + .3T2 + .4A2 + .05R2 > 44

Total production in Months 1-3 (April, May, June)

must equal or exceed total contracts for Months 1-3:
(3) .6P1+.3T1+.05R1+.6P2+.3T2+.4A2+.05R2 +.6P3+.4A3 > 74
 Workforce Assignment (6)
 Define the Constraints (continued)

The number of producers and trainers in a month

must equal the number of producers, trainers, and
apprentices in the previous month:
(4) P1 - P2 + T1 - T2 = 0
(5) P2 - P3 + T2 + A2 = 0

The number of apprentices in a month must equal

the number of recruits in the previous month:
(6) A2 - R1 = 0
(7) A3 - R2 = 0
 Workforce Assignment (7)
 Define the Constraints (continued)

Each trainer can train two recruits:

(8) 2T1 - R1 > 0
(9) 2T2 - R2 > 0

In April there are 100 employees that can be producers or trainers:

(10) P1 + T1 = 100

At the end of June, there are to be at least 140 employees:

(11) P3 + A3 > 140

Non-negativity:
P1, T1, R1, P2, T2, A2, R2, P3, A3 > 0
 Workforce Assignment (8)
 Solution Summary
P1 = 100, T1 = 0, R1 = 0
P2 = 80, T2 = 20, A2 = 0, R2 = 40
P3 = 100, A3 = 40
Total Wage Cost = $1,098,000

April May June July

Producers 100 80 100 140
Trainers 0 20 0 0
Apprentices 0 0 40 0
Recruits
0 40 0 0
 Chapter 4: Linear Programming
Applications
 Media Selection Final topic

 Portfolio Planning Problem

 Product Mix Problem
 Production Scheduling
 Workforce Assignment
 Blending Problem
 Marketing Applications
 One application of linear programming in marketing is
media selection.

 LP can be used to help marketing managers allocate a

fixed budget to various advertising media.

 The objective is to maximize reach, frequency, and quality

of exposure.

 Restrictions on the allowable allocation usually arise

during consideration of company policy, contract
requirements, and media availability.
 Significant Efforts to Reduce
Smoking (1)
 There are more than 1 billion smokers worldwide…

 Governments use antismoking campaigns to reduce

smoking
 In 1998, the World Health Organization(WHO) created the
World No Tobacco Day (WNTD) to raise awareness of the
dangers
 Significant Efforts to Reduce
Smoking (2)
 Advertising campaigns are costly

 Limited budgets

 Greater awareness can save lives!

 Greater awareness can be achieved

 By spending more money… but money is
limited
 Reaching more people with the same funds

Engineering methods can help us to do this!

 An Antismoking Campaign (1)
 The government wants to launch an antismoking campaign to inform
people of the dangers of smoking! There is $282,000 to spend on
the campaign. The money is to be spent on a TV campaign for World
No Tobacco Day (WNTD, 31th May) during one weekend (Friday,
Saturday, and Sunday)

 Three options are available:

 Daytime advertising,
 Evening news advertising, and
 Sunday sports-time advertising.

 A mixture of one-minute TV spots is desired.

 An Antismoking Campaign (2)
Estimated Audience
Ad Type Reached With Each Ad Cost Per Ad
Daytime 3,000 $5,000
Evening News 4,000 $7,000
Sunday Game 75,000 $100,000

 The government wants to take out at least one ad of each

type (daytime, evening-news, and game-time).
 Further, there are only two game-time ad spots available.
 There are ten daytime spots and six evening news spots
available daily.
 The government wants to have at least 5 ads per day, but
spend no more than $50,000 on Friday and no more than
$75,000 on Saturday.
 An Antismoking Campaign (3)
 Define the Decision Variables

DFR = number of daytime ads on Friday

DSA = number of daytime ads on Saturday
DSU = number of daytime ads on Sunday
EFR = number of evening ads on Friday
ESA = number of evening ads on Saturday
ESU = number of evening ads on Sunday
GSU = number of game-time ads on Sunday
 An Antismoking Campaign (3)
Formulate an LP for this problem
 1.a: Create an objective function (e.g., maximize
exposure)
 1.b: Create constraints for this problem
 Just formulate an LP, you do not need to solve this 7-
dimensional problem
An Antismoking Campaign (4)
 Homework 3
 Chapter 4
 Reading: Chapter 4
 No need to turn in
 Problems to be turned in
 Solve problems 8, 11, 14, 17, 25 in Chapter 4
 You must show all work to receive credit.
 Due: ?
 In-Class Activity
 Formulate an LP
 Company makes 2 grades of oil: Regular, High octane
 Two types of crude oil used as the raw ingredients
 Crude Oil Cost/Liter Ingredient A Ingredient B
1 $0.10 20% 60%
2 $0.15 50% 30%
 1 liter of regular must contain at least 40% of A
 1 liter of high octane can contain at most 50% of B
 Demand for regular is 800,000 liters
 Demand for high octane is 500,000 liters

 Objective: Minimize cost (meet constraints)

 HINT: Let x11 = liters of crude 1 used to make regular, …

 HINT: Let x12 = liters of crude 1 used to make high octane