ISOM 2700: Operations Management

Session 7. Resource Management II

Linear Programming Method

Lijian Lu
Dept. of ISOM, HKUST

1
 This class

• Formulate linear programming problems

• Solve linear programming problems

– Graphical Method (no more than 2 decision variables)
– Excel Solver

• Sensitivity analysis

2
Resource Allocation Decision
Example: Bland Brewery Problem

Corn Beer
Hops
Malt
Ale

3
 Bland Brewery Problem (continued)
• Profitability
1 Barrel of Beer 1 Barrel of Ale

$23 $13

• Mixing Quantities • Resource Availability

1 Barrel of Beer 1 Barrel of Ale Corn 480 lbs

Corn 15 lbs 5 lbs Hops 160 ozs

Hops 4 ozs 4 ozs Malt 1,190 lbs

Malt 20 lbs 35 lbs

How much of beer and ale to produce, if we want to maximize

profit?
4
 Plan 1: Beer-only Production
• Profitability • Mixing Quantities
1 Barrel of 1 Barrel of • Resource Availability
Beer Beer
Corn 15 lbs Corn 480 lbs
$23
Hops 4 ozs Hops 160 ozs

Malt 20 lbs Malt 1,190 lbs

• We run out of corn after producing 480/15=32 barrels of beer

• We run out of hops after producing 160/4=40 barrels of beer

• We run out of malt after producing 1190/20=59.5 barrels of beer

• We can produce at most 32 barrels of beer, making total profit of
$23×32=$736
5
 Plan 2: Ale-only Production
• Profitability • Mixing Quantities
1 Barrel of 1 Barrel of Ale • Resource Availability
Ale
Corn 5 lbs Corn 480 lbs
$13
Hops 4 ozs Hops 160 ozs

Malt 35 lbs Malt 1,190 lbs

• We run out of corn after producing 480/5=96 barrels of ale

• We run out of hops after producing 160/4=40 barrels of ale
• We run out of malt after producing 1190/35=34 barrels of ale
• We can produce at most 34 barrels of ale, making total profit of
$13×34=$442
6
 How to Best Use Our Resources?

Beer-only Production Ale-only Production

Number of Barrels 32 34

Profit $736 $442

Corn left 0 lbs 310 lbs
Malt left 32 lbs 24 lbs
Hops left 550 lbs 0 lbs

Can we earn more profit if we “mix” beer and ale in the production
plan?

Tradeoff: producing more beer vs. producing more ale

7
 Bland Brewery Model: Standard Notation
• Decision Variables
– A = # of barrels of ale to produce, and
– B = # of barrels of beer to produce.

1 Barrel of 1 Barrel of
Beer Ale
m Objective Function
Profit in $ = 13A + 23B
$23 $13

1 Barrel of m Constraints
1 Barrel of Beer
Ale
Corn Availability: 5A + 15B £ 480
Corn 15 lbs 5 lbs Hops Availability: 4A + 4B £ 160
Hops 4 ozs 4 ozs
Malt Availability: 35A + 20B £ 1190
Non-negativity: A, B ³ 0
Malt 20 lbs 35 lbs

8
 Bland Brewery Linear Program

Objective Function

max 13 A + 23 B (Profit)
subject to
Constraints (corn) 5A + 15B £ 480
(hops) 4A + 4B £ 160 Right hand side

(malt) 35A + 20B £ 1190

(non-negativity) A, B ³ 0

Variables
9
 Feasible/Infeasible Solution
• A production plan (A,B) that satisfies all of the constraints
is called a feasible solution

@ For example, in the Bland Brewery LP, is solution (A=10, B=10)

feasible?
@ Constraints
Corn Availability: 5 x 10 + 15 x 10 = 200 £ 480
Hops Availability: 4 x 10 + 4 x 10 = 80 £ 160
Malt Availability: 35 x 10 + 20 x 10 = 550 £ 1190
Non-negativity: 10, 10 ³ 0

@ The solution (A=10, B=10) is feasible.

10
 Feasible/Infeasible Solution
• A production plan (A,B) that satisfies all of the constraints
is called a feasible solution

@ For example, in the Bland Brewery LP, is solution (A=40, B=10)

feasible?
@ Constraints
Corn Availability: 5 x 40 + 15 x 10 = 350 £ 480
Hops Availability: 4 x 40 + 4 x 10 = 200 > 160
Malt Availability: 35 x 40 + 20 x 10 = 1600 > 1190
Non-negativity: 40, 10 ³ 0

@ The solution (A=40, B=10) is infeasible.

11
 Optimal Solution

• For a maximization (respectively, minimization)

problem, an optimal solution is a feasible solution that
has the largest objective function value (respectively,
smallest objective function value ) among all feasible
solutions

• The optimal solution for the Bland Brewery production

model is (A=12, B=28). The optimal objective function
value is $800.

12
 Definition of LP Problem

• Both the objective function and the constraints are

linear with respect to decision variables
– Linear functions are functions in which each variable
appears in a separate term raised to the first power and is
multiplied by a constant (which could be 0).

– Linear constraints are linear functions that are restricted

to be (³, £, or = ) a constant.

13
 Examples of Linear/Non-linear Functions

m Linear functions of A and B:

@13A + 23B
@0.5A + (2/3)B

m Non-Linear functions of A and B:

@13A2 + 23AB
@7A/B
@log(A) + cos(B)
@max(A,0)
@IF(A< 5,0,10)

14
Examples of Linear/Non-linear Constraints

• Linear Constraints of A, B, C
A-B ≤ 10;
A≥0;
A+B+3C=5;

• Non-linear Constraints of A, B, C
AB ≤ 2C;
A2≤ 100;

15
 Assumptions in Linear Program
m Continuity:
m the decision variables are continuous, i.e., fractional values
are allowed

m Proportionality
m Each unit of output uses the same amount of resources
m No economies of scale
m No diseconomies of scale

m Additivity
m Each unit of output has the same valuation
m Profit is the sum of the profit contributions from each output

16
 Procedure of LP Formulation
• Step 1. Define the decision variables.

• Step 2. Write the objective in terms of the decision

variables.

• Step 3. Write the constraints in terms of the decision

variables.

Make sure that objective function and constraints are linear!!!

17
 Exercise
A school board is investigating various
ways of composing the faculty for a
proposed new elementary school.

They can hire teachers and aides. The

amount of money the school district
will spend on salaries each year
depends on how many teachers and on
how many aides are hired.

18
 Objective
• The board finds that the annual teacher salary is
$15,000, and the average aide salary is $10,000.

• Objective: minimizing the annual cost =15t + 10a

– t = number of teachers hired
– a = number of aides hired

19
 School Board Requirements
• The building can accommodate no more
than 50 faculty members. t + a ≤ 50

• A minimum of 20 faculty members is t + a ≥ 20

needed to staff the school.

• For the proper teacher-to-aide ratio, the

number of teachers must be at least half t ≥ 1/2a
the number of aides.

• It is impossible to hire a negative number t≥0

of aides or teachers!
a≥0

20
 Linear Program (LP) Formulation
• Decision variables
– t = number of teachers hired
– a = number of aides hired

• LP problem
Min 15t + 10a
Objective s.t. t + a ≤ 50 Constraints
function
t + a ≥ 20
t ≥ 1/2a
t≥0
“Subject to” a≥0
21
 Solving LP by Graphical Method
• Formulate the problem in standard LP format

• Plot the constraints on a piece of graph paper and

define the feasible solution space

• Find the optimal solution:

– Examine all corner points
– Use the iso-profit (or iso-cost) line method

(Note: Graphical method is useful in understanding the LP

concept but cannot solve problems with more than 2 decision
variables.)
22
 Example: Product Mix Problem
A manager must decide on the mix of products A and B to produce for the coming week.
For each unit of Product A, it requires processing times of 1 minute for molding and 2
minutes for painting. For each unit of Product B, it requires 1 minute for molding, 1
minute for painting, and 1 minute for cutting. Based on the preliminary staff and
machine schedules, there will be 300 minutes available for molding, 400 minutes for
painting, and 250 minutes for cutting for the coming week. The manager also estimates
that the profit margins will be $3 per unit of A and $2 per unit of B.

(a) Formulate the problem and solve it graphically.

(b) What combination of the products will maximize the total profit?
(c) What is the maximum total profit?
(d) Is there any idle time in molding, painting, or cutting departments? If so,
which department has idle time and how many hours?
(e) If it is possible to increase the capacity of cutting at the cost of $50 for an
additional hour, what should you do?
(f) Is it profitable to increase the capacity of painting at the cost of $50 for an
additional hour?

23
 Example: Product Mix Problem
A manager must decide on the mix of products A and B to produce for the coming
week. For each unit of Product A, it requires processing times of 1 minute for
molding and 2 minutes for painting. For each unit of Product B, it requires 1
minute for molding, 1 minute for painting, and 1 minute for cutting. Based on
the preliminary staff and machine schedules, there will be 300 minutes available
for molding, 400 minutes for painting, and 250 minutes for cutting for the coming
week. The manager also estimates that the profit margins will be $3 per unit of A
and $2 per unit of B.

Let A = no. of units of product A to make in the coming week

B = no. of units of product B to make in the coming week

Max Z = 3 A + 2 B
s.t. A + B < 300 ( 1 ) Molding
2A + B < 400 ( 2 ) Painting
B < 250 ( 3 ) Cutting
A,B > 0
24
 Max Z = 3 A + 2 B
s.t. A + B < 300 (1)
2A + B < 400 (2)
B < 250 (3)
B A,B > 0
500

300

250

(1)

A 25
0 250 300 500
 Max Z = 3 A + 2 B
s.t. A + B < 300 (1)
2A + B < 400 (2)
B < 250 (3)
B A,B > 0
500

400

250

(1)
(2)

A 26
0 200 250 500
 Max Z = 3 A + 2 B
s.t. A + B < 300 (1)
2A + B < 400 (2)
B < 250 (3)
B A,B > 0
500

250 (3)

(1)
(2)

A 27
0 250 500
 Max Z = 3 A + 2 B Iso-profit Line Method
s.t. A + B < 300 (1) Set Z = 600 Þ 3 A + 2 B = 600
2A + B < 400 (2) If A = 0 Þ B = 300
B < 250 (3)
B A,B > 0 If B = 0 Þ A = 200
500 The objective function line can be
represented by a straight line connecting
points ( 0 , 300 ) and ( 200 , 0 ) on the
graph
To maximize Z, move the line to the
right until it reaches the last corner
point in the feasible region.

Feasible region Optimal solution

250 (3) A = 100
B = 200
Max Z = 700

(1)
(2)

A 28
0 250 500
(b) What combination of the products will maximize the total profit?
100 A and 200 B

B
500
Max Z = 3 A + 2 B
s.t. A + B < 300 (1)
2A + B < 400 (2)
B < 250 (3)
A,B > 0
Optimal solution
A = 100
B = 200
Max Z = 700 (3)
250

A 29
0 ( 2 ) 250 (1) 500
(c) What is the maximum total profit?
Total profit = 3(100) + 2(200) = $ 700

B
500
Max Z = 3 A + 2 B
s.t. A + B < 300 (1)
2A + B < 400 (2)
B < 250 (3)
A,B > 0
Optimal solution
A = 100
B = 200
Max Z = 700 (3)
250

A 30
0 ( 2 ) 250 (1) 500
(d) Is there any idle time in molding, painting, or cutting departments?
If so, which department has idle time and how much?

B
500 Check constraints
Max Z = 3 A + 2 B
s.t. A + B < 300 (1)
2A + B < 400 (2) •Molding: A + B = 300
B < 250 (3) •Painting: 2A + B = 400
A,B > 0 •Cutting: B = 200 < 250
Optimal solution
A = 100 Hence, cutting has idle time
B = 200 of 50 minutes
Max Z = 700 (3)
250

A 31
0 ( 2 ) 250 (1) 500
 Binding vs. Non-binding

• Binding constraints
– limit the improvement in the objective function,
e.g., use all resources available

• Non-binding constraints
– do not limit improvement, e.g., have “left over”
resources
– Slack is the amount of resources not being used

32
(e) If it is possible to increase the capacity of cutting at the cost of $50 for an additional
hour, what should you do?
Do nothing. As cutting already has 50 minutes of idle time,
B additional capacity will not improve the optimal solution.
500
Max Z = 3 A + 2 B Shadow price is the
s.t. A + B < 300 (1)
2A + B < 400 (2) marginal revenue that can be
B < 250 (3) generated by increasing one
A,B > 0 unit of capacity.
Optimal solution
A = 100
Example: shadow price is $0
B = 200 per unit of cutting capacity
Max Z = 700 (3)
250 Relationship between slack
variable (Si ) and shadow price
(SPi) :
Si > 0 (non-binding) Þ SPi = 0
SPi > 0 Þ Si = 0 (binding)

A 33
0 ( 2 ) 250 (1) 500
(f) Is it profitable to increase the capacity of painting at the cost of $50 for an additional hour?

If we increase the capacity of painting for 1 hr (i.e. 60 min) :

B
500
Max Z = 3 A + 2 B
s.t. A + B < 300 (1)
2A + B < 400 (2) 2A + B < 460 ( 2’ )
B < 250 (3)
A,B > 0
Optimal solution
A = 100
B = 200
Max Z = 700 (3)
250
Constraint (2) shifts to the right when capacity increases

A 34
0 ( 2 ) (250
2’ ) (1) 500
(f) Is it profitable to increase the capacity of painting at the cost of $50 for an additional hour?

If we increase the capacity of painting for 1 hr (i.e. 60 min) :

B
500
Max Z = 3 A + 2 B
s.t. A + B < 300 (1)
2A + B < 400 (2) 2A + B < 460 ( 2’ )
B < 250 (3)
A,B > 0
Optimal solution
A = 100
B = 200
Max Z = 700 (3)
250

New feasible region

A 35
0 ( 2 ) ( 2’ ) (1) 500
(f) Is it profitable to increase the capacity of painting at the cost of $50 for an additional hour?

If we increase the capacity of painting for 1 hr (i.e. 60 min) :

B
500
Max Z = 3 A + 2 B
s.t. A + B < 300 (1)
2A + B < 400 (2) 2A + B < 460 ( 2’ )
B < 250 (3)
A,B > 0
Optimal solution New optimal solution
A = 100 A = 160
B = 200 B = 140
Max Z = 700 (3) Max Z = 760
250

The revenue increases = 760 – 700 = $ 60

(shadow price is $1 per unit of painting
capacity)

It is profitable to increase the capacity of

painting (as $60>$50).

A 36
0 ( 2 ) ( 2’ ) (1) 500
 Takeaways
• Resource allocation via LP

• Solving LP via Graphical method (when

decision variable is two-dimensional)

• Next class: Solving LP using Excel Solver

– Access to computer with Excel installed

37