Mathematics in the Modern World

MODULE 2
Lesson 9
Introduction to Linear Programming
Graphical Solution and Simplex Method

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
1
COURSE OUTCOMES

At the end of this lesson, students are expected to demonstrate

the following:
• Solve system of linear inequalities.
• Solve linear programming problems using graphical method.
• Solve linear programming problems using Excel solver.
• solve linear programming problems using the simplex method

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
2
Linear Programming: The Graphical Approach and The Excel Solver

• A linear programming problem is basically a

problem of finding the minimum or maximum
linear function subject to linear inequality
constraints.
• In manufacturing industry, linear programming
can be used to determine the number of units a
certain product a company must produce to
maximize the profit or minimize the cost of
production. Mathematics in the Modern World by Earnhart & Adina
Copyright 2019 C&E
https://www.cebookshop.com/
3
The Linear Programming Problem

• The Linear Programming Problem

Minimize
Subject to

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
4
The Linear Programming Problem

Maximize
Subject to

Here, is called the objective function to be minimized

(maximized) with x and y as the decision variables.  

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
5
The Graphical Approach

• A set of points (, ) satisfying all the constraints is called

the feasible region.
• The maximum or minimum value of is always located
at the vertex of this feasibility region also called the
corner point.
• Graphical method is applicable only for two variables.
 

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
6
The Graphical Approach

Steps in Solving Linear Programming Problems.

• State the objective function.
• Write all the constraints.
• Graph the constraints.
• Shade the feasible region.
• Find the corner points.
• Solve for the objective function at each corner point.
• Determine the corner point that gives the minimum value
(maximum).
Mathematics in the Modern World by Earnhart & Adina
Copyright 2019 C&E
https://www.cebookshop.com/
7
EXAMPLE 1

Solve the given linear programming problem.

Minimize
Subject to

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
8
EXAMPLE 1

Solution
x+y=6
x y
y 0 6
6 0
6

0 6 x
Mathematics in the Modern World by Earnhart & Adina
Copyright 2019 C&E
https://www.cebookshop.com/
9
EXAMPLE 1

Solution

Test at origin:

y ==> avoid the

origin
6

0 6 x
Mathematics in the Modern World by Earnhart & Adina
Copyright 2019 C&E
https://www.cebookshop.com/
10
EXAMPLE 1

Solution
− 𝑥+2 𝑦=6
x y
y 0 3
-6 0
6

0 6 x
Mathematics in the Modern World by Earnhart & Adina
Copyright 2019 C&E
https://www.cebookshop.com/
11
EXAMPLE 1

Solution

Test at origin:
y
==> avoid the
6 origin

0 6 x
Mathematics in the Modern World by Earnhart & Adina
Copyright 2019 C&E
https://www.cebookshop.com/
12
EXAMPLE 1

Solution
We obtain the graph as follows.

y
Feasible solution
6 -x + 2y = 6

3
x+y=6

0 6 x
Mathematics in the Modern World by Earnhart & Adina
Copyright 2019 C&E
https://www.cebookshop.com/
13
EXAMPLE 1

Solving the two equations simultaneously, we obtain the intersection point.

Hence, .
Compute for z at the corner points.

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
14
EXAMPLE 1

• Hence, the minimum value is obtained at the point .

x y Z = 3x + 4y Remark
0 6 24  
2 4 22 minimum

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
15
EXAMPLE 2

A retail store stocks two types of customize travel bags

A and B. The store can sell a maximum of 400 type A
bags and a maximum of 300 type B bags per week.
However, the store can only store up to 600 bags of both
types because of limited storage capacity. The store
earns a profit of P30 per type A bag and a profit of P50
per type B bag. How many of each type of bags the store
should keep per week to maximize its profit?

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
16
EXAMPLE 2
Solution
Let be the number of units of type A bag and be the number of
units of type B bag the store can keep per week. Then, the linear
programming problem can be represented as follows.
Maximize
Subject to

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
17
EXAMPLE 2
Solution
y

600
x + y = 600

y=300
Feasible
solution
600
0 x
x=400

Corner Points :
Mathematics in the Modern World by Earnhart & Adina
Copyright 2019 C&E
https://www.cebookshop.com/
18
EXAMPLE 2
Solution
• Hence, the maximum profit will be obtained if the store will
keep 300 bags of each type per week.
Remark

400 0 12000  

0 300 15000  

400 200 22000  

300 300 24000 maximum

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
19
EXAMPLE 3 : EXCEL SOLVER

Solve the following maximization problem using Excel

Solver
Maximize
Subject to

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
20
EXAMPLE 3

Solution
Set up the table and the formula for the objective
function (C5) as shown below. Assign the decision
variable cells: C6 and C7.

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
21
EXAMPLE 3
Solution
Set up the formulas for the constraints.

Note: Use dollar sign to fix the cells for the decision variables (C6 & C7).
Move the cursor down to cells C11 and C12 to copy the formula from C10.
Mathematics in the Modern World by Earnhart & Adina
Copyright 2019 C&E
https://www.cebookshop.com/
22
EXAMPLE 3
Solution
Now, click solver from data menu. Select the indicated cells for the
objective function and decision variables. Add the constraints by clicking
the add button and then select the Max and non-negative options.

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
23
EXAMPLE 3
Solution
Finally, click solve to obtain the following results.

Thus, the maximum value occurs at and .

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
24
SIMPLEX METHOD
1. Set up the linear programming problem.
2. Convert each inequality to an equation by adding a slack variable (non-negative).
3. Construct the initial simplex table with the objective function written at the bottom row.
4. The smallest negative entry in the bottom row identifies a column for the pivot element.
5. Compute for the quotient by dividing the right-hand side value of the equation by the coefficient
from the identified column. The smallest of these quotients identifies the pivot row. The pivot
element is the entry common to the identified column and row.
6. Perform elementary row operations (Gauss-Jordan reduction method) to make the pivot element
equal to 1 and make the other entries in that column containing the pivot element all equal to
zero.
7. Repeat the process, until the entries in the bottom row are all positive.

8. The maximum value occurs at the bottom right-hand corner.

Mathematics in the Modern World by Earnhart & Adina
Copyright 2019 C&E
https://www.cebookshop.com/
25
SIMPLEX METHOD: Illustration

Solve the linear programming problem using the simplex method.

Maximize: Z = 36x + 24y

Subject to: x + y ≤ 12
4x + 2y ≤ 32
x, y ≥ 0

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
26
SIMPLEX METHOD: Illustration
Maximize: Z = 36x + 24y
Subject to: x + y ≤ 12
4x + 2y ≤ 32
x, y ≥ 0
Step 1 Maximize: Z = 36x + 24y
Step 2 The new objective function is –36x – 24y + Z = 0.
Convert the inequalities to equations to get
x + y + a = 12
4x + 2y + b = 32
with a and b as the slack variables.

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
27
SIMPLEX METHOD: Illustration
Step 3 Construct the initial simplex table. Note that the values in the cells correspond
to the numerical coefficients in the equations. Compute for the quotient Q by dividing
the right hand side value of the equation R by the coefficient X from the identified
column. The smallest negative entry in the bottom row identifies a column for the
pivot element. The smallest quotient identifies the pivot row. The pivot element is the
entry common to the identified column and row.
Simplex Table
Pivot column Operations x y a b Z R
1 1 1 0 0 12 a 12
Pivot element 4 2 0 1 0 32 b 8
-36 -24 0 0 1 0 Z Least quotient
Least negative
value

entering variable Pivot Row Outgoing variable

28
SIMPLEX METHOD: Illustration
Step 4 Perform elementary row operations (Gauss-Jordan reduction method) to make
the pivot element equal to 1 and make the other entries in that column containing the
pivot element all equal to zero. Repeat the process, until the entries in the bottom row
are all positive.
Simplex Table
Operations x y a b Z R
1 1 1 0 0 12 a
1 1/2 0 1/4 0 8 x
-36 -24 0 0 1 0 Z

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
29
SIMPLEX METHOD: Illustration
Step 4 Perform elementary row operations (Gauss-Jordan reduction method) to make
the pivot element equal to 1 and make the other entries in that column containing the
pivot element all equal to zero. Repeat the process, until the entries in the bottom row
are all positive.
Simplex Table
Operations x y a b Z R
1 1 1 0 0 12 a
1 1/2 0 1/4 0 8 x
-36 -24 0 0 1 0 Z

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
30
SIMPLEX METHOD: Illustration
Step 4 Perform elementary row operations (Gauss-Jordan reduction method) to make
the pivot element equal to 1 and make the other entries in that column containing the
pivot element all equal to zero. Repeat the process, until the entries in the bottom row
are all positive.
Simplex Table Simplex Table

Operations x y a b Z R Operations x y a b Z R

1 1 1 0 0 12 a 0 1/2 1 -1/4 0 4 a
1 1/2 0 1/4 0 8 x 1 1/2 0 1/4 0 8 x
-36 -24 0 0 1 0 Z 0 -6 0 9 1 288 Z

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
31
SIMPLEX METHOD: Illustration
Step 4 Perform elementary row operations (Gauss-Jordan reduction method) to make
the pivot element equal to 1 and make the other entries in that column containing the
pivot element all equal to zero. Repeat the process, until the entries in the bottom row
are all positive.
Simplex Table
Operations x y a b Z R
0 1/2 1 -1/4 0 4 a 8
1 1/2 0 1/4 0 8 x 16 Least quotient
0 -6 0 9 1 288 Z

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
32
SIMPLEX METHOD: Illustration
Step 4 Perform elementary row operations (Gauss-Jordan reduction method) to make
the pivot element equal to 1 and make the other entries in that column containing the
pivot element all equal to zero. Repeat the process, until the entries in the bottom row
are all positive.
Simplex Table
Operations x y a b Z R
0 1 2 -1/2 0 8 a
1 1/2 0 1/4 0 8 x
0 -6 0 9 1 288 Z

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
33
SIMPLEX METHOD: Illustration
Step 4 Perform elementary row operations (Gauss-Jordan reduction method) to make
the pivot element equal to 1 and make the other entries in that column containing the
pivot element all equal to zero. Repeat the process, until the entries in the bottom row
are all positive. entering variable
Simplex Table
Operations x y a b Z R
0 1 2 -1/2 0 8 a
1 1/2 0 1/4 0 8 x
0 -6 0 9 1 288 Z

Outgoing variable
Mathematics in the Modern World by Earnhart & Adina
Copyright 2019 C&E
https://www.cebookshop.com/
34
SIMPLEX METHOD: Illustration
Step 4 Perform elementary row operations (Gauss-Jordan reduction method) to make
the pivot element equal to 1 and make the other entries in that column containing the
pivot element all equal to zero. Repeat the process, until the entries in the bottom row
are all positive.
Simplex Table
Operations x y a b Z R
0 1 2 -1/2 0 8 y
1 1/2 0 1/4 0 8 x
0 -6 0 9 1 288 Z

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
35
SIMPLEX METHOD: Illustration
Step 4 Perform elementary row operations (Gauss-Jordan reduction method) to make
the pivot element equal to 1 and make the other entries in that column containing the
pivot element all equal to zero. Repeat the process, until the entries in the bottom row
are all positive.

Simplex Table Simplex Table

Operations x y a b Z R Operations x y a b Z R
0 1 2 -1/2 0 8 y 0 1 2 -1/2 0 8 y
1 1/2 0 1/4 0 8 x 1 0 -1 1/2 0 4 x
0 -6 0 9 1 288 Z 0 0 12 6 1 336 Z

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
36
SIMPLEX METHOD: Illustration
Step 4 Perform elementary row operations (Gauss-Jordan reduction method) to make
the pivot element equal to 1 and make the other entries in that column containing the
pivot element all equal to zero. Repeat the process, until the entries in the bottom row
are all positive.
Simplex Table
Operations x y a b Z R
0 1 2 -1/2 0 8 y
1 0 -1 1/2 0 4 x
0 0 12 6 1 336 Z
All positive
Hence, the maximum value Z = 336 occurs at x = 4 and y = 8.

Mathematics in the Modern World by Earnhart & Adina

Copyright 2019 C&E
https://www.cebookshop.com/
37