Unit 2

Linear Programming

Intended Learning Outcomes (ILO)

Construct a linear programming model and apply

solution methods for both maximization and
minimization problems.
Linear Programming (George B Dantzig, 1947)

One of the important Quantitative Methods used to have an optimal way

of allocating scarce resources so it can optimize the results either by
maximizing the profits or minimizing the costs.
Linear Programming (George B Dantzig, 1947)

⮚ It is a mathematical model technique designed to optimize the usage of

limited resources that have been developed to help managers or
administrators in decision-making.

⮚ It is a collection of procedures for maximizing (profit) or minimizing (cost)

Typical examples are as follows
⮚ Determining the best production levels for maximum profits under limited
materials and labor.
⮚ Determining the best way to allocate a fixed advertising budget among
alternative advertising media that would maximize advertising effectiveness.
⮚ Selecting the proper warehouse where it should ship the right quantity of
products to customers in order to minimize the total transportation costs.
⮚ Developing production schedule and an inventory policy that will satisfy
sales demand in the future periods while minimizing the production and
inventory costs.
Advantages of Linear Programming

⮚ It helps in proper and optimum utilization of scarce resources.

⮚ It improves the quality of decisions.
⮚ The decision-maker becomes more objective and less subjective.
⮚ It helps in considering other constraints operating outside the
problem.
⮚ It hints the manager about the difficulties faced during the
production activities.
Solving Linear Programming Problem

1. Formulate the LPP.

2. From the constraints, find the x and y intercepts.
3. Plot the x and y intercepts obtained from the constraints.
4. Determine the feasible region and the vertices of the feasible
region.
5. Substitute the value of the vertices into the Objective
Function.
Steps in Formulating LPP

1. Identify the decision variables.

The answer to linear programming problem is always “how much” of some things. Choose
variables to represent how much of each of those things.

2. Write the objective function.

Use the variables you just chose to write down an algebraic expression that describes the
amount you're trying to minimize or maximize.

3. Formulate the constraints.

These are limitations that restrict the alternatives available to decision- makers, each of which
is either linear equality or linear inequality.

4. State the non-negativity constraints.

The decision variables should always have non-negative values meaning the values for
decision variables should be greater than or equal to 0.
Example 1 :
A company manufactures 2 products, A and B. Each product is processed by two
machines, M1 and M2. Each unit of product A requires 1 hour of processing on M1 and 2 hours
on M2. and each unit of product B requires 3 hours of processing on M1 and 1 hour on M2. The
profit on product A is P20 per unit and on product B is P30 per unit. If M1 is available for 200
hours each month and M2 for 300 hours each month, how many units of each product can be
manufactured in one month in order to maximize the profits?
Machine Product A Product B Availability
Solution : M1 1 3 200
M2 2 1 300
Step 1. Formulating the LPP
x = no. of units (Product A) ⮚ Constraints: x + 3y ≤ 200
⮚ Define Decision Variables y = no. of units (Product B) 2x + y ≤ 300
⮚ Objective Function: Maximize P = 20x + 30y ⮚ Non-negativity x≥0
Constraints: y≥0
From the Constraints 🡪 x + 3y ≤ 200 ; 2x + y ≤ 300
Step 2 : Find the x and y intercepts
x + 3y = 200 2x + y = 300
Let y = 0; Let y = 0;
x + 2(0) = 200 2x + 0 = 300
x = 200 x = 150
x - intercept (200, 0) x - intercept (150, 0)

Let x = 0; Let x = 0;
0 + 3y = 200 2(0) + y = 300
y = 66.67 y = 300
y - intercept (0, 66.67) y - intercept (0, 300)
Step 3. Plot the x and y intercepts in the coordinate plane.

(0,300) 300

250

200

150

(0. 66.67) 100

50

50 100 150 200 250 300 350 400

(150,0) (200,0)
x + 3y = 200
2x + y = 300
 Step 4. Find the feasible region. Determine the vertices of the feasible
region. (0,300)
300

250
x + 3y ≤ 200
200
0 + 3(0) ≤ 200
150
0 ≤ 200
100
True Statement (0. 66.67)
50
2x + y ≤ 300
2(0) + 0 ≤ 300 50 100 150 200 250 300 350 400
(150,0) (200,0)
0 ≤ 300 x + 3y = 200
True Statement

2x + y = 300
 Determine the point of intersection of the boundary lines.

x + 3y = 200
2x + y = 300 (multiply each term by -3)
x + 3y = 200
Elimination x + 3y = 200 Elimination 140 + 3y = 200
by -6x -3y = -900 by 3y = 200 – 140
addition substitution y = 60/3
-5x = -700
y = 20
x = 140

Point of intersection (140, 20)

 300 (0,300)

250

200

150

100
(0. 66.67)
50
(140,20)

50 100 150 200 250 300 350 400

(150,0) (200,0)
x + 3y = 200

2x + y = 300
 The vertices are (0,66.67), (150,0), and (140,20).

Step 5. Substitute the value of the vertices into the Objective Function :
Maximize P = 20x + 30y
For vertex (0,66.67) For vertex (150,0) For vertex (140,20)

P = 20x + 30y P = 20x + 30y P = 20x + 30y

P = 20(0) + 30(66.67) P = 20(150) + 30(0) P = 20(140) + 30(20)
P = 2,000.10 P = 3,000.00 P = 3,400.00

Therefore, the firm should produce 140 units of product A and 20 units of product B to
get a maximum profit of php3,400.00.
Example 2 : Ayala Company manufactures two products: A and B. Each unit of product
A contains 2 kilos of aluminum and 1 kilo of steel. Each unit of B contains 14 kilos of
aluminum and 2 kilos of steel. Ayala has an available supply of 70 kilos of aluminum and
20 kilos of steel. Ayala makes a profit of $20 on each unit of A and $50 on each unit of B.
Find Ayala Company's maximum profit and the number of units of products A and B it
must manufacture in order to obtain its maximum profit.
Content Product A Product B Availability
Solution : Aluminum 2 14 70
Steel 1 2 20
Step 1 : Formulate the LPP
x = no. of units (Product A) ⮚ Constraints: 2x + 14y ≤ 70
⮚ Define Decision Variables:
y = no. of units (Product B) x + 2y ≤ 20

⮚ Objective Function: Maximize P = 20x + 50y ⮚ Non-negativity x≥0

Constraints: y≥0
From the Constraints 🡪 2x + 14y ≤ 70 x + 2y ≤ 20

Step 2 : Find the x and y intercepts

2x + 14y = 70 x + 2y = 20
y = 0; y = 0;
2x + 14(0) = 70 x + 2(0) = 20
x = 35 x = 20
x - intercept (35, 0) x - intercept (20, 0)
x = 0; x = 0;
2(0) + 14y = 70 x(0) + 2y = 20
y= 5 y = 10
y - intercept (0, 5) y - intercept (0, 10)
Step 3. Plot the x and y intercepts in the coordinate plane.

30

25

20

15

(0,10) 10

(0. 5) 5

5 10 15 20 25 30 35 40 2x + 14y = 70
(20,0) (35,0)
x + 2y = 20
 Step 4. Find the feasible region. Determine the vertices of the feasible
region. 30

25
2x + 14y ≤ 70
2(0) + 14(0) ≤ 70 20

0 ≤ 70 15

True Statement (0,10) 10

(0. 5) 5
x + 2y ≤ 20
0 ≤ 20
5 10 15 20 25 30 35 40
0 + 2(0) ≤ 20 2x + 14y = 70
(20,0) (35,0)
True Statement
x + 2y = 20
 Determine the point of intersection of the boundary lines.

2x + 14y = 70
x + 2y = 20 (multiply each term by -2)

x + 2y = 20
Elimination 2x + 14y = 70 Elimination
x + 2(3) = 20
by addition -2x - 4y = -40 by
x = 20 - 6
10y = 30 substitution
x = 14
y = 3

Point of intersection (14, 3)

 30

25

20

15

(0,10) 10

(0. 5) 5 (14,3)

5 10 15 20 25 30 35 40
(20,0) (35,0) 2x + 14y = 70

x + 2y = 20
 The vertices are (0, 5), (20,0), and (14,3).

Step 5. Substitute the value of the vertices into the Objective Function :
Maximize P = 20x + 50y
For vertex (0, 5) For vertex (20,0) For vertex (14, 3)

P = 20x + 50y P = 20x + 50y P = 20x + 50y

P = 20(0) + 50(5) P = 20(20) + 50(0) P = 20(14) + 50(3)
P = $250 P = $400 P = $430
Therefore, Ayala Company should produce 14 units of product A and 3 units of
product B for a maximum profit of $430.
Example 3 : An airline offers first-class and coach tickets. For the airline to be profitable,
it must sell a minimum of 25 first-class tickets and a minimum of 40 coach tickets. The
company makes a profit of $200 for each first-class ticket and $225 for each coach ticket.
At most, the plane has a capacity of 150 travelers. How many of each ticket should be
sold in order to maximize profits?
First Class ticket Coach ticket Capacity min no. of tickets to be sold

Solution : x
x
y 150
25
y 40
Step 1 : Formulate the LPP
x + y ≤ 150
x = no. of first-class ticket ⮚ Constraints: x ≥ 25
⮚ Define Decision Variables:
y = no. of coach ticket y ≥ 40

⮚ Objective Function: Maximum P = 200x + 225y ⮚ Non-negativity x≥0

Constraints: y≥0
From the Constraints 🡪 x + y ≤ 150 x ≥ 25 y ≥ 40

Step 2 : Find the x and y intercepts

x + y = 150 x = 25 y = 40

y = 0;
x + 0 = 150
x = 150
x - intercept (150, 0)

x = 0;
0 + y = 150
y = 150
y - intercept (0, 150)
Step 3. Plot the x and y intercepts in the coordinate system.

250

200

(0,150) 150

100

50
y = 40
(150,0)
50 100 150 200 250
x = 25
x + y = 150
Step 4. Find the feasible region. Determine the vertices of the feasible
region.

x + y ≤ 150 x ≥ 25 y ≥ 40
0 + 0 ≤ 150 0 ≥ 25 0 ≥ 40
0 ≤ 150
False Statement False Statement
True Statement
 250

200

(0,150) 150

100

50
y = 40

50 100 150 200 250

(150,0)
x = 25

x + y = 150
 Determine the point of intersection of the boundary lines.

x+ y = 150 x+ y = 150
y = 40 x = 25

x + y = 150
Elimination by Elimination by x + y = 150
Substitution x + 40 = 150 Substitution 25 + y = 150
x = 150 - 40 y = 150 - 25
x = 110 y = 125
Point of intersection (110, 40) Point of intersection (25, 125)
 250

200

(0,150) 150
(25,125)

100
(25,40) (110,40)
50
y = 40

50 100 150 200 250

(150,0)

x = 25 x + y = 150
 The vertices are (110, 40), (25, 125), and (25, 40)

Step 5. Substitute the value of the vertices into the Objective Function :
Maximize P = 200x + 225y

For vertex (110,40) For vertex (25, 125) For vertex (25, 40)
P = 200(110) + 225(40) P = 200(25) + 225(125) P = 200(25) + 225(40)
P = 22,000 + 9,000 P = 5,000 + 28,125 P = 5,000 + 9,000
P = $31,000 P = $33,125 P = $14,000

Therefore, the airline should sell 25 first-class tickets and 125 coach tickets in order to
maximize profits equivalent to $33,125.
 Example 4 : A diabetic patient needs to take at least 40 units of vitamin A, at least 30 units
of vitamin C, and at least 30 units of vitamin E each day. Each Brand A capsule contains 4
units of vitamin A, 6 units of vitamin C, and 2 units of vitamin E; each Brand B capsule
contains 5 units of vitamin A, 3 units of vitamin C, and 5 units of vitamin E. If each brand A
capsule costs $6 and each brand B capsule costs $9, how many brand A and brand B
capsules should the patient take each day in order to minimize the cost?
Vitamin Brand A Brand B Need to take
A 4 5 40
Solution : C 6 3 30

Step 1 : Formulate the LPP E 2 5 30

⮚ Constraints: 4x + 5y ≥ 40
⮚ Define Decision Variables: x = no. of brand A 6x + 3y ≥ 30
y = no. of brand B 2x + 5y ≥ 30

⮚ Objective Function: Minimize C = 6x + 9y ⮚ Non-negativity x≥0

Constraints: y≥0
From the Constraints 🡪 4x + 5y ≥ 40 6x + 3y ≥ 30 2x + 5y ≥ 30

Step 2 : Find the x and y intercepts

4x + 5y = 40 6x + 3y = 30 2x + 5y = 30
y = 0; y = 0; y = 0;
4x + 5(0) = 40 6x + 3(0) = 30 2x + 5(0) = 30
x = 10 x= 5 x = 15

x - intercept (10, 0) x - intercept (5, 0) x - intercept (15, 0)

x = 0; x = 0;
x = 0;
4(0) + 5y = 40 6(0) + 3y = 40 2(0) + 5y = 30
y= 8 y = 10 y= 6
y - intercept (0, 8) y - intercept (0, 10) y - intercept (0, 6)
Step 3. Plot the x and y intercepts in the coordinate system.

12

(0,10) 10

(0.8) 8

(0,6) 6

2 4 6 8 10 12 14 16
(5. 0) (10. 0) (15,0)
2x + 5y = 30
6x + 3y = 30 4x + 5y = 40
Step 4. Find the feasible region. Determine the vertices of the feasible
region.

4x + 5y ≥ 40 6x + 3y ≥ 30 2x + 5y ≥ 30
4(0) + 5(0) ≥ 40 6(0) + 3(0) ≥ 30 2(0) + 5(0) ≥ 30
0 ≥ 40 0 ≥ 30 0 ≥ 30

False False False

 12

(0,10) 10

(0.8) 8

(0,6) 6

2 4 6 8 10 12 14 16
(5. 0) (10. 0) (15,0)
2x + 5y = 30
6x + 3y = 30 4x + 5y = 40
 Determine the point of intersection of the boundary lines.

6x + 3y = 30 (multiply each term by 5)

4x + 5y = 40 (multiply each term by -3)

6x + 3y = 30
Elimination by 30x + 15y = 150 Elimination by 6(1.67) + 3y = 30
-12x - 15y = -120 substitution 3y = 30-10.02
addition
18x = 30 y = 19.98/3
x = 1.67 y = 6.66

Point of intersection (1.67, 6.66)

 Determine the point of intersection of the boundary lines.

2x + 5y = 30
4x + 5y = 40

2x + 5y = 30 Elimination 2x + 5y = 30
Elimination
-4x - 5y = -40 by 2(5) + 5y = 30
by
substitution 10 + 5y = 30
Subtraction -2x = -10
5y = 20
x = 5 y= 4

Point of intersection (5, 4)

 12

(0,10) 10

(0.8) 8
(1.67,6.66)

(0,6) 6
(5,4)
4

2 4 6 8 10 12 14 16
(5. 0) (10. 0) (15,0)
2x + 5y = 30
6x + 3y = 30 4x + 5y = 40
 The vertices are (0,10), (1.67,6.66), (5,4), and (15,0).

Step 5. Substitute the value of the vertices into the Objective Function :
Minimize C = 6x + 9y

For vertex (0, 10) For vertex (1.67, 6.67) For vertex (5, 4) For vertex (15, 0)
C = 6x + 9y C = 6x + 9y C = 6x + 9y C = 6x + 9y
C= 6(0) + 9(10) C = 6(1.67) + 9(6.67) C = 6(5) + 9(4) C = 6(15) + 9(0)
C = $90 C = 10.02 + 60.03 C = $66 C = $90
C = $70.05
Therefore, the patient must take 5 brand A capsules and 4 brand B capsules per day
in order to minimize the cost to $66.
Example 5 : Professor James wishes to employ John and Marsha to grade papers for
his classes. John can grade 20 papers per hour. He earns $15 per hour. Marsha can
grade 30 papers per hour. She earns $25 per hour. Each must be employed at least
one hour a week. If Professor James has at least 110 papers to be graded each week,
how many hours per week should he employ each person to minimize the cost?
John Marsha Graded Papers No. of hrs Required to be employed
20 30 110
Solution : x 1
Step 1 : Formulate the LPP y 1

20x + 30y ≥ 110

⮚ Define Decision Variables: x = no. of hours of John ⮚ Constraints: x≥1
y = no. of hours of Marsha
y≥1
⮚ Objective Function: Minimize C = 15x + 25y
⮚ Non-negativity x ≥ 0
Constraints: y≥0
From the Constraints🡪 20x + 30y ≥ 110 x≥1 y≥1

Step 2 : Find the x and y intercepts

20x + 30y = 110 x=1 y=1
Let y = 0; Let x = 0;
20x + 30y = 110 20x + 30y = 110
20(0) + 30y = 110
20 x +30(0) = 110
x = 110/20 y = 110/30

x = 5.5 y = 3.67

x - intercept (5.5, 0) y - intercept (0, 3.67)

Step 3. Plot the x and y intercepts in the coordinate system.

4
(0.3.67)
3

y=1 1

1 2 3 4 5 6 7 8
(5.5,0)
x=1 20x + 30y = 110
Step 4. Find the feasible region. Determine the vertices of the feasible
region.

20x + 30y ≥ 110 x≥1 y≥1

20(0) + 30(0) ≥ 110 0≥1 0≥1
0 ≥ 110
False Statement False Statement False Statement
 6

4
(0.3.67)
3

y=1 1

1 2 3 4 5 6 7 8
(5.5,0)
x=1 20x + 30y = 110
 Determine the point of intersection of the boundary lines.

20x + 30y = 110 20x + 30y = 110

y = 1 x = 1

Elimination by 20x + 30y = 110 Elimination by 20x + 30y = 110

Substitution 20x + 30(1) = 110 Substitution 20(1)+ 30y = 110
20x = 110 - 30 30y = 110 - 20
x = 80/20 y = 90/30
x=4 y=3

Point of intersection (4, 1) Point of intersection (1, 3)

 6

4
(0.3.67)
3 (1.3)

2
(4,1)
y=1 1

1 2 3 4 5 6 7 8
(5.5,0)
x=1 20x + 30y = 110
 The vertices are (1,3), and (4,1)

Step 5. Substitute the value of the vertices into the Objective Function :
Maximize C = 15x + 25y
For vertex (1,3) For vertex (4,1)
P = 15 (1) + 25(3) P = 15 (4) + 25(1)
P = 15 + 75 P = 60 + 25
P = $90 P = $85

Therefore, Professor James should employ John for 4 hours a week, and
Marsha for 1 hour a week at a minimum cost of $85 per week.